# R igraph manual pages

Use this if you are using igraph from R

 dominator_tree {igraph} R Documentation

## Dominator tree

### Description

Dominator tree of a directed graph.

### Usage

``````dominator_tree(graph, root, mode = c("out", "in", "all", "total"))
``````

### 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 ‘`in`’ or ‘`out`’. If it is ‘`in`’, then all directions are considered as opposite to the original one in the input graph.

### 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.

### Author(s)

Gabor Csardi csardi.gabor@gmail.com

### 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_from_literal(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_as_tree(dtree\$domtree, root="R")
layout[,2] <- -layout[,2]
plot(dtree\$domtree, layout=layout, vertex.label=V(dtree\$domtree)\$name)
``````

[Package igraph version 1.3.1 Index]