Class NumberedDominators<T>

java.lang.Object

com.ibm.wala.util.graph.dominators.Dominators<T>

com.ibm.wala.util.graph.dominators.NumberedDominators<T>

public class NumberedDominators<T>
extends Dominators<T>

Calculate dominators using Langauer and Tarjan's fastest algorithm. TOPLAS 1(1), July 1979. This implementation uses path compression and results in a O(e * alpha(e,n)) complexity, where e is the number of edges in the CFG and n is the number of nodes.

Sources: TOPLAS article, Muchnick book

Nested Class Summary

Nested classes/interfaces inherited from class com.ibm.wala.util.graph.dominators.Dominators

Dominators.DominatorInfo

Field Summary

Fields inherited from class com.ibm.wala.util.graph.dominators.Dominators

G, reachableNodeCount, root

Constructor Summary

Constructors

Constructor	Description
NumberedDominators(NumberedGraph<T> G, T root)

Method Summary

Modifier and Type	Method	Description
protected final Dominators<T>.DominatorInfo	getInfo(@Nullable T node)

Methods inherited from class com.ibm.wala.util.graph.dominators.Dominators

analyze, dominators, dominatorTree, getIdom, isDominatedBy, make, toString

Methods inherited from class java.lang.Object

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

Constructor Details

NumberedDominators

public NumberedDominators(NumberedGraph<T> G,
 T root)
                   throws IllegalArgumentException

Throws:

IllegalArgumentException

Method Details

getInfo

protected final Dominators<T>.DominatorInfo getInfo(@Nullable T node)

Specified by:

getInfo in class Dominators<T>