Algorithm
Development Kit 1.0

algs.model.network
Class Search

java.lang.Object
  extended by algs.model.network.Search
Direct Known Subclasses:
BFS_SearchArray, BFS_SearchList, DFS_SearchArray, DFS_SearchList, ShortestPathArray

public abstract class Search
extends java.lang.Object

Flow Network algorithms depend on locating an augmenting path through the network. This parent class simplifies the implementation of FordFulkerson by providing an abstract parent class that defines the API for identifying augmenting paths.

Appropriate subclasses use either BreadthFirstSearch or DepthFirstSearch to locate the path. In addition, the subclasses are implemented using two-dimensional arrays or adjacency lists.

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.
protected  int numVertices
          Number of vertices in the graph.
protected  int sinkIndex
          Index of the sink vertex.
protected  int sourceIndex
          Index of the source vertex.
 
Constructor Summary
Search(FlowNetwork network)
          Configure this augmenting path search with the information it needs to process.
 
Method Summary
abstract  boolean findAugmentingPath(VertexInfo[] vertices)
          Locate an augmenting path in the Flow Network determined by the edge structure information and knowledge of the vertices (such as the number, which one is source and which one is the sink).
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

sourceIndex

protected int sourceIndex
Index of the source vertex.


sinkIndex

protected int sinkIndex
Index of the sink vertex.


numVertices

protected int numVertices
Number of vertices in the graph.


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

Search

public Search(FlowNetwork network)
Configure this augmenting path search with the information it needs to process.

Note that information about the edges are omitted since that knowledge is deferred to the relevant subclasses. We don't care about the parameterization of FlowNetwork either, and that is deferred to the relevant subclasses.

Parameters:
network - Contains information about the FlowNetwork
Method Detail

findAugmentingPath

public abstract boolean findAugmentingPath(VertexInfo[] vertices)
Locate an augmenting path in the Flow Network determined by the edge structure information and knowledge of the vertices (such as the number, which one is source and which one is the sink).

Returns true if augmenting path was found; false otherwise. The resulting path can be computed from the vertices array (which is altered to contain this information) by traversing in reverse order from the sinkIndex.

Parameters:
vertices - initially an empty array of Vertex Info; afterwards, contains the path which can be determined by traversing backwards from the sink index.
Returns:
true if an augmented path was located; false otherwise.

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.