3 Copyright Daniel Trebbien 2010.
4 Distributed under the Boost Software License, Version 1.0.
5 (See accompanying file LICENSE_1_0.txt or the copy at
6 http://www.boost.org/LICENSE_1_0.txt)
10 <title>Boost Graph Library: Stoer
–Wagner Min-Cut
</title>
13 <img src=
"../../../boost.png" alt=
"C++ Boost">
15 <h1><a name=
"sec:stoer_wagner"><tt>stoer_wagner_min_cut
</tt></a></h1>
16 <table border=
"0" cellspacing=
"0" style=
"float: right">
17 <caption align=
"bottom">A min-cut of a weighted graph
<br>having min-cut weight
4</caption>
18 <tr><td style=
"border: #666 1px solid"><img src=
"stoer_wagner_imgs/stoer_wagner-example-min-cut.gif" width=
"376"></td></tr>
21 template
<class UndirectedGraph, class WeightMap, class P, class T, class R
>
23 stoer_wagner_min_cut(const UndirectedGraph
& g, WeightMap weights,
24 const bgl_named_params
<P, T, R
>& params =
<i>all defaults
</i>);
27 <p>The
<tt>stoer_wagner_min_cut
</tt> function determines a min-cut and the min-cut weight of a connected, undirected graph.
29 <p>A
<em>cut
</em> of a graph
<i>G
</i> is a partition of the vertices into two, non-empty sets. The
<em>weight
</em> of such a partition is the number of edges between the two sets if
<i>G
</i> is unweighted, or the sum of the weights of all edges between the two sets if
<i>G
</i> is weighted. A
<em>min-cut
</em> is a cut having the least weight.
31 <p>Sometimes a graph has multiple min-cuts, but all have the same weight. The
<tt>stoer_wagner_min_cut
</tt> function determines exactly one of the min-cuts as well as its weight.
33 <h3>Where Defined
</h3>
34 <p><a href=
"../../../boost/graph/stoer_wagner_min_cut.hpp"><tt>boost/graph/stoer_wagner_min_cut.hpp
</tt></a>
38 <p>IN:
<tt>const UndirectedGraph
& g
</tt>
40 A connected, undirected graph. The graph type must be a model of
41 <a href=
"./VertexListGraph.html">Vertex List Graph
</a>
42 and
<a href=
"./IncidenceGraph.html">Incidence Graph
</a>.
45 <p>IN:
<tt>WeightMap weights
</tt>
47 The weight or length of each edge in the graph. The
<tt>WeightMap
</tt> type must be a model
48 of
<a href=
"../../property_map/doc/ReadablePropertyMap.html">Readable
49 Property Map
</a> and its value type must be
<a class=
"external" href=
"http://www.sgi.com/tech/stl/LessThanComparable.html">Less Than
50 Comparable
</a> and summable. The key type of this map needs to be the graph's
54 <h3>Named Parameters
</h3>
56 <p>OUT:
<tt>parity_map(ParityMap parities)
</tt>
58 The algorithm computes a min-cut, which divides the set of vertices into two,
59 non-empty sets. The
<tt>stoer_wagner_min_cut
</tt> function records which of
60 the two sets that each vertex belongs to by setting the parity to
<tt>true
</tt>
61 (representing one set) or
<tt>false
</tt> (for the other).
<tt>ParityMap
</tt>
62 must be a model of a
<a href=
"../../property_map/doc/WritablePropertyMap.html">Writable
63 Property Map
</a> and its value type should be a bool type. The
64 key type must be the graph's vertex descriptor type.
<br>
65 <b>Default:
</b> <tt>boost::dummy_property_map
</tt>
68 <h4>Expert Parameters
</h4>
70 <p>IN:
<tt>vertex_index_map(VertexIndexMap vertexIndices)
</tt>
72 This maps each vertex to an integer in the range [
0,
<tt>num_vertices(g)
</tt>). This
73 is only necessary if the default is used for the assignment, index-in-heap, or distance maps.
74 <tt>VertexIndexMap
</tt> must be a model of
<a
75 href=
"../../property_map/doc/ReadablePropertyMap.html">Readable Property
76 Map
</a>. The value type of the map must be an integer type. The
77 key type must be the graph's vertex descriptor type.
<br>
78 <b>Default:
</b> <tt>get(boost::vertex_index, g)
</tt>
81 <p>UTIL:
<tt>assignment_map(AssignmentMap assignments)
</tt>
83 <tt>AssignmentMap
</tt> must be a model of
<a
84 href=
"../../property_map/doc/ReadWritePropertyMap.html">Read/Write Property
85 Map
</a>. The key and value types must be the graph's vertex descriptor type.
<br>
86 <b>Default:
</b> A
<tt>boost::iterator_property_map
</tt> using a
<tt>std::vector
</tt>
87 of
<tt>num_vertices(g)
</tt> vertex descriptors and
<tt>vertexIndices
</tt> for
91 <p>UTIL:
<tt>max_priority_queue(MaxPriorityQueue
& pq)
</tt>
93 <tt>MaxPriorityQueue
</tt> must be a model of
<a href=
"./KeyedUpdatableQueue.html">Keyed Updatable Queue
</a>
94 and a max-
<a href=
"./UpdatableQueue.html#concept%3AUpdatablePriorityQueue">Updatable Priority Queue
</a>.
95 The value type must be the graph's vertex descriptor and the key type must be
97 <b>Default:
</b> A
<tt>boost::d_ary_heap_indirect
</tt> using a default index-in-heap
101 <p>UTIL:
<tt>index_in_heap_map(IndexInHeapMap indicesInHeap)
</tt>
103 This parameter only has an effect when the default max-priority queue is used.
<br>
104 <tt>IndexInHeapMap
</tt> must be a model of
<a
105 href=
"../../property_map/doc/ReadWritePropertyMap.html">Read/Write Property
106 Map
</a>. The key type must be the graph's vertex descriptor type. The value type
107 must be a size type (
<tt>typename
std::vector
<vertex_descriptor
>::size_type
</tt>).
<br>
108 <b>Default:
</b> A
<tt>boost::iterator_property_map
</tt> using a
<tt>std::vector
</tt>
109 of
<tt>num_vertices(g)
</tt> size type objects and
<tt>vertexIndices
</tt> for
113 <p>UTIL:
<tt>distance_map(DistanceMap wAs)
</tt>
115 This parameter only has an effect when the default max-priority queue is used.
<br>
116 <tt>DistanceMap
</tt> must be a model of
<a
117 href=
"../../property_map/doc/ReadWritePropertyMap.html">Read/Write Property
118 Map
</a>. The key type must be the graph's vertex descriptor type. The value type
119 must be the weight type (
<tt>typename
boost::property_traits
<WeightMap
>::value_type
</tt>).
<br>
120 <b>Default:
</b> A
<tt>boost::iterator_property_map
</tt> using a
<tt>std::vector
</tt>
121 of
<tt>num_vertices(g)
</tt> weight type objects and
<tt>vertexIndices
</tt> for
126 <p>The weight of the min-cut
130 <p><tt>bad_graph
</tt>
132 If
<tt>num_vertices(g)
</tt> is less than
2
135 <p><tt>std::invalid_argument
</tt>
137 If a max-priority queue is given as an argument and it is not empty
142 <p>The time complexity is
<i>O
</i>(
<i>V
</i>·<i>E
</i> +
<i>V
</i><sup>2</sup> log
<i>V
</i>).
146 <p>The file
<a href=
"../example/stoer_wagner.cpp"><tt>examples/stoer_wagner.cpp
</tt></a> contains an example of calculating a min-cut of a weighted, undirected graph and its min-cut weight.
150 <li>Mehlhorn, Kurt and Christian Uhrig (
1995).
<q><a href=
"http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.31.614&rep=rep1&type=pdf">The minimum cut algorithm of Stoer and Wagner
</a></q>.
151 <li>Stoer, Mechthild and Frank Wagner (
1997).
<q><a href=
"http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.114.6687&rep=rep1&type=pdf">A simple min-cut algorithm
</a></q>.
<i>Journal of the ACM
</i> <b>44</b> (
4),
585–591.
152 <li>Zwick, Uri (
2008).
<q><a href=
"http://www.cs.tau.ac.il/~zwick/grad-algo-08/gmc.pdf">Global minimum cuts
</a></q>.
159 <td>Copyright
© 2010</td>
160 <td>Daniel Trebbien (
<a href=
"mailto:dtrebbien@gmail.com">dtrebbien@gmail.com
</a>)