org.evosuite.graphs.cdg

Class DominatorTree<V>

java.lang.Object

org.evosuite.graphs.EvoSuiteGraph<org.evosuite.graphs.cdg.DominatorNode<V>,org.jgrapht.graph.DefaultEdge>

org.evosuite.graphs.cdg.DominatorTree<V>

public class DominatorTree<V>
extends EvoSuiteGraph<org.evosuite.graphs.cdg.DominatorNode<V>,org.jgrapht.graph.DefaultEdge>

Given a CFG this class computes the immediateDominators and the dominatingFrontiers for each CFG vertex The current algorithm to determine the immediateDominators runs in time O(e*log n) where e is the number of control flow edges and n the number of CFG vertices and is taken from: "A Fast Algorithm for Finding Dominators in a Flowgraph" THOMAS LENGAUER and ROBERT ENDRE TARJAN 1979, Stanford University DOI: 10.1145/357062.357071 http://portal.acm.org/citation.cfm?doid=357062.357071 The algorithm for computing the dominatingFrontiers when given the immediateDominators is taken from "Efficiently Computing Static Single Assignment Form and the Control Dependence Graph" RON CYTRON, JEANNE FERRANTE, BARRY K. ROSEN, and MARK N. WEGMAN IBM Research Division and F. KENNETH ZADECK Brown University 1991

Author:

Andre Mis

Field Summary

Fields inherited from class org.evosuite.graphs.EvoSuiteGraph

edgeClass, graph, graphId

Constructor Summary

Constructors

Constructor and Description
DominatorTree(ControlFlowGraph<V> cfg) Will start the computation of all immediateDominators for the given CFG which can later be retrieved via getImmediateDominator()

Method Summary

Modifier and Type	Method and Description
Set<V>	getDominatingFrontiers(V v) Getter for the field dominatingFrontiers.
V	getImmediateDominator(V v) Given a node of this objects CFG this method returns it's previously computed immediateDominator The immediateDominator iDom of a node v has the following properties: 1) iDom dominates v 2) every other dominator of v dominates iDom A node w dominates v or is a dominator of v if and only if every path from the CFG's entryPoint to v contains w
String	getName() getName

Methods inherited from class org.evosuite.graphs.EvoSuiteGraph

addEdge, addEdge, addVertex, addVertices, addVertices, computeReverseJGraph, containsEdge, containsEdge, containsVertex, determineBranches, determineConnectedVertices, determineEntryPoints, determineExitPoints, determineJoins, dotSubFolder, edgeCount, edgeSet, getChildren, getDistance, getEdge, getEdgeSource, getEdgeTarget, getIsolatedNodes, getNodesWithoutChildren, getParents, getRandomVertex, getSingleChild, hasNPartentsMChildren, incomingEdgesOf, inDegreeOf, isConnected, isDirectSuccessor, isEmpty, outDegreeOf, outgoingEdgesOf, redirectEdges, redirectEdgeSource, redirectEdgeTarget, redirectIncomingEdges, redirectOutgoingEdges, registerEdgeAttributeProvider, registerVertexAttributeProvider, toDot, toFileString, vertexCount, vertexSet

Methods inherited from class java.lang.Object

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

Constructor Detail

DominatorTree

public DominatorTree(ControlFlowGraph<V> cfg)

Will start the computation of all immediateDominators for the given CFG which can later be retrieved via getImmediateDominator()

Parameters:

cfg - a ControlFlowGraph object.

Method Detail

getImmediateDominator

public V getImmediateDominator(V v)

Given a node of this objects CFG this method returns it's previously computed immediateDominator The immediateDominator iDom of a node v has the following properties: 1) iDom dominates v 2) every other dominator of v dominates iDom A node w dominates v or is a dominator of v if and only if every path from the CFG's entryPoint to v contains w

Parameters:

v - A node within this objects CFG for wich the immediateDominator is to be returned

Returns:

a V object.

getDominatingFrontiers

public Set<V> getDominatingFrontiers(V v)

Getter for the field dominatingFrontiers.

Parameters:

v - a V object.

Returns:

a Set object.

getName

public String getName()

getName

Overrides:

getName in class EvoSuiteGraph<org.evosuite.graphs.cdg.DominatorNode<V>,org.jgrapht.graph.DefaultEdge>

Returns:

a String object.