Package 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.
- See Also:
Graph
,DepthFirstSearch
,ReverseDepthFirstSearch
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private class
AbstractDepthFirstSearch.Visit
-
Field Summary
Fields Modifier and Type Field Description protected static int
BLACK
Color of a vertex whose entire search tree has been visited.private int[]
colorList
static boolean
DEBUG
private int[]
dfsEdgeTypeList
private int[]
discoveryTimeList
private int[]
finishTimeList
private GraphType
graph
protected static int
GRAY
Color of a vertex which has been visited, but not all of whose descendents have been visited.private SearchTreeCallback<VertexType>
searchTreeCallback
private int
timestamp
private java.util.LinkedList<VertexType>
topologicalSortList
private VertexChooser<VertexType>
vertexChooser
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 Modifier Constructor Description protected
AbstractDepthFirstSearch(GraphType graph)
Constructor.
-
Method Summary
All Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description private void
classifyUnknownEdges()
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.private void
setColor(VertexType vertex, int color)
private void
setDFSEdgeType(EdgeType edge, int dfsEdgeType)
private void
setDiscoveryTime(VertexType vertex, int ts)
private void
setFinishTime(VertexType vertex, int ts)
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()
private void
visitAll()
protected boolean
visitMe(VertexType vertex)
Predicate to determine which vertices should be visited as the search progresses.private void
visitSuccessor(java.util.ArrayList<AbstractDepthFirstSearch.Visit> stack, EdgeType edge)
-
-
-
Field Detail
-
DEBUG
public static final boolean DEBUG
- See Also:
- Constant Field Values
-
graph
private final GraphType extends Graph<EdgeType,VertexType> graph
-
colorList
private final int[] colorList
-
discoveryTimeList
private final int[] discoveryTimeList
-
finishTimeList
private final int[] finishTimeList
-
dfsEdgeTypeList
private final int[] dfsEdgeTypeList
-
timestamp
private int timestamp
-
topologicalSortList
private final java.util.LinkedList<VertexType extends GraphVertex<VertexType>> topologicalSortList
-
vertexChooser
private VertexChooser<VertexType extends GraphVertex<VertexType>> vertexChooser
-
searchTreeCallback
private SearchTreeCallback<VertexType extends GraphVertex<VertexType>> searchTreeCallback
-
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
protected 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.
-
visitAll
private void visitAll()
-
visitSuccessor
private void visitSuccessor(java.util.ArrayList<AbstractDepthFirstSearch.Visit> stack, EdgeType edge)
-
classifyUnknownEdges
private void classifyUnknownEdges()
-
setColor
private void setColor(VertexType vertex, int color)
-
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
-
setDiscoveryTime
private void setDiscoveryTime(VertexType vertex, int ts)
-
setFinishTime
private void setFinishTime(VertexType vertex, int ts)
-
setDFSEdgeType
private void setDFSEdgeType(EdgeType edge, int dfsEdgeType)
-
-