edu.umd.cs.findbugs.graph

Class AbstractDepthFirstSearch<GraphType,EdgeType,VertexType>

public abstract class AbstractDepthFirstSearch<GraphType extends Graph<EdgeType,VertexType>,EdgeType extends GraphEdge<EdgeType,VertexType>,VertexType extends GraphVertex<VertexType>> extends 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

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

Author: David Hovemeyer

See Also: Graph DepthFirstSearch ReverseDepthFirstSearch

Field Summary
protected static intBLACK
Color of a vertex whose entire search tree has been visited.
static booleanDEBUG
protected static intGRAY
Color of a vertex which has been visited, but not all of whose descendents have been visited.
protected static intWHITE
Color of a vertex which hasn't been visited yet.
Constructor Summary
AbstractDepthFirstSearch(GraphType graph)
Constructor.
Method Summary
booleancontainsCycle()
Return whether or not the graph contains a cycle: i.e., whether it contains any back edges.
protected intgetColor(VertexType vertex)
Get the current color of given vertex.
intgetDFSEdgeType(EdgeType edge)
Get the type of edge in the depth first search.
intgetDiscoveryTime(VertexType vertex)
Return the timestamp indicating when the given vertex was discovered.
intgetFinishTime(VertexType vertex)
Return the timestamp indicating when the given vertex was finished (meaning that all of its descendents were visited recursively).
protected VertexTypegetNextSearchTreeRoot()
Choose the next search tree root.
protected abstract VertexTypegetSource(EdgeType edge)
Get "logical" source of edge.
protected abstract VertexTypegetTarget(EdgeType edge)
Get "logical" target of edge.
protected abstract Iterator<EdgeType>outgoingEdgeIterator(GraphType graph, VertexType vertex)
Get Iterator over "logical" outgoing edges.
AbstractDepthFirstSearch<GraphType,EdgeType,VertexType>search()
Perform the depth first search.
voidsetSearchTreeCallback(SearchTreeCallback<VertexType> searchTreeCallback)
Set a search tree callback.
voidsetVertexChooser(VertexChooser<VertexType> vertexChooser)
Specify a VertexChooser object to be used to selected which vertices are visited by the search.
Iterator<VertexType>topologicalSortIterator()
Get an iterator over the vertexs in topological sort order.
protected booleanvisitMe(VertexType vertex)
Predicate to determine which vertices should be visited as the search progresses.

Field Detail

BLACK

protected static final int BLACK
Color of a vertex whose entire search tree has been visited.

DEBUG

public static final boolean DEBUG

GRAY

protected static final int GRAY
Color of a vertex which has been visited, but not all of whose descendents have been visited.

WHITE

protected static final int WHITE
Color of a vertex which hasn't been visited yet.

Constructor Detail

AbstractDepthFirstSearch

public AbstractDepthFirstSearch(GraphType graph)
Constructor.

Parameters: graph the graph to be searched

Throws: IllegalArgumentException if the graph has not had edge ids assigned yet

Method Detail

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

getColor

protected int getColor(VertexType vertex)
Get the current color of given vertex.

Parameters: vertex the vertex

Returns: the color (WHITE, BLACK, or GRAY)

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

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

getSource

protected abstract VertexType getSource(EdgeType edge)
Get "logical" source of edge.

getTarget

protected abstract VertexType getTarget(EdgeType edge)
Get "logical" target of edge.

outgoingEdgeIterator

protected abstract Iterator<EdgeType> outgoingEdgeIterator(GraphType graph, VertexType vertex)
Get Iterator over "logical" outgoing edges.

search

public AbstractDepthFirstSearch<GraphType,EdgeType,VertexType> search()
Perform the depth first search.

Returns: this object

setSearchTreeCallback

public void setSearchTreeCallback(SearchTreeCallback<VertexType> searchTreeCallback)
Set a search tree callback.

Parameters: searchTreeCallback the search tree callback

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

topologicalSortIterator

public Iterator<VertexType> topologicalSortIterator()
Get an iterator over the vertexs in topological sort order. This works if and only if the graph is acyclic.

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

FindBugs™ is licenced under the LGPL. Copyright © 2006 University of Maryland.