Algorithm
Development Kit 1.0

algs.model.network
Class FlowNetworkAdjacencyList

java.lang.Object
  extended by algs.model.network.FlowNetwork<VertexStructure[]>
      extended by algs.model.network.FlowNetworkAdjacencyList

public class FlowNetworkAdjacencyList
extends FlowNetwork<VertexStructure[]>

Store information regarding the graph as an adjacency list.

Several key steps in this algorithm depend on identifying both the forward edges leaving a vertex Vi as well as the incoming edges into a vertex. If we only stored the forward directed edges, we would have to scan all remaining vertices to locate any that have outgoing edges into Vi.

For this reason, we maintain two separate forward and backward edge lists. This means we have twice as many edges as are needed. The structure used to maintain both lists is VertexStructure.

Author:
George Heineman

Field Summary
 
Fields inherited from class algs.model.network.FlowNetwork
numVertices, sinkIndex, sourceIndex
 
Constructor Summary
FlowNetworkAdjacencyList(int numVertices, int srcIndex, int tgtIndex, java.util.Iterator<EdgeInfo> edges)
          Construct an instance of the FlowNetwork problem using a two-dimensional array to store the edge information.
 
Method Summary
 EdgeInfo edge(int start, int end)
          Given an adjacency list for vertex 'n', find the edge (if it exists) from start to end.
 int getCost()
          Return the cost of the network solution.
 VertexStructure[] getEdgeStructure()
          Subclasses are responsible for interpreting the info in the appropriate data structure.
 int getFlow()
          After the termination of the network flow algorithm, this method returns the final flow pushed out of the source.
 DoubleLinkedList<EdgeInfo> getMinCut()
          After the termination of the network flow algorithms, the last round of labeled vertices (including the source) can be grouped into a set X while the unlabeled vertices are grouped into X'.
 java.lang.String toString()
          Useful for debugging.
 void validate()
          Validate the FlowNetwork.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

FlowNetworkAdjacencyList

public FlowNetworkAdjacencyList(int numVertices,
                                int srcIndex,
                                int tgtIndex,
                                java.util.Iterator<EdgeInfo> edges)
Construct an instance of the FlowNetwork problem using a two-dimensional array to store the edge information.

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

getEdgeStructure

public VertexStructure[] getEdgeStructure()
Description copied from class: FlowNetwork
Subclasses are responsible for interpreting the info in the appropriate data structure.

Specified by:
getEdgeStructure in class FlowNetwork<VertexStructure[]>
See Also:
FlowNetwork.getEdgeStructure()

edge

public EdgeInfo edge(int start,
                     int end)
Given an adjacency list for vertex 'n', find the edge (if it exists) from start to end.

Specified by:
edge in class FlowNetwork<VertexStructure[]>
Parameters:
start - index of start vertex
end - index of end vertex.
Returns:
edge if it exists as a directed edge; null otherwise.

getMinCut

public DoubleLinkedList<EdgeInfo> getMinCut()
Description copied from class: FlowNetwork
After the termination of the network flow algorithms, the last round of labeled vertices (including the source) can be grouped into a set X while the unlabeled vertices are grouped into X'. The division between these two sets is known as the min-cut. Given sets X and X', group the edges between them as follows:
  1. Forward Edges: These are edges from X to X' whose flow is equal to the edges' capacity.
  2. Backward Edges: These are edges from X' to X whose flow is zero.
As a corollary, the sum total of the flow along the forward edges is, in fact, equal to the maximum flow through the network. This is no coincidence, and is known as the Max-flow, Min-cut theorem.

Specified by:
getMinCut in class FlowNetwork<VertexStructure[]>

getFlow

public int getFlow()
Description copied from class: FlowNetwork
After the termination of the network flow algorithm, this method returns the final flow pushed out of the source.

Specified by:
getFlow in class FlowNetwork<VertexStructure[]>

getCost

public int getCost()
Description copied from class: FlowNetwork
Return the cost of the network solution.

Subclasses are free to override with more efficient implementations, so long as they are correct :)

Specified by:
getCost in class FlowNetwork<VertexStructure[]>

validate

public void validate()
              throws java.lang.IllegalStateException
Validate the FlowNetwork.

A valid flow network satisfies three criteria:

  1. Capacity Constraint -- for all edges e=(u,v) it must be that f(u,v) <= c(u,v)
  2. Skew Symmetry -- for all (u,v) it must be that f(u,v) = -f(v,u)
  3. Flow Conservation -- for all nodes in the Flow Network (other than source and sink) it must be that the sum of f(u,v) to all other vertices v must be zero.

Specified by:
validate in class FlowNetwork<VertexStructure[]>
Throws:
java.lang.IllegalStateException - if any of these criteria is violated.

toString

public java.lang.String toString()
Useful for debugging.

Overrides:
toString in class java.lang.Object

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.