|
||||||||||
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 EdmondsKarpMaxFlow algorithm for solving the maximum flow problem. After the algorithm is executed, each edge is labeled with a MutableDouble value that indicates the flow along that edge.
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 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()
Retrieves the flow graph used to compute the max flow |
int |
getMaxFlow()
Returns the max flow value |
Set<E> |
getMinCutEdges()
Retrieve the min-cut edge set |
Set<V> |
getNodesInSinkPartition()
Retrieves the nodes lying on the side of the partition (partitioned using the min-cut) of the sink node |
Set<V> |
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. |
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, getStatus, 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 backEdgesMethod Detail |
---|
protected 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 Set<E> getMinCutEdges()
public DirectedGraph<V,E> getFlowGraph()
protected void initializeIterations()
IterativeProcess
initializeIterations
in class IterativeProcess
protected void finalizeIterations()
IterativeProcess
finalizeIterations
in class IterativeProcess
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |