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> 61template <class Graph, class P, class T, class R> 62typename property_traits<typename property_map<Graph, edge_capacity_t>::const_type>::value_type 63boykov_kolmogorov_max_flow(Graph& g, 64 typename graph_traits<Graph>::vertex_descriptor src, 65 typename graph_traits<Graph>::vertex_descriptor sink, 66 const bgl_named_params<P, T, R>& params = <I>all defaults</I>) 67 68<I>// non-named parameter version</I> 69template <class Graph, class CapacityEdgeMap, class ResidualCapacityEdgeMap, class ReverseEdgeMap, 70 class PredecessorMap, class ColorMap, class DistanceMap, class IndexMap> 71typename property_traits<CapacityEdgeMap>::value_type 72boykov_kolmogorov_max_flow(Graph& 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 <Graph>::vertex_descriptor src, 81 typename graph_traits <Graph >::vertex_descriptor sink)</PRE><P> 82<FONT SIZE=3>Additional overloaded versions for non-named parameters 83are provided (without DistanceMap/ColorMap/DistanceMap; for those 84iterator_property_maps with the provided index map are used)</FONT></P> 85<P>The <TT>boykov_kolmogorov_max_flow()</TT> function calculates the maximum 86flow of a network. See Section <A HREF="graph_theory_review.html#sec:network-flow-algorithms">Network 87Flow Algorithms</A> for a description of maximum flow. The calculated 88maximum flow will be the return value of the function. The function 89also 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 94represents 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> 97must map each edge in the original graph to its reverse edge, that is 98<I>(u,v) -> (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> 102has to have capacity of 0, the reverse edges for this algorithm ARE 103allowed to carry capacities. If there are already reverse edges in 104the input Graph <I><FONT FACE="Courier New, monospace">G</FONT></I>, 105those can be used. This can halve the amount of edges and will 106noticeably increase the performance.</P> 107 108<P> 109<B>Algorithm description:</B><BR>The Boykov-Kolmogorov max-flow (or often 110BK max-flow) algorithm is a variety of the augmenting-path algorithm. Standard 111augmenting path algorithms find shortest paths from source to sink vertex and 112augment them by subtracting the bottleneck capacity found on that path from the 113residual capacities of each edge and adding it to the total flow. Additionally 114the minimum capacity is added to the residual capacity of the reverse edges. If 115no more paths in the residual-edge tree are found, the algorithm terminates. 116Instead of finding a new shortest path from source to sink in the graph in each 117iteration, the Boykov-Kolmogorov algorithm keeps the already found paths as 118follows:</P> 119 120<P>The algorithm builds up two search trees, a source-tree and a 121sink-tree. Each vertex has a label (stored in <I>ColorMap</I>) to 122which tree it belongs and a status-flag if this vertex is active or 123passive. In the beginning of the algorithm only the source and the 124sink are colored (source==black, sink==white) and have active status. 125All other vertices are colored gray. The algorithm consists of three 126phases:</P> 127<P><I>grow-phase</I>: In this phase active vertices are allowed to 128acquire neighbor vertices that are connected through an edge that has 129a capacity-value greater than zero. Acquiring means that those vertices 130become active and belong now to the search tree of the current 131active vertex. If there are no more valid connections to neighbor 132vertices, the current vertex becomes passive and the grow phase 133continues with the next active vertex. The grow phase terminates if 134there are no more active vertices left or a vertex discovers a vertex 135from the other search tree through an unsaturated edge. In this case 136a path from source to sink is found.</P> 137<P><I>augment-phase</I>: This phase augments the path that was found 138in the grow phase. First it finds the bottleneck capacity of the 139found path, and then it updates the residual-capacity of the edges 140from this path by subtracting the bottleneck capacity from the 141residual capacity. Furthermore the residual capacity of the reverse 142edges are updated by adding the bottleneck capacity. This phase can 143destroy the built up search trees, as it creates at least one 144saturated edge. That means, that the search trees collapse to 145forests, because a condition for the search trees is, that each 146vertex 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 148simple solution would be to mark all vertices coming after the first 149orphan in the found path free vertices (gray). A more sophisticated 150solution is to give those orphans new parents: The neighbor vertices 151are checked if they have a valid connection to the same terminal like 152this vertex had (a path with unsaturated edges). If there is one, 153this vertex becomes the new parent of the current orphan and this 154forest is re-included into the search tree. If no new valid parent is 155found, this vertex becomes a free vertex (marked gray), and it's 156children become orphans. The adoption phase terminates if there are 157no 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 191can be found in the PhD Thesis of Kolmogorov [<A HREF="bibliography.html#kolmogorov03">68</a>]. 192The following changes are made to improve performance:</P> 193<UL> 194 <LI>initialization: the algorithm first augments all paths from 195 source->sink and all paths from source->VERTEX->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& 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 220List Graph</A> and <A HREF="IncidenceGraph.html">Incidence Graph</A>. 221For each edge <I>(u,v)</I> in the graph, the reverse edge <I>(v,u)</I> 222must also be in the graph. Performance of the algorithm will be slightly 223improved if the graph type also models <a href="AdjacencyMatrix.html">Adjacency 224Matrix</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 238of a constant <A HREF="../../property_map/doc/LvaluePropertyMap.html">Lvalue 239Property Map</A>. The key type of the map must be the graph's edge 240descriptor 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 245a model of a mutable <A HREF="../../property_map/doc/LvaluePropertyMap.html">Lvalue 246Property Map</A>. The key type of the map must be the graph's edge 247descriptor type.<BR><B>Default:</B> <TT>get(edge_residual_capacity, 248g)</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 253the graph to the reverse edge <I>(v,u)</I>. The map must be a model 254of constant <A HREF="../../property_map/doc/LvaluePropertyMap.html">Lvalue 255Property Map</A>. The key type of the map must be the graph's edge 256descriptor 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' 261predecessor. The map must be a model of mutable <A HREF="../../property_map/doc/LvaluePropertyMap.html">Lvalue 262Property Map</A>. The key type of the map must be the graph's vertex 263descriptor 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 268vertex. If the color of a vertex after running the algorithm is black 269the vertex belongs to the source tree else it belongs to the 270sink-tree (used for minimum cuts). The map must be a model of mutable 271<A HREF="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property 272Map</A>. The key type of the map must be the graph's vertex 273descriptor 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 278corresponding terminal. It's a utility-map for speeding up the 279algorithm. The map must be a model of mutable <A HREF="../../property_map/doc/LvaluePropertyMap.html">Lvalue 280Property Map</A>. The key type of the map must be the graph's vertex 281descriptor 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 286range <TT>[0, num_vertices(g))</TT>. The map must be a model of 287constant <A HREF="../../property_map/doc/LvaluePropertyMap.html">LvaluePropertyMap</A>. 288The key type of the map must be the graph's vertex descriptor 289type.<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 293capacities) from a file in the DIMACS format (<TT><A HREF="../example/max_flow.dat">example/max_flow.dat</A></TT>). 294The 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 <boost/config.hpp> 298#include <iostream> 299#include <string> 300#include <boost/graph/adjacency_list.hpp> 301#include <boost/graph/boykov_kolmogorov_max_flow.hpp> 302#include <boost/graph/read_dimacs.hpp> 303#include <boost/graph/graph_utility.hpp> 304 305int 306main() 307{ 308 using namespace boost; 309 310 typedef adjacency_list_traits < vecS, vecS, directedS > Traits; 311 typedef adjacency_list < vecS, vecS, directedS, 312 property < vertex_name_t, std::string, 313 property < vertex_index_t, long, 314 property < vertex_color_t, boost::default_color_type, 315 property < vertex_distance_t, long, 316 property < vertex_predecessor_t, Traits::edge_descriptor > > > > >, 317 318 property < edge_capacity_t, long, 319 property < edge_residual_capacity_t, long, 320 property < edge_reverse_t, Traits::edge_descriptor > > > > Graph; 321 322 Graph g; 323 property_map < Graph, edge_capacity_t >::type 324 capacity = get(edge_capacity, g); 325 property_map < Graph, edge_residual_capacity_t >::type 326 residual_capacity = get(edge_residual_capacity, g); 327 property_map < Graph, edge_reverse_t >::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<default_color_type> color(num_vertices(g)); 332 std::vector<long> distance(num_vertices(g)); 333 long flow = boykov_kolmogorov_max_flow(g ,s, t); 334 335 std::cout << "c The total flow:" << std::endl; 336 std::cout << "s " << flow << std::endl << std::endl; 337 338 std::cout << "c flow values:" << std::endl; 339 graph_traits < Graph >::vertex_iterator u_iter, u_end; 340 graph_traits < Graph >::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] > 0) 344 std::cout << "f " << *u_iter << " " << target(*ei, g) << " " 345 << (capacity[*ei] - residual_capacity[*ei]) << std::endl; 346 347 return EXIT_SUCCESS; 348}</PRE><P> 349The output is: 350</P> 351<PRE>c The total flow: 352s 13 353 354c flow values: 355f 0 6 3 356f 0 1 0 357f 0 2 10 358f 1 5 1 359f 1 0 0 360f 1 3 0 361f 2 4 4 362f 2 3 6 363f 2 0 0 364f 3 7 5 365f 3 2 0 366f 3 1 1 367f 4 5 4 368f 4 6 0 369f 5 4 0 370f 5 7 5 371f 6 7 3 372f 6 4 0 373f 7 6 0 374f 7 5 0</PRE><H3> 375See 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 © 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> 396
