Package org.jgrapht.alg
Class EdmondsKarpMaximumFlow<V,E>
- java.lang.Object
-
- org.jgrapht.alg.EdmondsKarpMaximumFlow<V,E>
-
public final class EdmondsKarpMaximumFlow<V,E> extends java.lang.Object
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
Fields Modifier and Type Field Description static double
DEFAULT_EPSILON
Default tolerance.
-
Constructor Summary
Constructors Constructor 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.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method 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.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.
-
-
-
Field Detail
-
DEFAULT_EPSILON
public static final double DEFAULT_EPSILON
Default tolerance.- See Also:
- Constant Field Values
-
-
Constructor Detail
-
EdmondsKarpMaximumFlow
public EdmondsKarpMaximumFlow(DirectedGraph<V,E> network)
Constructs MaximumFlow instance to work with a copy of network. Current source and sink are set to null. If network is weighted, then capacities are weights, otherwise all capacities are equal to one. Doubles are compared using DEFAULT_EPSILON tolerance.- Parameters:
network
- network, where maximum flow will be calculated
-
EdmondsKarpMaximumFlow
public EdmondsKarpMaximumFlow(DirectedGraph<V,E> network, double epsilon)
Constructs MaximumFlow instance to work with a copy of network. Current source and sink are set to null. If network is weighted, then capacities are weights, otherwise all capacities are equal to one.- Parameters:
network
- network, where maximum flow will be calculatedepsilon
- tolerance for comparing doubles
-
-
Method Detail
-
calculateMaximumFlow
public void calculateMaximumFlow(V source, V sink)
Sets current source to source, current sink to sink, then calculates maximum flow from source to sink. Note, that source and sink must be vertices of the network passed to the constructor, and they must be different.- Parameters:
source
- source vertexsink
- sink vertex
-
getMaximumFlowValue
public java.lang.Double getMaximumFlowValue()
Returns maximum flow value, that was calculated during last calculateMaximumFlow call, or null, if there was no calculateMaximumFlow calls.- Returns:
- maximum flow value
-
getMaximumFlow
public 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.- Returns:
- read-only mapping from edges to doubles - flow values
-
getCurrentSource
public V getCurrentSource()
Returns current source vertex, or null if there was no calculateMaximumFlow calls.- Returns:
- current source
-
getCurrentSink
public V getCurrentSink()
Returns current sink vertex, or null if there was no calculateMaximumFlow calls.- Returns:
- current sink
-
-