V
 the graph vertex typeE
 the graph edge typepublic final class EdmondsKarpMFImpl<V,E> extends MaximumFlowAlgorithmBase<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 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!).
MaximumFlowAlgorithm.MaximumFlow<E>, MaximumFlowAlgorithm.MaximumFlowImpl<E>
FlowAlgorithm.Flow<E>, FlowAlgorithm.FlowImpl<E>
comparator, cutEdges, DEFAULT_EPSILON, directedGraph, edgeExtensionManager, maxFlow, maxFlowValue, network, sink, sinkPartition, source, sourcePartition, vertexExtensionManager
Constructor and 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.

Modifier and Type  Method and Description 

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.

calculateMinCut, calculateSourcePartition, composeFlow, getCurrentSink, getCurrentSource, getCutCapacity, getCutEdges, getFlowDirection, getFlowMap, getMaximumFlowValue, getSinkPartition, getSourcePartition, init, pushFlowThrough
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
getMaximumFlowValue
getFlow
public EdmondsKarpMFImpl(Graph<V,E> network)
network
 network, where maximum flow will be calculatedpublic EdmondsKarpMFImpl(Graph<V,E> network, double epsilon)
network
 network, where maximum flow will be calculatedepsilon
 tolerance for comparing doublespublic MaximumFlowAlgorithm.MaximumFlow<E> getMaximumFlow(V source, V sink)
source
 source vertexsink
 sink vertexpublic double calculateMaximumFlow(V source, V sink)
source
 source vertexsink
 sink vertexCopyright © 2019. All rights reserved.