Algorithm
Development Kit 1.0

algs.model.network
Class Optimized

java.lang.Object
  extended by algs.model.network.FlowNetwork
      extended by algs.model.network.Optimized

public class Optimized
extends FlowNetwork

Optimized implementation of Ford-Fulkerson that uses arrays for all storage. Ignore typed parameterizations of FlowNetwork since they aren't used in this implementation.

Author:
George Heineman

Field Summary
 
Fields inherited from class algs.model.network.FlowNetwork
numVertices, sinkIndex, sourceIndex
 
Constructor Summary
Optimized(int n, int s, int t, java.util.Iterator<EdgeInfo> edges)
          Load up information for this network problem.
 
Method Summary
 int compute(int source, int sink)
           
 EdgeInfo edge(int start, int end)
          Subclasses provide this implementation, based upon their data structures.
 int getCost()
          The optimized Ford-Fulkerson is not able to process costs.
 java.lang.Object getEdgeStructure()
          Expect this to be unused.
 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  int processPath(int source, int sink)
           
 boolean search(int source, int sink)
           
 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

Optimized

public Optimized(int n,
                 int s,
                 int t,
                 java.util.Iterator<EdgeInfo> edges)
Load up information for this network problem.

Method Detail

compute

public int compute(int source,
                   int sink)

processPath

protected int processPath(int source,
                          int sink)

search

public boolean search(int source,
                      int sink)

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
Parameters:
start - the start index of desired edge.
end - the end index of desired edge.

getEdgeStructure

public java.lang.Object getEdgeStructure()
Expect this to be unused.

Specified by:
getEdgeStructure in class FlowNetwork

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

getCost

public int getCost()
The optimized Ford-Fulkerson is not able to process costs. This subclass is a specialized optimization and it is not a problem that this method has no proper implementation.

Specified by:
getCost in class FlowNetwork

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

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