Dominator Tree
(graph/dominator_tree.hpp)

• View this file on GitHub
• Last update: 2024-01-08 15:10:29+09:00
• Include: #include "graph/dominator_tree.hpp"

Description

有向グラフ $G$ において，頂点 $v$ が頂点 $w$ の dominator であるとは，$G$ における任意の $s-w$ パス ($s$ は source vertex) が $v$ を通ることである．

$v$ が $w$ の immediate dominator であるとは，$v$ が $w$ の dominator であり，かつ $v$ が $w$ の任意の dominator $u$ を dominate しないことである．これは $w$ に対して一意に定まる．

$G$ の dominator tree は，$G$ で $v$ が $w$ の immediate dominator であるときかつそのときに限り有向辺 $(v, w)$ が存在するような有向木である．

Operations

• vector<int> dominator_tree(vector<vector<int>> G, int s)
  • グラフ $G$ の隣接リストと source vertex $s$ が与えられたとき，各頂点 $v$ の immediate dominator を返す．$v$ が $s$ なら到達できない場合 -1 を返す．$s$ の immediate dominator は $s$ とする．
  • 時間計算量: $O((V + E) \log V)$

Reference

• Dominator Tree of a Directed Graph
• Dominator Tree

Verified with

• test/yosupo/dominatortree.test.cpp

Code

#pragma once
#include <algorithm>
#include <numeric>
#include <vector>

std::vector<int> dominator_tree(const std::vector<std::vector<int>>& G, int s) {
    const int n = G.size();

    // label nodes with the arrival times of a dfs
    std::vector<int> sdom(n, -1), par(n, -1), vs;
    vs.reserve(n);
    int k = 0;

    auto dfs = [&](auto& dfs, int v) -> void {
        sdom[v] = k++;
        vs.push_back(v);
        for (int c : G[v]) {
            if (sdom[c] == -1) {
                par[c] = v;
                dfs(dfs, c);
            }
        }
    };

    dfs(dfs, s);

    std::vector<std::vector<int>> G_rev(n);
    for (int u = 0; u < n; ++u) {
        if (sdom[u] == -1) continue;
        for (int v : G[u]) {
            G_rev[v].push_back(u);
        }
    }

    // union find with path compression
    std::vector<int> dsu(n), val(n);
    std::iota(dsu.begin(), dsu.end(), 0);
    std::iota(val.begin(), val.end(), 0);

    auto unite = [&](int u, int v) {  // make u the parent of v
        dsu[v] = u;
    };

    auto find = [&](auto& find, int v) -> int {
        if (v == dsu[v]) return v;
        int r = find(find, dsu[v]);
        if (sdom[val[v]] > sdom[val[dsu[v]]]) {
            val[v] = val[dsu[v]];
        }
        return dsu[v] = r;
    };

    auto eval = [&](int v) {  // return the ancestor of v with minimum sdom
        find(find, v);
        return val[v];
    };

    // calculate sdom
    std::vector<int> us(n);
    std::vector<std::vector<int>> bucket(n);
    for (int i = k - 1; i > 0; --i) {
        int w = vs[i];
        for (int v : G_rev[w]) {
            sdom[w] = std::min(sdom[w], sdom[eval(v)]);
        }
        bucket[vs[sdom[w]]].push_back(w);
        for (int v : bucket[par[w]]) {
            us[v] = eval(v);
        }
        bucket[par[w]].clear();
        unite(par[w], w);
    }

    // calculate idom
    std::vector<int> idom(n, -1);
    idom[s] = sdom[s];
    for (int i = 1; i < k; ++i) {
        int w = vs[i], u = us[w];
        idom[w] = (sdom[w] == sdom[u] ? sdom[w] : idom[u]);
    }
    for (int v : vs) {
        idom[v] = vs[idom[v]];
    }
    return idom;
}

#line 2 "graph/dominator_tree.hpp"
#include <algorithm>
#include <numeric>
#include <vector>

std::vector<int> dominator_tree(const std::vector<std::vector<int>>& G, int s) {
    const int n = G.size();

    // label nodes with the arrival times of a dfs
    std::vector<int> sdom(n, -1), par(n, -1), vs;
    vs.reserve(n);
    int k = 0;

    auto dfs = [&](auto& dfs, int v) -> void {
        sdom[v] = k++;
        vs.push_back(v);
        for (int c : G[v]) {
            if (sdom[c] == -1) {
                par[c] = v;
                dfs(dfs, c);
            }
        }
    };

    dfs(dfs, s);

    std::vector<std::vector<int>> G_rev(n);
    for (int u = 0; u < n; ++u) {
        if (sdom[u] == -1) continue;
        for (int v : G[u]) {
            G_rev[v].push_back(u);
        }
    }

    // union find with path compression
    std::vector<int> dsu(n), val(n);
    std::iota(dsu.begin(), dsu.end(), 0);
    std::iota(val.begin(), val.end(), 0);

    auto unite = [&](int u, int v) {  // make u the parent of v
        dsu[v] = u;
    };

    auto find = [&](auto& find, int v) -> int {
        if (v == dsu[v]) return v;
        int r = find(find, dsu[v]);
        if (sdom[val[v]] > sdom[val[dsu[v]]]) {
            val[v] = val[dsu[v]];
        }
        return dsu[v] = r;
    };

    auto eval = [&](int v) {  // return the ancestor of v with minimum sdom
        find(find, v);
        return val[v];
    };

    // calculate sdom
    std::vector<int> us(n);
    std::vector<std::vector<int>> bucket(n);
    for (int i = k - 1; i > 0; --i) {
        int w = vs[i];
        for (int v : G_rev[w]) {
            sdom[w] = std::min(sdom[w], sdom[eval(v)]);
        }
        bucket[vs[sdom[w]]].push_back(w);
        for (int v : bucket[par[w]]) {
            us[v] = eval(v);
        }
        bucket[par[w]].clear();
        unite(par[w], w);
    }

    // calculate idom
    std::vector<int> idom(n, -1);
    idom[s] = sdom[s];
    for (int i = 1; i < k; ++i) {
        int w = vs[i], u = us[w];
        idom[w] = (sdom[w] == sdom[u] ? sdom[w] : idom[u]);
    }
    for (int v : vs) {
        idom[v] = vs[idom[v]];
    }
    return idom;
}

Back to top page