Algorithm
Development Kit 1.0

algs.model.network
Class FlowNetworkArray

java.lang.Object
  extended by algs.model.network.FlowNetwork<EdgeInfo[][]>
      extended by algs.model.network.FlowNetworkArray
Direct Known Subclasses:
BipartiteMatchingMinCost, Transshipment

public class FlowNetworkArray
extends FlowNetwork<EdgeInfo[][]>

Store information regarding the graph in a two-dimensional matrix. The matrix may be either sparse or dense, depending upon the problem at hand.

Author:
George Heineman

Field Summary
 
Fields inherited from class algs.model.network.FlowNetwork
numVertices, sinkIndex, sourceIndex
 
Constructor Summary
protected FlowNetworkArray(int sourceIndex, int sinkIndex, int numVertices)
          Minimal constructor for use by subclasses.
  FlowNetworkArray(int numVertices, int srcIndex, int sinkIndex, 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)
          Subclasses provide this implementation, based upon their data structures.
 int getCost()
          Return the cost of the network solution.
 EdgeInfo[][] 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'.
protected  void populate(java.util.Iterator<EdgeInfo> edges)
          Helper method to populate edges.
 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

FlowNetworkArray

public FlowNetworkArray(int numVertices,
                        int srcIndex,
                        int sinkIndex,
                        java.util.Iterator<EdgeInfo> edges)
Construct an instance of the FlowNetwork problem using a two-dimensional array to store the edge information. For sanity sake, clear out any existing flow

Parameters:
numVertices - the number of vertices in the Flow Network
srcIndex - the index of the vertex designated to be the source
sinkIndex - 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)

FlowNetworkArray

protected FlowNetworkArray(int sourceIndex,
                           int sinkIndex,
                           int numVertices)
Minimal constructor for use by subclasses.

Parameters:
sourceIndex - the sourceIndex to use for network (typically 0)
sinkIndex - the sinkIndex to use for network
numVertices - the number of vertices
Method Detail

populate

protected void populate(java.util.Iterator<EdgeInfo> edges)
Helper method to populate edges. Useful for subclasses as well. Note that this allocates the matrix storage so it effectively replaces the entire edge structure found in the graph. Be careful when using this!

Parameters:
edges - Iterator of all edges in the network.

getEdgeStructure

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

Specified by:
getEdgeStructure in class FlowNetwork<EdgeInfo[][]>

edge

public EdgeInfo edge(int start,
                     int end)
Description copied from class: FlowNetwork
Subclasses provide this implementation, based upon their data structures.

If the forward edge doesn't exist, then null is returned.

Specified by:
edge in class FlowNetwork<EdgeInfo[][]>
Parameters:
start - the start index of desired edge.
end - the end index of desired edge.

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<EdgeInfo[][]>

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<EdgeInfo[][]>

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<EdgeInfo[][]>

validate

public void validate()
              throws java.lang.IllegalStateException
Description copied from class: FlowNetwork
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<EdgeInfo[][]>
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.