|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectorg.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 non-negative). 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 Edmonds-Karp algorithm. Be careful: for large networks this algorithm may consume significant amount of time (its upper-bound 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. |
java.util.Map<E,java.lang.Double> |
getMaximumFlow()
Returns maximum flow, that was calculated during last calculateMaximumFlow call, or null, if there was no calculateMaximumFlow calls. |
java.lang.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 java.lang.Double getMaximumFlowValue()
public java.util.Map<E,java.lang.Double> getMaximumFlow()
public V getCurrentSource()
public V getCurrentSink()
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |