public class EdmondsKarpMaxFlow extends IterativeProcess
The algorithm operates on the assumption that the user has provided a UserDatum value (with copy action either SHARED or CLONE, but not REMOVE) of type Number along each edge indicating the capacity available.
An example of using this algorithm is as follows:
EdmondsKarpMaxFlow ek = new EdmondsKarpMaxFlow(graph,sourceVertex,"CAPACITY","FLOW"); ek.evaluate(); // This actually instructs the solver to compute the max flow
Constructor and Description |
---|
EdmondsKarpMaxFlow(DirectedGraph directedGraph,
Vertex source,
Vertex sink,
java.lang.String edgeCapacityKey,
java.lang.String edgeFlowKey)
Constructs a new instance of the algorithm solver for a given graph, source, and sink.
|
Modifier and Type | Method and Description |
---|---|
protected double |
evaluateIteration()
Evaluate the result of the current interation.
|
protected void |
finalizeIterations()
Perform eventual clean-up operations
(must be implement by subclass when needed).
|
DirectedGraph |
getFlowGraph()
Retrieves the flow graph used to compute the max flow
|
int |
getMaxFlow()
Returns the max flow value
|
java.util.Set |
getMinCutEdges()
Retrieve the min-cut edge set
|
java.util.Set |
getNodesInSinkPartition()
Retrieves the nodes lying on the side of the partition (partitioned using the
min-cut) of the sink node
|
java.util.Set |
getNodesInSourcePartition()
Retrieves the nodes lying on the side of the partition (partitioned using the
min-cut) of the source node
|
protected boolean |
hasAugmentingPath() |
protected void |
initializeIterations()
Initializes internal parameters to start the iterative process.
|
evaluate, getDesiredPrecision, getIterations, getMaximumIterations, getPrecision, hasConverged, reinitialize, relativePrecision, setDesiredPrecision, setMaximumIterations
public EdmondsKarpMaxFlow(DirectedGraph directedGraph, Vertex source, Vertex sink, java.lang.String edgeCapacityKey, java.lang.String edgeFlowKey)
directedGraph
- the flow graphsource
- the source vertexsink
- the sink vertexedgeCapacityKey
- the UserDatum key that stores the capacity for each edge.edgeFlowKey
- the UserDatum key where the solver will place the value of the flow for each edgeprotected boolean hasAugmentingPath()
protected double evaluateIteration()
IterativeProcess
evaluateIteration
in class IterativeProcess
public int getMaxFlow()
public java.util.Set getNodesInSinkPartition()
public java.util.Set getNodesInSourcePartition()
public java.util.Set getMinCutEdges()
public DirectedGraph getFlowGraph()
protected void initializeIterations()
IterativeProcess
initializeIterations
in class IterativeProcess
protected void finalizeIterations()
IterativeProcess
finalizeIterations
in class IterativeProcess