Package ghidra.util.graph

Class Dominator

java.lang.Object
ghidra.util.graph.DirectedGraph
ghidra.util.graph.Dominator
@Deprecated(forRemoval=true, since="10.2") public class Dominator extends DirectedGraph
Deprecated, for removal: This API element is subject to removal in a future version.
Title: Dominator Description: This class contains the functions necessary to build the dominance graph of a FlowGraph, ShrinkWrap or Modularized Graph. A more complete explanation of my algorithm can be found in my paper titled "Building a Dominance Graph"

  • Constructor Details

    • Dominator

      public Dominator(int vertexCapacity, int edgeCapacity)
      Deprecated, for removal: This API element is subject to removal in a future version.

    • Dominator

      public Dominator()
      Deprecated, for removal: This API element is subject to removal in a future version.

    • Dominator

      public Dominator(DirectedGraph cg)
      Deprecated, for removal: This API element is subject to removal in a future version.

  • Method Details

    • backTrack

      public Vertex backTrack(Vertex v)
      Deprecated, for removal: This API element is subject to removal in a future version.
      this aids in going back to the parent from which a vertex was accessed in the depth first search

    • getDominator

      public Vertex getDominator(Vertex v)
      Deprecated, for removal: This API element is subject to removal in a future version.
      this returns the vertex that is the dominator

    • allPathsContaining

      public Vector allPathsContaining(Vertex v)
      Deprecated, for removal: This API element is subject to removal in a future version.
      this returns all paths that contain v which we need to consider when looking for the dominator of v. It places the longest path as the first element in the vector pathSet.

    • allPathsContain

      public Vertex allPathsContain(Vector pathSet, Vertex v, Vector path)
      Deprecated, for removal: This API element is subject to removal in a future version.
      This takes the longest path that contains vertex v and looks to see if any of v's ancestors from that path are contained in all other paths that contain v.

    • goToNextWhiteChild

      public Vertex goToNextWhiteChild(Vertex v)
      Deprecated, for removal: This API element is subject to removal in a future version.
      Goes to the next child of v that has not been visited and sets the calling parent to be v so that we can backtrack.

    • setDominance

      public DirectedGraph setDominance()
      Deprecated, for removal: This API element is subject to removal in a future version.
      This makes a list of all the paths that are in a graph that terminate either because of a repeated vertex or hitting a sink. It then calls getDominanceGraph which gets the dominator for every vertex and builds a dominance graph.

    • getDominanceGraph

      public DirectedGraph getDominanceGraph()
      Deprecated, for removal: This API element is subject to removal in a future version.
      This iterates through the vertices of our graph and gets the dominator for each. In a new graph - dom - it adds each vertex and an edge between the vertex and its dominator. It returns dom, the dominance graph.

    • addToPaths

      public Vertex addToPaths(Vertex v, Vector singlePath)
      Deprecated, for removal: This API element is subject to removal in a future version.
      This function originally did not return anything. It returns a vertex for the purpose of keeping track of which vertex we left off on. So if we backtrack, we can copy the portion of the previous path that is contained in the path we are currently construction. I tried to do this without passing v as a parameter and it did not work. Something funny happened I suppose with JAVA and pointers. This function simply adds to singlePath until there are no more white children which means we've either reached a sink, or the only vertices left are repeated meaning we have a loop.

    • whitenChildren

      public void whitenChildren(Vertex v)
      Deprecated, for removal: This API element is subject to removal in a future version.
      Whitens the children of v. It is only called after v has no more children left and we have backtracked to the calling parent of v. This is to ensure that we don't miss out on any paths that contain a child of v which has other parents.

    • setColor

      public void setColor(Vertex v, int color)
      Deprecated, for removal: This API element is subject to removal in a future version.

    • getColor

      public int getColor(Vertex v)
      Deprecated, for removal: This API element is subject to removal in a future version.

    • setCallingParent

      public void setCallingParent(Vertex v, Vertex parent)
      Deprecated, for removal: This API element is subject to removal in a future version.

    • getCallingParent

      public Vertex getCallingParent(Vertex v)
      Deprecated, for removal: This API element is subject to removal in a future version.

    • setType

      public void setType(Vertex v, String type)
      Deprecated, for removal: This API element is subject to removal in a future version.

    • getType

      public String getType(KeyedObject o)
      Deprecated, for removal: This API element is subject to removal in a future version.

    • setWeight

      public void setWeight(Vertex v, double weight)
      Deprecated, for removal: This API element is subject to removal in a future version.

    • getWeight

      public double getWeight(Vertex v)
      Deprecated, for removal: This API element is subject to removal in a future version.

    • setWeight

      public void setWeight(Edge e, double weight)
      Deprecated, for removal: This API element is subject to removal in a future version.

    • getWeight

      public double getWeight(Edge e)
      Deprecated, for removal: This API element is subject to removal in a future version.