Package org.jgrapht.alg.flow
Class EdmondsKarpMFImpl<V,E>
- java.lang.Object
-
- org.jgrapht.alg.flow.MaximumFlowAlgorithmBase<V,E>
-
- org.jgrapht.alg.flow.EdmondsKarpMFImpl<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
MaximumFlowAlgorithm<V,E>
,MinimumSTCutAlgorithm<V,E>
public final class EdmondsKarpMFImpl<V,E> extends MaximumFlowAlgorithmBase<V,E>
A flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge can not exceed the capacity of the edge (note, that all capacities must be non-negative). A flow must satisfy the restriction that the amount of flow into a vertex equals the amount of flow out of it, except when it is a source, which "produces" flow, or sink, which "consumes" flow.This class computes maximum flow in a network using Edmonds-Karp algorithm. Be careful: for large networks this algorithm may consume significant amount of time (its upper-bound complexity is O(VE^2), where V - amount of vertices, E - amount of edges in the network).
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.
For more details see Andrew V. Goldberg's Combinatorial Optimization (Lecture Notes). 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 (package private) class
EdmondsKarpMFImpl.VertexExtension
-
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 EdmondsKarpMFImpl.VertexExtension
currentSink
private EdmondsKarpMFImpl.VertexExtension
currentSource
private ExtensionFactory<MaximumFlowAlgorithmBase.AnnotatedFlowEdge>
edgeExtensionsFactory
private ExtensionFactory<EdmondsKarpMFImpl.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 EdmondsKarpMFImpl(Graph<V,E> network)
Constructs MaximumFlow instance to work with a copy of network.EdmondsKarpMFImpl(Graph<V,E> network, double epsilon)
Constructs MaximumFlow instance to work with a copy of network.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private double
augmentFlow()
For all paths which end in the sink.private boolean
augmentFlowAlongInternal(double deltaFlow, EdmondsKarpMFImpl.VertexExtension node, java.util.Set<EdmondsKarpMFImpl.VertexExtension> seen)
private void
breadthFirstSearch()
Method which finds a path from source to sink the in the residual graph.double
calculateMaximumFlow(V source, V sink)
Sets current source to source, current sink to sink, then calculates maximum flow from source to sink.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 EdmondsKarpMFImpl.VertexExtension
getVertexExtension(V v)
-
Methods inherited from class org.jgrapht.alg.flow.MaximumFlowAlgorithmBase
calculateMinCut, calculateSourcePartition, composeFlow, getCurrentSink, getCurrentSource, getCutCapacity, getCutEdges, getFlowDirection, getFlowMap, getMaximumFlowValue, getSinkPartition, getSourcePartition, init, pushFlowThrough
-
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
-
currentSource
private EdmondsKarpMFImpl.VertexExtension currentSource
-
currentSink
private EdmondsKarpMFImpl.VertexExtension currentSink
-
vertexExtensionsFactory
private final ExtensionFactory<EdmondsKarpMFImpl.VertexExtension> vertexExtensionsFactory
-
edgeExtensionsFactory
private final ExtensionFactory<MaximumFlowAlgorithmBase.AnnotatedFlowEdge> edgeExtensionsFactory
-
-
Constructor Detail
-
EdmondsKarpMFImpl
public EdmondsKarpMFImpl(Graph<V,E> network)
Constructs MaximumFlow instance to work with a copy of network. Current source and sink are set to null. If network is weighted, then capacities are weights, otherwise all capacities are equal to one. Doubles are compared using DEFAULT_EPSILON tolerance.- Parameters:
network
- network, where maximum flow will be calculated
-
EdmondsKarpMFImpl
public EdmondsKarpMFImpl(Graph<V,E> network, double epsilon)
Constructs MaximumFlow instance to work with a copy of network. Current source and sink are set to null. If network is weighted, then capacities are weights, otherwise all capacities are equal to one.- Parameters:
network
- network, where maximum flow will be calculatedepsilon
- tolerance for comparing doubles
-
-
Method Detail
-
getMaximumFlow
public 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. 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:
- a 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. If desired, a flow map can be queried afterwards; this will not require a new invocation of the algorithm.- Parameters:
source
- source vertexsink
- sink vertex- Returns:
- the value of the maximum flow
-
breadthFirstSearch
private void breadthFirstSearch()
Method which finds a path from source to sink the in the residual graph. Note that this method tries to find multiple paths at once. Once a single path has been discovered, no new nodes are added to the queue, but nodes which are already in the queue are fully explored. As such there's a chance that multiple paths are discovered.
-
augmentFlow
private double augmentFlow()
For all paths which end in the sink. trace them back to the source and push flow through them.- Returns:
- total increase in flow from source to sink
-
augmentFlowAlongInternal
private boolean augmentFlowAlongInternal(double deltaFlow, EdmondsKarpMFImpl.VertexExtension node, java.util.Set<EdmondsKarpMFImpl.VertexExtension> seen)
-
getVertexExtension
private EdmondsKarpMFImpl.VertexExtension getVertexExtension(V v)
-
-