 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 EdmondsKarp 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 nonnegative 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 st cuts. Effectively, to compute a minimum st cut, the implementation first computes a minimum st 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

