Algorithm
Development Kit 1.0

algs.model.network
Class OptimizedFlowNetwork

java.lang.Object
  extended by algs.model.network.OptimizedFlowNetwork

public class OptimizedFlowNetwork
extends java.lang.Object

Store information regarding the graph in a two-dimensional matrix. FordFulkerson implementation.

Author:
George Heineman

Field Summary
static boolean BACKWARD
          Declares a path in the augmenting path follows a backward edge.
static boolean FORWARD
          Declares a path in the augmenting path follows a forward edge.
 
Constructor Summary
OptimizedFlowNetwork(int numVertices, int srcIndex, int sinkIndex, java.util.Iterator<EdgeInfo> edges)
          Construct an instance of the FlowNetwork problem using optimized array structure to solve problem.
 
Method Summary
 int compute(int source, int sink)
          Compute the Maximal flow for the given flow network.
 boolean findAugmentingPath(int source, int sink)
          Locate an augmenting path in the Flow Network from the source vertex to the sink.
 DoubleLinkedList<EdgeInfo> getMinCut()
           
 int getSink()
           
 int getSource()
           
protected  int processPath(int source, int sink)
          Augments the flows within the network along the path found from source to sink.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

FORWARD

public static final boolean FORWARD
Declares a path in the augmenting path follows a forward edge.

See Also:
Constant Field Values

BACKWARD

public static final boolean BACKWARD
Declares a path in the augmenting path follows a backward edge.

See Also:
Constant Field Values
Constructor Detail

OptimizedFlowNetwork

public OptimizedFlowNetwork(int numVertices,
                            int srcIndex,
                            int sinkIndex,
                            java.util.Iterator<EdgeInfo> edges)
Construct an instance of the FlowNetwork problem using optimized array structure to solve problem.

We use the same input representation so we can properly compare the performance of this implementation.

Parameters:
numVertices - the number of vertices in the Flow Network
srcIndex - the index of the source vertex
sinkIndex - the index of the sink vertex
edges - an iterator of EdgeInfo objects representing edge capacities
See Also:
FlowNetwork.FlowNetwork(int, int, int)
Method Detail

compute

public int compute(int source,
                   int sink)
Compute the Maximal flow for the given flow network.

The results of the computation are stored within the network object. Specifically, the final labeling of vertices computes the set S of nodes which is disjoint from the unlabeled vertices which form the set T. Together, S and T represent the disjoint split of the graph into two sets whose connecting edges for the min-cut, in other words, the forward edges from S to T all have flow values which equal their capacity. Thus no additional augmentations are possible.

Parameters:
source - the index of the source vertex
sink - the index of the sink vertex
Throws:
java.lang.Exception - if the graph structure is not a flow network.

processPath

protected int processPath(int source,
                          int sink)
Augments the flows within the network along the path found from source to sink.

Walking backwards from the sink vertex to the source vertex, this updates the flow values for the edges in the augmenting path.

Note that the available units in the sinkIndex are used as the additive value (for forward edges) and the subtractive value (for backward edges).

Parameters:
source - source index of the augmenting path
sink - sink index of the augmenting path

getMinCut

public DoubleLinkedList<EdgeInfo> getMinCut()

findAugmentingPath

public boolean findAugmentingPath(int source,
                                  int sink)
Locate an augmenting path in the Flow Network from the source vertex to the sink.

Path is stored within the vertices[] array by traversing in reverse order from the sinkIndex.

Assume path always fits within queue size of length QUEUE_SIZE

Parameters:
source - index of source vertex
sink - index of sink vertex
Returns:
true if an augmented path was located; false otherwise.

getSink

public int getSink()

getSource

public int getSource()

Algorithm Development Kit 1.0

This code supports the Algorithms in a Nutshell book, published by O'Reilly Media, Inc. in November 2008. Please visit the book web page to learn of any changes to the code repository or to record a potential defect.