Algorithm
Development Kit 1.0

algs.model.network
Class FlowNetwork<E>

java.lang.Object
  extended by algs.model.network.FlowNetwork<E>
Type Parameters:
E - type parameter to describe Edge Structure used by each algorithm variation.
Direct Known Subclasses:
FlowNetworkAdjacencyList, FlowNetworkArray, Optimized

public abstract class FlowNetwork<E>
extends java.lang.Object

Parent abstract class for representing a flow network problem to be solved.

Subclasses included an array-based implementation and one using adjacency lists.

Since:
1.0
Version:
1.0, 6/15/08
Author:
George Heineman

Field Summary
 int numVertices
          Number of vertices in the graph.
 int sinkIndex
          Index of the sink vertex.
 int sourceIndex
          Index of the source vertex.
 
Constructor Summary
FlowNetwork(int numVertices, int srcIndex, int sinkindex)
          Store relevant information about the FlowNetwork graph.
 
Method Summary
abstract  EdgeInfo edge(int start, int end)
          Subclasses provide this implementation, based upon their data structures.
abstract  int getCost()
          Return the cost of the network solution.
abstract  E getEdgeStructure()
          Subclasses are responsible for interpreting the info in the appropriate data structure.
abstract  int getFlow()
          After the termination of the network flow algorithm, this method returns the final flow pushed out of the source.
abstract  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'.
abstract  void validate()
          Validate the FlowNetwork.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

sourceIndex

public final int sourceIndex
Index of the source vertex.


sinkIndex

public final int sinkIndex
Index of the sink vertex.


numVertices

public final int numVertices
Number of vertices in the graph.

Constructor Detail

FlowNetwork

public FlowNetwork(int numVertices,
                   int srcIndex,
                   int sinkindex)
Store relevant information about the FlowNetwork graph.

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
Method Detail

getEdgeStructure

public abstract E getEdgeStructure()
Subclasses are responsible for interpreting the info in the appropriate data structure.


edge

public abstract EdgeInfo edge(int start,
                              int end)
Subclasses provide this implementation, based upon their data structures.

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

Parameters:
start - the start index of desired edge.
end - the end index of desired edge.

validate

public abstract 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.

Throws:
java.lang.IllegalStateException - if any of these criteria is violated.

getMinCut

public abstract 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'. 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.


getFlow

public abstract int getFlow()
After the termination of the network flow algorithm, this method returns the final flow pushed out of the source.


getCost

public abstract int getCost()
Return the cost of the network solution.

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


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.