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,
com.google.common.base.Function<E,Number> edgeCapacityTransformer,
Map<E,Number> edgeFlowMap,
com.google.common.base.Supplier<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() |
int |
getMaxFlow() |
Set<E> |
getMinCutEdges() |
Set<V> |
getNodesInSinkPartition() |
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.
|
done, evaluate, getDesiredPrecision, getIterations, getMaximumIterations, getPrecision, hasConverged, relativePrecision, reset, setDesiredPrecision, setMaximumIterations, setPrecision
public EdmondsKarpMaxFlow(DirectedGraph<V,E> directedGraph, V source, V sink, com.google.common.base.Function<E,Number> edgeCapacityTransformer, Map<E,Number> edgeFlowMap, com.google.common.base.Supplier<E> edgeFactory)
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 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 © 2015. All rights reserved.