Package ghidra.util.graph

Class Dominator

  • public class Dominator
extends DirectedGraph
    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 Detail

      • Dominator

        public Dominator​(int vertexCapacity,
                 int edgeCapacity)

      • Dominator

        public Dominator()

    • Method Detail

      • backTrack

        public Vertex backTrack​(Vertex v)
        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)
        this returns the vertex that is the dominator

      • allPathsContaining

        public java.util.Vector allPathsContaining​(Vertex v)
        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​(java.util.Vector pathSet,
                              Vertex v,
                              java.util.Vector path)
        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)
        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()
        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()
        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,
                         java.util.Vector singlePath)
        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)
        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)

      • getColor

        public int getColor​(Vertex v)

      • setCallingParent

        public void setCallingParent​(Vertex v,
                             Vertex parent)

      • getCallingParent

        public Vertex getCallingParent​(Vertex v)

      • setType

        public void setType​(Vertex v,
                    java.lang.String type)

      • getType

        public java.lang.String getType​(KeyedObject o)

      • setWeight

        public void setWeight​(Vertex v,
                      double weight)

      • getWeight

        public double getWeight​(Vertex v)

      • setWeight

        public void setWeight​(Edge e,
                      double weight)

      • getWeight

        public double getWeight​(Edge e)