edu.umd.cs.findbugs.graph
public abstract class AbstractDepthFirstSearch<GraphType extends Graph<EdgeType,VertexType>,EdgeType extends GraphEdge<EdgeType,VertexType>,VertexType extends GraphVertex<VertexType>> extends Object implements DFSEdgeTypes
Concrete subclasses implement forward and reverse versions of depth first search.
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. |
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).
|
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 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.
|
Iterator<VertexType> | topologicalSortIterator()
Get an iterator over the vertexs in topological sort order.
|
protected boolean | visitMe(VertexType vertex)
Predicate to determine which vertices should be visited
as the search progresses. |
Parameters: graph the graph to be searched
Throws: IllegalArgumentException if the graph has not had edge ids assigned yet
Returns: true if the graph contains a cycle, false otherwise
Parameters: vertex the vertex
Returns: the color (WHITE, BLACK, or GRAY)
Parameters: edge the edge
Returns: the DFS type of edge: TREE_EDGE, FORWARD_EDGE, CROSS_EDGE, or BACK_EDGE
See Also: DFSEdgeTypes
Parameters: vertex the vertex
Parameters: vertex the vertex
Returns: the next search tree root
Returns: this object
Parameters: searchTreeCallback the search tree callback
Parameters: vertexChooser the VertexChooser to use
Parameters: vertex the vertex to possibly be visited
Returns: true if the vertex should be visited, false if not