- java.lang.Object
-
- org.jgrapht.alg.flow.MaximumFlowAlgorithmBase<V,E>
-
- org.jgrapht.alg.flow.PushRelabelMFImpl<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- 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!).
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private class
PushRelabelMFImpl.PushRelabelDiagnostic
class
PushRelabelMFImpl.VertexExtension
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
Fields Modifier and Type Field Description private java.util.Queue<PushRelabelMFImpl.VertexExtension>
activeVertices
private static ToleranceDoubleComparator
comparator
private int[]
countHeight
private PushRelabelMFImpl.PushRelabelDiagnostic
diagnostic
private static boolean
DIAGNOSTIC_ENABLED
private ExtensionFactory<MaximumFlowAlgorithmBase.AnnotatedFlowEdge>
edgeExtensionsFactory
private int
n
private int
relabelCounter
static boolean
USE_GAP_RELABELING_HEURISTIC
Deprecated, for removal: This API element is subject to removal in a future version.usesetUseGapRelabelingHeuristic(boolean)
insteadstatic boolean
USE_GLOBAL_RELABELING_HEURISTIC
Deprecated, for removal: This API element is subject to removal in a future version.usesetUseGlobalRelabelingHeuristic(boolean)
insteadprivate PushRelabelMFImpl.VertexExtension[]
vertexExtension
private ExtensionFactory<PushRelabelMFImpl.VertexExtension>
vertexExtensionsFactory
-
Fields inherited from class org.jgrapht.alg.flow.MaximumFlowAlgorithmBase
cutEdges, DEFAULT_EPSILON, directedGraph, edgeExtensionManager, maxFlow, maxFlowValue, network, sink, sinkPartition, source, sourcePartition, vertexExtensionManager
-
-
Constructor Summary
Constructors Constructor Description PushRelabelMFImpl(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
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
bfs(java.util.Queue<java.lang.Integer> queue, boolean[] visited)
double
calculateMaximumFlow(V source, V sink)
Sets current source tosource
, current sink tosink
, then calculates maximum flow fromsource
tosink
.private void
discharge(PushRelabelMFImpl.VertexExtension ux)
private void
enqueue(PushRelabelMFImpl.VertexExtension vx)
private void
gapHeuristic(int l)
MaximumFlowAlgorithm.MaximumFlow<E>
getMaximumFlow(V source, V sink)
Sets current source tosource
, current sink tosink
, then calculates maximum flow fromsource
tosink
.private PushRelabelMFImpl.VertexExtension
getVertexExtension(V v)
(package private) void
init(V source, V sink)
Prepares all data structures to start a new invocation of the Maximum Flow or Minimum Cut algorithmsvoid
initialize(PushRelabelMFImpl.VertexExtension source, PushRelabelMFImpl.VertexExtension sink, java.util.Queue<PushRelabelMFImpl.VertexExtension> active)
Initializationprivate boolean
isAdmissible(MaximumFlowAlgorithmBase.AnnotatedFlowEdge e)
private void
push(MaximumFlowAlgorithmBase.AnnotatedFlowEdge ex)
protected void
pushFlowThrough(MaximumFlowAlgorithmBase.AnnotatedFlowEdge ex, double f)
Push flow through an edge.private void
recomputeHeightsHeuristic()
private void
relabel(PushRelabelMFImpl.VertexExtension ux)
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 Detail
-
DIAGNOSTIC_ENABLED
private static final boolean DIAGNOSTIC_ENABLED
- See Also:
- Constant Field Values
-
USE_GLOBAL_RELABELING_HEURISTIC
@Deprecated(since="1.5.2", forRemoval=true) public static boolean 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(since="1.5.2", forRemoval=true) public static boolean USE_GAP_RELABELING_HEURISTIC
Deprecated, for removal: This API element is subject to removal in a future version.usesetUseGapRelabelingHeuristic(boolean)
instead
-
vertexExtensionsFactory
private final ExtensionFactory<PushRelabelMFImpl.VertexExtension> vertexExtensionsFactory
-
edgeExtensionsFactory
private final ExtensionFactory<MaximumFlowAlgorithmBase.AnnotatedFlowEdge> edgeExtensionsFactory
-
countHeight
private int[] countHeight
-
activeVertices
private java.util.Queue<PushRelabelMFImpl.VertexExtension> activeVertices
-
diagnostic
private PushRelabelMFImpl.PushRelabelDiagnostic diagnostic
-
n
private final int n
-
vertexExtension
private final PushRelabelMFImpl.VertexExtension[] vertexExtension
-
relabelCounter
private int relabelCounter
-
comparator
private static ToleranceDoubleComparator comparator
-
-
Method Detail
-
setUseGlobalRelabelingHeuristic
public static void setUseGlobalRelabelingHeuristic(boolean useGlobalRelabelingHeuristic)
-
setUseGapRelabelingHeuristic
public static void setUseGapRelabelingHeuristic(boolean useGapRelabelingHeuristic)
-
enqueue
private void enqueue(PushRelabelMFImpl.VertexExtension vx)
-
init
void init(V source, V sink)
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.VertexExtension source, PushRelabelMFImpl.VertexExtension sink, java.util.Queue<PushRelabelMFImpl.VertexExtension> active)
Initialization- Parameters:
source
- the sourcesink
- the sinkactive
- resulting queue with all active vertices
-
getMaximumFlow
public MaximumFlowAlgorithm.MaximumFlow<E> getMaximumFlow(V source, V sink)
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
public double calculateMaximumFlow(V source, V sink)
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
protected void pushFlowThrough(MaximumFlowAlgorithmBase.AnnotatedFlowEdge ex, double f)
Push flow through an edge.- Overrides:
pushFlowThrough
in classMaximumFlowAlgorithmBase<V,E>
- Parameters:
ex
- the edgef
- the amount of flow to push through
-
push
private void push(MaximumFlowAlgorithmBase.AnnotatedFlowEdge ex)
-
gapHeuristic
private void gapHeuristic(int l)
-
relabel
private void relabel(PushRelabelMFImpl.VertexExtension ux)
-
bfs
private void bfs(java.util.Queue<java.lang.Integer> queue, boolean[] visited)
-
recomputeHeightsHeuristic
private void recomputeHeightsHeuristic()
-
discharge
private void discharge(PushRelabelMFImpl.VertexExtension ux)
-
isAdmissible
private boolean isAdmissible(MaximumFlowAlgorithmBase.AnnotatedFlowEdge e)
-
getVertexExtension
private PushRelabelMFImpl.VertexExtension getVertexExtension(V v)
-
-