# dominator.tree

##### Dominator tree

Dominator tree of a directed graph.

- Keywords
- graphs

##### Usage

`dominator.tree (graph, root, mode = c("out", "in"))`

##### Arguments

- graph
- A directed graph. If it is not a flowgraph, and it contains some vertices not reachable from the root vertex, then these vertices will be collected and returned as part of the result.
- root
- The id of the root (or source) vertex, this will be the root of the tree.
- mode
- Constant, must be
or`in`

. If it is`out`

, then all directions are considered as opposite to the original one in the input graph.`in`

##### Details

A flowgraph is a directed graph with a distinguished start (or root) vertex $r$, such that for any vertex $v$, there is a path from $r$ to $v$. A vertex $v$ dominates another vertex $w$ (not equal to $v$), if every path from $r$ to $w$ contains $v$. Vertex $v$ is the immediate dominator or $w$, $v=\textrm{idom}(w)$, if $v$ dominates $w$ and every other dominator of $w$ dominates $v$. The edges ${(\textrm{idom}(w), w)| w \ne r}$ form a directed tree, rooted at $r$, called the dominator tree of the graph. Vertex $v$ dominates vertex $w$ if and only if $v$ is an ancestor of $w$ in the dominator tree.

This function implements the Lengauer-Tarjan algorithm to construct the dominator tree of a directed graph. For details see the reference below.

##### Value

- A list with components:
dom A numeric vector giving the immediate dominators for each vertex. For vertices that are unreachable from the root, it contains `NaN`

. For the root vertex itself it contains minus one.domtree A graph object, the dominator tree. Its vertex ids are the as the vertex ids of the input graph. Isolate vertices are the ones that are unreachable from the root. leftout A numeric vector containing the vertex ids that are unreachable from the root.

##### concept

Domintor tree

##### References

Thomas Lengauer, Robert Endre Tarjan: A fast algorithm
for finding dominators in a flowgraph, *ACM Transactions on
Programming Languages and Systems (TOPLAS)* I/1, 121--141, 1979.

##### Examples

```
## The example from the paper
g <- graph.formula(R-+A:B:C, A-+D, B-+A:D:E, C-+F:G, D-+L,
E-+H, F-+I, G-+I:J, H-+E:K, I-+K, J-+I,
K-+I:R, L-+H)
dtree <- dominator.tree(g, root="R")
layout <- layout.reingold.tilford(dtree$domtree, root="R")
layout[,2] <- -layout[,2]
if (interactive()) {
plot(dtree$domtree, layout=layout, vertex.label=V(dtree$domtree)$name)
}
```

*Documentation reproduced from package igraph, version 0.6.5-2, License: GPL (>= 2)*