1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
% Generated by roxygen2 (4.1.1): do not edit by hand
% Please edit documentation in R/flow.R
\name{dominator_tree}
\alias{dominator.tree}
\alias{dominator_tree}
\title{Dominator tree}
\usage{
dominator_tree(graph, root, mode = c("out", "in"))
}
\arguments{
\item{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.}
\item{root}{The id of the root (or source) vertex, this will be the root of
the tree.}
\item{mode}{Constant, must be \sQuote{\code{in}} or \sQuote{\code{out}}. If
it is \sQuote{\code{in}}, then all directions are considered as opposite to
the original one in the input graph.}
}
\value{
A list with components: \item{dom}{ A numeric vector giving the
immediate dominators for each vertex. For vertices that are unreachable from
the root, it contains \code{NaN}. For the root vertex itself it contains
minus one. } \item{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. } \item{leftout}{ A numeric vector
containing the vertex ids that are unreachable from the root. }
}
\description{
Dominator tree of a directed graph.
}
\details{
A flowgraph is a directed graph with a distinguished start (or root) vertex
\eqn{r}, such that for any vertex \eqn{v}, there is a path from \eqn{r} to
\eqn{v}. A vertex \eqn{v} dominates another vertex \eqn{w} (not equal to
\eqn{v}), if every path from \eqn{r} to \eqn{w} contains \eqn{v}. Vertex
\eqn{v} is the immediate dominator or \eqn{w},
\eqn{v=\textrm{idom}(w)}{v=idom(w)}, if \eqn{v} dominates \eqn{w} and every
other dominator of \eqn{w} dominates \eqn{v}. The edges
\eqn{{(\textrm{idom}(w), w)| w \ne r}}{{(idom(w),w)| w is not r}} form a
directed tree, rooted at \eqn{r}, called the dominator tree of the graph.
Vertex \eqn{v} dominates vertex \eqn{w} if and only if \eqn{v} is an
ancestor of \eqn{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.
}
\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)
}
\author{
Gabor Csardi \email{csardi.gabor@gmail.com}
}
\references{
Thomas Lengauer, Robert Endre Tarjan: A fast algorithm for
finding dominators in a flowgraph, \emph{ACM Transactions on Programming
Languages and Systems (TOPLAS)} I/1, 121--141, 1979.
}
\keyword{graphs}
|
