src/graph/domtree/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../util/alias/others/lib.hpp" | ||
| 4 | #include "../ds/graph_c/lib.hpp" | ||
| 5 | |||
| 6 | namespace tifa_libs { | ||
| 7 | |||
| 8 | template <graph_c G> | ||
| 9 | class domtree { | ||
| 10 | u32 n, t{0}; | ||
| 11 | G CR g; | ||
| 12 | G rg; | ||
| 13 | vvecu bucket; | ||
| 14 | vecu arr, par, rev, dsu, label; | ||
| 15 | |||
| 16 | 600022 | CEXP void dfs(u32 u) NE { | |
| 17 |
2/2✓ Branch 12 taken 1200009 times.
✓ Branch 13 taken 600022 times.
|
1800031 | for (rev[arr[u] = label[t] = sdom[t] = dsu[t] = t] = u, ++t; cu32 w : g[u]) { |
| 18 |
2/2✓ Branch 1 taken 600009 times.
✓ Branch 2 taken 600000 times.
|
1200009 | if (!~arr[w]) dfs(w), par[arr[w]] = arr[u]; |
| 19 | 1200009 | rg.add_arc(arr[w], arr[u]); | |
| 20 | } | ||
| 21 | 600022 | } | |
| 22 | 6174141 | CEXP u32 find(u32 u, int x = 0) NE { | |
| 23 |
2/2✓ Branch 1 taken 1800018 times.
✓ Branch 2 taken 4374123 times.
|
6174141 | if (u == dsu[u]) { |
| 24 |
2/2✓ Branch 0 taken 1123374 times.
✓ Branch 1 taken 676644 times.
|
1800018 | retif_((x), -1_u32, u); |
| 25 | } | ||
| 26 | 4374123 | cu32 v = find(dsu[u], x + 1); | |
| 27 |
2/2✓ Branch 0 taken 1123374 times.
✓ Branch 1 taken 3250749 times.
|
4374123 | if (!~v) return u; |
| 28 |
2/2✓ Branch 5 taken 359778 times.
✓ Branch 6 taken 2890971 times.
|
3250749 | if (sdom[label[dsu[u]]] < sdom[label[u]]) label[u] = label[dsu[u]]; |
| 29 |
2/2✓ Branch 1 taken 2379726 times.
✓ Branch 2 taken 871023 times.
|
3250749 | retif_((dsu[u] = v; x), v, label[u]); |
| 30 | } | ||
| 31 | |||
| 32 | public: | ||
| 33 | vecu sdom, dom; | ||
| 34 | |||
| 35 | 156 | CEXPE domtree(G CR g) NE : n{g.vsize()}, g(g), rg(n), bucket(n), arr(n, -1_u32), par(n, -1_u32), rev(n, -1_u32), dsu(n), label(n), sdom(n, -1_u32), dom(n, -1_u32) {} | |
| 36 | |||
| 37 | // @return p, parents of dominator tree, p_i = -1_u32 if not exist else parent of vertex i | ||
| 38 | 13 | CEXP vecu get_domtree(u32 root) NE { | |
| 39 | 13 | dfs(root), rg.build(), std::iota(begin(dom), end(dom), 0); | |
| 40 |
2/2✓ Branch 0 taken 600022 times.
✓ Branch 1 taken 13 times.
|
600035 | for (u32 i = t - 1; ~i; --i) { |
| 41 |
2/2✓ Branch 12 taken 1200009 times.
✓ Branch 13 taken 600022 times.
|
1800031 | for (auto w : rg[i]) sdom[i] = min(sdom[i], sdom[find((u32)w)]); |
| 42 |
2/2✓ Branch 0 taken 600009 times.
✓ Branch 1 taken 13 times.
|
600022 | if (i) bucket[sdom[i]].push_back(i); |
| 43 |
2/2✓ Branch 6 taken 600009 times.
✓ Branch 7 taken 600022 times.
|
1200031 | for (cu32 w : bucket[i]) |
| 44 |
2/2✓ Branch 3 taken 509112 times.
✓ Branch 4 taken 90897 times.
|
600009 | if (cu32 v = find(w); sdom[v] == sdom[w]) dom[w] = sdom[w]; |
| 45 | 90897 | else dom[w] = v; | |
| 46 |
2/2✓ Branch 0 taken 599999 times.
✓ Branch 1 taken 23 times.
|
600022 | if (i > 1) dsu[i] = par[i]; |
| 47 | } | ||
| 48 |
2/2✓ Branch 0 taken 600009 times.
✓ Branch 1 taken 13 times.
|
600022 | flt_ (u32, i, 1, t) |
| 49 |
2/2✓ Branch 2 taken 90897 times.
✓ Branch 3 taken 509112 times.
|
600009 | if (dom[i] != sdom[i]) dom[i] = dom[dom[i]]; |
| 50 | 13 | vecu fa(n, -1_u32); | |
| 51 |
2/2✓ Branch 4 taken 600009 times.
✓ Branch 5 taken 13 times.
|
600022 | flt_ (u32, i, 1, t) fa[rev[i]] = rev[dom[i]]; |
| 52 | 13 | fa[root] = root; | |
| 53 | 13 | return fa; | |
| 54 | } | ||
| 55 | }; | ||
| 56 | |||
| 57 | } // namespace tifa_libs | ||
| 58 |