All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class jdsl.core.algo.graphtraversals.DFS 

java.lang.Object
   |
   +----jdsl.core.algo.graphtraversals.DFS
public abstract class DFS
extends Object
A template method implementation of a depth first search. A subclass should override various methods to add functionality to this traversal.

Variable Index

o graph
The graph being traversed.
o markedEdges
A table of marked edges.
o markedVerts
A table of marked vertices.
o visitResult
The result of the traversal.

Constructor Index

o DFS()

Method Index

o dfsVisit(Vertex)
Performs a recursive depth-first search starting at v
o execute(InspectableGraph, Vertex, Object)
Runs the depth first search algorithm on a graph.
o finishVisit(Vertex)
Called when the search has finished with the vertex.
o initResult()
Initializes the result.
o isDone()
Tests if the depth first search is done.
o isMarked(Edge)
Tests if an edge has been marked.
o isMarked(Vertex)
Tests if a vertex has been marked.
o mark(Edge)
Marks an edge as traversed.
o mark(Vertex)
Called when a vertex needs to be marked as visited.
o result()
Returns the result of the search.
o startVisit(Vertex)
Called when a vertex is visited.
o traverseBack(Edge, Vertex)
Called when a back edge is traversed.
o traverseDiscovery(Edge, Vertex)
Called when a discovery edge is traversed.

Variables

o graph 
 protected InspectableGraph graph
The graph being traversed.

o visitResult 
 protected Object visitResult
The result of the traversal.

o markedVerts 
 protected Hashtable markedVerts
A table of marked vertices.

o markedEdges 
 protected Hashtable markedEdges
A table of marked edges.

Constructors

o DFS 
 public DFS()

Methods

o execute 
 public Object execute(InspectableGraph g,
                       Vertex start,
                       Object info)
Runs the depth first search algorithm on a graph.

Parameters:
g - An InspectableGraph on which to run a depth first search.
start - The Vertex at which to start the depth first search.
info - any extra information that the subclass might need.
o dfsVisit 
 protected Object dfsVisit(Vertex v)
Performs a recursive depth-first search starting at v

o mark 
 protected void mark(Vertex v)
Called when a vertex needs to be marked as visited.

o mark 
 protected void mark(Edge e)
Marks an edge as traversed.

o isMarked 
 protected boolean isMarked(Vertex v)
Tests if a vertex has been marked.

o isMarked 
 protected boolean isMarked(Edge e)
Tests if an edge has been marked.

o initResult 
 protected void initResult()
Initializes the result. Should be overridden by a subclass.

o startVisit 
 protected void startVisit(Vertex v)
Called when a vertex is visited. Should be overridden by a subclass.

o traverseDiscovery 
 protected void traverseDiscovery(Edge e,
                                  Vertex from)
Called when a discovery edge is traversed. Should be overridden by a subclass.

o traverseBack 
 protected void traverseBack(Edge e,
                             Vertex from)
Called when a back edge is traversed. Should be overridden by a subclass.

o isDone 
 protected boolean isDone()
Tests if the depth first search is done. Should be overridden by a subclass.

o finishVisit 
 protected void finishVisit(Vertex v)
Called when the search has finished with the vertex. Should be overridden by a subclass.

o result 
 protected Object result()
Returns the result of the search. Should be overridden by a subclass. 

All Packages  Class Hierarchy  This Package  Previous  Next  Index