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:
FlowAlgorithm<V,E>
,MaximumFlowAlgorithm<V,E>
,MinimumSTCutAlgorithm<V,E>
public final class EdmondsKarpMFImpl<V,E> extends MaximumFlowAlgorithmBase<V,E>
This class computes a maximum flow in a flow network using Edmonds-Karp algorithm. Given is a weighted directed or undirected graph $G(V,E)$ with vertex set $V$ and edge set $E$. Each edge $e\in E$ has an associated non-negative capacity $u_e$. The maximum flow problem involves finding a feasible flow from a source vertex $s$ to a sink vertex $t$ which is maximum. The amount of flow $f_e$ through any edge $e$ cannot exceed capacity $u_e$. Moreover, flow conservation must hold: the sum of flows entering a node must equal the sum of flows exiting that node, except for the source and the sink nodes.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!).
- Author:
- Ilya Razensteyn
-
-
Nested Class Summary
-
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 inherited from class org.jgrapht.alg.flow.MaximumFlowAlgorithmBase
comparator, cutEdges, DEFAULT_EPSILON, directedGraph, edgeExtensionManager, maxFlow, maxFlowValue, network, sink, sinkPartition, source, sourcePartition, vertexExtensionManager
-
-
Constructor Summary
Constructors Constructor Description EdmondsKarpMFImpl(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
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
.-
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
-
-
-
-
Constructor Detail
-
EdmondsKarpMFImpl
public EdmondsKarpMFImpl(Graph<V,E> network)
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
public EdmondsKarpMFImpl(Graph<V,E> network, double epsilon)
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 Detail
-
getMaximumFlow
public MaximumFlowAlgorithm.MaximumFlow<E> getMaximumFlow(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:
- a 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. 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
-
-