FindBugs™ 1.3.9

edu.umd.cs.findbugs.graph
Class AbstractDepthFirstSearch<GraphType extends Graph<EdgeType,VertexType>,EdgeType extends GraphEdge<EdgeType,VertexType>,VertexType extends GraphVertex<VertexType>>

java.lang.Object
  extended by 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

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

Author:
David Hovemeyer
See Also:
Graph, DepthFirstSearch, ReverseDepthFirstSearch

Field Summary
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
AbstractDepthFirstSearch(GraphType graph)
          Constructor.
 
Method Summary
 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

FindBugs™ 1.3.9

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