dominator_tree.hpp¶
Immediate dominators in a directed graph using Lengauer-Tarjan. The root dominates itself; unreachable vertices have parent -1.
Verified by dominatortree.
求流程图中每个点的直接支配点；适合判断从源点到目标的所有路径必须经过哪些点。
Implementation¶
#ifndef NOYA_DOMINATOR_TREE_HPP
#define NOYA_DOMINATOR_TREE_HPP 1
/// @complexity Time: O((V + E) log V) with the implemented link-eval structure.
/// Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <numeric>
#include <vector>
namespace noya {
/// @brief Immediate dominators in a directed graph using Lengauer-Tarjan.
/// The root dominates itself; unreachable vertices have parent -1.
inline std::vector<int>
dominator_tree(const std::vector<std::vector<int>> &graph, int root) {
const int n = int(graph.size());
assert(0 <= root && root < n);
std::vector<std::vector<int>> reverse_graph(n);
for (int vertex = 0; vertex < n; vertex++) {
for (int to : graph[vertex]) {
assert(0 <= to && to < n);
reverse_graph[to].push_back(vertex);
}
}
std::vector<int> order(n, -1), parent(n, -1), next_edge(n);
std::vector<int> vertices = {root};
std::vector<int> stack = {root};
order[root] = 0;
while (!stack.empty()) {
int vertex = stack.back();
if (next_edge[vertex] == int(graph[vertex].size())) {
stack.pop_back();
continue;
}
int to = graph[vertex][next_edge[vertex]++];
if (order[to] == -1) {
parent[to] = vertex;
order[to] = int(vertices.size());
vertices.push_back(to);
stack.push_back(to);
}
}
std::vector<int> semidominator(n), label(n), ancestor(n, -1),
candidate(n, -1);
std::iota(semidominator.begin(), semidominator.end(), 0);
std::iota(label.begin(), label.end(), 0);
std::vector<std::vector<int>> bucket(n);
std::vector<int> compression_path;
compression_path.reserve(vertices.size());
auto evaluate = [&](int start) {
compression_path.clear();
int vertex = start;
while (ancestor[vertex] != -1) {
compression_path.push_back(vertex);
vertex = ancestor[vertex];
}
for (auto it = compression_path.rbegin(); it != compression_path.rend();
++it) {
int current = *it;
int above = ancestor[current];
if (order[semidominator[label[above]]] <
order[semidominator[label[current]]]) {
label[current] = label[above];
}
ancestor[current] = vertex;
}
return label[start];
};
for (int index = int(vertices.size()) - 1; index >= 1; index--) {
int vertex = vertices[index];
for (int from : reverse_graph[vertex]) {
if (order[from] == -1) {
continue;
}
int best = evaluate(from);
if (order[semidominator[best]] < order[semidominator[vertex]]) {
semidominator[vertex] = semidominator[best];
}
}
bucket[semidominator[vertex]].push_back(vertex);
for (int pending : bucket[parent[vertex]]) {
candidate[pending] = evaluate(pending);
}
bucket[parent[vertex]].clear();
ancestor[vertex] = parent[vertex];
}
std::vector<int> immediate_dominator(n, -1);
immediate_dominator[root] = root;
for (int index = 1; index < int(vertices.size()); index++) {
int vertex = vertices[index];
immediate_dominator[vertex] =
semidominator[vertex] == semidominator[candidate[vertex]]
? semidominator[vertex]
: immediate_dominator[candidate[vertex]];
}
return immediate_dominator;
}
} // namespace noya
#endif // NOYA_DOMINATOR_TREE_HPP
#include <algorithm>
#include <cassert>
#include <numeric>
#include <vector>
/// @complexity Time: O((V + E) log V) with the implemented link-eval structure.
/// Space: O(V + E).
namespace noya {
/// @brief Immediate dominators in a directed graph using Lengauer-Tarjan.
/// The root dominates itself; unreachable vertices have parent -1.
inline std::vector<int>
dominator_tree(const std::vector<std::vector<int>> &graph, int root) {
const int n = int(graph.size());
assert(0 <= root && root < n);
std::vector<std::vector<int>> reverse_graph(n);
for (int vertex = 0; vertex < n; vertex++) {
for (int to : graph[vertex]) {
assert(0 <= to && to < n);
reverse_graph[to].push_back(vertex);
}
}
std::vector<int> order(n, -1), parent(n, -1), next_edge(n);
std::vector<int> vertices = {root};
std::vector<int> stack = {root};
order[root] = 0;
while (!stack.empty()) {
int vertex = stack.back();
if (next_edge[vertex] == int(graph[vertex].size())) {
stack.pop_back();
continue;
}
int to = graph[vertex][next_edge[vertex]++];
if (order[to] == -1) {
parent[to] = vertex;
order[to] = int(vertices.size());
vertices.push_back(to);
stack.push_back(to);
}
}
std::vector<int> semidominator(n), label(n), ancestor(n, -1),
candidate(n, -1);
std::iota(semidominator.begin(), semidominator.end(), 0);
std::iota(label.begin(), label.end(), 0);
std::vector<std::vector<int>> bucket(n);
std::vector<int> compression_path;
compression_path.reserve(vertices.size());
auto evaluate = [&](int start) {
compression_path.clear();
int vertex = start;
while (ancestor[vertex] != -1) {
compression_path.push_back(vertex);
vertex = ancestor[vertex];
}
for (auto it = compression_path.rbegin(); it != compression_path.rend();
++it) {
int current = *it;
int above = ancestor[current];
if (order[semidominator[label[above]]] <
order[semidominator[label[current]]]) {
label[current] = label[above];
}
ancestor[current] = vertex;
}
return label[start];
};
for (int index = int(vertices.size()) - 1; index >= 1; index--) {
int vertex = vertices[index];
for (int from : reverse_graph[vertex]) {
if (order[from] == -1) {
continue;
}
int best = evaluate(from);
if (order[semidominator[best]] < order[semidominator[vertex]]) {
semidominator[vertex] = semidominator[best];
}
}
bucket[semidominator[vertex]].push_back(vertex);
for (int pending : bucket[parent[vertex]]) {
candidate[pending] = evaluate(pending);
}
bucket[parent[vertex]].clear();
ancestor[vertex] = parent[vertex];
}
std::vector<int> immediate_dominator(n, -1);
immediate_dominator[root] = root;
for (int index = 1; index < int(vertices.size()); index++) {
int vertex = vertices[index];
immediate_dominator[vertex] =
semidominator[vertex] == semidominator[candidate[vertex]]
? semidominator[vertex]
: immediate_dominator[candidate[vertex]];
}
return immediate_dominator;
}
} // namespace noya