R igraph 手册页

dominator_tree {igraph}

R 文档

支配树

描述

有向图的支配树。

用法

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

参数

图	一个有向图。如果它不是一个流图，并且包含一些从根顶点不可达的顶点，那么这些顶点将被收集并作为结果的一部分返回。
root	根（或源）顶点的 ID，这将是树的根。
模式	常量，必须是 'in' 或 'out'。 如果是 'in'，那么所有方向都被认为是与输入图中原始方向相反的。

详细信息

流图是一个有向图，具有一个特殊的起始（或根）顶点 r，使得对于任何顶点 v，都存在一条从 r 到 v 的路径。顶点 v 支配另一个顶点 w (不等于 v)，如果从 r 到 w 的每条路径都包含 v。顶点 v 是 w 的直接支配者，v=\textrm{idom}(w)，如果 v 支配 w 并且 w 的每个其他支配者都支配 v。边 {(\textrm{idom}(w), w)| w \ne r} 形成一棵有向树，以 r 为根，称为图的支配树。顶点 v 支配顶点 w 当且仅当 v 是支配树中 w 的祖先。

此函数实现 Lengauer-Tarjan 算法来构造有向图的支配树。有关详细信息，请参见下面的参考。

值

具有以下组件的列表

dom	一个数值向量，给出每个顶点的直接支配者。 对于从根无法到达的顶点，它包含 NaN。 对于根顶点本身，它包含负一。
domtree	一个图对象，即支配树。 它的顶点 ID 与输入图的顶点 ID 相同。 孤立顶点是从根无法到达的顶点。
leftout	一个数值向量，包含从根无法到达的顶点 ID。

作者

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)

---