jdsl.graph.algo
Class DFS

java.lang.Object
  |
  +--jdsl.graph.algo.DFS
Direct Known Subclasses:
DirectedDFS, FindCycleDFS

public class DFS
extends java.lang.Object

Class implementing an abstract Depth First Search. This abstract algorithmic template may be extended to solve a variety of problems on either directed or undirected graphs.

This algorithm runs in O(V+E) time where V is the number of vertices in the graph, and E is the number of edges. It also uses O(V+E) additional space to store data about the vertices and edges during the computation. To this end, it is expected that the Edges and Vertices implement the Decorable interface.

This DFS also conforms to the CLR version in that it maintains "parent references" to the previous Vertex in a DFS path as well as "start-" and "finish times".

Version:
$Revision: 1.3 $, $Date: 2000/11/06 01:01:19 $
Author:
Natasha Gelfand, Keith Schmidt (kas)

Field Summary
static java.lang.Object BACK_EDGE
          Constant signifying that a marked edge is a back edge.
static java.lang.Object CROSS_EDGE
          Constant signifying that a marked edge is a cross edge.
static java.lang.Object EDGE_TYPE
          Constant used as key to look up an edge's type.
static java.lang.Object FINISH_TIME
          Constant used as key to look up the finish time of a vertex.
static java.lang.Object FORWARD_EDGE
          Constant signifying that a marked edge is a forward edge.
protected  InspectableGraph graph_
          The graph being traversed.
static java.lang.Object PARENT
          Constant used as key to look up the parent of a vertex.
static java.lang.Object START_TIME
          Constant used as key to look up the start time of a vertex.
static java.lang.Object TREE_EDGE
          Constant signifying that a marked edge is a tree edge.
static java.lang.Object TREE_NUMBER
          Constant used as key to look up the tree to which a Vertex belongs.
protected  int treeNum_
          The number of the DFS tree being traversed.
static java.lang.Object UNSEEN
          Constant signifying that an edge has not yet been seen.
static java.lang.Object UNVISITED
          Constant signifying that an vertex has not been visited
static java.lang.Object VERTEX_STATUS
          Constant used as key to look up an vertex's status.
static java.lang.Object VISITED
          Constant signifying that an vertex has been visited
static java.lang.Object VISITING
          Constant signifying that an vertex is being visited
protected  java.lang.Object visitResult_
          The result of the traversal.
 
Constructor Summary
DFS()
           
 
Method Summary
 void cleanup()
          Cleans up all decorations stored in the provided graph.
protected  void dfsVisit(Vertex v)
          Performs a recursive depth-first search starting at v
 void execute(InspectableGraph g)
          Execute a DFS without specifying an initial source vertex.
 void execute(InspectableGraph g, Vertex start)
          Runs the depth first search algorithm on a graph.
 java.lang.Integer finishTime(Vertex v)
          Returns the "Finish time" of a Vertex.
protected  void finishVisit(Vertex v)
          Called when the search has finished with the vertex.
protected  EdgeIterator interestingIncidentEdges(Vertex v)
          A method that returns an iterator over those edges incident to the parameter vertex in the graph which should be considered for exploration.
 boolean isBackEdge(Edge e)
          Tests if an edge is a back edge.
 boolean isCrossEdge(Edge e)
          Tests if an edge is a cross edge.
protected  boolean isDone()
          Tests if the depth first search is done.
 boolean isForwardEdge(Edge e)
          Tests if an edge is a forward edge.
 boolean isTreeEdge(Edge e)
          Tests if an edge is a tree edge.
 boolean isUnseen(Edge e)
          Tests if an edge has been seen yet.
 boolean isUnvisited(Vertex v)
          Tests if a vertex has not been visited.
 boolean isVisited(Vertex v)
          Tests if a vertex has been visited.
 boolean isVisiting(Vertex v)
          Tests if a vertex is being visited.
 Vertex parent(Vertex v)
          Retrieves the parent Vertex of a Vertex
 java.lang.Integer startTime(Vertex v)
          Returns the "Start time" of a Vertex.
protected  void startVisit(Vertex v)
          Called when a vertex is visited.
 java.lang.Object status(Vertex v)
          Accesses the current status of the given Vertex.
protected  void traverseBackEdge(Edge e, Vertex from)
          Called when a back edge is traversed.
protected  void traverseCrossEdge(Edge e, Vertex from)
          Called when a cross edge is traversed.
protected  void traverseForwardEdge(Edge e, Vertex from)
          Called when a forward edge is traversed.
protected  void traverseTreeEdge(Edge e, Vertex from)
          Called when a discovery edge is traversed.
 java.lang.Integer treeNumber(Vertex v)
          Retrieves an index representing a connected DFS component.
 java.lang.Object type(Edge e)
          Accesses the current type of the given Edge.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

EDGE_TYPE

public static final java.lang.Object EDGE_TYPE
Constant used as key to look up an edge's type. (UNSEEN, TREE_EDGE, BACK_EDGE, FORWARD_EDGE, or CROSS_EDGE)

UNSEEN

public static final java.lang.Object UNSEEN
Constant signifying that an edge has not yet been seen.

TREE_EDGE

public static final java.lang.Object TREE_EDGE
Constant signifying that a marked edge is a tree edge.

BACK_EDGE

public static final java.lang.Object BACK_EDGE
Constant signifying that a marked edge is a back edge.

FORWARD_EDGE

public static final java.lang.Object FORWARD_EDGE
Constant signifying that a marked edge is a forward edge.

CROSS_EDGE

public static final java.lang.Object CROSS_EDGE
Constant signifying that a marked edge is a cross edge.

VERTEX_STATUS

public static final java.lang.Object VERTEX_STATUS
Constant used as key to look up an vertex's status. (UNVISITED, VISITING, or VISITED)

UNVISITED

public static final java.lang.Object UNVISITED
Constant signifying that an vertex has not been visited

VISITING

public static final java.lang.Object VISITING
Constant signifying that an vertex is being visited

VISITED

public static final java.lang.Object VISITED
Constant signifying that an vertex has been visited

PARENT

public static final java.lang.Object PARENT
Constant used as key to look up the parent of a vertex.

TREE_NUMBER

public static final java.lang.Object TREE_NUMBER
Constant used as key to look up the tree to which a Vertex belongs. [0, 1,...]

START_TIME

public static final java.lang.Object START_TIME
Constant used as key to look up the start time of a vertex.

FINISH_TIME

public static final java.lang.Object FINISH_TIME
Constant used as key to look up the finish time of a vertex.

graph_

protected InspectableGraph graph_
The graph being traversed.

visitResult_

protected java.lang.Object visitResult_
The result of the traversal.

treeNum_

protected int treeNum_
The number of the DFS tree being traversed.
Constructor Detail

DFS

public DFS()
Method Detail

execute

public void execute(InspectableGraph g,
                    Vertex start)
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.

execute

public void execute(InspectableGraph g)
Execute a DFS without specifying an initial source vertex.

dfsVisit

protected void dfsVisit(Vertex v)
Performs a recursive depth-first search starting at v
Parameters:
v - - the vertex at which to start a DFS.

startTime

public java.lang.Integer startTime(Vertex v)
Returns the "Start time" of a Vertex.
Parameters:
v - - the Vertex to check.

finishTime

public java.lang.Integer finishTime(Vertex v)
Returns the "Finish time" of a Vertex.
Parameters:
v - - the Vertex to check.

parent

public Vertex parent(Vertex v)
Retrieves the parent Vertex of a Vertex
Parameters:
v - - the Vertex whose parent to find.

treeNumber

public java.lang.Integer treeNumber(Vertex v)
Retrieves an index representing a connected DFS component. These numbers start at 0 and are incremented after a component is fully traversed. If a certain start Vertex is specified, it will be the root of a DFS tree (defined be Vertices and Tree Edges) with number 0.
Parameters:
v - - the Vertex to check.

status

public java.lang.Object status(Vertex v)
Accesses the current status of the given Vertex. If the Vertex has no status, null is returned.
Parameters:
v - - the Vertex to check.

isUnvisited

public boolean isUnvisited(Vertex v)
Tests if a vertex has not been visited.
Parameters:
v - - the Vertex to check.

isVisiting

public boolean isVisiting(Vertex v)
Tests if a vertex is being visited.
Parameters:
v - - the Vertex to check.

isVisited

public boolean isVisited(Vertex v)
Tests if a vertex has been visited.
Parameters:
v - - the Vertex to check.

type

public java.lang.Object type(Edge e)
Accesses the current type of the given Edge. If the Edge has no type, null is returned.
Parameters:
e - - the Edge to check.

isUnseen

public boolean isUnseen(Edge e)
Tests if an edge has been seen yet.
Parameters:
e - - the Edge to check.

isTreeEdge

public boolean isTreeEdge(Edge e)
Tests if an edge is a tree edge.
Parameters:
e - - the Edge to check.

isBackEdge

public boolean isBackEdge(Edge e)
Tests if an edge is a back edge.
Parameters:
e - - the Edge to check.

isForwardEdge

public boolean isForwardEdge(Edge e)
Tests if an edge is a forward edge.
Parameters:
e - - the Edge to check.

isCrossEdge

public boolean isCrossEdge(Edge e)
Tests if an edge is a cross edge.
Parameters:
e - - the Edge to check.

cleanup

public void cleanup()
Cleans up all decorations stored in the provided graph. This should be called after the user has completely finished everything resulting from a single DFS execution.

startVisit

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

traverseTreeEdge

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

traverseBackEdge

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

traverseForwardEdge

protected void traverseForwardEdge(Edge e,
                                   Vertex from)
Called when a forward edge is traversed. Can be overridden by a subclass.

traverseCrossEdge

protected void traverseCrossEdge(Edge e,
                                 Vertex from)
Called when a cross edge is traversed. Can be overridden by a subclass.

isDone

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

finishVisit

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

interestingIncidentEdges

protected EdgeIterator interestingIncidentEdges(Vertex v)
A method that returns an iterator over those edges incident to the parameter vertex in the graph which should be considered for exploration. Subclasses of DFS may implement this method so as to traverse edges as though they were undirected or to traverse the directed edges in the forward or reverse directions, or to in some other way hand pick which edges were of interest for exploration.
Parameters:
Vertex - The vertex for which interesting incident edges shouldbe returned
Returns:
EdgeIterator An Iterator over interesting edges incident to the parameter Vertex