public class EdmondsKarpMaxFlow<V,E> extends IterativeProcess
Map
is populated with a Number
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
Constructor and Description |
---|
EdmondsKarpMaxFlow(DirectedGraph<V,E> directedGraph,
V source,
V sink,
org.apache.commons.collections4.Transformer<E,Number> edgeCapacityTransformer,
Map<E,Number> edgeFlowMap,
org.apache.commons.collections4.Factory<E> edgeFactory)
Constructs a new instance of the algorithm solver for a given graph, source, and sink.
|
Modifier and Type | Method and Description |
---|---|
protected void |
finalizeIterations()
Perform eventual clean-up operations
(must be implement by subclass when needed).
|
DirectedGraph<V,E> |
getFlowGraph()
Returns the graph for which the maximum flow is calculated.
|
int |
getMaxFlow()
Returns the value of the maximum flow from the source to the sink.
|
Set<E> |
getMinCutEdges()
Returns the edges in the minimum cut.
|
Set<V> |
getNodesInSinkPartition()
Returns the nodes which share the same partition (as defined by the min-cut edges)
as the sink node.
|
Set<V> |
getNodesInSourcePartition()
Returns the nodes which share the same partition (as defined by the min-cut edges)
as the source node.
|
protected boolean |
hasAugmentingPath() |
protected void |
initializeIterations()
Initializes internal parameters to start the iterative process.
|
void |
step()
Evaluate the result of the current iteration.
|
done, evaluate, getDesiredPrecision, getIterations, getMaximumIterations, getPrecision, hasConverged, relativePrecision, reset, setDesiredPrecision, setMaximumIterations, setPrecision
public EdmondsKarpMaxFlow(DirectedGraph<V,E> directedGraph, V source, V sink, org.apache.commons.collections4.Transformer<E,Number> edgeCapacityTransformer, Map<E,Number> edgeFlowMap, org.apache.commons.collections4.Factory<E> edgeFactory)
directedGraph
- the flow graphsource
- the source vertexsink
- the sink vertexedgeCapacityTransformer
- the transformer 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 backEdgesprotected boolean hasAugmentingPath()
public void step()
IterativeProcess
step
in interface IterativeContext
step
in class IterativeProcess
public int getMaxFlow()
public Set<V> getNodesInSinkPartition()
public Set<V> getNodesInSourcePartition()
public DirectedGraph<V,E> getFlowGraph()
protected void initializeIterations()
IterativeProcess
initializeIterations
in class IterativeProcess
protected void finalizeIterations()
IterativeProcess
finalizeIterations
in class IterativeProcess
Copyright © 2014. All rights reserved.