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 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!).- Author:
- Alexandru Valeanu, Alexey Kudinkin
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description class
PushRelabelMFImpl.VertexExtension
Vertex extension for the push-relabel algorithm, which contains an additional height.-
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 static boolean
USE_GAP_RELABELING_HEURISTIC
static boolean
USE_GLOBAL_RELABELING_HEURISTIC
-
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 Instance Methods Concrete Methods Modifier and Type Method Description double
calculateMaximumFlow(V source, V sink)
Sets current source tosource
, current sink tosink
, then calculates maximum flow fromsource
tosink
.MaximumFlowAlgorithm.MaximumFlow<E>
getMaximumFlow(V source, V sink)
Sets current source tosource
, current sink tosink
, then calculates maximum flow fromsource
tosink
.void
initialize(PushRelabelMFImpl.VertexExtension source, PushRelabelMFImpl.VertexExtension sink, java.util.Queue<PushRelabelMFImpl.VertexExtension> active)
Initializationprotected void
pushFlowThrough(org.jgrapht.alg.flow.MaximumFlowAlgorithmBase.AnnotatedFlowEdge ex, double f)
Push flow through an edge.-
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
-
-
-
-
Method Detail
-
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(org.jgrapht.alg.flow.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
-
-