...one of the most highly
regarded and expertly designed C++ library projects in the
world.

— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards

// named parameter versiontemplate <class Graph, class P, class T, class R> typename detail::edge_capacity_value<Graph, P, T, R>::value_type edmonds_karp_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 =all defaults)// non-named parameter versiontemplate <class Graph, class CapacityEdgeMap, class ResidualCapacityEdgeMap, class ReverseEdgeMap, class ColorMap, class PredEdgeMap> typename property_traits<CapacityEdgeMap>::value_type edmonds_karp_max_flow(Graph& g, typename graph_traits<Graph>::vertex_descriptor src, typename graph_traits<Graph>::vertex_descriptor sink, CapacityEdgeMap cap, ResidualCapacityEdgeMap res, ReverseEdgeMap rev, ColorMap color, PredEdgeMap pred)

The `edmonds_karp_max_flow()` function calculates the maximum flow
of a network. See Section Network
Flow Algorithms 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 *f(u,v)* for all *(u,v)* in
*E*, which are returned in the form of the residual capacity
*r(u,v) = c(u,v) - f(u,v)*.

There are several special requirements on the input graph and property
map parameters for this algorithm. First, the directed graph
*G=(V,E)* that represents the network must be augmented to
include the reverse edge for every edge in *E*. That is, the
input graph should be *G _{in} = (V,{E U
E^{T}})*. The

The algorithm is due to Edmonds and Karp, though we are using the variation called the ``labeling algorithm'' described in Network Flows.

This algorithm provides a very simple and easy to implement solution to
the maximum flow problem. However, there are several reasons why this
algorithm is not as good as the `push_relabel_max_flow()`
or the `boykov_kolmogorov_max_flow()`
algorithm.

- In the non-integer capacity case, the time complexity is
*O(V E*which is worse than the time complexity of the push-relabel algorithm^{2})*O(V*for all but the sparsest of graphs.^{2}E^{1/2}) - In the integer capacity case, if the capacity bound
*U*is very large then the algorithm will take a long time.

`boost/graph/edmonds_karp_max_flow.hpp`

A directed graph. The graph's type must be a model of VertexListGraph and IncidenceGraph For each edgeIN:(u,v)in the graph, the reverse edge(v,u)must also be in the graph.

The source vertex for the flow network graph.IN:

The sink vertex for the flow network graph.

The edge capacity property map. The type must be a model of a constant Lvalue Property Map. The key type of the map must be the graph's edge descriptor type.OUT:

Default:get(edge_capacity, g)

This maps edges to their residual capacity. The type must be a model of a mutable Lvalue Property Map. The key type of the map must be the graph's edge descriptor type.IN:

Default:get(edge_residual_capacity, g)

An edge property map that maps every edgeUTIL:(u,v)in the graph to the reverse edge(v,u). The map must be a model of constant Lvalue Property Map. The key type of the map must be the graph's edge descriptor type.

Default:get(edge_reverse, g)

Used by the algorithm to keep track of progress during the breadth-first search stage. At the end of the algorithm, the white vertices define the minimum cut set. The map must be a model of mutable Lvalue Property Map. The key type of the map should be the graph's vertex descriptor type, and the value type must be a model of ColorValue.UTIL:

Default:aniterator_property_mapcreated from astd::vectorofdefault_color_typeof sizenum_vertices(g)and using thei_mapfor the index map.

Use by the algorithm to store augmenting paths. The map must be a model of mutable Lvalue Property Map. The key type must be the graph's vertex descriptor type and the value type must be the graph's edge descriptor type.IN:

Default:aniterator_property_mapcreated from astd::vectorof edge descriptors of sizenum_vertices(g)and using thei_mapfor the index map.

Maps each vertex of the graph to a unique integer in the range[0, num_vertices(g)). This property map is only needed if the default for the color or predecessor map is used. The vertex index map must be a model of Readable Property Map. The key type of the map must be the graph's vertex descriptor type.

Default:get(vertex_index, g)Note: if you use this default, make sure your graph has an internalvertex_indexproperty. For example,adjacenty_listwithVertexList=listSdoes not have an internalvertex_indexproperty.

Copyright © 2000-2001 | Jeremy Siek, Indiana University (jsiek@osl.iu.edu) |