org.jgrapht.alg.flow

## Class EdmondsKarpMFImpl<V,E>

• Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
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 classes/interfaces inherited from interface org.jgrapht.alg.interfaces.MaximumFlowAlgorithm

MaximumFlowAlgorithm.MaximumFlow<E>, MaximumFlowAlgorithm.MaximumFlowImpl<E>

• ### 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 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.
• ### Method Summary

All Methods
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.
• ### 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
• ### Constructor Detail

• #### EdmondsKarpMFImpl

public EdmondsKarpMFImpl(Graph<V,E> network)
Constructs MaximumFlow instance to work with a copy of network. Current source and sink are set to null. If network is weighted, then capacities are weights, otherwise all capacities are equal to one. Doubles are compared using DEFAULT_EPSILON tolerance.
Parameters:
network - network, where maximum flow will be calculated
• #### EdmondsKarpMFImpl

public EdmondsKarpMFImpl(Graph<V,E> network,
double epsilon)
Constructs MaximumFlow instance to work with a copy of network. Current source and sink are set to null. If network is weighted, then capacities are weights, otherwise all capacities are equal to one.
Parameters:
network - network, where maximum flow will be calculated
epsilon - tolerance for comparing doubles
• ### Method Detail

• #### getMaximumFlow

public 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. Note, that source and sink must be vertices of the network passed to the constructor, and they must be different.
Parameters:
source - source vertex
sink - sink vertex
Returns:
a maximum flow
• #### calculateMaximumFlow

public double calculateMaximumFlow(V source,
V sink)
Sets current source to source, current sink to sink, then calculates maximum flow from source to sink. Note, that source and sink must be vertices of the network 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 vertex
sink - sink vertex
Returns:
the value of the maximum flow