Module org.jgrapht.core
Package org.jgrapht.alg.flow

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!).

    • 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

      • setUseGlobalRelabelingHeuristic

        public static void setUseGlobalRelabelingHeuristic​(boolean useGlobalRelabelingHeuristic)

      • setUseGapRelabelingHeuristic

        public static void setUseGapRelabelingHeuristic​(boolean useGapRelabelingHeuristic)

      • init

        void init​(V source,
          V sink)
        Prepares all data structures to start a new invocation of the Maximum Flow or Minimum Cut algorithms
        Parameters:
        source - source
        sink - sink

      • 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

      • gapHeuristic

        private void gapHeuristic​(int l)

      • bfs

        private void bfs​(java.util.Queue<java.lang.Integer> queue,
                 boolean[] visited)

      • recomputeHeightsHeuristic

        private void recomputeHeightsHeuristic()