dominator_tree

クラス · 支配木（Lengauer-Tarjan 法）

template <graph_type G>
struct dominator_tree;

概要

支配木（Lengauer-Tarjan 法）

始点 root から到達可能な各頂点 $v$ について、その直接支配点 (immediate dominator) $\mathrm{idom}(v)$ を計算する。root から $v$ へのすべての経路が必ず通る頂点のうち、$v$ に最も近いものが $\mathrm{idom}(v)$。 $\mathrm{idom}(root) = root$ とする。root から到達不能な頂点は $-1$。辺の重みは無視する。計算量はほぼ $O((V + E)\alpha(V))$。

テンプレートパラメータ

名前	説明
`G`	グラフ型（`list_graph<T>` / `csr_graph<T>` のいずれでも可）

計算量

構築は $O((V+E)\alpha(V))$、問合せは $O(1)$

構築・破棄

名前	説明	計算量
`(constructor)`	始点rootからの支配木を構築する	$O((V+E)\alpha(V))$

メンバ関数

名前	説明	計算量
`idom`	(1) 直接支配点を取得する（root は自分自身、到達不能な頂点は -1） (2) 直接支配点の配列を取得する	$O(1)$

メンバの詳細

(constructor)

dominator_tree(const G &g, int root = 0);

始点rootからの支配木を構築する

パラメータ g: 有向グラフ
パラメータ root: 支配関係の始点
計算量: $O((V+E)\alpha(V))$

idom

// (1)
int idom(int v) const;

// (2)
const std::vector<int> &idom() const;

(1) 直接支配点を取得する（root は自分自身、到達不能な頂点は -1）

計算量: $O(1)$

(2) 直接支配点の配列を取得する

計算量: $O(1)$