|
Algorithm Development Kit 1.0 |
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectalgs.model.network.Search
algs.model.network.BFS_SearchList
public class BFS_SearchList
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.
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 |
---|
public BFS_SearchList(FlowNetwork<VertexStructure[]> network)
Search.Search(FlowNetwork)
Method Detail |
---|
public boolean findAugmentingPath(VertexInfo[] vertices)
Search
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.
findAugmentingPath
in class Search
vertices
- initially an empty array of Vertex Info; afterwards, contains the
path which can be determined by traversing backwards from the sink index.
Search.findAugmentingPath(VertexInfo[])
|
Algorithm Development Kit 1.0 | ||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |