V
 the graph vertex typeE
 the graph edge typepublic final class EdmondsKarpMFImpl<V,E> extends MaximumFlowAlgorithmBase<V,E>
This class computes maximum flow in a network using EdmondsKarp algorithm. Be careful: for large networks this algorithm may consume significant amount of time (its upperbound complexity is O(VE^2), where V  amount of vertices, E  amount of edges in the network).
This class can also computes 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>
comparator, cutEdges, DEFAULT_EPSILON, directed_graph, 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
buildMaximumFlow
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 © 2017. All rights reserved.