src/graph/find_cycle/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 <bool directed, graph_c G> | ||
| 9 | 153 | CEXP vecptu find_cycle(G CR g) NE { | |
| 10 |
4/4std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > tifa_libs::find_cycle<false, tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > >(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > const&):
✓ Branch 1 taken 11928771 times.
✓ Branch 2 taken 48 times.
std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > tifa_libs::find_cycle<true, tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > >(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > const&):
✓ Branch 1 taken 20132259 times.
✓ Branch 2 taken 105 times.
|
32061183 | flt_ (u32, i, 0, g.vsize()) |
| 11 |
4/4std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > tifa_libs::find_cycle<false, tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > >(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > const&):
✓ Branch 6 taken 18550896 times.
✓ Branch 7 taken 11928771 times.
std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > tifa_libs::find_cycle<true, tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > >(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > const&):
✓ Branch 6 taken 31281288 times.
✓ Branch 7 taken 20132259 times.
|
81893214 | for (auto j : g[i]) |
| 12 |
2/4std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > tifa_libs::find_cycle<false, tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > >(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > const&):
✗ Branch 1 not taken.
✓ Branch 2 taken 18550896 times.
std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > tifa_libs::find_cycle<true, tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > >(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > const&):
✗ Branch 1 not taken.
✓ Branch 2 taken 31281288 times.
|
49832184 | if (i == (u32)j) return vecptu{{i, i}}; |
| 13 | 306 | vecu pidx(g.vsize(), -1_u32), vis(g.vsize(), 0); | |
| 14 | 153 | vecptu cycle; | |
| 15 | 153 | bool fin = false; | |
| 16 | 24194493 | auto f = [&](auto&& f, u32 now, u32 pval, u32 fa) NE -> u32 { | |
| 17 |
4/4unsigned int tifa_libs::find_cycle<false, tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > >(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > const&)::{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&>({lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&, unsigned int, unsigned int, unsigned int) const:
✓ Branch 9 taken 13593966 times.
✓ Branch 10 taken 7530078 times.
unsigned int tifa_libs::find_cycle<true, tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > >(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > const&)::{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&>({lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&, unsigned int, unsigned int, unsigned int) const:
✓ Branch 9 taken 17854278 times.
✓ Branch 10 taken 14551698 times.
|
53530020 | for (pidx[now] = pval, vis[now] = 1; u32 to : g[now]) { |
| 18 |
4/4unsigned int tifa_libs::find_cycle<false, tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > >(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > const&)::{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&>({lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&, unsigned int, unsigned int, unsigned int) const:
✓ Branch 0 taken 161343 times.
✓ Branch 1 taken 13432623 times.
unsigned int tifa_libs::find_cycle<true, tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > >(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > const&)::{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&>({lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&, unsigned int, unsigned int, unsigned int) const:
✓ Branch 0 taken 1080 times.
✓ Branch 1 taken 17853198 times.
|
33398385 | if (fin) return -1_u32; |
| 19 | if CEXP (!directed) | ||
| 20 |
2/2✓ Branch 0 taken 6268542 times.
✓ Branch 1 taken 7164081 times.
|
13432623 | if (to == fa) continue; |
| 21 |
4/4unsigned int tifa_libs::find_cycle<false, tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > >(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > const&)::{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&>({lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&, unsigned int, unsigned int, unsigned int) const:
✓ Branch 2 taken 24 times.
✓ Branch 3 taken 7164057 times.
unsigned int tifa_libs::find_cycle<true, tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > >(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > const&)::{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&>({lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&, unsigned int, unsigned int, unsigned int) const:
✓ Branch 2 taken 45 times.
✓ Branch 3 taken 17853153 times.
|
25017279 | if (pidx[to] == pidx[now]) { |
| 22 | 69 | cycle.emplace_back(now, to); | |
| 23 | 69 | return to; | |
| 24 | } | ||
| 25 |
3/4unsigned int tifa_libs::find_cycle<false, tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > >(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > const&)::{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&>({lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&, unsigned int, unsigned int, unsigned int) const:
✗ Branch 1 not taken.
✓ Branch 2 taken 7164057 times.
unsigned int tifa_libs::find_cycle<true, tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > >(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > const&)::{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&>({lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&, unsigned int, unsigned int, unsigned int) const:
✓ Branch 1 taken 12367833 times.
✓ Branch 2 taken 5485320 times.
|
25017210 | if (vis[to]) continue; |
| 26 |
4/4unsigned int tifa_libs::find_cycle<false, tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > >(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > const&)::{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&>({lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&, unsigned int, unsigned int, unsigned int) const:
✓ Branch 1 taken 1469673 times.
✓ Branch 2 taken 5694384 times.
unsigned int tifa_libs::find_cycle<true, tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > >(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > const&)::{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&>({lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&, unsigned int, unsigned int, unsigned int) const:
✓ Branch 1 taken 480399 times.
✓ Branch 2 taken 5004921 times.
|
12649377 | if (u32 nxt = f(f, to, pval, now); ~nxt) { |
| 27 |
4/4unsigned int tifa_libs::find_cycle<false, tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > >(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > const&)::{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&>({lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&, unsigned int, unsigned int, unsigned int) const:
✓ Branch 1 taken 24 times.
✓ Branch 2 taken 1469649 times.
unsigned int tifa_libs::find_cycle<true, tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > >(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > const&)::{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&>({lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&, unsigned int, unsigned int, unsigned int) const:
✓ Branch 1 taken 45 times.
✓ Branch 2 taken 480354 times.
|
1950072 | if (cycle.emplace_back(now, to); now == nxt) { |
| 28 | 69 | fin = true; | |
| 29 | 69 | return -1_u32; | |
| 30 | } | ||
| 31 | 1950003 | return nxt; | |
| 32 | } | ||
| 33 | } | ||
| 34 | 22081776 | return pidx[now] = -1_u32; | |
| 35 | }; | ||
| 36 |
4/4unsigned int tifa_libs::find_cycle<false, tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > >(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > const&)::{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&>({lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&, unsigned int, unsigned int, unsigned int) const:
✓ Branch 1 taken 5124936 times.
✓ Branch 2 taken 24 times.
unsigned int tifa_libs::find_cycle<true, tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > >(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > const&)::{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&>({lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&, unsigned int, unsigned int, unsigned int) const:
✓ Branch 1 taken 12901698 times.
✓ Branch 2 taken 60 times.
|
18026718 | flt_ (u32, i, 0, g.vsize()) { |
| 37 |
4/4unsigned int tifa_libs::find_cycle<false, tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > >(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > const&)::{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&>({lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&, unsigned int, unsigned int, unsigned int) const:
✓ Branch 1 taken 3127875 times.
✓ Branch 2 taken 1997061 times.
unsigned int tifa_libs::find_cycle<true, tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > >(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > const&)::{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&>({lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&, unsigned int, unsigned int, unsigned int) const:
✓ Branch 1 taken 3353796 times.
✓ Branch 2 taken 9547902 times.
|
18026634 | if (vis[i]) continue; |
| 38 |
4/4unsigned int tifa_libs::find_cycle<false, tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > >(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > const&)::{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&>({lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&, unsigned int, unsigned int, unsigned int) const:
✓ Branch 2 taken 24 times.
✓ Branch 3 taken 1997037 times.
unsigned int tifa_libs::find_cycle<true, tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > >(tifa_libs::graph_impl_::graph<tifa_libs::alist_impl_::alist_tag<void> > const&)::{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}::operator()<{lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&>({lambda(auto:1&&, unsigned int, unsigned int, unsigned int)#1}&, unsigned int, unsigned int, unsigned int) const:
✓ Branch 2 taken 45 times.
✓ Branch 3 taken 9547857 times.
|
11544963 | if (f(f, i, i, -1_u32); fin) { |
| 39 | 69 | reverse(cycle); | |
| 40 | 69 | return cycle; | |
| 41 | } | ||
| 42 | } | ||
| 43 | 84 | return vecptu{}; | |
| 44 | 153 | } | |
| 45 | |||
| 46 | } // namespace tifa_libs | ||
| 47 |