Algorithm
Development Kit 1.0

algs.model.network
Class DFS_SearchArray

java.lang.Object
  extended by algs.model.network.Search
      extended by algs.model.network.DFS_SearchArray

public class DFS_SearchArray
extends Search

Encapsulate algorithm by which the augmenting path for a flow network is found.

Use depth-first search as implemented using a Stack. parameterized to work with EdgeInfo[][] array structure.

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

Field Summary
 
Fields inherited from class algs.model.network.Search
BACKWARD, FORWARD, numVertices, sinkIndex, sourceIndex
 
Constructor Summary
DFS_SearchArray(FlowNetwork<EdgeInfo[][]> network)
           
 
Method Summary
 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
 

Constructor Detail

DFS_SearchArray

public DFS_SearchArray(FlowNetwork<EdgeInfo[][]> network)
See Also:
Search.Search(FlowNetwork)
Method Detail

findAugmentingPath

public boolean findAugmentingPath(VertexInfo[] vertices)
Description copied from class: Search
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.

Specified by:
findAugmentingPath in class Search
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.
See Also:
Search.findAugmentingPath(VertexInfo[])

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.