

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 