- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
FlowAlgorithm<V,
,E> MaximumFlowAlgorithm<V,
,E> MinimumSTCutAlgorithm<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!).-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate class
class
Vertex extension for the push-relabel algorithm, which contains an additional height.Nested classes/interfaces inherited from class org.jgrapht.alg.flow.MaximumFlowAlgorithmBase
MaximumFlowAlgorithmBase.AnnotatedFlowEdge, MaximumFlowAlgorithmBase.VertexExtensionBase
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.FlowAlgorithm
FlowAlgorithm.Flow<E>, FlowAlgorithm.FlowImpl<E>
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.MaximumFlowAlgorithm
MaximumFlowAlgorithm.MaximumFlow<E>, MaximumFlowAlgorithm.MaximumFlowImpl<E>
-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate Queue
<PushRelabelMFImpl<V, E>.VertexExtension> private static ToleranceDoubleComparator
private int[]
private PushRelabelMFImpl<V,
E>.PushRelabelDiagnostic private static final boolean
private final ExtensionFactory
<MaximumFlowAlgorithmBase<V, E>.AnnotatedFlowEdge> private final int
private int
static boolean
Deprecated, for removal: This API element is subject to removal in a future version.static boolean
Deprecated, for removal: This API element is subject to removal in a future version.usesetUseGlobalRelabelingHeuristic(boolean)
insteadprivate final PushRelabelMFImpl<V,
E>.VertexExtension[] private final ExtensionFactory
<PushRelabelMFImpl<V, E>.VertexExtension> Fields inherited from class org.jgrapht.alg.flow.MaximumFlowAlgorithmBase
cutEdges, DEFAULT_EPSILON, directedGraph, edgeExtensionManager, maxFlow, maxFlowValue, network, sink, sinkPartition, source, sourcePartition, vertexExtensionManager
-
Constructor Summary
ConstructorsConstructorDescriptionPushRelabelMFImpl
(Graph<V, E> network) Construct a new push-relabel algorithm.PushRelabelMFImpl
(Graph<V, E> network, double epsilon) Construct a new push-relabel algorithm. -
Method Summary
Modifier and TypeMethodDescriptionprivate void
double
calculateMaximumFlow
(V source, V sink) Sets current source tosource
, current sink tosink
, then calculates maximum flow fromsource
tosink
.private void
private void
private void
gapHeuristic
(int l) getMaximumFlow
(V source, V sink) Sets current source tosource
, current sink tosink
, then calculates maximum flow fromsource
tosink
.private PushRelabelMFImpl<V,
E>.VertexExtension (package private) void
Prepares all data structures to start a new invocation of the Maximum Flow or Minimum Cut algorithmsvoid
initialize
(PushRelabelMFImpl<V, E>.VertexExtension source, PushRelabelMFImpl<V, E>.VertexExtension sink, Queue<PushRelabelMFImpl<V, E>.VertexExtension> active) Initializationprivate boolean
private void
protected void
pushFlowThrough
(MaximumFlowAlgorithmBase<V, E>.AnnotatedFlowEdge ex, double f) Push flow through an edge.private void
private void
static void
setUseGapRelabelingHeuristic
(boolean useGapRelabelingHeuristic) static void
setUseGlobalRelabelingHeuristic
(boolean useGlobalRelabelingHeuristic) Methods inherited from class org.jgrapht.alg.flow.MaximumFlowAlgorithmBase
calculateMinCut, calculateSourcePartition, composeFlow, getCurrentSink, getCurrentSource, getCutCapacity, getCutEdges, getFlowDirection, getFlowMap, getMaximumFlowValue, getSinkPartition, getSourcePartition, init
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
Methods inherited from interface org.jgrapht.alg.interfaces.FlowAlgorithm
getFlow
Methods inherited from interface org.jgrapht.alg.interfaces.MaximumFlowAlgorithm
getMaximumFlowValue
-
Field Details
-
DIAGNOSTIC_ENABLED
private static final boolean DIAGNOSTIC_ENABLED- See Also:
-
USE_GLOBAL_RELABELING_HEURISTIC
Deprecated, for removal: This API element is subject to removal in a future version.usesetUseGlobalRelabelingHeuristic(boolean)
instead -
USE_GAP_RELABELING_HEURISTIC
Deprecated, for removal: This API element is subject to removal in a future version.usesetUseGapRelabelingHeuristic(boolean)
instead -
vertexExtensionsFactory
-
edgeExtensionsFactory
private final ExtensionFactory<MaximumFlowAlgorithmBase<V,E>.AnnotatedFlowEdge> edgeExtensionsFactory -
countHeight
private int[] countHeight -
activeVertices
-
diagnostic
-
n
private final int n -
vertexExtension
-
relabelCounter
private int relabelCounter -
comparator
-
-
Constructor Details
-
PushRelabelMFImpl
Construct a new push-relabel algorithm.- Parameters:
network
- the network
-
PushRelabelMFImpl
Construct a new push-relabel algorithm.- Parameters:
network
- the networkepsilon
- tolerance used when comparing floating-point values
-
-
Method Details
-
setUseGlobalRelabelingHeuristic
public static void setUseGlobalRelabelingHeuristic(boolean useGlobalRelabelingHeuristic) -
setUseGapRelabelingHeuristic
public static void setUseGapRelabelingHeuristic(boolean useGapRelabelingHeuristic) -
enqueue
-
init
Prepares all data structures to start a new invocation of the Maximum Flow or Minimum Cut algorithms- Parameters:
source
- sourcesink
- sink
-
initialize
public void initialize(PushRelabelMFImpl<V, E>.VertexExtension source, PushRelabelMFImpl<V, E>.VertexExtension sink, Queue<PushRelabelMFImpl<V, E>.VertexExtension> active) Initialization- Parameters:
source
- the sourcesink
- the sinkactive
- resulting queue with all active vertices
-
getMaximumFlow
Description copied from interface:MaximumFlowAlgorithm
Sets current source tosource
, current sink tosink
, then calculates maximum flow fromsource
tosink
. Returns an object containing detailed information about the flow.- Parameters:
source
- source of the flow inside the networksink
- sink of the flow inside the network- Returns:
- maximum flow
-
calculateMaximumFlow
Sets current source tosource
, current sink tosink
, then calculates maximum flow fromsource
tosink
. Note, thatsource
andsink
must be vertices of thenetwork
passed to the constructor, and they must be different.- Parameters:
source
- source vertexsink
- sink vertex- Returns:
- the value of the maximum flow
-
pushFlowThrough
Push flow through an edge.- Overrides:
pushFlowThrough
in classMaximumFlowAlgorithmBase<V,
E> - Parameters:
ex
- the edgef
- the amount of flow to push through
-
push
-
gapHeuristic
private void gapHeuristic(int l) -
relabel
-
bfs
-
recomputeHeightsHeuristic
private void recomputeHeightsHeuristic() -
discharge
-
isAdmissible
-
getVertexExtension
-
setUseGapRelabelingHeuristic(boolean)
instead