|
FindBugs™ 1.3.9 | |||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectedu.umd.cs.findbugs.graph.AbstractDepthFirstSearch<GraphType,EdgeType,VertexType>
public abstract class AbstractDepthFirstSearch<GraphType extends Graph<EdgeType,VertexType>,EdgeType extends GraphEdge<EdgeType,VertexType>,VertexType extends GraphVertex<VertexType>>
Perform a depth first search on a graph. Algorithm based on Cormen, et. al, Introduction to Algorithms, p. 478. Currently, this class
DFSEdgeTypes
)
Concrete subclasses implement forward and reverse versions of depth first search.
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 |
---|
public static final boolean DEBUG
protected static final int WHITE
protected static final int GRAY
protected static final int BLACK
Constructor Detail |
---|
public AbstractDepthFirstSearch(GraphType graph)
graph
- the graph to be searched
java.lang.IllegalArgumentException
- if the graph has not had edge ids assigned yetMethod Detail |
---|
protected abstract java.util.Iterator<EdgeType> outgoingEdgeIterator(GraphType graph, VertexType vertex)
protected abstract VertexType getTarget(EdgeType edge)
protected abstract VertexType getSource(EdgeType edge)
protected VertexType getNextSearchTreeRoot()
public java.util.Collection<VertexType> unvisitedVertices()
public void setVertexChooser(VertexChooser<VertexType> vertexChooser)
vertexChooser
- the VertexChooser to usepublic void setSearchTreeCallback(SearchTreeCallback<VertexType> searchTreeCallback)
searchTreeCallback
- the search tree callbackpublic AbstractDepthFirstSearch<GraphType,EdgeType,VertexType> search()
public boolean containsCycle()
public int getDFSEdgeType(EdgeType edge)
edge
- the edge
DFSEdgeTypes
public int getDiscoveryTime(VertexType vertex)
vertex
- the vertexpublic int getFinishTime(VertexType vertex)
vertex
- the vertexpublic int[] getFinishTimeList()
public java.util.Iterator<VertexType> topologicalSortIterator()
protected int getColor(VertexType vertex)
vertex
- the vertex
protected boolean visitMe(VertexType vertex)
vertex
- the vertex to possibly be visited
|
FindBugs™ 1.3.9 | |||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |