## Class 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 Detail

• #### USE_GLOBAL_RELABELING_HEURISTIC

public static boolean USE_GLOBAL_RELABELING_HEURISTIC
• #### USE_GAP_RELABELING_HEURISTIC

public static boolean USE_GAP_RELABELING_HEURISTIC
• ### Constructor Detail

• #### 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 Detail

• #### 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​(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