public final class EdmondsKarpMaximumFlow<V,E> extends Object
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).
For more details see Andrew V. Goldberg's Combinatorial Optimization (Lecture Notes).
Modifier and Type  Field and Description 

static double 
DEFAULT_EPSILON
Default tolerance.

Constructor and Description 

EdmondsKarpMaximumFlow(DirectedGraph<V,E> network)
Constructs MaximumFlow instance to work with a copy of
network.

EdmondsKarpMaximumFlow(DirectedGraph<V,E> network,
double epsilon)
Constructs MaximumFlow instance to work with a copy of
network.

Modifier and Type  Method and Description 

void 
calculateMaximumFlow(V source,
V sink)
Sets current source to source, current sink to sink,
then calculates maximum flow from source to sink.

V 
getCurrentSink()
Returns current sink vertex, or null if there was no
calculateMaximumFlow calls.

V 
getCurrentSource()
Returns current source vertex, or null if there was no
calculateMaximumFlow calls.

Map<E,Double> 
getMaximumFlow()
Returns maximum flow, that was calculated during last
calculateMaximumFlow call, or null, if there was no
calculateMaximumFlow calls.

Double 
getMaximumFlowValue()
Returns maximum flow value, that was calculated during last
calculateMaximumFlow call, or null, if there was no
calculateMaximumFlow calls.

public static final double DEFAULT_EPSILON
public EdmondsKarpMaximumFlow(DirectedGraph<V,E> network)
network
 network, where maximum flow will be calculatedpublic EdmondsKarpMaximumFlow(DirectedGraph<V,E> network, double epsilon)
network
 network, where maximum flow will be calculatedepsilon
 tolerance for comparing doublespublic void calculateMaximumFlow(V source, V sink)
source
 source vertexsink
 sink vertexpublic Double getMaximumFlowValue()
public Map<E,Double> getMaximumFlow()
public V getCurrentSource()
public V getCurrentSink()
Copyright © 2015. All rights reserved.