|
|||||||||
| 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 calculated
public EdmondsKarpMaximumFlow(DirectedGraph<V,E> network,
double epsilon)
network - network, where maximum flow will be calculatedepsilon - tolerance for comparing doubles| Method 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 | ||||||||