Class 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!).
    Author:
    Alexandru Valeanu, Alexey Kudinkin
    • Field Detail

      • USE_GLOBAL_RELABELING_HEURISTIC

        public static boolean USE_GLOBAL_RELABELING_HEURISTIC
      • USE_GAP_RELABELING_HEURISTIC

        public static boolean USE_GAP_RELABELING_HEURISTIC
    • Constructor Detail

      • PushRelabelMFImpl

        public PushRelabelMFImpl​(Graph<V,​E> network)
        Construct a new push-relabel algorithm.
        Parameters:
        network - the network
      • PushRelabelMFImpl

        public PushRelabelMFImpl​(Graph<V,​E> network,
                                 double epsilon)
        Construct a new push-relabel algorithm.
        Parameters:
        network - the network
        epsilon - tolerance used when comparing floating-point values
    • Method Detail

      • getMaximumFlow

        public MaximumFlowAlgorithm.MaximumFlow<E> getMaximumFlow​(V source,
                                                                  V sink)
        Description copied from interface: MaximumFlowAlgorithm
        Sets current source to source, current sink to sink, then calculates maximum flow from source to sink. Returns an object containing detailed information about the flow.
        Parameters:
        source - source of the flow inside the network
        sink - sink of the flow inside the network
        Returns:
        maximum flow
      • calculateMaximumFlow

        public double calculateMaximumFlow​(V source,
                                           V sink)
        Sets current source to source, current sink to sink, then calculates maximum flow from source to sink. Note, that source and sink must be vertices of the network passed to the constructor, and they must be different.
        Parameters:
        source - source vertex
        sink - sink vertex
        Returns:
        the value of the maximum flow
      • pushFlowThrough

        protected void pushFlowThrough​(org.jgrapht.alg.flow.MaximumFlowAlgorithmBase.AnnotatedFlowEdge ex,
                                       double f)
        Push flow through an edge.
        Overrides:
        pushFlowThrough in class MaximumFlowAlgorithmBase<V,​E>
        Parameters:
        ex - the edge
        f - the amount of flow to push through