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)\)

  • sophisticated version の EVAL-LINK を用いた実装: \(O(M \alpha(M, N))\) (\(\alpha\) はアッカーマン関数の逆数)

実装 (simple version の EVAL-LINK)

def dfs_preorder(N, G, s):
    order = [-1]*N
    order[s] = 0
    vs = [0]*N
    vs[0] = s
    prt = [-1]*N
    stk = [s]
    it = [0]*N

    cur = 0
    while stk:
        v = stk[-1]
        while it[v] < len(G[v]):
            w = G[v][it[v]]; it[v] += 1
            if order[w] == -1:
                prt[w] = v
                stk.append(w)

                order[w] = cur = cur+1
                vs[cur] = w
                break
        else:
            stk.pop()
    return vs, order, prt

def dominator(N, G, s):
    vs, semi, prt = dfs_preorder(N, G, s)
    doms = [-1]*N

    RG = [[] for i in range(N)]
    for v in range(N):
        for w in G[v]:
            RG[w].append(v)
    bucket = [[] for i in range(N)]

    *anc, = range(N)
    *label, = range(N)

    def s_link(v, w):
        anc[w] = v
    def s_eval(v):
        if v == anc[v]:
            return v
        compress(v, anc[v])
        return label[v]
    def compress(v, w):
        if w == anc[w]:
            return w
        anc[v] = u = compress(w, anc[w])
        if semi[label[w]] < semi[label[v]]:
            label[v] = label[w]
        return u

    for w in reversed(vs[1:]):
        for v in bucket[w]:
            u = s_eval(v)
            if semi[u] < semi[v]:
                doms[v] = u
            else:
                doms[v] = w
        for v in RG[w]:
            su = semi[s_eval(v)]
            if su < semi[w]:
                semi[w] = su
        if vs[semi[w]] != prt[w]:
            bucket[vs[semi[w]]].append(w)
        else:
            doms[w] = prt[w]
        s_link(prt[w], w)
    for v in bucket[s]:
        doms[v] = s
    for w in vs[1:]:
        if doms[w] != vs[semi[w]]:
            doms[w] = doms[doms[w]]
    doms[s] = s
    return doms

Verified

  • AOJ: "0294: Catch a Thief": source (Python3, 1.31sec)

実装 (sophisticated version の EVAL-LINK)

def dfs_preorder(N, G, s):
    order = [-1]*N
    order[s] = 0
    vs = [0]*N
    vs[0] = s
    prt = [-1]*N
    stk = [s]
    it = [0]*N

    cur = 0
    while stk:
        v = stk[-1]
        while it[v] < len(G[v]):
            w = G[v][it[v]]; it[v] += 1
            if order[w] == -1:
                prt[w] = v
                stk.append(w)

                order[w] = cur = cur+1
                vs[cur] = w
                break
        else:
            stk.pop()
    return vs, order, prt

def dominator(N, G, s):
    vs, semi, prt = dfs_preorder(N, G, s)
    doms = [-1]*N

    RG = [[] for i in range(N)]
    for v in range(N):
        for w in G[v]:
            RG[w].append(v)
    bucket = [[] for i in range(N)]

    *anc, = range(N)
    *label, = range(N)
    size = [1]*N; child = [-1]*N

    def s_link(v, w):
        s = w
        while child[s] != -1 and semi[label[w]] < semi[label[child[s]]]:
            ccsz = (size[child[child[s]]] if child[child[s]] != -1 else 0)
            if size[s] + ccsz >= 2*size[child[s]]:
                anc[child[s]] = s
                child[s] = child[child[s]]
            else:
                size[child[s]] = size[s]
                anc[s] = s = child[s]
        label[s] = label[w]
        size[v] += size[w]
        if size[v] < 2*size[w]:
            s, child[v] = child[v], s
        while s != -1:
            anc[s] = v
            s = child[s]
    def s_eval(v):
        if anc[v] == v:
            return label[v]
        compress(v, anc[v])
        if semi[label[anc[v]]] >= semi[label[v]]:
            return label[v]
        return label[anc[v]]
    def compress(v, w):
        if w == anc[w]:
            return w
        anc[v] = u = compress(w, anc[w])
        if semi[label[w]] < semi[label[v]]:
            label[v] = label[w]
        return u

    for w in reversed(vs[1:]):
        for v in bucket[w]:
            u = s_eval(v)
            if semi[u] < semi[v]:
                doms[v] = u
            else:
                doms[v] = w
        for v in RG[w]:
            su = semi[s_eval(v)]
            if su < semi[w]:
                semi[w] = su
        if vs[semi[w]] != prt[w]:
            bucket[vs[semi[w]]].append(w)
        else:
            doms[w] = prt[w]
        s_link(prt[w], w)
    for v in bucket[s]:
        doms[v] = s
    for w in vs[1:]:
        if doms[w] != vs[semi[w]]:
            doms[w] = doms[doms[w]]
    doms[s] = s
    return doms

Verified

  • AOJ: "0294: Catch a Theif": source (Python3, 1.26sec)

参考

  • 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.

戻る