Algorithm
Development Kit 1.0

algs.model.network
Class DFS_SearchList

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

public class DFS_SearchList
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 an edge structure based on VertexStructure array.

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_SearchList(FlowNetwork<VertexStructure[]> 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_SearchList

public DFS_SearchList(FlowNetwork<VertexStructure[]> 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.