edu.umd.cs.findbugs.graph

Class AbstractDepthFirstSearch<GraphType extends Graph<EdgeType,VertexType>,EdgeType extends GraphEdge<EdgeType,VertexType>,VertexType extends GraphVertex<VertexType>>

java.lang.Object

edu.umd.cs.findbugs.graph.AbstractDepthFirstSearch<GraphType,EdgeType,VertexType>

All Implemented Interfaces:

DFSEdgeTypes

Direct Known Subclasses:

DepthFirstSearch, ReverseDepthFirstSearch

public abstract class AbstractDepthFirstSearch<GraphType extends Graph<EdgeType,VertexType>,EdgeType extends GraphEdge<EdgeType,VertexType>,VertexType extends GraphVertex<VertexType>>
extends java.lang.Object
implements DFSEdgeTypes

Perform a depth first search on a graph. Algorithm based on Cormen, et. al, Introduction to Algorithms, p. 478. Currently, this class

• assigns DFS edge types (see DFSEdgeTypes)
• assigns discovery and finish times for each vertex
• produces a topological sort of the vertices, if and only if the graph is acyclic

Concrete subclasses implement forward and reverse versions of depth first search.

Author:

David Hovemeyer

See Also:

Graph, DepthFirstSearch, ReverseDepthFirstSearch

Field Summary

Fields

Modifier and Type	Field and Description
protected static int	BLACK Color of a vertex whose entire search tree has been visited.
static boolean	DEBUG
protected static int	GRAY Color of a vertex which has been visited, but not all of whose descendents have been visited.
protected static int	WHITE Color of a vertex which hasn't been visited yet.

Fields inherited from interface edu.umd.cs.findbugs.graph.DFSEdgeTypes

BACK_EDGE, CROSS_EDGE, FORWARD_EDGE, TREE_EDGE, UNKNOWN_EDGE

Constructor Summary

Constructors

Constructor and Description
AbstractDepthFirstSearch(GraphType graph) Constructor.

Method Summary

Methods

Modifier and Type	Method and Description
boolean	containsCycle() Return whether or not the graph contains a cycle: i.e., whether it contains any back edges.
protected int	getColor(VertexType vertex) Get the current color of given vertex.
int	getDFSEdgeType(EdgeType edge) Get the type of edge in the depth first search.
int	getDiscoveryTime(VertexType vertex) Return the timestamp indicating when the given vertex was discovered.
int	getFinishTime(VertexType vertex) Return the timestamp indicating when the given vertex was finished (meaning that all of its descendents were visited recursively).
int[]	getFinishTimeList() Get array of finish times, indexed by vertex label.
protected VertexType	getNextSearchTreeRoot() Choose the next search tree root.
protected abstract VertexType	getSource(EdgeType edge) Get "logical" source of edge.
protected abstract VertexType	getTarget(EdgeType edge) Get "logical" target of edge.
protected abstract java.util.Iterator<EdgeType>	outgoingEdgeIterator(GraphType graph, VertexType vertex) Get Iterator over "logical" outgoing edges.
AbstractDepthFirstSearch<GraphType,EdgeType,VertexType>	search() Perform the depth first search.
void	setSearchTreeCallback(SearchTreeCallback<VertexType> searchTreeCallback) Set a search tree callback.
void	setVertexChooser(VertexChooser<VertexType> vertexChooser) Specify a VertexChooser object to be used to selected which vertices are visited by the search.
java.util.Iterator<VertexType>	topologicalSortIterator() Get an iterator over the vertexs in topological sort order.
java.util.Collection<VertexType>	unvisitedVertices()
protected boolean	visitMe(VertexType vertex) Predicate to determine which vertices should be visited as the search progresses.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

DEBUG

public static final boolean DEBUG

See Also:

Constant Field Values

WHITE

protected static final int WHITE

Color of a vertex which hasn't been visited yet.

See Also:

Constant Field Values

GRAY

protected static final int GRAY

Color of a vertex which has been visited, but not all of whose descendents have been visited.

See Also:

Constant Field Values

BLACK

protected static final int BLACK

Color of a vertex whose entire search tree has been visited.

See Also:

Constant Field Values

Constructor Detail

AbstractDepthFirstSearch

public AbstractDepthFirstSearch(GraphType graph)

Constructor.

Parameters:

graph - the graph to be searched

Throws:

java.lang.IllegalArgumentException - if the graph has not had edge ids assigned yet

Method Detail

outgoingEdgeIterator

protected abstract java.util.Iterator<EdgeType> outgoingEdgeIterator(GraphType graph,
                                                VertexType vertex)

Get Iterator over "logical" outgoing edges.

getTarget

protected abstract VertexType getTarget(EdgeType edge)

Get "logical" target of edge.

getSource

protected abstract VertexType getSource(EdgeType edge)

Get "logical" source of edge.

getNextSearchTreeRoot

protected VertexType getNextSearchTreeRoot()

Choose the next search tree root. By default, this method just scans for a WHITE vertex. Subclasses may override this method in order to choose which vertices are used as search tree roots.

Returns:

the next search tree root

unvisitedVertices

public java.util.Collection<VertexType> unvisitedVertices()

setVertexChooser

public void setVertexChooser(VertexChooser<VertexType> vertexChooser)

Specify a VertexChooser object to be used to selected which vertices are visited by the search. This is useful if you only want to search a subset of the vertices in the graph.

Parameters:

vertexChooser - the VertexChooser to use

setSearchTreeCallback

public void setSearchTreeCallback(SearchTreeCallback<VertexType> searchTreeCallback)

Set a search tree callback.

Parameters:

searchTreeCallback - the search tree callback

search

public AbstractDepthFirstSearch<GraphType,EdgeType,VertexType> search()

Perform the depth first search.

Returns:

this object

containsCycle

public boolean containsCycle()

Return whether or not the graph contains a cycle: i.e., whether it contains any back edges. This should only be called after search() has been called (since that method actually executes the search).

Returns:

true if the graph contains a cycle, false otherwise

getDFSEdgeType

public int getDFSEdgeType(EdgeType edge)

Get the type of edge in the depth first search.

Parameters:

edge - the edge

Returns:

the DFS type of edge: TREE_EDGE, FORWARD_EDGE, CROSS_EDGE, or BACK_EDGE

See Also:

DFSEdgeTypes

getDiscoveryTime

public int getDiscoveryTime(VertexType vertex)

Return the timestamp indicating when the given vertex was discovered.

Parameters:

vertex - the vertex

getFinishTime

public int getFinishTime(VertexType vertex)

Return the timestamp indicating when the given vertex was finished (meaning that all of its descendents were visited recursively).

Parameters:

vertex - the vertex

getFinishTimeList

public int[] getFinishTimeList()

Get array of finish times, indexed by vertex label.

Returns:

the array of finish times

topologicalSortIterator

public java.util.Iterator<VertexType> topologicalSortIterator()

Get an iterator over the vertexs in topological sort order. This works if and only if the graph is acyclic.

getColor

protected int getColor(VertexType vertex)

Get the current color of given vertex.

Parameters:

vertex - the vertex

Returns:

the color (WHITE, BLACK, or GRAY)

visitMe

protected boolean visitMe(VertexType vertex)

Predicate to determine which vertices should be visited as the search progresses. Takes both vertex color and the vertex chooser (if any) into account.

Parameters:

vertex - the vertex to possibly be visited

Returns:

true if the vertex should be visited, false if not