|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectpolyglot.ext.ibex.lr.Dominators
Dominators finds the dominators of a RootedGraph
The algorithm used is Purdum-Moore. It isn't as fast as Lengauer-Tarjan, but it's a lot simpler.
Constructor Summary | |
Dominators(polyglot.ext.ibex.lr.RootedGraph graph)
Calculates which nodes in a graph dominate which other nodes. |
Method Summary | |
java.util.BitSet |
allDominators(Node i)
Return the set of all dominators of i . |
java.util.BitSet |
DF(Node i)
Return the set of nodes in the dominance frontier of node i . |
boolean |
dominates(Node j,
Node i)
Return true if j dominates i . |
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Constructor Detail |
public Dominators(polyglot.ext.ibex.lr.RootedGraph graph)
graph
- The graph that is used to find the dominator tree.Method Detail |
public boolean dominates(Node j, Node i)
j
dominates i
.
public java.util.BitSet allDominators(Node i)
i
.
public java.util.BitSet DF(Node i)
i
.
The dominance frontier of a node x is the set of all nodes w such that x dominates a predecessor of w, but does not strictly dominate w. Essentially, nodes in the dominance frontier have one parent that is dominated by x and at least one parent that is not dominated by x.
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |