3 Copyright (c) Jeremy Siek 2000
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)
10 <Title>Boost Graph Library: Edmonds-Karp Maximum Flow
</Title>
11 <BODY BGCOLOR=
"#ffffff" LINK=
"#0000ee" TEXT=
"#000000" VLINK=
"#551a8b"
13 <IMG SRC=
"../../../boost.png"
14 ALT=
"C++ Boost" width=
"277" height=
"86">
18 <H1><A NAME=
"sec:edmonds_karp_max_flow">
19 <TT>edmonds_karp_max_flow
</TT>
23 <i>// named parameter version
</i>
24 template
<class
<a href=
"./Graph.html">Graph
</a>, class P, class T, class R
>
25 typename detail::edge_capacity_value
<Graph, P, T, R
>::value_type
26 edmonds_karp_max_flow(Graph& g,
27 typename graph_traits
<Graph
>::vertex_descriptor src,
28 typename graph_traits
<Graph
>::vertex_descriptor sink,
29 const bgl_named_params
<P, T, R
>& params =
<i>all defaults
</i>)
31 <i>// non-named parameter version
</i>
32 template
<class
<a href=
"./Graph.html">Graph
</a>,
33 class CapacityEdgeMap, class ResidualCapacityEdgeMap,
34 class ReverseEdgeMap, class ColorMap, class PredEdgeMap
>
35 typename property_traits
<CapacityEdgeMap
>::value_type
36 edmonds_karp_max_flow(Graph
& g,
37 typename graph_traits
<Graph
>::vertex_descriptor src,
38 typename graph_traits
<Graph
>::vertex_descriptor sink,
39 CapacityEdgeMap cap, ResidualCapacityEdgeMap res, ReverseEdgeMap rev,
40 ColorMap color, PredEdgeMap pred)
44 The
<tt>edmonds_karp_max_flow()
</tt> function calculates the maximum flow
45 of a network. See Section
<a
46 href=
"./graph_theory_review.html#sec:network-flow-algorithms">Network
47 Flow Algorithms
</a> for a description of maximum flow. The calculated
48 maximum flow will be the return value of the function. The function
49 also 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>.
54 There are several special requirements on the input graph and property
55 map parameters for this algorithm. First, the directed graph
56 <i>G=(V,E)
</i> that represents the network must be augmented to
57 include the reverse edge for every edge in
<i>E
</i>. That is, the
58 input graph should be
<i>G
<sub>in
</sub> = (V,{E U
59 E
<sup>T
</sup>})
</i>. The
<tt>ReverseEdgeMap
</tt> argument
<tt>rev
</tt>
60 must 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>
67 The algorithm is due to
<a
68 href=
"./bibliography.html#edmonds72:_improvements_netflow">Edmonds and
69 Karp
</a>, though we are using the variation called the ``labeling
70 algorithm'' described in
<a
71 href=
"./bibliography.html#ahuja93:_network_flows">Network Flows
</a>.
74 This algorithm provides a very simple and easy to implement solution to
75 the maximum flow problem. However, there are several reasons why this
76 algorithm is not as good as the
<a
77 href=
"./push_relabel_max_flow.html"><tt>push_relabel_max_flow()
</tt></a>
79 href=
"./boykov_kolmogorov_max_flow.html"><tt>boykov_kolmogorov_max_flow()
</tt></a>
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>
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>
93 <H3>Where Defined
</H3>
96 <a href=
"../../../boost/graph/edmonds_karp_max_flow.hpp"><TT>boost/graph/edmonds_karp_max_flow.hpp
</TT></a>
102 IN:
<tt>Graph
& g
</tt>
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
111 IN:
<tt>vertex_descriptor src
</tt>
113 The source vertex for the flow network graph.
116 IN:
<tt>vertex_descriptor sink
</tt>
118 The sink vertex for the flow network graph.
121 <h3>Named Parameters
</h3>
124 IN:
<tt>capacity_map(CapacityEdgeMap cap)
</tt>
126 The edge capacity property map. The type must be a model of 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>
133 OUT:
<tt>residual_capacity_map(ResidualCapacityEdgeMap res)
</tt>
135 This maps edges to their residual capacity. The type must be a model
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
140 <b>Default:
</b> <tt>get(edge_residual_capacity, g)
</tt>
143 IN:
<tt>reverse_edge_map(ReverseEdgeMap rev)
</tt>
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
150 <b>Default:
</b> <tt>get(edge_reverse, g)
</tt>
153 UTIL:
<tt>color_map(ColorMap color)
</tt>
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
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>
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.
171 UTIL:
<tt>predecessor_map(PredEdgeMap pred)
</tt>
173 Use by the algorithm to store augmenting paths. The map must be 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>
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.
186 IN:
<tt>vertex_index_map(VertexIndexMap i_map)
</tt>
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
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.
205 The time complexity is
<i>O(V E
<sup>2</sup>)
</i> in the general case
206 or
<i>O(V E U)
</i> if capacity values are integers bounded by
207 some constant
<i>U
</i>.
212 href=
"../example/edmonds-karp-eg.cpp"><tt>example/edmonds-karp-eg.cpp
</tt></a>
213 reads an example maximum flow problem (a graph with edge capacities)
214 from a file in the DIMACS format and computes the maximum flow.
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>.
226 <TD nowrap
>Copyright
© 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>)
232 <!-- LocalWords: HTML Siek Edmonds BGCOLOR ffffff ee VLINK ALINK ff IMG SRC
234 <!-- LocalWords: gif ALT BR sec edmonds karp TT DIV CELLPADDING TR TD PRE lt
236 <!-- LocalWords: typename VertexListGraph CapacityEdgeMap ReverseEdgeMap gt
238 <!-- LocalWords: ResidualCapacityEdgeMap VertexIndexMap src rev ColorMap pred
240 <!-- LocalWords: PredEdgeMap tt href html hpp ul li nbsp br LvaluePropertyMap
242 <!-- LocalWords: num ColorValue DIMACS cpp pre config iostream dimacs int std
244 <!-- LocalWords: namespace vecS directedS cout endl iter ei HR valign nowrap
246 <!-- LocalWords: jeremy siek htm Univ mailto jsiek lsc edu