Class EdmondsKarpMaxFlow<V,E>
- java.lang.Object
-
- edu.uci.ics.jung.algorithms.util.IterativeProcess
-
- edu.uci.ics.jung.algorithms.flows.EdmondsKarpMaxFlow<V,E>
-
- All Implemented Interfaces:
IterativeContext
public class EdmondsKarpMaxFlow<V,E> extends IterativeProcess
Implements the Edmonds-Karp maximum flow algorithm for solving the maximum flow problem. After the algorithm is executed, the inputMap
is populated with aNumber
for each edge that indicates the flow along that edge.An example of using this algorithm is as follows:
EdmondsKarpMaxFlow ek = new EdmondsKarpMaxFlow(graph, source, sink, edge_capacities, edge_flows, edge_factory); ek.evaluate(); // This instructs the class to compute the max flow
- See Also:
- "Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein.", "Network Flows by Ahuja, Magnanti, and Orlin.", "Theoretical improvements in algorithmic efficiency for network flow problems by Edmonds and Karp, 1972."
-
-
Field Summary
Fields Modifier and Type Field Description private com.google.common.base.Function<E,java.lang.Number>
edgeCapacityTransformer
private com.google.common.base.Supplier<E>
edgeFactory
private java.util.Map<E,java.lang.Number>
edgeFlowMap
private DirectedGraph<V,E>
mFlowGraph
private int
mMaxFlow
private java.util.Set<E>
mMinCutEdges
private DirectedGraph<V,E>
mOriginalGraph
private java.util.Set<V>
mSinkPartitionNodes
private java.util.Set<V>
mSourcePartitionNodes
private java.util.Map<V,java.lang.Number>
parentCapacityMap
private java.util.Map<V,V>
parentMap
private java.util.Map<E,java.lang.Number>
residualCapacityMap
private V
source
private V
target
-
Constructor Summary
Constructors Constructor Description EdmondsKarpMaxFlow(DirectedGraph<V,E> directedGraph, V source, V sink, com.google.common.base.Function<E,java.lang.Number> edgeCapacityTransformer, java.util.Map<E,java.lang.Number> edgeFlowMap, com.google.common.base.Supplier<E> edgeFactory)
Constructs a new instance of the algorithm solver for a given graph, source, and sink.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
clearParentValues()
private void
computeMinCut()
protected void
finalizeIterations()
Perform eventual clean-up operations (must be implement by subclass when needed).DirectedGraph<V,E>
getFlowGraph()
int
getMaxFlow()
java.util.Set<E>
getMinCutEdges()
java.util.Set<V>
getNodesInSinkPartition()
java.util.Set<V>
getNodesInSourcePartition()
protected boolean
hasAugmentingPath()
protected void
initializeIterations()
Initializes internal parameters to start the iterative process.void
step()
Evaluate the result of the current iteration.private void
updateResidualCapacities()
-
Methods inherited from class edu.uci.ics.jung.algorithms.util.IterativeProcess
done, evaluate, getDesiredPrecision, getIterations, getMaximumIterations, getPrecision, hasConverged, relativePrecision, reset, setDesiredPrecision, setMaximumIterations, setPrecision
-
-
-
-
Field Detail
-
mFlowGraph
private DirectedGraph<V,E> mFlowGraph
-
mOriginalGraph
private DirectedGraph<V,E> mOriginalGraph
-
source
private V source
-
target
private V target
-
mMaxFlow
private int mMaxFlow
-
mSourcePartitionNodes
private java.util.Set<V> mSourcePartitionNodes
-
mSinkPartitionNodes
private java.util.Set<V> mSinkPartitionNodes
-
mMinCutEdges
private java.util.Set<E> mMinCutEdges
-
residualCapacityMap
private java.util.Map<E,java.lang.Number> residualCapacityMap
-
parentCapacityMap
private java.util.Map<V,java.lang.Number> parentCapacityMap
-
edgeCapacityTransformer
private com.google.common.base.Function<E,java.lang.Number> edgeCapacityTransformer
-
edgeFlowMap
private java.util.Map<E,java.lang.Number> edgeFlowMap
-
edgeFactory
private com.google.common.base.Supplier<E> edgeFactory
-
-
Constructor Detail
-
EdmondsKarpMaxFlow
public EdmondsKarpMaxFlow(DirectedGraph<V,E> directedGraph, V source, V sink, com.google.common.base.Function<E,java.lang.Number> edgeCapacityTransformer, java.util.Map<E,java.lang.Number> edgeFlowMap, com.google.common.base.Supplier<E> edgeFactory)
Constructs a new instance of the algorithm solver for a given graph, source, and sink. Source and sink vertices must be elements of the specified graph, and must be distinct.- Parameters:
directedGraph
- the flow graphsource
- the source vertexsink
- the sink vertexedgeCapacityTransformer
- the Function that gets the capacity for each edge.edgeFlowMap
- the map where the solver will place the value of the flow for each edgeedgeFactory
- used to create new edge instances for backEdges
-
-
Method Detail
-
clearParentValues
private void clearParentValues()
-
hasAugmentingPath
protected boolean hasAugmentingPath()
-
step
public void step()
Description copied from class:IterativeProcess
Evaluate the result of the current iteration.- Specified by:
step
in interfaceIterativeContext
- Specified by:
step
in classIterativeProcess
-
computeMinCut
private void computeMinCut()
-
getMaxFlow
public int getMaxFlow()
- Returns:
- the value of the maximum flow from the source to the sink.
-
getNodesInSinkPartition
public java.util.Set<V> getNodesInSinkPartition()
- Returns:
- the nodes which share the same partition (as defined by the min-cut edges) as the sink node.
-
getNodesInSourcePartition
public java.util.Set<V> getNodesInSourcePartition()
- Returns:
- the nodes which share the same partition (as defined by the min-cut edges) as the source node.
-
getMinCutEdges
public java.util.Set<E> getMinCutEdges()
- Returns:
- the edges in the minimum cut.
-
getFlowGraph
public DirectedGraph<V,E> getFlowGraph()
- Returns:
- the graph for which the maximum flow is calculated.
-
initializeIterations
protected void initializeIterations()
Description copied from class:IterativeProcess
Initializes internal parameters to start the iterative process.- Overrides:
initializeIterations
in classIterativeProcess
-
finalizeIterations
protected void finalizeIterations()
Description copied from class:IterativeProcess
Perform eventual clean-up operations (must be implement by subclass when needed).- Overrides:
finalizeIterations
in classIterativeProcess
-
updateResidualCapacities
private void updateResidualCapacities()
-
-