jdsl.graph.algo
Class DFS

java.lang.Object
  jdsl.graph.algo.DFS

Direct Known Subclasses:

DirectedDFS, FindCycleDFS

public class DFS

extends Object

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:

JDSL 2.1.1

Author:

Natasha Gelfand, Keith Schmidt (kas)

Field Summary

static Object	BACK_EDGE Constant signifying that a marked edge is a back edge.
static Object	CROSS_EDGE Constant signifying that a marked edge is a cross edge.
static Object	EDGE_TYPE Constant used as key to look up an edge's type.
static Object	FINISH_TIME Constant used as key to look up the finish time of a vertex.
static Object	FORWARD_EDGE Constant signifying that a marked edge is a forward edge.
protected InspectableGraph	graph_ The graph being traversed.
static Object	PARENT Constant used as key to look up the parent of a vertex.
static Object	START_TIME Constant used as key to look up the start time of a vertex.
static Object	TREE_EDGE Constant signifying that a marked edge is a tree edge.
static 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 Object	UNSEEN Constant signifying that an edge has not yet been seen.
static Object	UNVISITED Constant signifying that an vertex has not been visited
static Object	VERTEX_STATUS Constant used as key to look up an vertex's status.
static Object	VISITED Constant signifying that an vertex has been visited
static Object	VISITING Constant signifying that an vertex is being visited
protected 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.
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
Integer	startTime(Vertex v) Returns the "Start time" of a Vertex.
protected void	startVisit(Vertex v) Called when a vertex is visited.
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.
Integer	treeNumber(Vertex v) Retrieves an index representing a connected DFS component.
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 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 Object UNSEEN

Constant signifying that an edge has not yet been seen.

TREE_EDGE

public static final Object TREE_EDGE

Constant signifying that a marked edge is a tree edge.

BACK_EDGE

public static final Object BACK_EDGE

Constant signifying that a marked edge is a back edge.

FORWARD_EDGE

public static final Object FORWARD_EDGE

Constant signifying that a marked edge is a forward edge.

CROSS_EDGE

public static final Object CROSS_EDGE

Constant signifying that a marked edge is a cross edge.

VERTEX_STATUS

public static final Object VERTEX_STATUS

Constant used as key to look up an vertex's status. (UNVISITED, VISITING, or VISITED)

UNVISITED

public static final Object UNVISITED

Constant signifying that an vertex has not been visited

VISITING

public static final Object VISITING

Constant signifying that an vertex is being visited

VISITED

public static final Object VISITED

Constant signifying that an vertex has been visited

PARENT

public static final Object PARENT

Constant used as key to look up the parent of a vertex.

TREE_NUMBER

public static final Object TREE_NUMBER

Constant used as key to look up the tree to which a Vertex belongs.

START_TIME

public static final Object START_TIME

Constant used as key to look up the start time of a vertex.

FINISH_TIME

public static final 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 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 Integer startTime(Vertex v)

Returns the "Start time" of a Vertex.

Parameters:

v - - the Vertex to check.

finishTime

public 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 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 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 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:

v - The vertex for which interesting incident edges shouldbe returned

Returns:

EdgeIterator An Iterator over interesting edges incident to the parameter Vertex