Package ghidra.util.graph
Class DepthFirstSearch
- java.lang.Object
-
- ghidra.util.graph.DepthFirstSearch
-
public class DepthFirstSearch extends java.lang.Object
Provides a depth first search service to directed graphs. Once a search has finished information about the search can be obtained.
-
-
Constructor Summary
Constructors Constructor Description DepthFirstSearch(DirectedGraph graph, Vertex[] initialSeeds, boolean getAdditionalSeedsIfNeeded, boolean goForward, boolean goBackward)
Upon creation a depth first search of the given graph is performed.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description Edge[]
backEdges()
Return the back edges found in this depth first search.boolean
isAcyclic()
Return true iff no back edges were found.boolean
isCompleted(Vertex v)
Return true if the vertex has completed its role in the depth first search.boolean
isTree()
Return true iff the every edge is a tree edge.boolean
isUnseen(Vertex v)
Return true if the vertex has not yet been discovered in the depth first search.DirectedGraph
spanningTree()
Returns a spanning tree (in the form of a DirectedGraph).Vertex[]
topologicalSort()
Returns a topological sort of the directed graph.Edge[]
treeEdges()
Return the tree edges in this depth first search.
-
-
-
Constructor Detail
-
DepthFirstSearch
public DepthFirstSearch(DirectedGraph graph, Vertex[] initialSeeds, boolean getAdditionalSeedsIfNeeded, boolean goForward, boolean goBackward)
Upon creation a depth first search of the given graph is performed.- Parameters:
graph
- The graph to searchinitialSeeds
- The vertices used to start the searchgetAdditionalSeedsIfNeeded
- If true, when searching from the initial seeds does not find all vertices in the graph, additional start vertices will be selected until every vertex is the graph has been found.goForward
- Follow edges in their specifed directiongoBackward
- Follow edges in the opposite of their specified direction.
-
-
Method Detail
-
isUnseen
public boolean isUnseen(Vertex v)
Return true if the vertex has not yet been discovered in the depth first search.
-
isCompleted
public boolean isCompleted(Vertex v)
Return true if the vertex has completed its role in the depth first search.
-
backEdges
public Edge[] backEdges()
Return the back edges found in this depth first search.
-
treeEdges
public Edge[] treeEdges()
Return the tree edges in this depth first search.
-
isAcyclic
public boolean isAcyclic()
Return true iff no back edges were found. Note that if the graph is not completely explored the answer is only for the portion of the graph expored.
-
isTree
public boolean isTree()
Return true iff the every edge is a tree edge. Will always be false if the entire graph is not explored.
-
topologicalSort
public Vertex[] topologicalSort()
Returns a topological sort of the directed graph. Return the vertices in the explored portion of the graph with the following property:- If the graph is acyclic then v[i] -> v[j] => i < j .
- If the graph contains cycles, then the above is true except when (v[i],v[j]) is a back edge.
-
spanningTree
public DirectedGraph spanningTree()
Returns a spanning tree (in the form of a DirectedGraph). No claims that the spanning tree returned has any special properties.
-
-