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> 21template <class UndirectedGraph, class WeightMap, class P, class T, class R> 22weight_type 23stoer_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.boost.org/sgi/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> 167
