]> git.proxmox.com Git - ceph.git/blame - ceph/src/boost/libs/graph/doc/edmonds_karp_max_flow.html
bump version to 12.2.2-pve1
[ceph.git] / ceph / src / boost / libs / graph / doc / edmonds_karp_max_flow.html
CommitLineData
7c673cae
FG
1<HTML>
2<!--
3 Copyright (c) Jeremy Siek 2000
4
5 Distributed under the Boost Software License, Version 1.0.
6 (See accompanying file LICENSE_1_0.txt or copy at
7 http://www.boost.org/LICENSE_1_0.txt)
8 -->
9<Head>
10<Title>Boost Graph Library: Edmonds-Karp Maximum Flow</Title>
11<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
12 ALINK="#ff0000">
13<IMG SRC="../../../boost.png"
14 ALT="C++ Boost" width="277" height="86">
15
16<BR Clear>
17
18<H1><A NAME="sec:edmonds_karp_max_flow">
19<TT>edmonds_karp_max_flow</TT>
20</H1>
21
22<PRE>
23<i>// named parameter version</i>
24template &lt;class <a href="./Graph.html">Graph</a>, class P, class T, class R&gt;
25typename detail::edge_capacity_value&lt;Graph, P, T, R&gt;::value_type
26edmonds_karp_max_flow(Graph& g,
27 typename graph_traits&lt;Graph&gt;::vertex_descriptor src,
28 typename graph_traits&lt;Graph&gt;::vertex_descriptor sink,
29 const bgl_named_params&lt;P, T, R&gt;&amp; params = <i>all defaults</i>)
30
31<i>// non-named parameter version</i>
32template &lt;class <a href="./Graph.html">Graph</a>,
33 class CapacityEdgeMap, class ResidualCapacityEdgeMap,
34 class ReverseEdgeMap, class ColorMap, class PredEdgeMap&gt;
35typename property_traits&lt;CapacityEdgeMap&gt;::value_type
36edmonds_karp_max_flow(Graph&amp; g,
37 typename graph_traits&lt;Graph&gt;::vertex_descriptor src,
38 typename graph_traits&lt;Graph&gt;::vertex_descriptor sink,
39 CapacityEdgeMap cap, ResidualCapacityEdgeMap res, ReverseEdgeMap rev,
40 ColorMap color, PredEdgeMap pred)
41</PRE>
42
43<P>
44The <tt>edmonds_karp_max_flow()</tt> function calculates the maximum flow
45of a network. See Section <a
46href="./graph_theory_review.html#sec:network-flow-algorithms">Network
47Flow Algorithms</a> for a description of maximum flow. The calculated
48maximum flow will be the return value of the function. The function
49also calculates the flow values <i>f(u,v)</i> for all <i>(u,v)</i> in
50<i>E</i>, which are returned in the form of the residual capacity
51<i>r(u,v) = c(u,v) - f(u,v)</i>.
52
53<p>
54There are several special requirements on the input graph and property
55map parameters for this algorithm. First, the directed graph
56<i>G=(V,E)</i> that represents the network must be augmented to
57include the reverse edge for every edge in <i>E</i>. That is, the
58input graph should be <i>G<sub>in</sub> = (V,{E U
59E<sup>T</sup>})</i>. The <tt>ReverseEdgeMap</tt> argument <tt>rev</tt>
60must map each edge in the original graph to its reverse edge, that is
61<i>(u,v) -> (v,u)</i> for all <i>(u,v)</i> in <i>E</i>. The
62<tt>CapacityEdgeMap</tt> argument <tt>cap</tt> must map each edge in
63<i>E</i> to a positive number, and each edge in <i>E<sup>T</sup></i>
64to 0.
65
66<p>
67The algorithm is due to <a
68href="./bibliography.html#edmonds72:_improvements_netflow">Edmonds and
69Karp</a>, though we are using the variation called the ``labeling
70algorithm'' described in <a
71href="./bibliography.html#ahuja93:_network_flows">Network Flows</a>.
72
73<p>
74This algorithm provides a very simple and easy to implement solution to
75the maximum flow problem. However, there are several reasons why this
76algorithm is not as good as the <a
77href="./push_relabel_max_flow.html"><tt>push_relabel_max_flow()</tt></a>
78or the <a
79href="./boykov_kolmogorov_max_flow.html"><tt>boykov_kolmogorov_max_flow()</tt></a>
80algorithm.
81
82<ul>
83 <li>In the non-integer capacity case, the time complexity is <i>O(V
84 E<sup>2</sup>)</i> which is worse than the time complexity of the
85 push-relabel algorithm <i>O(V<sup>2</sup>E<sup>1/2</sup>)</i>
86 for all but the sparsest of graphs.</li>
87
88 <li>In the integer capacity case, if the capacity bound <i>U</i> is
89 very large then the algorithm will take a long time.</li>
90</ul>
91
92
93<H3>Where Defined</H3>
94
95<P>
96<a href="../../../boost/graph/edmonds_karp_max_flow.hpp"><TT>boost/graph/edmonds_karp_max_flow.hpp</TT></a>
97
98<P>
99
100<h3>Parameters</h3>
101
102IN: <tt>Graph&amp; g</tt>
103<blockquote>
104 A directed graph. The
105 graph's type must be a model of <a
106 href="./VertexListGraph.html">VertexListGraph</a> and <a href="./IncidenceGraph.html">IncidenceGraph</a> For each edge
107 <i>(u,v)</i> in the graph, the reverse edge <i>(v,u)</i> must also
108 be in the graph.
109</blockquote>
110
111IN: <tt>vertex_descriptor src</tt>
112<blockquote>
113 The source vertex for the flow network graph.
114</blockquote>
115
116IN: <tt>vertex_descriptor sink</tt>
117<blockquote>
118 The sink vertex for the flow network graph.
119</blockquote>
120
121<h3>Named Parameters</h3>
122
123
124IN: <tt>capacity_map(CapacityEdgeMap cap)</tt>
125<blockquote>
126 The edge capacity property map. The type must be a model of a
127 constant <a
128 href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property Map</a>. The
129 key type of the map must be the graph's edge descriptor type.<br>
130 <b>Default:</b> <tt>get(edge_capacity, g)</tt>
131</blockquote>
132
133OUT: <tt>residual_capacity_map(ResidualCapacityEdgeMap res)</tt>
134<blockquote>
135 This maps edges to their residual capacity. The type must be a model
136 of a mutable <a
137 href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property
138 Map</a>. The key type of the map must be the graph's edge descriptor
139 type.<br>
140 <b>Default:</b> <tt>get(edge_residual_capacity, g)</tt>
141</blockquote>
142
143IN: <tt>reverse_edge_map(ReverseEdgeMap rev)</tt>
144<blockquote>
145 An edge property map that maps every edge <i>(u,v)</i> in the graph
146 to the reverse edge <i>(v,u)</i>. The map must be a model of
147 constant <a href="../../property_map/doc/LvaluePropertyMap.html">Lvalue
148 Property Map</a>. The key type of the map must be the graph's edge
149 descriptor type.<br>
150 <b>Default:</b> <tt>get(edge_reverse, g)</tt>
151</blockquote>
152
153UTIL: <tt>color_map(ColorMap color)</tt>
154<blockquote>
155 Used by the algorithm to keep track of progress during the
156 breadth-first search stage. At the end of the algorithm, the white
157 vertices define the minimum cut set. The map must be a model of
158 mutable <a
159 href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property Map</a>.
160 The key type of the map should be the graph's vertex descriptor type, and
161 the value type must be a model of <a
162 href="./ColorValue.html">ColorValue</a>.<br>
163
164 <b>Default:</b> an <a
165 href="../../property_map/doc/iterator_property_map.html">
166 <tt>iterator_property_map</tt></a> created from a <tt>std::vector</tt>
167 of <tt>default_color_type</tt> of size <tt>num_vertices(g)</tt> and
168 using the <tt>i_map</tt> for the index map.
169</blockquote>
170
171UTIL: <tt>predecessor_map(PredEdgeMap pred)</tt>
172<blockquote>
173 Use by the algorithm to store augmenting paths. The map must be a
174 model of mutable <a
175 href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property Map</a>.
176 The key type must be the graph's vertex descriptor type and the
177 value type must be the graph's edge descriptor type.<br>
178
179 <b>Default:</b> an <a
180 href="../../property_map/doc/iterator_property_map.html">
181 <tt>iterator_property_map</tt></a> created from a <tt>std::vector</tt>
182 of edge descriptors of size <tt>num_vertices(g)</tt> and
183 using the <tt>i_map</tt> for the index map.
184</blockquote>
185
186IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
187<blockquote>
188 Maps each vertex of the graph to a unique integer in the range
189 <tt>[0, num_vertices(g))</tt>. This property map is only needed
190 if the default for the color or predecessor map is used.
191 The vertex index map must be a model of <a
192 href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
193 Map</a>. The key type of the map must be the graph's vertex
194 descriptor type.<br>
195 <b>Default:</b> <tt>get(vertex_index, g)</tt>
196 Note: if you use this default, make sure your graph has
197 an internal <tt>vertex_index</tt> property. For example,
198 <tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does
199 not have an internal <tt>vertex_index</tt> property.
200</blockquote>
201
202
203<h3>Complexity</h3>
204
205The time complexity is <i>O(V E<sup>2</sup>)</i> in the general case
206or <i>O(V E U)</i> if capacity values are integers bounded by
207some constant <i>U</i>.
208
209<h3>Example</h3>
210
211The program in <a
212href="../example/edmonds-karp-eg.cpp"><tt>example/edmonds-karp-eg.cpp</tt></a>
213reads an example maximum flow problem (a graph with edge capacities)
214from a file in the DIMACS format and computes the maximum flow.
215
216
217<h3>See Also</h3>
218
219<a href="./push_relabel_max_flow.html"><tt>push_relabel_max_flow()</tt></a><br>
220<a href="./boykov_kolmogorov_max_flow.html"><tt>boykov_kolmogorov_max_flow()</tt></a>.
221
222<br>
223<HR>
224<TABLE>
225<TR valign=top>
226<TD nowrap>Copyright &copy; 2000-2001</TD><TD>
227<A HREF="http://www.boost.org/users/people/jeremy_siek.html">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)
228</TD></TR></TABLE>
229
230</BODY>
231</HTML>
232<!-- LocalWords: HTML Siek Edmonds BGCOLOR ffffff ee VLINK ALINK ff IMG SRC
233 -->
234<!-- LocalWords: gif ALT BR sec edmonds karp TT DIV CELLPADDING TR TD PRE lt
235 -->
236<!-- LocalWords: typename VertexListGraph CapacityEdgeMap ReverseEdgeMap gt
237 -->
238<!-- LocalWords: ResidualCapacityEdgeMap VertexIndexMap src rev ColorMap pred
239 -->
240<!-- LocalWords: PredEdgeMap tt href html hpp ul li nbsp br LvaluePropertyMap
241 -->
242<!-- LocalWords: num ColorValue DIMACS cpp pre config iostream dimacs int std
243 -->
244<!-- LocalWords: namespace vecS directedS cout endl iter ei HR valign nowrap
245 -->
246<!-- LocalWords: jeremy siek htm Univ mailto jsiek lsc edu
247p -->