Package ghidra.util.graph
Class Dominator
- java.lang.Object
-
- ghidra.util.graph.DirectedGraph
-
- ghidra.util.graph.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 Summary
Constructors Constructor Description Dominator()
Dominator(int vertexCapacity, int edgeCapacity)
Dominator(DirectedGraph cg)
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description Vertex
addToPaths(Vertex v, java.util.Vector singlePath)
This function originally did not return anything.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.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.Vertex
backTrack(Vertex v)
this aids in going back to the parent from which a vertex was accessed in the depth first searchVertex
getCallingParent(Vertex v)
int
getColor(Vertex v)
DirectedGraph
getDominanceGraph()
This iterates through the vertices of our graph and gets the dominator for each.Vertex
getDominator(Vertex v)
this returns the vertex that is the dominatorjava.lang.String
getType(KeyedObject o)
double
getWeight(Edge e)
double
getWeight(Vertex v)
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.void
setCallingParent(Vertex v, Vertex parent)
void
setColor(Vertex v, int color)
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.void
setType(Vertex v, java.lang.String type)
void
setWeight(Edge e, double weight)
void
setWeight(Vertex v, double weight)
void
whitenChildren(Vertex v)
Whitens the children of v.-
Methods inherited from class ghidra.util.graph.DirectedGraph
add, add, areRelatedAs, assignVerticesToStrongComponents, clear, complexityDepth, contains, contains, containsAsSubgraph, copy, copyAll, copyEdge, copyEdgeAttributeValues, copyVertex, copyVertexAttributeValues, degree, descendantsGraph, edgeAttributes, edgeIterator, edges, getAncestors, getChildren, getChildren, getComponentContaining, getComponents, getDescendants, getDescendants, getEdgeArray, getEdgeAttribute, getEdgeProperty, getEdges, getEdges, getEdgeWithKey, getEntryPoints, getIncomingEdges, getLevels, getNeighborhood, getNeighborhood, getOutgoingEdges, getParents, getParents, getReferent, getSinks, getSources, getVertexArray, getVertexAttribute, getVertexProperty, getVertexWithKey, getVertices, getVerticesHavingReferent, getVerticesInContainingComponent, incomingEdges, inDegree, inducedSubgraph, intersectionWith, inValence, join, loopDegree, numEdges, numLoops, numSinks, numSources, numVertices, outDegree, outgoingEdges, outValence, remove, remove, selfEdges, setEdgeProperty, setVertexProperty, unionWith, valence, vertexAttributes, vertexIterator, vertices, verticesUnreachableFromSources, verts2referentSet
-
-
-
-
Constructor Detail
-
Dominator
public Dominator(int vertexCapacity, int edgeCapacity)
-
Dominator
public Dominator()
-
Dominator
public Dominator(DirectedGraph cg)
-
-
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
-
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)
-
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)
-
-