edu.uci.ics.jung.algorithms.flows
Class EdmondsKarpMaxFlow

java.lang.Object
  edu.uci.ics.jung.algorithms.IterativeProcess
      edu.uci.ics.jung.algorithms.flows.EdmondsKarpMaxFlow

public class EdmondsKarpMaxFlow

extends IterativeProcess

Implements the EdmondsKarpMaxFlow algorithm for solving the maximum flow problem. After the algorithm is executed, each edge is labeled with a MustableDouble value that indicates the flow along that edge.

The algorithm operates on the assumption that the user has provided a UserDatum value 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
 

Author:

Scott White

See Also:

"Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein.", "Network Flows by Ahuja, Magnanti, and Orlin.", "Theoretical improvements in algorithmic efficiency for network flow problems by Edmonds and Karp, 1972."

Constructor Summary

EdmondsKarpMaxFlow(DirectedGraph directedGraph, Vertex source, Vertex sink, java.lang.String edgeCapacityKey, java.lang.String edgeFlowKey)
Constructs a new instance of the algorithm solver for a given graph, source, and sink.

Method Summary

DirectedGraph	getFlowGraph() Retrieves the flow graph used to compute the max flow
int	getMaxFlow() Returns the max flow value
java.util.Set	getMinCutEdges() Retrieve the min-cut edge set
java.util.Set	getNodesInSinkPartition() Retrieves the nodes lying on the side of the partition (partitioned using the min-cut) of the sink node
java.util.Set	getNodesInSourcePartition() Retrieves the nodes lying on the side of the partition (partitioned using the min-cut) of the source node

Methods inherited from class edu.uci.ics.jung.algorithms.IterativeProcess

evaluate, getDesiredPrecision, getIterations, getMaximumIterations, getPrecision, hasConverged, relativePrecision, setDesiredPrecision, setMaximumIterations

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

EdmondsKarpMaxFlow

public EdmondsKarpMaxFlow(DirectedGraph directedGraph,
                          Vertex source,
                          Vertex sink,
                          java.lang.String edgeCapacityKey,
                          java.lang.String edgeFlowKey)

Constructs a new instance of the algorithm solver for a given graph, source, and sink.

Parameters:

directedGraph - the flow graph

source - the source vertex

sink - the sink vertex

edgeCapacityKey - the UserDatum key that stores the capacity for each edge.

edgeFlowKey - the UserDatum key where the solver will place the value of the flow for each edge

Method Detail

getMaxFlow

public int getMaxFlow()

Returns the max flow value

Returns:

int the value of the maximum flow from the source to the sink

getNodesInSinkPartition

public java.util.Set getNodesInSinkPartition()

Retrieves the nodes lying on the side of the partition (partitioned using the min-cut) of the sink node

Returns:

the set of nodes in the sink partition class

getNodesInSourcePartition

public java.util.Set getNodesInSourcePartition()

Retrieves the nodes lying on the side of the partition (partitioned using the min-cut) of the source node

Returns:

the set of nodes in the source partition class

getMinCutEdges

public java.util.Set getMinCutEdges()

Retrieve the min-cut edge set

Returns:

set of edges in the min cut set

getFlowGraph

public DirectedGraph getFlowGraph()

Retrieves the flow graph used to compute the max flow

Returns:

a copy of the flow graph