|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--jdsl.graph.algo.BFS
Class implementing an abstract Breadth First Search. This abstract algorithmic template may be extended to solve a variety of problems on either directed or undirected graphs.
Field Summary | |
protected static java.lang.Object |
CROSS_EDGE
Constant signifying that an edge stored in markedEdges is a cross edge. |
protected static java.lang.Object |
DISCOVERY_EDGE
Constant signifying that an edge stored in markedEdges is a discovery edge. |
protected InspectableGraph |
graph
The graph on which the algorithm is currently executing. |
Constructor Summary | |
BFS()
|
Method Summary | |
protected int |
depth(Vertex v)
|
java.lang.Object |
execute(InspectableGraph g,
Vertex start,
java.lang.Object info)
Executes a breadth first search (BFS). |
protected abstract void |
finishVisit(Vertex v)
Abstract method called on a vertex at the end of a visit (after all of its untraversed edges have been traversed). |
protected abstract void |
initialize(Vertex v,
java.lang.Object info)
Abstract method to initialize the object at the beginning of a BFS execution. |
protected abstract EdgeIterator |
interestingEdges(Vertex v)
Abstract method that returns an iterator over those edges incident to the parameter vertex in the graph which should be considered for exploration. |
protected boolean |
isCrossEdge(Edge e)
|
protected boolean |
isDiscoveryEdge(Edge e)
|
protected boolean |
isMarked(Edge e)
|
protected boolean |
isMarked(Vertex v)
|
protected void |
mark(Edge e,
java.lang.Object kind)
Marks e as being of type kind . |
protected void |
mark(Vertex v,
int depth)
Marks v as being of depth depth in the BFS
tree created by this BFS. |
protected abstract java.lang.Object |
result()
Abstract method called at the very end of the BFS execution. |
protected abstract void |
startVisit(Vertex v)
Abstract method called on a vertex when it is visited. |
protected abstract void |
traverseCross(Edge e,
Vertex v,
Vertex w)
Abstract method called when traversing a cross edge. |
protected abstract void |
traverseDiscovery(Edge e,
Vertex parent,
Vertex child)
Abstract method called when traversing a disocvery edge. |
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
protected static final java.lang.Object DISCOVERY_EDGE
protected static final java.lang.Object CROSS_EDGE
protected InspectableGraph graph
Constructor Detail |
public BFS()
Method Detail |
public java.lang.Object execute(InspectableGraph g, Vertex start, java.lang.Object info)
InspectableGraph
- The graph on which to perform the BFSVertex
- The Vertex
at which to start (the root
of the BFS tree)Object
- Should store any auxilary information needed for
successful execution of subclasses. This variable is passed on to the
initialize(.)
method, which should be redefined by the user.result(.)
protected abstract void initialize(Vertex v, java.lang.Object info)
Vertex
- v The start vertex in the call to execute(.)
Object
- info The Object info
passed to
execute(.)
. Should contain any extra data needed by
subclasses of BFS.protected abstract void startVisit(Vertex v)
depth(Vertex)
method. Must be reimplemented by subclasses.Vertex
- v The vertex for which the visit is now startingprotected abstract void finishVisit(Vertex v)
Vertex
- The vertex for which the visit is now ending.protected abstract EdgeIterator interestingEdges(Vertex v)
Vertex
- The vertex for which interesting incident edges shouldbe
returnedprotected abstract void traverseDiscovery(Edge e, Vertex parent, Vertex child)
Note that the difference in depth between parent
and
child
is exactly one.
Edge
- e The discovery edge being traversedVertex
- parent The vertex incident to e
with
lesser depth in the BFS tree.Vertex
- child The vertex incident to e
with greater
depth in the BFS tree.protected abstract void traverseCross(Edge e, Vertex v, Vertex w)
Note that the difference in depth between parent
and
child
is not necessarily exactly one, although the
depth of both nodes is known.
Edge
- e The cross edge being traversedVertex
- v The vertex to which e
is incident that
is being visited currently.Vertex
- w The vertex opposite v along e.protected abstract java.lang.Object result()
protected void mark(Edge e, java.lang.Object kind)
e
as being of type kind
.Edge
- e The edge to markObject
- kind either DISCOVERY_EDGE, or CROSS_EDGE.protected boolean isMarked(Edge e)
protected boolean isDiscoveryEdge(Edge e)
protected boolean isCrossEdge(Edge e)
protected void mark(Vertex v, int depth)
v
as being of depth depth
in the BFS
tree created by this BFS.Vertex
- v the vertex to markint
- depth The depth of v
in the BFS tree.protected boolean isMarked(Vertex v)
protected int depth(Vertex v)
v
or -1 if v
has not yet been marked.
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |