Package com.jgalgo.alg.flow

Class 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:
    Wikipedia

    • Method Detail

      • 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