graph_tool.flow.edmonds_karp_max_flow(g, source, target, capacity, residual=None)[source]#

Calculate maximum flow on the graph with the Edmonds-Karp algorithm.


Graph to be used.


The source vertex.


The target (or “sink”) vertex.


Edge property map with the edge capacities.

residualEdgePropertyMap (optional, default: none)

Edge property map where the residuals should be stored.


Edge property map with the residual capacities (capacity - flow).


The algorithm is due to [edmonds-theoretical-1972], though we are using the variation called the “labeling algorithm” described in [ravindra-network-1993].

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(VE^2)\) which is worse than the time complexity of the push-relabel algorithm \(O(V^2E^{1/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.

The time complexity is \(O(VE^2)\) in the general case or \(O(VEU)\) if capacity values are integers bounded by some constant \(U\).



Jack Edmonds and Richard M. Karp, “Theoretical improvements in the algorithmic efficiency for network flow problems. Journal of the ACM”, 19:248-264, 1972 DOI: 10.1145/321694.321699 [sci-hub, @tor]


Ravindra K. Ahuja and Thomas L. Magnanti and James B. Orlin,”Network Flows: Theory, Algorithms, and Applications”. Prentice Hall, 1993.


>>> g = gt.load_graph("flow-example.xml.gz")
>>> cap = g.edge_properties["cap"]
>>> src, tgt = g.vertex(0), g.vertex(1)
>>> res = gt.edmonds_karp_max_flow(g, src, tgt, cap)
>>> res.a = cap.a - res.a  # the actual flow
>>> max_flow = sum(res[e] for e in tgt.in_edges())
>>> print(max_flow)
>>> pos = g.vertex_properties["pos"]
>>> gt.graph_draw(g, pos=pos, edge_pen_width=gt.prop_to_size(res, mi=0, ma=5, power=1), output="example-edmonds-karp.pdf")

Edge flows obtained with the Edmonds-Karp algorithm. The source and target are on the upper left and lower right corners, respectively. The edge flows are represented by the edge width.#