Finding Dominators in Directed Graphs (SEMI-NCA Algorithm)

概要

\(r\) を始点とする有向グラフ \(G = (V, A, r)\) において、各頂点 \(v\) を直近で支配する頂点 (an immediate dominator) を求める。

SEMI-NCA では、各頂点 \(v\) の semidominator \(sdom(v)\) を求め、この semidominator を元に徐々に dominator tree を構築する。

各頂点 \(w\) の親頂点 \(parent(w)\) から dominator tree を遡り、 \(x \le sdom(w)\) を満たす初めの頂点 \(x\) を immediate dominator とする。

dominator tree の構築での最悪計算量は \(O(|V|^2)\) になるが、実用的なケースでは高速に動作することが期待できる。
(競プロ的には、時間がかかるケースが人為的に生成される可能性がある)

計算量

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

Lengauer-Tarjan Algorithm の simple version の LINK-EVAL を用いて semidominator を構築する場合は \(O(N^2 + M \log N)\)

実装

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, order, prt = dfs_preorder(N, G, s)
    semi = order[:]
    doms = [s]*N

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

    *anc, = range(N)
    label = order[:]
    def s_link(v, w):
        anc[w] = v
    def s_eval(v):
        if v == anc[v]:
            return label[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 label[w] < label[v]:
            label[v] = label[w]
        return u

    for w in reversed(vs[1:]):
        for v in RG[w]:
            s_min = s_eval(v)
            if s_min < semi[w]:
                semi[w] = s_min
        label[w] = semi[w]
        s_link(prt[w], w)
    doms[s] = s
    for w in vs[1:]:
        x = prt[w]
        while semi[w] < order[x]:
            x = doms[x]
        doms[w] = x
    return doms

Verified

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

参考

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

戻る