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 typeE
- the graph edge type
- All Implemented Interfaces:
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 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 label.-
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.MaximumFlowAlgorithm
MaximumFlowAlgorithm.MaximumFlow<E>, MaximumFlowAlgorithm.MaximumFlowImpl<E>
-
-
Field Summary
Fields Modifier and Type Field Description private PushRelabelMFImpl.PushRelabelDiagnostic
diagnostic
private static boolean
DIAGNOSTIC_ENABLED
private ExtensionFactory<MaximumFlowAlgorithmBase.AnnotatedFlowEdge>
edgeExtensionsFactory
(package private) boolean
flowBack
private java.util.Map<java.lang.Integer,java.lang.Integer>
labeling
private ExtensionFactory<PushRelabelMFImpl.VertexExtension>
vertexExtensionsFactory
-
Fields inherited from class org.jgrapht.alg.flow.MaximumFlowAlgorithmBase
comparator, cutEdges, DEFAULT_EPSILON, directed_graph, 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 to source, current sink to sink, then calculates maximum flow from source to sink.private boolean
discharge(MaximumFlowAlgorithmBase.AnnotatedFlowEdge ex)
MaximumFlowAlgorithm.MaximumFlow<E>
getMaximumFlow(V source, V sink)
Sets current source to source, current sink to sink, then calculates maximum flow from source to sink.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
label(PushRelabelMFImpl.VertexExtension source, PushRelabelMFImpl.VertexExtension sink)
protected void
pushFlowThrough(MaximumFlowAlgorithmBase.AnnotatedFlowEdge ex, double f)
Push flow through an edge.private void
relabel(PushRelabelMFImpl.VertexExtension vx)
private void
updateLabeling(PushRelabelMFImpl.VertexExtension vx, int l)
-
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.MaximumFlowAlgorithm
buildMaximumFlow
-
-
-
-
Field Detail
-
DIAGNOSTIC_ENABLED
private static final boolean DIAGNOSTIC_ENABLED
- See Also:
- Constant Field Values
-
vertexExtensionsFactory
private final ExtensionFactory<PushRelabelMFImpl.VertexExtension> vertexExtensionsFactory
-
edgeExtensionsFactory
private final ExtensionFactory<MaximumFlowAlgorithmBase.AnnotatedFlowEdge> edgeExtensionsFactory
-
labeling
private java.util.Map<java.lang.Integer,java.lang.Integer> labeling
-
flowBack
boolean flowBack
-
diagnostic
private PushRelabelMFImpl.PushRelabelDiagnostic diagnostic
-
-
Method Detail
-
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
-
label
private void label(PushRelabelMFImpl.VertexExtension source, PushRelabelMFImpl.VertexExtension sink)
-
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 networksink
- 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 vertexsink
- sink vertex- Returns:
- the value of the maximum flow
-
relabel
private void relabel(PushRelabelMFImpl.VertexExtension vx)
-
updateLabeling
private void updateLabeling(PushRelabelMFImpl.VertexExtension vx, int l)
-
discharge
private boolean discharge(MaximumFlowAlgorithmBase.AnnotatedFlowEdge ex)
-
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
-
isAdmissible
private boolean isAdmissible(MaximumFlowAlgorithmBase.AnnotatedFlowEdge e)
-
getVertexExtension
private PushRelabelMFImpl.VertexExtension getVertexExtension(V v)
-
-