Class PushRelabelMFImpl<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    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 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!).