## soot.toolkits.graph Class MHGDominatorsFinder<N>

```java.lang.Object
soot.toolkits.graph.MHGDominatorsFinder<N>
```
All Implemented Interfaces:
DominatorsFinder<N>
Direct Known Subclasses:
MHGPostDominatorsFinder

`public class MHGDominatorsFinder<N>extends Objectimplements DominatorsFinder<N>`

Calculate dominators for basic blocks.

Uses the algorithm contained in Dragon book, pg. 670-1.

```       D(n0) := { n0 }
for n in N - { n0 } do D(n) := N;
while changes to any D(n) occur do
for n in N - {n0} do
D(n) := {n} U (intersect of D(p) over all predecessors p of n)
```
2007/07/03 - updated to use `BitSet`s instead of `HashSet`s, as the most expensive operation in this algorithm used to be cloning of the fullSet, which is very cheap for `BitSet`s.

Author:
Navindra Umanee, Eric Bodden

Field Summary
`protected  BitSet` `fullSet`

`protected  DirectedGraph<N>` `graph`

`protected  List<N>` `heads`

`protected  Map<Integer,N>` `indexToNode`

`protected  int` `lastIndex`

`protected  Map<N,BitSet>` `nodeToFlowSet`

`protected  Map<N,Integer>` `nodeToIndex`

Constructor Summary
`MHGDominatorsFinder(DirectedGraph<N> graph)`

Method Summary
`protected  void` `doAnalysis()`

` List<N>` `getDominators(Object node)`
Returns a list of dominators for the given node in the graph.
` DirectedGraph<N>` `getGraph()`
Returns the graph to which the analysis pertains.
` N` `getImmediateDominator(Object node)`
Returns the immediate dominator of node or null if the node has no immediate dominator.
`protected  int` `indexOf(N o)`

` boolean` ```isDominatedBy(N node, N dominator)```
True if "node" is dominated by "dominator" in the graph.
` boolean` ```isDominatedByAll(N node, Collection<N> dominators)```
True if "node" is dominated by all nodes in "dominators" in the graph.

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Field Detail

### graph

`protected DirectedGraph<N> graph`

### fullSet

`protected BitSet fullSet`

`protected List<N> heads`

### nodeToFlowSet

`protected Map<N,BitSet> nodeToFlowSet`

### nodeToIndex

`protected Map<N,Integer> nodeToIndex`

### indexToNode

`protected Map<Integer,N> indexToNode`

### lastIndex

`protected int lastIndex`
Constructor Detail

### MHGDominatorsFinder

`public MHGDominatorsFinder(DirectedGraph<N> graph)`
Method Detail

### doAnalysis

`protected void doAnalysis()`

### indexOf

`protected int indexOf(N o)`

### getGraph

`public DirectedGraph<N> getGraph()`
Description copied from interface: `DominatorsFinder`
Returns the graph to which the analysis pertains.

Specified by:
`getGraph` in interface `DominatorsFinder<N>`

### getDominators

`public List<N> getDominators(Object node)`
Description copied from interface: `DominatorsFinder`
Returns a list of dominators for the given node in the graph.

Specified by:
`getDominators` in interface `DominatorsFinder<N>`

### getImmediateDominator

`public N getImmediateDominator(Object node)`
Description copied from interface: `DominatorsFinder`
Returns the immediate dominator of node or null if the node has no immediate dominator.

Specified by:
`getImmediateDominator` in interface `DominatorsFinder<N>`

### isDominatedBy

```public boolean isDominatedBy(N node,
N dominator)```
Description copied from interface: `DominatorsFinder`
True if "node" is dominated by "dominator" in the graph.

Specified by:
`isDominatedBy` in interface `DominatorsFinder<N>`

### isDominatedByAll

```public boolean isDominatedByAll(N node,
Collection<N> dominators)```
Description copied from interface: `DominatorsFinder`
True if "node" is dominated by all nodes in "dominators" in the graph.

Specified by:
`isDominatedByAll` in interface `DominatorsFinder<N>`