

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object org.jgrapht.alg.EdmondsKarpMaximumFlow<V,E>
public final class EdmondsKarpMaximumFlow<V,E>
A flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge can not exceed the capacity of the edge (note, that all capacities must be nonnegative). A flow must satisfy the restriction that the amount of flow into a vertex equals the amount of flow out of it, except when it is a source, which "produces" flow, or sink, which "consumes" flow.
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).
Field Summary  

static double 
DEFAULT_EPSILON
Default tolerance. 
Constructor Summary  

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

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. 
Methods inherited from class java.lang.Object 

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait 
Field Detail 

public static final double DEFAULT_EPSILON
Constructor Detail 

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 doublesMethod Detail 

public void calculateMaximumFlow(V source, V sink)
source
 source vertexsink
 sink vertexpublic Double getMaximumFlowValue()
public Map<E,Double> getMaximumFlow()
public V getCurrentSource()
public V getCurrentSink()


PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 