Package com.jgalgo.alg.flow

Class MaximumFlowPushRelabelDynamicTrees

java.lang.Object
com.jgalgo.alg.connect.MinimumEdgeCutStAbstract
com.jgalgo.alg.flow.MaximumFlowAbstract
com.jgalgo.alg.flow.MaximumFlowAbstractWithResidualNet
com.jgalgo.alg.flow.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:

  • Constructor Details

    • MaximumFlowPushRelabelDynamicTrees

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

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