src/graph/chordal/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> // prefer alist | ||
| 9 | class chordal { | ||
| 10 | G CR g; | ||
| 11 | vecu deg; | ||
| 12 | |||
| 13 | public: | ||
| 14 | vecu peo, rnk; | ||
| 15 | |||
| 16 | // @param g simple UNDIRECTED graph | ||
| 17 | //! g[i] MUST be sorted | ||
| 18 | 192 | CEXPE chordal(G CR g) NE : g(g), deg(g.vsize()), peo(g.vsize()), rnk(g.vsize()) { | |
| 19 | 32 | cu32 n = g.vsize(); | |
| 20 | 96 | vecu l(n * 2 + 1), r, idx(n); | |
| 21 | 32 | std::iota(begin(l), end(l), 0), r = l; | |
| 22 | 7249769 | auto ins = [&](u32 i, u32 j) NE { r[l[i] = l[j]] = i, r[l[j] = i] = j; }; | |
| 23 | 7249769 | auto del = [&](u32 i) NE { r[l[i]] = r[i], l[r[i]] = l[i]; }; | |
| 24 |
2/2✓ Branch 1 taken 2126127 times.
✓ Branch 2 taken 32 times.
|
2126159 | flt_ (u32, i, 0, n) ins(i, n); |
| 25 | 32 | u32 li = n; | |
| 26 |
2/2✓ Branch 0 taken 2126127 times.
✓ Branch 1 taken 32 times.
|
2126159 | flt_ (u32, i, 0, n) { |
| 27 | 2126127 | ++li; | |
| 28 |
2/2✓ Branch 1 taken 2123210 times.
✓ Branch 2 taken 2126127 times.
|
4249337 | while (l[li] == li) --li; |
| 29 | 2126127 | u32 v = l[li]; | |
| 30 |
2/2✓ Branch 10 taken 10247284 times.
✓ Branch 11 taken 2126127 times.
|
12373411 | for (idx[v] = -1_u32, del(v); u32 to : g[v]) |
| 31 |
2/2✓ Branch 1 taken 5123642 times.
✓ Branch 2 taken 5123642 times.
|
10247284 | if (~idx[to]) ++deg[to], del(to), ins(to, n + (++idx[to])); |
| 32 | 2126127 | peo[i] = v; | |
| 33 | } | ||
| 34 | 32 | reverse(peo); | |
| 35 |
2/2✓ Branch 2 taken 2126127 times.
✓ Branch 3 taken 32 times.
|
2126159 | flt_ (u32, i, 0, n) rnk[peo[i]] = i; |
| 36 | 32 | } | |
| 37 | |||
| 38 | template <bool find_indcycle = false> | ||
| 39 | 22 | std::conditional_t<find_indcycle, std::optional<vecu>, bool> is_chordal_graph() CNE { | |
| 40 | 22 | std::optional<vecu> ret; | |
| 41 | 22631305 | auto has_edge = [&](u32 u, u32 v) { return binary_search(g[u], v, {}, [](auto CR e) { return (u32)e; }); }; | |
| 42 |
4/4✓ Branch 4 taken 908741 times.
✓ Branch 5 taken 12 times.
✓ Branch 8 taken 908753 times.
✓ Branch 9 taken 10 times.
|
1817516 | for (u32 u : peo) { |
| 43 | 908753 | vecu s; | |
| 44 |
2/2✓ Branch 8 taken 3684597 times.
✓ Branch 9 taken 908753 times.
|
4593350 | for (s.reserve(g.deg_out(u)); auto v : g[u]) |
| 45 |
2/2✓ Branch 3 taken 1843562 times.
✓ Branch 4 taken 1841035 times.
|
3684597 | if (rnk[u] < rnk[v]) |
| 46 |
2/2✓ Branch 6 taken 250481 times.
✓ Branch 7 taken 1593081 times.
|
1843562 | if (s.push_back(v); rnk[s.back()] < rnk[s[0]]) swap(s[0], s.back()); |
| 47 |
2/2✓ Branch 1 taken 1096553 times.
✓ Branch 2 taken 908741 times.
|
2005294 | flt_ (u32, j, 1, (u32)s.size()) |
| 48 |
2/2✓ Branch 3 taken 12 times.
✓ Branch 4 taken 1096541 times.
|
1096553 | if (!has_edge(s[0], s[j])) { |
| 49 | if CEXP (!find_indcycle) return false; | ||
| 50 | else { | ||
| 51 | 12 | cu32 x = s[j], y = s[0], z = u; | |
| 52 | 12 | vecu pre(peo.size(), -1_u32); | |
| 53 | 24 | std::queue<u32> q({x}); | |
| 54 |
1/2✓ Branch 1 taken 792285 times.
✗ Branch 2 not taken.
|
792285 | while (!q.empty()) { |
| 55 | 792285 | cu32 t = q.front(); | |
| 56 |
2/2✓ Branch 2 taken 12 times.
✓ Branch 3 taken 792273 times.
|
792285 | if (q.pop(); has_edge(t, y)) { |
| 57 | 12 | pre[y] = t; | |
| 58 | 12 | ret.emplace({y}); | |
| 59 |
2/2✓ Branch 7 taken 350085 times.
✓ Branch 8 taken 12 times.
|
350097 | while (ret->back() != x) ret->push_back(pre[ret->back()]); |
| 60 | 12 | ret->push_back(z); | |
| 61 | 12 | return ret; | |
| 62 | } | ||
| 63 |
2/2✓ Branch 7 taken 2171175 times.
✓ Branch 8 taken 792273 times.
|
2963448 | for (cu32 u : g[t]) |
| 64 |
8/8✓ Branch 0 taken 2171163 times.
✓ Branch 1 taken 12 times.
✓ Branch 3 taken 2070513 times.
✓ Branch 4 taken 100650 times.
✓ Branch 6 taken 923871 times.
✓ Branch 7 taken 1146642 times.
✓ Branch 8 taken 923871 times.
✓ Branch 9 taken 1247304 times.
|
2171175 | if (u != z && !has_edge(u, z) && !~pre[u]) pre[u] = t, q.push(u); |
| 65 | } | ||
| 66 |
2/4✗ Branch 1 not taken.
✓ Branch 2 taken 12 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 12 times.
|
24 | } |
| 67 | } | ||
| 68 | } | ||
| 69 | 10 | if CEXP (find_indcycle) return ret; | |
| 70 | else return true; | ||
| 71 | } | ||
| 72 | // @return {x}, which $\{x\}+N(x)$ be a maximal clique | ||
| 73 | ND CEXP vecu maximal_cliques() CNE { | ||
| 74 | vecu fst(peo.size(), -1_u32), n(peo.size()), res; | ||
| 75 | for (cu32 u : peo) | ||
| 76 | for (auto v : g[u]) | ||
| 77 | if (rnk[u] < rnk[(u32)v]) | ||
| 78 | if (++n[u]; !~fst[u] || rnk[(u32)v] < rnk[fst[u]]) fst[u] = (u32)v; | ||
| 79 | for (vecb vis(peo.size()); cu32 u : peo) { | ||
| 80 | if (vis[u]) continue; | ||
| 81 | res.push_back(u), vis[fst[u]] = n[u] > n[fst[u]]; | ||
| 82 | } | ||
| 83 | return res; | ||
| 84 | } | ||
| 85 | 10 | ND CEXP u32 chromatic_number() CNE { return max(deg) + 1; } | |
| 86 | ND CEXP vecu max_independent_set() CNE { | ||
| 87 | vecu res; | ||
| 88 | for (vecb vis(peo.size()); cu32 u : peo) { | ||
| 89 | if (vis[u]) continue; | ||
| 90 | for (res.push_back(u); u32 v : g[u]) vis[v] = true; | ||
| 91 | } | ||
| 92 | return res; | ||
| 93 | } | ||
| 94 | }; | ||
| 95 | |||
| 96 | } // namespace tifa_libs | ||
| 97 |