

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object edu.uci.ics.jung.algorithms.util.IterativeProcess edu.uci.ics.jung.algorithms.flows.EdmondsKarpMaxFlow<V,E>
public class EdmondsKarpMaxFlow<V,E>
Implements the EdmondsKarp 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,
org.apache.commons.collections15.Transformer<E,Number> edgeCapacityTransformer,
Map<E,Number> edgeFlowMap,
org.apache.commons.collections15.Factory<E> edgeFactory)
Constructs a new instance of the algorithm solver for a given graph, source, and sink. 
Method Summary  

protected void 
finalizeIterations()
Perform eventual cleanup 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 mincut edges) as the sink node. 
Set<V> 
getNodesInSourcePartition()
Returns the nodes which share the same partition (as defined by the mincut 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, org.apache.commons.collections15.Transformer<E,Number> edgeCapacityTransformer, Map<E,Number> edgeFlowMap, org.apache.commons.collections15.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 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 