]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 <class Graph, class P, class T, class R> | |
62 | typename property_traits<typename property_map<Graph, edge_capacity_t>::const_type>::value_type | |
63 | boykov_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> | |
69 | template <class Graph, class CapacityEdgeMap, class ResidualCapacityEdgeMap, class ReverseEdgeMap, | |
70 | class PredecessorMap, class ColorMap, class DistanceMap, class IndexMap> | |
71 | typename property_traits<CapacityEdgeMap>::value_type | |
72 | boykov_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 | |
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) -> (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->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 | |
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 <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 | ||
305 | int | |
306 | main() | |
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> | |
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 © 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> |