Package ghidra.util.graph

Class DepthFirstSearch

java.lang.Object
ghidra.util.graph.DepthFirstSearch
@Deprecated(since="10.2") public class DepthFirstSearch extends Object
Deprecated.
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)
    Deprecated.
    Upon creation a depth first search of the given graph is performed.

  • Method Summary

    Modifier and Type
    Method
    Description
    Edge[]
    backEdges()
    Deprecated.
    Return the back edges found in this depth first search.
    boolean
    isAcyclic()
    Deprecated.
    Return true iff no back edges were found.
    boolean
    isCompleted(Vertex v)
    Deprecated.
    Return true if the vertex has completed its role in the depth first search.
    boolean
    isTree()
    Deprecated.
    Return true iff the every edge is a tree edge.
    boolean
    isUnseen(Vertex v)
    Deprecated.
    Return true if the vertex has not yet been discovered in the depth first search.
    DirectedGraph
    spanningTree()
    Deprecated.
    Returns a spanning tree (in the form of a DirectedGraph).
    Vertex[]
    topologicalSort()
    Deprecated.
    Returns a topological sort of the directed graph.
    Edge[]
    treeEdges()
    Deprecated.
    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 Details

    • DepthFirstSearch

      public DepthFirstSearch(DirectedGraph graph, Vertex[] initialSeeds, boolean getAdditionalSeedsIfNeeded, boolean goForward, boolean goBackward)
      Deprecated.
      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 Details

    • isUnseen

      public boolean isUnseen(Vertex v)
      Deprecated.
      Return true if the vertex has not yet been discovered in the depth first search.

    • isCompleted

      public boolean isCompleted(Vertex v)
      Deprecated.
      Return true if the vertex has completed its role in the depth first search.

    • backEdges

      public Edge[] backEdges()
      Deprecated.
      Return the back edges found in this depth first search.

    • treeEdges

      public Edge[] treeEdges()
      Deprecated.
      Return the tree edges in this depth first search.

    • isAcyclic

      public boolean isAcyclic()
      Deprecated.
      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()
      Deprecated.
      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()
      Deprecated.
      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()
      Deprecated.
      Returns a spanning tree (in the form of a DirectedGraph). No claims that the spanning tree returned has any special properties.