|
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.DFS_SearchList
public class DFS_SearchList
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.
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 |
---|
public DFS_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 |