Package com.jgalgo.alg.flow

Class MaximumFlowPushRelabelDynamicTrees

  • All Implemented Interfaces:
    MinimumEdgeCutSt, MaximumFlow
    public class MaximumFlowPushRelabelDynamicTrees
extends MaximumFlowAbstractWithResidualNet
    The push relabel algorithm for maximum flow using dynamic trees.

    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.

    Conceptually, the dynamic trees are used to push flow along multiple edges simultaneously. The current flow of each individual edges is not maintained explicitly, rather each path is stored as a dynamic tree, and the flow is stored as a weight of the tree edges - to calculate the weight (flow) of an edge, one would have to traverse the tree from the root to the edge and sum all weights on the path.

    Using the dynamic trees reduce the running time of the push-relabel algorithm to \(O(m n \log (n^2 / m))\) and linear space. This implementation uses FIFO to order the vertices to be examined. Note that this implementation is usually out preformed in practice by simpler variants of the push-relabel algorithm, such as MaximumFlowPushRelabel with highest label heuristic.

    Author:
    Barak Ugav
    See Also:
    MaximumFlowPushRelabel

    • Constructor Detail

      • MaximumFlowPushRelabelDynamicTrees

        public MaximumFlowPushRelabelDynamicTrees()
        Create a new maximum flow algorithm object.

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