- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
FlowAlgorithm<V,
,E> MaximumFlowAlgorithm<V,
,E> MinimumSTCutAlgorithm<V,
E>
Mathematically, the maximum flow problem is stated as follows: \[ \begin{align} \max~& \sum_{e\in \delta^+(s)}f_e &\\ \mbox{s.t. }&\sum_{e\in \delta^-(i)} f_e=\sum_{e\in \delta^+(i)} f_e & \forall i\in V\setminus\{s,t\}\\ &0\leq f_e \leq u_e & \forall e\in E \end{align} \] Here $\delta^+(i)$ resp $\delta^-(i)$ denote resp the outgoing and incoming edges of vertex $i$.
When the input graph is undirected, an edge $(i,j)$ is treated as two directed arcs: $(i,j)$ and $(j,i)$. In such a case, there is the additional restriction that the flow can only go in one direction: the flow either goes form $i$ to $j$, or from $j$ to $i$, but there cannot be a positive flow on $(i,j)$ and $(j,i)$ simultaneously.
The runtime complexity of this class is $O(nm^2)$, where $n$ is the number of vertices and $m$
the number of edges in the graph. For a more efficient algorithm, consider using
PushRelabelMFImpl
instead.
This class can also compute 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 ClassesNested 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 EdmondsKarpMFImpl<V,
E>.VertexExtension private EdmondsKarpMFImpl<V,
E>.VertexExtension private final ExtensionFactory
<MaximumFlowAlgorithmBase<V, E>.AnnotatedFlowEdge> private final ExtensionFactory
<EdmondsKarpMFImpl<V, E>.VertexExtension> Fields inherited from class org.jgrapht.alg.flow.MaximumFlowAlgorithmBase
comparator, cutEdges, DEFAULT_EPSILON, directedGraph, edgeExtensionManager, maxFlow, maxFlowValue, network, sink, sinkPartition, source, sourcePartition, vertexExtensionManager
-
Constructor Summary
ConstructorsConstructorDescriptionEdmondsKarpMFImpl
(Graph<V, E> network) ConstructsMaximumFlow
instance to work with a copy ofnetwork
.EdmondsKarpMFImpl
(Graph<V, E> network, double epsilon) ConstructsMaximumFlow
instance to work with a copy ofnetwork
. -
Method Summary
Modifier and TypeMethodDescriptionprivate double
For all paths which end in the sink.private boolean
augmentFlowAlongInternal
(double deltaFlow, EdmondsKarpMFImpl<V, E>.VertexExtension node, Set<EdmondsKarpMFImpl<V, E>.VertexExtension> seen) private void
Method which finds a path from source to sink the in the residual graph.double
calculateMaximumFlow
(V source, V sink) Sets current source tosource
, current sink tosink
, then calculates maximum flow fromsource
tosink
.getMaximumFlow
(V source, V sink) Sets current source tosource
, current sink tosink
, then calculates maximum flow fromsource
tosink
.private EdmondsKarpMFImpl<V,
E>.VertexExtension 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.FlowAlgorithm
getFlow
Methods inherited from interface org.jgrapht.alg.interfaces.MaximumFlowAlgorithm
getMaximumFlowValue
-
Field Details
-
currentSource
-
currentSink
-
vertexExtensionsFactory
-
edgeExtensionsFactory
private final ExtensionFactory<MaximumFlowAlgorithmBase<V,E>.AnnotatedFlowEdge> edgeExtensionsFactory
-
-
Constructor Details
-
EdmondsKarpMFImpl
ConstructsMaximumFlow
instance to work with a copy ofnetwork
. Current source and sink are set tonull
. Ifnetwork
is weighted, then capacities are weights, otherwise all capacities are equal to one. Doubles are compared usingDEFAULT_EPSILON
tolerance.- Parameters:
network
- network, where maximum flow will be calculated
-
EdmondsKarpMFImpl
ConstructsMaximumFlow
instance to work with a copy ofnetwork
. Current source and sink are set tonull
. Ifnetwork
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 Details
-
getMaximumFlow
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:
- a 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. 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<V, E>.VertexExtension node, Set<EdmondsKarpMFImpl<V, E>.VertexExtension> seen) -
getVertexExtension
-