Package ghidra.util.graph

Class 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.

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • 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 search
        initialSeeds - The vertices used to start the search
        getAdditionalSeedsIfNeeded - 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 direction
        goBackward - 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:
        1. If the graph is acyclic then v[i] -> v[j] => i < j .
        2. 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.