Class PushRelabelMFImpl<V,E>

java.lang.Object
org.jgrapht.alg.flow.MaximumFlowAlgorithmBase<V,E>
org.jgrapht.alg.flow.PushRelabelMFImpl<V,E>
Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
FlowAlgorithm<V,E>, MaximumFlowAlgorithm<V,E>, MinimumSTCutAlgorithm<V,E>

public class PushRelabelMFImpl<V,E> extends MaximumFlowAlgorithmBase<V,E>

Push-relabel maximum flow algorithm designed by Andrew V. Goldberg and Robert Tarjan. Current implementation complexity upper-bound is $O(V^3)$. For more details see: "A new approach to the maximum flow problem" by Andrew V. Goldberg and Robert Tarjan STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computing

This implementation is based on On Implementing the Push—Relabel Method for the Maximum Flow Problem by B. V. Cherkassky and A.V. Goldberg (Cherkassky, B. & Goldberg, A. Algorithmica (1997) 19: 390. https://doi.org/10.1007/PL00009180) and Introduction to Algorithms (3rd Edition).

This class can also computes minimum $s-t$ cuts. Effectively, to compute a minimum $s-t$ cut, the implementation first computes a minimum $s-t$ flow, after which a BFS is run on the residual graph.

Note: even though the algorithm accepts any kind of graph, currently only Simple directed and undirected graphs are supported (and tested!).