Edmonds-Karp Maximum Flow

Calculates the maximum flow of a network using the Edmonds-Karp variant of the Ford-Fulkerson algorithm.

Complexity: O(V E2), or O(V E U) for integer capacities bounded by U
Defined in: <boost/graph/edmonds_karp_max_flow.hpp>

Example

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/edmonds_karp_max_flow.hpp>
#include <iostream>
#include <vector>

using namespace boost;

// Bundled edge data replaces the nested `property<edge_capacity_t, ...>`
// chain. The reverse descriptor field links each edge to its counterpart.
using Traits = adjacency_list_traits<vecS, vecS, directedS>;
struct Edge {
    int capacity;
    int residual_capacity;
    Traits::edge_descriptor reverse;
};

using Graph = adjacency_list<vecS, vecS, directedS, no_property, Edge>;
using Descriptor = graph_traits<Graph>::edge_descriptor;
using Vertex = graph_traits<Graph>::vertex_descriptor;

void add_flow_edge(Graph& g, int from, int to, int cap) {
    Descriptor e = add_edge(from, to, g).first;
    Descriptor r = add_edge(to, from, g).first;
    g[e].capacity = cap; g[e].reverse = r;
    g[r].capacity = 0;   g[r].reverse = e;
}

int main() {
    Graph g(4);
    add_flow_edge(g, 0, 1, 10);
    add_flow_edge(g, 0, 2, 10);
    add_flow_edge(g, 1, 3, 5);
    add_flow_edge(g, 2, 3, 15);
    add_flow_edge(g, 1, 2, 4);

    // 8-arg positional form accepts explicit capacity / residual / reverse maps.
    std::vector<default_color_type> color(num_vertices(g));
    std::vector<Descriptor> pred(num_vertices(g));
    auto color_map = make_iterator_property_map(color.begin(), get(vertex_index, g));
    auto pred_map  = make_iterator_property_map(pred.begin(),  get(vertex_index, g));

    int flow = edmonds_karp_max_flow(g, Vertex(0), Vertex(3),
        get(&Edge::capacity, g),
        get(&Edge::residual_capacity, g),
        get(&Edge::reverse, g),
        color_map, pred_map);
    std::cout << "Edmonds-Karp max flow: " << flow << "\n";
}
Edmonds-Karp max flow: 19

(1) Positional version

template <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);
Direction Parameter Description

IN

Graph& g

A directed graph. The graph’s type must be a model of Vertex List Graph and Incidence Graph. For each edge (u,v) in the graph, the reverse edge (v,u) must also be in the graph.

IN

vertex_descriptor src

The source vertex for the flow network graph.

IN

vertex_descriptor sink

The sink vertex for the flow network graph.

IN

CapacityEdgeMap cap

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

ResidualCapacityEdgeMap res

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

ReverseEdgeMap rev

An edge property map that maps every edge (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.

UTIL

ColorMap color

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 Color Value.

UTIL

PredEdgeMap pred

Used 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.

(2) Named parameter version

template <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);
Direction Parameter Description

IN

Graph& g

A directed graph. Must model Vertex List Graph and Incidence Graph. For each edge (u,v) in the graph, the reverse edge (v,u) must also be in the graph.

IN

vertex_descriptor src

The source vertex for the flow network graph.

IN

vertex_descriptor sink

The sink vertex for the flow network graph.

IN

params

Named parameters passed via bgl_named_params. The following are accepted:
Direction Named Parameter Description / Default

IN

capacity_map(CapacityEdgeMap cap)

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.
Default: get(edge_capacity, g)

OUT

residual_capacity_map(ResidualCapacityEdgeMap res)

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.
Default: get(edge_residual_capacity, g)

IN

reverse_edge_map(ReverseEdgeMap rev)

An edge property map that maps every edge (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)

UTIL

color_map(ColorMap color)

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 Color Value.
Default: an iterator_property_map created from a std::vector of default_color_type of size num_vertices(g) and using the i_map for the index map.

UTIL

predecessor_map(PredEdgeMap pred)

Used 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.
Default: an iterator_property_map created from a std::vector of edge descriptors of size num_vertices(g) and using the i_map for the index map.

IN

vertex_index_map(VertexIndexMap i_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 internal vertex_index property. For example, adjacency_list with VertexList=listS does not have an internal vertex_index property.

Description

The edmonds_karp_max_flow() function implements the Edmonds-Karp algorithm to calculate 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 Gin = (V,{E U ET}). The ReverseEdgeMap argument rev must map each edge in the original graph to its reverse edge, that is (u,v) → (v,u) for all (u,v) in E. The CapacityEdgeMap argument cap must map each edge in E to a positive number, and each edge in ET to 0.

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 E2) which is worse than the time complexity of the push-relabel algorithm O(V2E1/2) for all but the sparsest of graphs.

  • In the integer capacity case, if the capacity bound U is very large then the algorithm will take a long time.

Returns

The maximum flow value of the network.

Example

The program in example/edmonds-karp-eg.cpp reads an example maximum flow problem (a graph with edge capacities) from a file in the DIMACS format and computes the maximum flow.

Edit this Page