libs/graph/doc/boykov_kolmogorov_max_flow.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
   2 <HTML>
   3 <HEAD>
   4         <META HTTP-EQUIV="CONTENT-TYPE" CONTENT="text/html; charset=iso-8859-15">
   5         <TITLE>Boost Graph Library: Boykov-Kolmogorov Maximum Flow</TITLE>
   6         <META NAME="GENERATOR" CONTENT="OpenOffice.org 2.0  (Linux)">
   7         <META NAME="CREATED" CONTENT="20060820;17315200">
   8         <META NAME="CHANGEDBY" CONTENT="Stephan Diederich">
   9         <META NAME="CHANGED" CONTENT="20060820;23125100">
  10 <!--
  11 //  Copyright (c) 2006 Stephan Diederich
  12 //
  13 //  This documentation may be used under either of the following two licences:
  14 //
  15 //    Permission is hereby granted, free of charge, to any person
  16 //    obtaining a copy of this software and associated documentation
  17 //    files (the "Software"), to deal in the Software without
  18 //    restriction, including without limitation the rights to use,
  19 //    copy, modify, merge, publish, distribute, sublicense, and/or
  20 //    sell copies of the Software, and to permit persons to whom the
  21 //    Software is furnished to do so, subject to the following
  22 //    conditions:
  23 //
  24 //    The above copyright notice and this permission notice shall be
  25 //    included in all copies or substantial portions of the Software.
  26 //
  27 //    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  28 //    EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
  29 //    OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  30 //    NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
  31 //    HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
  32 //    WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  33 //    FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
  34 //    OTHER DEALINGS IN THE SOFTWARE. OF SUCH DAMAGE.
  35 //
  36 //  Or:
  37 //
  38 //    Distributed under the Boost Software License, Version 1.0.
  39 //    (See accompanying file LICENSE_1_0.txt or copy at
  40 //    http://www.boost.org/LICENSE_1_0.txt)
  41  -->
  42         <STYLE>
  43         <!--
  44                 TD P { color: #000000 }
  45                 H1 { color: #000000 }
  46                 P { color: #000000 }
  47                 PRE { color: #000000 }
  48                 H3 { color: #000000 }
  49                 BLOCKQUOTE { color: #000000 }
  50                 A:link { color: #0000ee }
  51                 A:visited { color: #551a8b }
  52         -->
  53         </STYLE>
  54 </HEAD>
  55 <BODY LANG="de-DE" TEXT="#000000" LINK="#0000ee" VLINK="#551a8b" BGCOLOR="#ffffff" DIR="LTR">
  56 <P><IMG SRC="../../../boost.png" NAME="Grafik1" ALT="C++ Boost" ALIGN=BOTTOM WIDTH=277 HEIGHT=86 BORDER=0>
  57 </P>
  58 <H1><A NAME="sec:boykov_kolmogorov_max_flow"></A><TT>boykov_kolmogorov_max_flow</TT>
  59 </H1>
  60 <PRE><I>// named parameter version</I>
  61 template &lt;class Graph, class P, class T, class R&gt;
  62 typename property_traits&lt;typename property_map&lt;Graph, edge_capacity_t&gt;::const_type&gt;::value_type
  63 boykov_kolmogorov_max_flow(Graph&amp; g,
  64    typename graph_traits&lt;Graph&gt;::vertex_descriptor src,
  65    typename graph_traits&lt;Graph&gt;::vertex_descriptor sink,
  66    const bgl_named_params&lt;P, T, R&gt;&amp; params = <I>all defaults</I>)
  67
  68 <I>// non-named parameter version</I>
  69 template &lt;class Graph, class CapacityEdgeMap, class ResidualCapacityEdgeMap, class ReverseEdgeMap,
  70           class PredecessorMap, class ColorMap, class DistanceMap, class IndexMap&gt;
  71 typename property_traits&lt;CapacityEdgeMap&gt;::value_type
  72 boykov_kolmogorov_max_flow(Graph&amp; g,
  73        CapacityEdgeMap cap,
  74        ResidualCapacityEdgeMap res_cap,
  75        ReverseEdgeMap rev_map,
  76        PredecessorMap pre_map,
  77        ColorMap color,
  78        DistanceMap dist,
  79        IndexMap idx,
  80        typename graph_traits &lt;Graph&gt;::vertex_descriptor src,
  81        typename graph_traits &lt;Graph &gt;::vertex_descriptor sink)</PRE><P>
  82 <FONT SIZE=3>Additional overloaded versions for non-named parameters
  83 are provided (without DistanceMap/ColorMap/DistanceMap; for those
  84 iterator_property_maps with the provided index map are used)</FONT></P>
  85 <P>The <TT>boykov_kolmogorov_max_flow()</TT> function calculates the maximum
  86 flow of a network. See Section <A HREF="graph_theory_review.html#sec:network-flow-algorithms">Network
  87 Flow Algorithms</A> for a description of maximum flow. The calculated
  88 maximum flow will be the return value of the function. The function
  89 also calculates the flow values <I>f(u,v)</I> for all <I>(u,v)</I> in
  90 <I>E</I>, which are returned in the form of the residual capacity
  91 <I>r(u,v) = c(u,v) - f(u,v)</I>.
  92 </P>
  93 <P><B>Requirements:</B><BR>The directed graph <I>G=(V,E)</I> that
  94 represents the network must include a reverse edge for every edge in
  95 <I>E</I>. That is, the input graph should be <I>G<SUB>in</SUB> =
  96 (V,{E U E<SUP>T</SUP>})</I>. The <TT>ReverseEdgeMap</TT> argument <TT>rev</TT>
  97 must map each edge in the original graph to its reverse edge, that is
  98 <I>(u,v) -&gt; (v,u)</I> for all <I>(u,v)</I> in <I>E</I>.
  99 </P>
 100
 101 <P>Remarks: While the push-relabel method states that each edge in <I>E<SUP>T</SUP></I>
 102 has to have capacity of 0, the reverse edges for this algorithm ARE
 103 allowed to carry capacities. If there are already reverse edges in
 104 the input Graph <I><FONT FACE="Courier New, monospace">G</FONT></I>,
 105 those can be used. This can halve the amount of edges and will
 106 noticeably increase the performance.</P>
 107
 108 <P>
 109 <B>Algorithm description:</B><BR>The Boykov-Kolmogorov max-flow (or often
 110 BK max-flow) algorithm is a variety of the augmenting-path algorithm. Standard
 111 augmenting path algorithms find shortest paths from source to sink vertex and
 112 augment them by substracting the bottleneck capacity found on that path from the
 113 residual capacities of each edge and adding it to the total flow. Additionally
 114 the minimum capacity is added to the residual capacity of the reverse edges. If
 115 no more paths in the residual-edge tree are found, the algorithm terminates.
 116 Instead of finding a new shortest path from source to sink in the graph in each
 117 iteration, the Boykov-Kolmogorov algorithm keeps the already found paths as
 118 follows:</P>
 119
 120 <P>The algorithm builds up two search trees, a source-tree and a
 121 sink-tree. Each vertex has a label (stored in <I>ColorMap</I>) to
 122 which tree it belongs and a status-flag if this vertex is active or
 123 passive. In the beginning of the algorithm only the source and the
 124 sink are colored (source==black, sink==white) and have active status.
 125 All other vertices are colored gray. The algorithm consists of three
 126 phases:</P>
 127 <P><I>grow-phase</I>: In this phase active vertices are allowed to
 128 acquire neighbor vertices that are connected through an edge that has
 129 a capacity-value greater than zero. Acquiring means that those vertices
 130 become active and belong now to the search tree of the current
 131 active vertex. If there are no more valid connections to neighbor
 132 vertices, the current vertex becomes passive and the grow phase
 133 continues with the next active vertex. The grow phase terminates if
 134 there are no more active vertices left or a vertex discovers a vertex
 135 from the other search tree through an unsaturated edge. In this case
 136 a path from source to sink is found.</P>
 137 <P><I>augment-phase</I>: This phase augments the path that was found
 138 in the grow phase. First it finds the bottleneck capacity of the
 139 found path, and then it updates the residual-capacity of the edges
 140 from this path by substracting the bottleneck capacity from the
 141 residual capacity. Furthermore the residual capacity of the reverse
 142 edges are updated by adding the bottleneck capacity. This phase can
 143 destroy the built up search trees, as it creates at least one
 144 saturated edge. That means, that the search trees collapse to
 145 forests, because a condition for the search trees is, that each
 146 vertex in them has a valid (=non-saturated) connection to a terminal.</P>
 147 <P><I>adoption-phase</I>: Here the search trees are reconstructed. A
 148 simple solution would be to mark all vertices coming after the first
 149 orphan in the found path free vertices (gray). A more sophisticated
 150 solution is to give those orphans new parents: The neighbor vertices
 151 are checked if they have a valid connection to the same terminal like
 152 this vertex had (a path with unsaturated edges). If there is one,
 153 this vertex becomes the new parent of the current orphan and this
 154 forest is re-included into the search tree. If no new valid parent is
 155 found, this vertex becomes a free vertex (marked gray), and it's
 156 children become orphans. The adoption phase terminates if there are
 157 no more orphans.</P>
 158 <P><IMG SRC="figs/bk_max_flow.gif" NAME="Grafik2" ALIGN=LEFT WIDTH=827 HEIGHT=311 BORDER=0><BR CLEAR=LEFT><B>Details:</B></P>
 159 <UL>
 160         <LI><P>Marking heuristics: A timestamp is stored for each vertex
 161         which shows in which iteration of the algorithm the distance to the
 162         corresponding terminal was calculated.
 163         </P>
 164         <UL>
 165                 <LI><P>This distance is used and gets calculated in the
 166                 adoption-phase. In order to find a valid new parent for an orphan,
 167                 the possible parent is checked for a connection to the terminal to
 168                 which tree it belongs. If there is such a connection, the path is
 169                 tagged with the current time-stamp, and the distance value. If
 170                 another orphan has to find a parent and it comes across a vertex
 171                 with a current timestamp, this information is used.</P>
 172                 <LI><P>The distance is also used in the grow-phase. If a vertex
 173                 comes across another vertex of the same tree while searching for
 174                 new vertices, the other's distance is compared to its distance. If
 175                 it is smaller, that other vertex becomes the new parent of the
 176                 current. This can decrease the length of the search paths, and so
 177                 amount of adoptions.</P>
 178         </UL>
 179         <LI><P>Ordering of orphans: As described above, the augment-phase
 180         and the adoption phase can create orphans. The orphans the
 181         augment-phase generates, are ordered according to their distance to
 182         the terminals (smallest first). This combined with the
 183         distance/timestamp heuristics results in the possibility for not
 184         having to recheck terminal-connections too often. New orphans which
 185         are generated in adoption phase are processed before orphans from
 186         the main queue for the same reason.</P>
 187 </UL>
 188 <P><BR><B>Implementation notes:</B></P>
 189 <P>The algorithm is mainly implemented as described by Boykov and Kolmogorov in
 190 [<a href="bibliography.html#boykov-kolmogorov04">69</a>]. An extended version
 191 can be found in the PhD Thesis of Kolmogorov [<A HREF="bibliography.html#kolmogorov03">68</a>].
 192 The following changes are made to improve performance:</P>
 193 <UL>
 194         <LI>initialization: the algorithm first augments all paths from
 195         source-&gt;sink and all paths from source-&gt;VERTEX-&gt;sink. This
 196         improves especially graph-cuts used in image vision where nearly
 197         each vertex has a source and sink connect. During this step, all
 198         vertices that have an unsaturated connection from source are added
 199         to the active vertex list and so the source is not.</LI>
 200         <LI>active vertices: Boykov-Kolmogorov uses two lists for active nodes
 201         and states that new active vertices are added to the rear of the
 202         second. Fetching an active vertex is done from the beginning of the
 203         first list. If the first list is empty, it is exchanged by the
 204         second. This implementation uses just one list.</LI>
 205         <LI>grow-phase: In the grow phase the first vertex in the
 206         active-list is taken and all outgoing edges are checked if they are
 207         unsaturated. This decreases performance for graphs with high-edge
 208         density. This implementation stores the last accessed edge and
 209         continues with it, if the first vertex in the active-list is the
 210         same one as during the last grow-phase.</LI>
 211 </UL>
 212 <H3>Where Defined</H3>
 213 <P><TT><A HREF="../../../boost/graph/boykov_kolmogorov_max_flow.hpp">boost/graph/boykov_kolmogorov_max_flow.hpp</A></TT>
 214 </P>
 215 <H3>Parameters</H3>
 216 <P>IN: <TT>Graph&amp; g</TT>
 217 </P>
 218 <BLOCKQUOTE>A directed graph. The graph's type must be a model of
 219 <A HREF="VertexListGraph.html">Vertex List Graph</A>, <A HREF="EdgeListGraph.html">Edge
 220 List Graph</A> and <A HREF="IncidenceGraph.html">Incidence Graph</A>.
 221 For each edge <I>(u,v)</I> in the graph, the reverse edge <I>(v,u)</I>
 222 must also be in the graph.  Performance of the algorithm will be slightly
 223 improved if the graph type also models <a href="AdjacencyMatrix.html">Adjacency
 224 Matrix</a>.
 225 </BLOCKQUOTE>
 226 <P>IN: <TT>vertex_descriptor src</TT>
 227 </P>
 228 <BLOCKQUOTE>The source vertex for the flow network graph.
 229 </BLOCKQUOTE>
 230 <P>IN: <TT>vertex_descriptor sink</TT>
 231 </P>
 232 <BLOCKQUOTE>The sink vertex for the flow network graph.
 233 </BLOCKQUOTE>
 234 <H3>Named Parameters</H3>
 235 <P>IN: <TT>edge_capacity(EdgeCapacityMap cap)</TT>
 236 </P>
 237 <BLOCKQUOTE>The edge capacity property map. The type must be a model
 238 of a constant <A HREF="../../property_map/doc/LvaluePropertyMap.html">Lvalue
 239 Property Map</A>. The key type of the map must be the graph's edge
 240 descriptor type.<BR><B>Default:</B> <TT>get(edge_capacity, g)</TT>
 241 </BLOCKQUOTE>
 242 <P>OUT: <TT>edge_residual_capacity(ResidualCapacityEdgeMap res)</TT>
 243 </P>
 244 <BLOCKQUOTE>The edge residual capacity property map. The type must be
 245 a model of a mutable <A HREF="../../property_map/doc/LvaluePropertyMap.html">Lvalue
 246 Property Map</A>. The key type of the map must be the graph's edge
 247 descriptor type.<BR><B>Default:</B> <TT>get(edge_residual_capacity,
 248 g)</TT>
 249 </BLOCKQUOTE>
 250 <P>IN: <TT>edge_reverse(ReverseEdgeMap rev)</TT>
 251 </P>
 252 <BLOCKQUOTE>An edge property map that maps every edge <I>(u,v)</I> in
 253 the graph to the reverse edge <I>(v,u)</I>. The map must be a model
 254 of constant <A HREF="../../property_map/doc/LvaluePropertyMap.html">Lvalue
 255 Property Map</A>. The key type of the map must be the graph's edge
 256 descriptor type.<BR><B>Default:</B> <TT>get(edge_reverse, g)</TT>
 257 </BLOCKQUOTE>
 258 <P>UTIL: <TT>vertex_predecessor(PredecessorMap pre_map)</TT>
 259 </P>
 260 <BLOCKQUOTE>A vertex property map that stores the edge to the vertex'
 261 predecessor. The map must be a model of mutable <A HREF="../../property_map/doc/LvaluePropertyMap.html">Lvalue
 262 Property Map</A>. The key type of the map must be the graph's vertex
 263 descriptor type.<BR><B>Default:</B> <TT>get(vertex_predecessor, g)</TT>
 264 </BLOCKQUOTE>
 265 <P>OUT/UTIL: <TT>vertex_color(ColorMap color)</TT>
 266 </P>
 267 <BLOCKQUOTE>A vertex property map that stores a color for edge
 268 vertex. If the color of a vertex after running the algorithm is black
 269 the vertex belongs to the source tree else it belongs to the
 270 sink-tree (used for minimum cuts). The map must be a model of mutable
 271 <A HREF="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property
 272 Map</A>. The key type of the map must be the graph's vertex
 273 descriptor type.<BR><B>Default:</B> <TT>get(vertex_color, g)</TT>
 274 </BLOCKQUOTE>
 275 <P>UTIL: <TT>vertex_distance(DistanceMap dist)</TT>
 276 </P>
 277 <BLOCKQUOTE>A vertex property map that stores the distance to the
 278 corresponding terminal. It's a utility-map for speeding up the
 279 algorithm. The map must be a model of mutable <A HREF="../../property_map/doc/LvaluePropertyMap.html">Lvalue
 280 Property Map</A>. The key type of the map must be the graph's vertex
 281 descriptor type.<BR><B>Default:</B> <TT>get(vertex_distance, g)</TT>
 282 </BLOCKQUOTE>
 283 <P>IN: <TT>vertex_index(VertexIndexMap index_map)</TT>
 284 </P>
 285 <BLOCKQUOTE>Maps each vertex of the graph to a unique integer in the
 286 range <TT>[0, num_vertices(g))</TT>. The map must be a model of
 287 constant <A HREF="../../property_map/doc/LvaluePropertyMap.html">LvaluePropertyMap</A>.
 288 The key type of the map must be the graph's vertex descriptor
 289 type.<BR><B>Default:</B> <TT>get(vertex_index, g)</TT>
 290 </BLOCKQUOTE>
 291 <H3>Example</H3>
 292 <P>This reads an example maximum flow problem (a graph with edge
 293 capacities) from a file in the DIMACS format (<TT><A HREF="../example/max_flow.dat">example/max_flow.dat</A></TT>).
 294 The source for this example can be found in
 295 <TT><A HREF="../example/boykov_kolmogorov-eg.cpp">example/boykov_kolmogorov-eg.cpp</A></TT>.
 296 </P>
 297 <PRE>#include &lt;boost/config.hpp&gt;
 298 #include &lt;iostream&gt;
 299 #include &lt;string&gt;
 300 #include &lt;boost/graph/adjacency_list.hpp&gt;
 301 #include &lt;boost/graph/boykov_kolmogorov_max_flow.hpp&gt;
 302 #include &lt;boost/graph/read_dimacs.hpp&gt;
 303 #include &lt;boost/graph/graph_utility.hpp&gt;
 304
 305 int
 306 main()
 307 {
 308   using namespace boost;
 309
 310   typedef adjacency_list_traits &lt; vecS, vecS, directedS &gt; Traits;
 311   typedef adjacency_list &lt; vecS, vecS, directedS,
 312     property &lt; vertex_name_t, std::string,
 313     property &lt; vertex_index_t, long,
 314     property &lt; vertex_color_t, boost::default_color_type,
 315     property &lt; vertex_distance_t, long,
 316     property &lt; vertex_predecessor_t, Traits::edge_descriptor &gt; &gt; &gt; &gt; &gt;,
 317
 318     property &lt; edge_capacity_t, long,
 319     property &lt; edge_residual_capacity_t, long,
 320     property &lt; edge_reverse_t, Traits::edge_descriptor &gt; &gt; &gt; &gt; Graph;
 321
 322   Graph g;
 323   property_map &lt; Graph, edge_capacity_t &gt;::type
 324       capacity = get(edge_capacity, g);
 325   property_map &lt; Graph, edge_residual_capacity_t &gt;::type
 326       residual_capacity = get(edge_residual_capacity, g);
 327   property_map &lt; Graph, edge_reverse_t &gt;::type rev = get(edge_reverse, g);
 328   Traits::vertex_descriptor s, t;
 329   read_dimacs_max_flow(g, capacity, rev, s, t);
 330
 331   std::vector&lt;default_color_type&gt; color(num_vertices(g));
 332   std::vector&lt;long&gt; distance(num_vertices(g));
 333   long flow = boykov_kolmogorov_max_flow(g ,s, t);
 334
 335   std::cout &lt;&lt; "c  The total flow:" &lt;&lt; std::endl;
 336   std::cout &lt;&lt; "s " &lt;&lt; flow &lt;&lt; std::endl &lt;&lt; std::endl;
 337
 338   std::cout &lt;&lt; "c flow values:" &lt;&lt; std::endl;
 339   graph_traits &lt; Graph &gt;::vertex_iterator u_iter, u_end;
 340   graph_traits &lt; Graph &gt;::out_edge_iterator ei, e_end;
 341   for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
 342     for (boost::tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei)
 343       if (capacity[*ei] &gt; 0)
 344         std::cout &lt;&lt; "f " &lt;&lt; *u_iter &lt;&lt; " " &lt;&lt; target(*ei, g) &lt;&lt; " "
 345           &lt;&lt; (capacity[*ei] - residual_capacity[*ei]) &lt;&lt; std::endl;
 346
 347   return EXIT_SUCCESS;
 348 }</PRE><P>
 349 The output is:
 350 </P>
 351 <PRE>c  The total flow:
 352 s 13
 353
 354 c flow values:
 355 f 0 6 3
 356 f 0 1 0
 357 f 0 2 10
 358 f 1 5 1
 359 f 1 0 0
 360 f 1 3 0
 361 f 2 4 4
 362 f 2 3 6
 363 f 2 0 0
 364 f 3 7 5
 365 f 3 2 0
 366 f 3 1 1
 367 f 4 5 4
 368 f 4 6 0
 369 f 5 4 0
 370 f 5 7 5
 371 f 6 7 3
 372 f 6 4 0
 373 f 7 6 0
 374 f 7 5 0</PRE><H3>
 375 See Also</H3>
 376 <P STYLE="margin-bottom: 0cm">
 377 <TT><A HREF="edmonds_karp_max_flow.html">edmonds_karp_max_flow()</A></TT>,
 378 <TT><A HREF="push_relabel_max_flow.html">push_relabel_max_flow()</A></TT>.
 379 </P>
 380 <HR>
 381 <TABLE CELLPADDING=2 CELLSPACING=2>
 382         <TR VALIGN=TOP>
 383                 <TD>
 384                         <P>Copyright &copy; 2006</P>
 385                 </TD>
 386                 <TD>
 387                         <P>Stephan Diederich, University
 388                         Mannheim(<A HREF="mailto:diederich@ti.uni-manheim.de">diederich@ti.uni-manheim.de</A>)</P>
 389                 </TD>
 390         </TR>
 391 </TABLE>
 392 <P><BR><BR>
 393 </P>
 394 </BODY>
 395 </HTML>