123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395 |
- <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
- <HTML>
- <HEAD>
- <META HTTP-EQUIV="CONTENT-TYPE" CONTENT="text/html; charset=iso-8859-15">
- <TITLE>Boost Graph Library: Boykov-Kolmogorov Maximum Flow</TITLE>
- <META NAME="GENERATOR" CONTENT="OpenOffice.org 2.0 (Linux)">
- <META NAME="CREATED" CONTENT="20060820;17315200">
- <META NAME="CHANGEDBY" CONTENT="Stephan Diederich">
- <META NAME="CHANGED" CONTENT="20060820;23125100">
- <!--
- // Copyright (c) 2006 Stephan Diederich
- //
- // This documentation may be used under either of the following two licences:
- //
- // Permission is hereby granted, free of charge, to any person
- // obtaining a copy of this software and associated documentation
- // files (the "Software"), to deal in the Software without
- // restriction, including without limitation the rights to use,
- // copy, modify, merge, publish, distribute, sublicense, and/or
- // sell copies of the Software, and to permit persons to whom the
- // Software is furnished to do so, subject to the following
- // conditions:
- //
- // The above copyright notice and this permission notice shall be
- // included in all copies or substantial portions of the Software.
- //
- // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
- // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
- // OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
- // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
- // HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
- // WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
- // FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
- // OTHER DEALINGS IN THE SOFTWARE. OF SUCH DAMAGE.
- //
- // Or:
- //
- // Distributed under the Boost Software License, Version 1.0.
- // (See accompanying file LICENSE_1_0.txt or copy at
- // http://www.boost.org/LICENSE_1_0.txt)
- -->
- <STYLE>
- <!--
- TD P { color: #000000 }
- H1 { color: #000000 }
- P { color: #000000 }
- PRE { color: #000000 }
- H3 { color: #000000 }
- BLOCKQUOTE { color: #000000 }
- A:link { color: #0000ee }
- A:visited { color: #551a8b }
- -->
- </STYLE>
- </HEAD>
- <BODY LANG="de-DE" TEXT="#000000" LINK="#0000ee" VLINK="#551a8b" BGCOLOR="#ffffff" DIR="LTR">
- <P><IMG SRC="../../../boost.png" NAME="Grafik1" ALT="C++ Boost" ALIGN=BOTTOM WIDTH=277 HEIGHT=86 BORDER=0>
- </P>
- <H1><A NAME="sec:boykov_kolmogorov_max_flow"></A><TT>boykov_kolmogorov_max_flow</TT>
- </H1>
- <PRE><I>// named parameter version</I>
- template <class Graph, class P, class T, class R>
- typename property_traits<typename property_map<Graph, edge_capacity_t>::const_type>::value_type
- boykov_kolmogorov_max_flow(Graph& g,
- typename graph_traits<Graph>::vertex_descriptor src,
- typename graph_traits<Graph>::vertex_descriptor sink,
- const bgl_named_params<P, T, R>& params = <I>all defaults</I>)
- <I>// non-named parameter version</I>
- template <class Graph, class CapacityEdgeMap, class ResidualCapacityEdgeMap, class ReverseEdgeMap,
- class PredecessorMap, class ColorMap, class DistanceMap, class IndexMap>
- typename property_traits<CapacityEdgeMap>::value_type
- boykov_kolmogorov_max_flow(Graph& g,
- CapacityEdgeMap cap,
- ResidualCapacityEdgeMap res_cap,
- ReverseEdgeMap rev_map,
- PredecessorMap pre_map,
- ColorMap color,
- DistanceMap dist,
- IndexMap idx,
- typename graph_traits <Graph>::vertex_descriptor src,
- typename graph_traits <Graph >::vertex_descriptor sink)</PRE><P>
- <FONT SIZE=3>Additional overloaded versions for non-named parameters
- are provided (without DistanceMap/ColorMap/DistanceMap; for those
- iterator_property_maps with the provided index map are used)</FONT></P>
- <P>The <TT>boykov_kolmogorov_max_flow()</TT> function calculates the maximum
- flow of a network. See Section <A HREF="graph_theory_review.html#sec:network-flow-algorithms">Network
- Flow Algorithms</A> for a description of maximum flow. The calculated
- maximum flow will be the return value of the function. The function
- also calculates the flow values <I>f(u,v)</I> for all <I>(u,v)</I> in
- <I>E</I>, which are returned in the form of the residual capacity
- <I>r(u,v) = c(u,v) - f(u,v)</I>.
- </P>
- <P><B>Requirements:</B><BR>The directed graph <I>G=(V,E)</I> that
- represents the network must include a reverse edge for every edge in
- <I>E</I>. That is, the input graph should be <I>G<SUB>in</SUB> =
- (V,{E U E<SUP>T</SUP>})</I>. The <TT>ReverseEdgeMap</TT> argument <TT>rev</TT>
- must map each edge in the original graph to its reverse edge, that is
- <I>(u,v) -> (v,u)</I> for all <I>(u,v)</I> in <I>E</I>.
- </P>
- <P>Remarks: While the push-relabel method states that each edge in <I>E<SUP>T</SUP></I>
- has to have capacity of 0, the reverse edges for this algorithm ARE
- allowed to carry capacities. If there are already reverse edges in
- the input Graph <I><FONT FACE="Courier New, monospace">G</FONT></I>,
- those can be used. This can halve the amount of edges and will
- noticeably increase the performance.</P>
- <P>
- <B>Algorithm description:</B><BR>The Boykov-Kolmogorov max-flow (or often
- BK max-flow) algorithm is a variety of the augmenting-path algorithm. Standard
- augmenting path algorithms find shortest paths from source to sink vertex and
- augment them by subtracting the bottleneck capacity found on that path from the
- residual capacities of each edge and adding it to the total flow. Additionally
- the minimum capacity is added to the residual capacity of the reverse edges. If
- no more paths in the residual-edge tree are found, the algorithm terminates.
- Instead of finding a new shortest path from source to sink in the graph in each
- iteration, the Boykov-Kolmogorov algorithm keeps the already found paths as
- follows:</P>
- <P>The algorithm builds up two search trees, a source-tree and a
- sink-tree. Each vertex has a label (stored in <I>ColorMap</I>) to
- which tree it belongs and a status-flag if this vertex is active or
- passive. In the beginning of the algorithm only the source and the
- sink are colored (source==black, sink==white) and have active status.
- All other vertices are colored gray. The algorithm consists of three
- phases:</P>
- <P><I>grow-phase</I>: In this phase active vertices are allowed to
- acquire neighbor vertices that are connected through an edge that has
- a capacity-value greater than zero. Acquiring means that those vertices
- become active and belong now to the search tree of the current
- active vertex. If there are no more valid connections to neighbor
- vertices, the current vertex becomes passive and the grow phase
- continues with the next active vertex. The grow phase terminates if
- there are no more active vertices left or a vertex discovers a vertex
- from the other search tree through an unsaturated edge. In this case
- a path from source to sink is found.</P>
- <P><I>augment-phase</I>: This phase augments the path that was found
- in the grow phase. First it finds the bottleneck capacity of the
- found path, and then it updates the residual-capacity of the edges
- from this path by subtracting the bottleneck capacity from the
- residual capacity. Furthermore the residual capacity of the reverse
- edges are updated by adding the bottleneck capacity. This phase can
- destroy the built up search trees, as it creates at least one
- saturated edge. That means, that the search trees collapse to
- forests, because a condition for the search trees is, that each
- vertex in them has a valid (=non-saturated) connection to a terminal.</P>
- <P><I>adoption-phase</I>: Here the search trees are reconstructed. A
- simple solution would be to mark all vertices coming after the first
- orphan in the found path free vertices (gray). A more sophisticated
- solution is to give those orphans new parents: The neighbor vertices
- are checked if they have a valid connection to the same terminal like
- this vertex had (a path with unsaturated edges). If there is one,
- this vertex becomes the new parent of the current orphan and this
- forest is re-included into the search tree. If no new valid parent is
- found, this vertex becomes a free vertex (marked gray), and it's
- children become orphans. The adoption phase terminates if there are
- no more orphans.</P>
- <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>
- <UL>
- <LI><P>Marking heuristics: A timestamp is stored for each vertex
- which shows in which iteration of the algorithm the distance to the
- corresponding terminal was calculated.
- </P>
- <UL>
- <LI><P>This distance is used and gets calculated in the
- adoption-phase. In order to find a valid new parent for an orphan,
- the possible parent is checked for a connection to the terminal to
- which tree it belongs. If there is such a connection, the path is
- tagged with the current time-stamp, and the distance value. If
- another orphan has to find a parent and it comes across a vertex
- with a current timestamp, this information is used.</P>
- <LI><P>The distance is also used in the grow-phase. If a vertex
- comes across another vertex of the same tree while searching for
- new vertices, the other's distance is compared to its distance. If
- it is smaller, that other vertex becomes the new parent of the
- current. This can decrease the length of the search paths, and so
- amount of adoptions.</P>
- </UL>
- <LI><P>Ordering of orphans: As described above, the augment-phase
- and the adoption phase can create orphans. The orphans the
- augment-phase generates, are ordered according to their distance to
- the terminals (smallest first). This combined with the
- distance/timestamp heuristics results in the possibility for not
- having to recheck terminal-connections too often. New orphans which
- are generated in adoption phase are processed before orphans from
- the main queue for the same reason.</P>
- </UL>
- <P><BR><B>Implementation notes:</B></P>
- <P>The algorithm is mainly implemented as described by Boykov and Kolmogorov in
- [<a href="bibliography.html#boykov-kolmogorov04">69</a>]. An extended version
- can be found in the PhD Thesis of Kolmogorov [<A HREF="bibliography.html#kolmogorov03">68</a>].
- The following changes are made to improve performance:</P>
- <UL>
- <LI>initialization: the algorithm first augments all paths from
- source->sink and all paths from source->VERTEX->sink. This
- improves especially graph-cuts used in image vision where nearly
- each vertex has a source and sink connect. During this step, all
- vertices that have an unsaturated connection from source are added
- to the active vertex list and so the source is not.</LI>
- <LI>active vertices: Boykov-Kolmogorov uses two lists for active nodes
- and states that new active vertices are added to the rear of the
- second. Fetching an active vertex is done from the beginning of the
- first list. If the first list is empty, it is exchanged by the
- second. This implementation uses just one list.</LI>
- <LI>grow-phase: In the grow phase the first vertex in the
- active-list is taken and all outgoing edges are checked if they are
- unsaturated. This decreases performance for graphs with high-edge
- density. This implementation stores the last accessed edge and
- continues with it, if the first vertex in the active-list is the
- same one as during the last grow-phase.</LI>
- </UL>
- <H3>Where Defined</H3>
- <P><TT><A HREF="../../../boost/graph/boykov_kolmogorov_max_flow.hpp">boost/graph/boykov_kolmogorov_max_flow.hpp</A></TT>
- </P>
- <H3>Parameters</H3>
- <P>IN: <TT>Graph& g</TT>
- </P>
- <BLOCKQUOTE>A directed graph. The graph's type must be a model of
- <A HREF="VertexListGraph.html">Vertex List Graph</A>, <A HREF="EdgeListGraph.html">Edge
- List Graph</A> and <A HREF="IncidenceGraph.html">Incidence Graph</A>.
- For each edge <I>(u,v)</I> in the graph, the reverse edge <I>(v,u)</I>
- must also be in the graph. Performance of the algorithm will be slightly
- improved if the graph type also models <a href="AdjacencyMatrix.html">Adjacency
- Matrix</a>.
- </BLOCKQUOTE>
- <P>IN: <TT>vertex_descriptor src</TT>
- </P>
- <BLOCKQUOTE>The source vertex for the flow network graph.
- </BLOCKQUOTE>
- <P>IN: <TT>vertex_descriptor sink</TT>
- </P>
- <BLOCKQUOTE>The sink vertex for the flow network graph.
- </BLOCKQUOTE>
- <H3>Named Parameters</H3>
- <P>IN: <TT>edge_capacity(EdgeCapacityMap cap)</TT>
- </P>
- <BLOCKQUOTE>The edge capacity property map. The type must be a model
- of a constant <A HREF="../../property_map/doc/LvaluePropertyMap.html">Lvalue
- Property Map</A>. The key type of the map must be the graph's edge
- descriptor type.<BR><B>Default:</B> <TT>get(edge_capacity, g)</TT>
- </BLOCKQUOTE>
- <P>OUT: <TT>edge_residual_capacity(ResidualCapacityEdgeMap res)</TT>
- </P>
- <BLOCKQUOTE>The edge residual capacity property map. The type must be
- a model of a mutable <A HREF="../../property_map/doc/LvaluePropertyMap.html">Lvalue
- Property Map</A>. The key type of the map must be the graph's edge
- descriptor type.<BR><B>Default:</B> <TT>get(edge_residual_capacity,
- g)</TT>
- </BLOCKQUOTE>
- <P>IN: <TT>edge_reverse(ReverseEdgeMap rev)</TT>
- </P>
- <BLOCKQUOTE>An edge property map that maps every edge <I>(u,v)</I> in
- the graph to the reverse edge <I>(v,u)</I>. The map must be a model
- of constant <A HREF="../../property_map/doc/LvaluePropertyMap.html">Lvalue
- Property Map</A>. The key type of the map must be the graph's edge
- descriptor type.<BR><B>Default:</B> <TT>get(edge_reverse, g)</TT>
- </BLOCKQUOTE>
- <P>UTIL: <TT>vertex_predecessor(PredecessorMap pre_map)</TT>
- </P>
- <BLOCKQUOTE>A vertex property map that stores the edge to the vertex'
- predecessor. The map must be a model of mutable <A HREF="../../property_map/doc/LvaluePropertyMap.html">Lvalue
- Property Map</A>. The key type of the map must be the graph's vertex
- descriptor type.<BR><B>Default:</B> <TT>get(vertex_predecessor, g)</TT>
- </BLOCKQUOTE>
- <P>OUT/UTIL: <TT>vertex_color(ColorMap color)</TT>
- </P>
- <BLOCKQUOTE>A vertex property map that stores a color for edge
- vertex. If the color of a vertex after running the algorithm is black
- the vertex belongs to the source tree else it belongs to the
- sink-tree (used for minimum cuts). The map must be a model of mutable
- <A HREF="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property
- Map</A>. The key type of the map must be the graph's vertex
- descriptor type.<BR><B>Default:</B> <TT>get(vertex_color, g)</TT>
- </BLOCKQUOTE>
- <P>UTIL: <TT>vertex_distance(DistanceMap dist)</TT>
- </P>
- <BLOCKQUOTE>A vertex property map that stores the distance to the
- corresponding terminal. It's a utility-map for speeding up the
- algorithm. The map must be a model of mutable <A HREF="../../property_map/doc/LvaluePropertyMap.html">Lvalue
- Property Map</A>. The key type of the map must be the graph's vertex
- descriptor type.<BR><B>Default:</B> <TT>get(vertex_distance, g)</TT>
- </BLOCKQUOTE>
- <P>IN: <TT>vertex_index(VertexIndexMap index_map)</TT>
- </P>
- <BLOCKQUOTE>Maps each vertex of the graph to a unique integer in the
- range <TT>[0, num_vertices(g))</TT>. The map must be a model of
- constant <A HREF="../../property_map/doc/LvaluePropertyMap.html">LvaluePropertyMap</A>.
- The key type of the map must be the graph's vertex descriptor
- type.<BR><B>Default:</B> <TT>get(vertex_index, g)</TT>
- </BLOCKQUOTE>
- <H3>Example</H3>
- <P>This reads an example maximum flow problem (a graph with edge
- capacities) from a file in the DIMACS format (<TT><A HREF="../example/max_flow.dat">example/max_flow.dat</A></TT>).
- The source for this example can be found in
- <TT><A HREF="../example/boykov_kolmogorov-eg.cpp">example/boykov_kolmogorov-eg.cpp</A></TT>.
- </P>
- <PRE>#include <boost/config.hpp>
- #include <iostream>
- #include <string>
- #include <boost/graph/adjacency_list.hpp>
- #include <boost/graph/boykov_kolmogorov_max_flow.hpp>
- #include <boost/graph/read_dimacs.hpp>
- #include <boost/graph/graph_utility.hpp>
- int
- main()
- {
- using namespace boost;
- typedef adjacency_list_traits < vecS, vecS, directedS > Traits;
- typedef adjacency_list < vecS, vecS, directedS,
- property < vertex_name_t, std::string,
- property < vertex_index_t, long,
- property < vertex_color_t, boost::default_color_type,
- property < vertex_distance_t, long,
- property < vertex_predecessor_t, Traits::edge_descriptor > > > > >,
- property < edge_capacity_t, long,
- property < edge_residual_capacity_t, long,
- property < edge_reverse_t, Traits::edge_descriptor > > > > Graph;
- Graph g;
- property_map < Graph, edge_capacity_t >::type
- capacity = get(edge_capacity, g);
- property_map < Graph, edge_residual_capacity_t >::type
- residual_capacity = get(edge_residual_capacity, g);
- property_map < Graph, edge_reverse_t >::type rev = get(edge_reverse, g);
- Traits::vertex_descriptor s, t;
- read_dimacs_max_flow(g, capacity, rev, s, t);
- std::vector<default_color_type> color(num_vertices(g));
- std::vector<long> distance(num_vertices(g));
- long flow = boykov_kolmogorov_max_flow(g ,s, t);
- std::cout << "c The total flow:" << std::endl;
- std::cout << "s " << flow << std::endl << std::endl;
- std::cout << "c flow values:" << std::endl;
- graph_traits < Graph >::vertex_iterator u_iter, u_end;
- graph_traits < Graph >::out_edge_iterator ei, e_end;
- for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
- for (boost::tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei)
- if (capacity[*ei] > 0)
- std::cout << "f " << *u_iter << " " << target(*ei, g) << " "
- << (capacity[*ei] - residual_capacity[*ei]) << std::endl;
- return EXIT_SUCCESS;
- }</PRE><P>
- The output is:
- </P>
- <PRE>c The total flow:
- s 13
- c flow values:
- f 0 6 3
- f 0 1 0
- f 0 2 10
- f 1 5 1
- f 1 0 0
- f 1 3 0
- f 2 4 4
- f 2 3 6
- f 2 0 0
- f 3 7 5
- f 3 2 0
- f 3 1 1
- f 4 5 4
- f 4 6 0
- f 5 4 0
- f 5 7 5
- f 6 7 3
- f 6 4 0
- f 7 6 0
- f 7 5 0</PRE><H3>
- See Also</H3>
- <P STYLE="margin-bottom: 0cm">
- <TT><A HREF="edmonds_karp_max_flow.html">edmonds_karp_max_flow()</A></TT>,
- <TT><A HREF="push_relabel_max_flow.html">push_relabel_max_flow()</A></TT>.
- </P>
- <HR>
- <TABLE CELLPADDING=2 CELLSPACING=2>
- <TR VALIGN=TOP>
- <TD>
- <P>Copyright © 2006</P>
- </TD>
- <TD>
- <P>Stephan Diederich, University
- Mannheim(<A HREF="mailto:diederich@ti.uni-manheim.de">diederich@ti.uni-manheim.de</A>)</P>
- </TD>
- </TR>
- </TABLE>
- <P><BR><BR>
- </P>
- </BODY>
- </HTML>
|