Finding Dominators in Directed Graphs (Lengauer-Tarjan Algorithm)

概要

\(r\) を始点とする有向グラフ \(G = (V, A, r)\) において、各頂点 \(v\) を直近で支配する頂点 (an immediate dominator) を求める。 始点 \(r\) から頂点 \(v\) に到達する際に必ず頂点 \(u\) を通るとき、頂点 \(u\) は頂点 \(v\) の dominator となる。

グラフ \(G\) の DFS Tree \(T\) を構築し \(T\) 上の行きがけ順を求め、そこから semidominator を求める。 そして、この semidominator を元に各頂点の immediate dominator を求める。

ここでは、頂点 \(v\) の semidominator \(sdom(v)\) は、 \(v\) への semidominator path が存在する頂点で、 (\(T\) 上の行きがけ順で) 最小となる頂点 \(u\) として定義する。
また、 semidominator path は (\(G\) 上の) path \(P = (u = v_0, v_1, ..., v_{k-1}, v_k = v)\) に対し (\(T\) 上の行きがけ順で) \(v_i > v \; (1 \le i \le k-1)\) を満たす path として定義する。

計算量

\(N = |V|\), \(M = |A|\) とする

  • simple version の EVAL-LINK を用いた実装: \(O(M \log N)\)

実装 (simple version の EVAL-LINK)

#include<vector>
using namespace std;

#define N 100003

int n;
vector<int> g[N];

vector<int> vs;
int order[N];
int prt[N];
int doms[N], semi[N];
int anc[N], label[N];
vector<int> rg[N], bucket[N];

inline void link(int v, int w) {
  anc[w] = v;
}

int compress(int v, int w) {
  if(w == anc[w]) {
    return w;
  }

  anc[v] = compress(w, anc[w]);
  if(semi[label[w]] < semi[label[v]]) {
    label[v] = label[w];
  }
  return anc[v];
}

inline int eval(int v) {
  if(v == anc[v]) {
    return v;
  }

  compress(v, anc[v]);
  return label[v];
}

void dfs(int v) {
  order[v] = vs.size();
  vs.push_back(v);
  for(int w : g[v]) {
    if(order[w] != -1) continue;
    prt[w] = v;
    dfs(w);
  }
}

void dominator(int s) {
  for(int i=0; i<n; ++i) order[i] = -1, prt[i] = -1;
  vs.reserve(n);

  dfs(s);

  for(int i=0; i<n; ++i) semi[i] = order[i], doms[i] = -1;
  for(int i=0; i<n; ++i) anc[i] = label[i] = i;

  for(int v=0; v<n; ++v) {
    for(int w : g[v]) {
      rg[w].push_back(v);
    }
  }

  for(int i=n-1; i>0; --i) {
    int w = vs[i];
    for(int v : bucket[w]) {
      int u = eval(v);
      doms[v] = (semi[u] < semi[v] ? u : w);
    }
    for(int v : rg[w]) {
      int u = eval(v);
      if(semi[u] < semi[w]) {
        semi[w] = semi[u];
      }
    }
    if(vs[semi[w]] != prt[w]) {
      bucket[vs[semi[w]]].push_back(w);
    } else {
      doms[w] = prt[w];
    }
    link(prt[w], w);
  }
  for(int v : bucket[s]) doms[v] = s;

  for(int i=1; i<n; ++i) {
    int w = vs[i];
    if(doms[w] != vs[semi[w]]) {
      doms[w] = doms[doms[w]];
    }
  }
  doms[s] = s;
}

Verified

  • AOJ: "0294: Catch a Thief": source (C++11, 0.17sec)

参考

  • Lengauer, Thomas, and Robert Endre Tarjan. "A fast algorithm for finding dominators in a flowgraph." ACM Transactions on Programming Languages and Systems (TOPLAS) 1.1 (1979): 121-141.

  • Georgiadis, Loukas, Robert E. Tarjan, and Renato F. Werneck. "Finding dominators in practice." Journal of Graph Algorithms and Applications 10.1 (2006): 69-94.

戻る