Algorithm
Development Kit 1.0

algs.model.network
Class BFS_SearchList

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

public class BFS_SearchList
extends Search

Encapsulate algorithm by which the augmenting path for a flow network is found when the underlying data structure is represented as an adjacency list.

Use Breadth-first search as implemented using DoubleLinkedList as a queue.

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

BFS_SearchList

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