]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | <!DOCTYPE html> |
2 | <!-- | |
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) | |
7 | --> | |
8 | <html> | |
9 | <head> | |
10 | <title>Boost Graph Library: Stoer–Wagner Min-Cut</title> | |
11 | </head> | |
12 | <body> | |
13 | <img src="../../../boost.png" alt="C++ Boost"> | |
14 | ||
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> | |
19 | </table> | |
20 | <pre> | |
21 | template <class UndirectedGraph, class WeightMap, class P, class T, class R> | |
22 | weight_type | |
23 | stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights, | |
24 | const bgl_named_params<P, T, R>& params = <i>all defaults</i>); | |
25 | </pre> | |
26 | ||
27 | <p>The <tt>stoer_wagner_min_cut</tt> function determines a min-cut and the min-cut weight of a connected, undirected graph. | |
28 | ||
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. | |
30 | ||
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. | |
32 | ||
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> | |
35 | ||
36 | <h3>Parameters</h3> | |
37 | ||
38 | <p>IN: <tt>const UndirectedGraph& g</tt> | |
39 | <blockquote> | |
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>. | |
43 | </blockquote> | |
44 | ||
45 | <p>IN: <tt>WeightMap weights</tt> | |
46 | <blockquote> | |
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 | |
51 | edge descriptor type. | |
52 | </blockquote> | |
53 | ||
54 | <h3>Named Parameters</h3> | |
55 | ||
56 | <p>OUT: <tt>parity_map(ParityMap parities)</tt> | |
57 | <blockquote> | |
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> | |
66 | </blockquote> | |
67 | ||
68 | <h4>Expert Parameters</h4> | |
69 | ||
70 | <p>IN: <tt>vertex_index_map(VertexIndexMap vertexIndices)</tt> | |
71 | <blockquote> | |
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> | |
79 | </blockquote> | |
80 | ||
81 | <p>UTIL: <tt>assignment_map(AssignmentMap assignments)</tt> | |
82 | <blockquote> | |
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 | |
88 | the index map. | |
89 | </blockquote> | |
90 | ||
91 | <p>UTIL: <tt>max_priority_queue(MaxPriorityQueue& pq)</tt> | |
92 | <blockquote> | |
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 | |
96 | the weight type. | |
97 | <b>Default:</b> A <tt>boost::d_ary_heap_indirect</tt> using a default index-in-heap | |
98 | and distance map. | |
99 | </blockquote> | |
100 | ||
101 | <p>UTIL: <tt>index_in_heap_map(IndexInHeapMap indicesInHeap)</tt> | |
102 | <blockquote> | |
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 | |
110 | the index map. | |
111 | </blockquote> | |
112 | ||
113 | <p>UTIL: <tt>distance_map(DistanceMap wAs)</tt> | |
114 | <blockquote> | |
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 | |
122 | the index map. | |
123 | </blockquote> | |
124 | ||
125 | <h3>Returns</h3> | |
126 | <p>The weight of the min-cut | |
127 | ||
128 | <h3>Throws</h3> | |
129 | ||
130 | <p><tt>bad_graph</tt> | |
131 | <blockquote> | |
132 | If <tt>num_vertices(g)</tt> is less than 2 | |
133 | </blockquote> | |
134 | ||
135 | <p><tt>std::invalid_argument</tt> | |
136 | <blockquote> | |
137 | If a max-priority queue is given as an argument and it is not empty | |
138 | </blockquote> | |
139 | ||
140 | <h3>Complexity</h3> | |
141 | ||
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>). | |
143 | ||
144 | <h3>Example</h3> | |
145 | ||
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. | |
147 | ||
148 | <h3>References</h3> | |
149 | <ul> | |
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>. | |
153 | </ul> | |
154 | ||
155 | <br> | |
156 | <hr> | |
157 | <table> | |
158 | <tr> | |
159 | <td>Copyright © 2010</td> | |
160 | <td>Daniel Trebbien (<a href="mailto:dtrebbien@gmail.com">dtrebbien@gmail.com</a>) | |
161 | </td> | |
162 | </tr> | |
163 | </table> | |
164 | ||
165 | </body> | |
166 | </html> |