4.2.4 Dominator Tree (Lengauer-Tarjan)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

/*

Given a directed graph and a start node, find the immediate dominator of every node reachable from
the start. A node `u` dominates node `v` if every path from the start to `v` passes through `u`.
The immediate dominator `idom[v]` is the closest strict dominator of `v`; these parent links form
the dominator tree rooted at the start. Dominator trees are useful in control-flow graphs, program
analysis, and reachability problems with unavoidable checkpoints.

Lengauer-Tarjan's algorithm numbers vertices by DFS order, computes each reachable node's
semidominator using a disjoint-set structure with path compression, and then resolves immediate
dominators from semidominator buckets.

- `Dominators(n)` constructs a directed graph of `n` nodes numbered [0, `n`).
- `add_edge(u, v)` adds a directed edge from `u` to `v`.
- `find_dominators(start)` returns a vector `idom` where `idom[start]` = `start`, `idom[v]` is the
  immediate dominator of reachable node `v`, and `idom[v]` $= -1$ if `v` is unreachable.

Time Complexity:
- O(max(n, m) log n) per call to `find_dominators()` in this path-compressed implementation, where
  $n$ is the number of nodes and $m$ is the number of edges.

Space Complexity:
- O(max(n, m)) for the graph and auxiliary arrays.
- O(n) auxiliary stack space for the DFS.

*/

#include <algorithm>
#include <vector>

class Dominators {
  std::vector<std::vector<int>> adj, pred, bucket;
  std::vector<int> time, vertex, parent, sdom, idom_index, dsu, best;
  int timer;

  void dfs(int u) {
    time[u] = ++timer;
    vertex[timer] = u;
    sdom[timer] = dsu[timer] = best[timer] = timer;
    for (int v : adj[u]) {
      if (time[v] == 0) {
        dfs(v);
        parent[time[v]] = time[u];
      }
      if (time[v] != 0) {
        pred[time[v]].push_back(time[u]);
      }
    }
  }

  int find_best(int u, bool compress) {
    if (dsu[u] != u) {
      int v = find_best(dsu[u], true);
      if (sdom[v] < sdom[best[u]]) {
        best[u] = v;
      }
      if (compress) {
        dsu[u] = dsu[dsu[u]];
      }
    }
    return best[u];
  }

 public:
  explicit Dominators(int n) : adj(n), timer(0) {}

  void add_edge(int u, int v) { adj[u].push_back(v); }

  std::vector<int> find_dominators(int start) {
    int n = static_cast<int>(adj.size());
    timer = 0;
    time.assign(n, 0);
    vertex.assign(n + 1, 0);
    parent.assign(n + 1, 0);
    sdom.assign(n + 1, 0);
    idom_index.assign(n + 1, 0);
    dsu.assign(n + 1, 0);
    best.assign(n + 1, 0);
    pred.assign(n + 1, {});
    bucket.assign(n + 1, {});
    dfs(start);
    for (int i = timer; i >= 1; i--) {
      for (int v : pred[i]) {
        sdom[i] = std::min(sdom[i], sdom[find_best(v, false)]);
      }
      if (i > 1) {
        bucket[sdom[i]].push_back(i);
      }
      for (int v : bucket[i]) {
        int u = find_best(v, false);
        idom_index[v] = (sdom[u] == sdom[v]) ? sdom[v] : u;
      }
      if (i > 1) {
        dsu[i] = parent[i];
      }
    }
    std::vector<int> idom(adj.size(), -1);
    idom[start] = start;
    for (int i = 2; i <= timer; i++) {
      if (idom_index[i] != sdom[i]) {
        idom_index[i] = idom_index[idom_index[i]];
      }
      idom[vertex[i]] = vertex[idom_index[i]];
    }
    return idom;
  }
};

/*** Example Usage ***/

#include <cassert>
using namespace std;

int main() {
  Dominators g(7);
  // 0 branches through 1 and 2, then reconverges at 3 before reaching 4 and 5.
  g.add_edge(0, 1);
  g.add_edge(0, 2);
  g.add_edge(1, 3);
  g.add_edge(2, 3);
  g.add_edge(3, 4);
  g.add_edge(3, 5);
  g.add_edge(4, 6);
  g.add_edge(5, 6);
  vector<int> idom = g.find_dominators(0);
  assert(idom[0] == 0);
  assert(idom[1] == 0);
  assert(idom[2] == 0);
  assert(idom[3] == 0);
  assert(idom[4] == 3);
  assert(idom[5] == 3);
  assert(idom[6] == 3);
  assert(g.find_dominators(0) == idom);
  return 0;
}