|
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
public abstract class Search
Flow Network algorithms depend on locating an augmenting path through
the network. This parent class simplifies the implementation of
FordFulkerson
by providing an abstract parent class that
defines the API for identifying augmenting paths.
Appropriate subclasses use either BreadthFirstSearch or DepthFirstSearch to locate the path. In addition, the subclasses are implemented using two-dimensional arrays or adjacency lists.
Field Summary | |
---|---|
static boolean |
BACKWARD
Declares a path in the augmenting path follows a backward edge. |
static boolean |
FORWARD
Declares a path in the augmenting path follows a forward edge. |
protected int |
numVertices
Number of vertices in the graph. |
protected int |
sinkIndex
Index of the sink vertex. |
protected int |
sourceIndex
Index of the source vertex. |
Constructor Summary | |
---|---|
Search(FlowNetwork network)
Configure this augmenting path search with the information it needs to process. |
Method Summary | |
---|---|
abstract 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 |
Field Detail |
---|
protected int sourceIndex
protected int sinkIndex
protected int numVertices
public static final boolean FORWARD
public static final boolean BACKWARD
Constructor Detail |
---|
public Search(FlowNetwork network)
Note that information about the edges are omitted since that knowledge is deferred to the relevant subclasses. We don't care about the parameterization of FlowNetwork either, and that is deferred to the relevant subclasses.
network
- Contains information about the FlowNetworkMethod Detail |
---|
public abstract boolean findAugmentingPath(VertexInfo[] vertices)
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.
vertices
- initially an empty array of Vertex Info; afterwards, contains the
path which can be determined by traversing backwards from the sink index.
|
Algorithm Development Kit 1.0 | ||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |