|
||||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | |||||||||
java.lang.Objectedu.uci.ics.jung.algorithms.util.IterativeProcess
edu.uci.ics.jung.algorithms.flows.EdmondsKarpMaxFlow<V,E>
public class EdmondsKarpMaxFlow<V,E>
Implements the Edmonds-Karp maximum flow algorithm for solving the maximum flow problem.
After the algorithm is executed,
the input 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 Summary | |
|---|---|
EdmondsKarpMaxFlow(DirectedGraph<V,E> directedGraph,
V source,
V sink,
Constructs a new instance of the algorithm solver for a given graph, source, and sink. |
|
| Method Summary | |
|---|---|
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. |
| Methods inherited from class edu.uci.ics.jung.algorithms.util.IterativeProcess |
|---|
done, evaluate, getDesiredPrecision, getIterations, getMaximumIterations, getPrecision, hasConverged, relativePrecision, reset, setDesiredPrecision, setMaximumIterations, setPrecision |
| Methods inherited from class java.lang.Object |
|---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
| Constructor Detail |
|---|
public EdmondsKarpMaxFlow(DirectedGraph<V,E> directedGraph,
V source,
V sink,
edgeCapacityTransformer,
Map<E,Number> edgeFlowMap,
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 backEdges| Method Detail |
|---|
protected boolean hasAugmentingPath()
public void step()
IterativeProcess
step in interface IterativeContextstep in class IterativeProcesspublic int getMaxFlow()
public Set<V> getNodesInSinkPartition()
public Set<V> getNodesInSourcePartition()
public Set<E> getMinCutEdges()
public DirectedGraph<V,E> getFlowGraph()
protected void initializeIterations()
IterativeProcess
initializeIterations in class IterativeProcessprotected void finalizeIterations()
IterativeProcess
finalizeIterations in class IterativeProcess
|
||||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | |||||||||