Package com.jgalgo.alg.flow

Class MaximumFlowPushRelabel

java.lang.Object
com.jgalgo.alg.connect.MinimumEdgeCutStAbstract
com.jgalgo.alg.flow.MaximumFlowAbstract
com.jgalgo.alg.flow.MaximumFlowAbstractWithoutResidualNet
com.jgalgo.alg.flow.MaximumFlowPushRelabel
All Implemented Interfaces:
MinimumEdgeCutSt, MaximumFlow
public class MaximumFlowPushRelabel extends MaximumFlowAbstractWithoutResidualNet
The push-relabel maximum flow algorithm with FIFO ordering.

The push-relabel algorithm maintain a "preflow" and gradually converts it into a maximum flow by moving flow locally between neighboring vertices using push operations under the guidance of an admissible network maintained by relabel operations.

Different variants of the push relabel algorithm exists, mostly differing in the order the vertices with excess (more in-going than out-going flow) are examined. The implementation support four different such ordering:

  • FIFO - active vertices are examined by the order they became active. Using this ordering achieve \(O(n^3)\) time complexity.
  • Highest First - active vertices are examined in decreasing order of their label. Using this ordering achieve \(O(n^2 \sqrt{m})\) time complexity.
  • Lowest First - active vertices are examined in increasing order of their label. Using this ordering achieve \(O(n^2 m)\) time complexity.
  • Move To Front - the active vertices are stored in a linked list, and the next examined vertex is the list head. When an active vertex is relabeled it is moved to the list head. Using this ordering achieve \(O(n^3)\) time complexity.
In addition to the order of the active vertices, the algorithm can be implemented in by pushing from an active vertex to one of its neighbor vertices, namely by pushing along a single edge, or by pushing from an active vertex along a path of admissable edges.

Heuristics are crucial for the practical running time of push-relabel algorithm, and this implementation uses the 'global relabeling', 'gap' and 'incremental restart' (optional) heuristics.

This algorithm can be implemented with better time theoretical bound using dynamic trees, but in practice it has little to non advantages. See MaximumFlowPushRelabelDynamicTrees.

Author:
Barak Ugav
See Also:

  • Method Details

    • newInstanceFifo

      public static MaximumFlowPushRelabel newInstanceFifo()
      Create a new push-relabel maximum flow algorithm object with a FIFO heuristic.

      The push-relabel algorithm with FIFO heuristic examine active vertices by the order they became active. Using this ordering achieve \(O(n^3)\) time complexity.

      Please prefer using MaximumFlow.newInstance() to get a default implementation for the MaximumFlow interface.

      Returns:
      a new push-relabel maximum flow algorithm object with a FIFO heuristic

    • newInstanceHighestFirst

      public static MaximumFlowPushRelabel newInstanceHighestFirst()
      Create a new push-relabel maximum flow algorithm object with a highest first heuristic.

      The push-relabel algorithm with highest first heuristic examine active vertices in decreasing order of their label. Using this ordering achieve \(O(n^2 \sqrt{m})\) time complexity.

      Please prefer using MaximumFlow.newInstance() to get a default implementation for the MaximumFlow interface.

      Returns:
      a new push-relabel maximum flow algorithm object with a highest first heuristic

    • newInstanceLowestFirst

      public static MaximumFlowPushRelabel newInstanceLowestFirst()
      Create a new push-relabel maximum flow algorithm object with a lowest first heuristic.

      The push-relabel algorithm with lowest first heuristic examine active vertices in increasing order of their label. Using this ordering achieve \(O(n^2 m)\) time complexity.

      Please prefer using MaximumFlow.newInstance() to get a default implementation for the MaximumFlow interface.

      Returns:
      a new push-relabel maximum flow algorithm object with a lowest first heuristic

    • newInstanceMoveToFront

      public static MaximumFlowPushRelabel newInstanceMoveToFront()
      Create a new push-relabel maximum flow algorithm object with a move-to-front heuristic.

      The push-relabel algorithm with move-to-front heuristic examine active vertices in the order they became active, but when an active vertex is relabeled it is moved to the front of the list. Using this ordering achieve \(O(n^3)\) time complexity.

      Please prefer using MaximumFlow.newInstance() to get a default implementation for the MaximumFlow interface.

      Returns:
      a new push-relabel maximum flow algorithm object with a move-to-front heuristic

    • newInstancePartialAugment

      public static MaximumFlowPushRelabel newInstancePartialAugment()
      Create a new push-relabel maximum flow algorithm object with a partial augment discharge policy and highest first active heuristic.

      The push-relabel algorithm with partial augment discharge policy push flow along a path of admissible edges. This policy is based on 'The Partial Augment–Relabel Algorithm for the Maximum Flow Problem' by Andrew V. Goldberg.

      Please prefer using MaximumFlow.newInstance() to get a default implementation for the MaximumFlow interface.

      Returns:
      a new push-relabel maximum flow algorithm object with a partial augment discharge policy

    • computeMinimumCut

      public IVertexBiPartition computeMinimumCut(IndexGraph g, IWeightFunction w, int source, int sink)