Use this if you are using igraph from R
dominator_tree {igraph} | R Documentation |
Dominator tree of a directed graph.
dominator_tree(graph, root, mode = c("out", "in", "all", "total"))
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 ‘ |
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.
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 |
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. |
Gabor Csardi csardi.gabor@gmail.com
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.
## 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)