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

Class PushRelabelMFImpl<V,E>

java.lang.Object
org.jgrapht.alg.flow.MaximumFlowAlgorithmBase<V,E>
org.jgrapht.alg.flow.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!).
Author:
Alexandru Valeanu, Alexey Kudinkin

  • Field Details

  • Constructor Details

    • 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 Details

    • setUseGlobalRelabelingHeuristic

      public static void setUseGlobalRelabelingHeuristic(boolean useGlobalRelabelingHeuristic)

    • setUseGapRelabelingHeuristic

      public static void setUseGapRelabelingHeuristic(boolean useGapRelabelingHeuristic)

    • initialize

      public void initialize(PushRelabelMFImpl<V,E>.VertexExtension source, PushRelabelMFImpl<V,E>.VertexExtension sink, Queue<PushRelabelMFImpl<V,E>.VertexExtension> active)
      Initialization
      Parameters:
      source - the source
      sink - the sink
      active - resulting queue with all active vertices

    • 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

    • pushFlowThrough

      protected void pushFlowThrough(MaximumFlowAlgorithmBase<V,E>.org.jgrapht.alg.flow.MaximumFlowAlgorithmBase.AnnotatedFlowEdge ex, double f)
      Push flow through an edge.
      Overrides:
      pushFlowThrough in class MaximumFlowAlgorithmBase<V,E>
      Parameters:
      ex - the edge
      f - the amount of flow to push through