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 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!).
MaximumFlowAlgorithm.MaximumFlow<E>, MaximumFlowAlgorithm.MaximumFlowImpl<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, pushFlowThroughpublic 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 © 2017. All rights reserved.