GCC Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 100.0% 74 / 0 / 74
Functions: 100.0% 6 / 0 / 6
Branches: 97.1% 68 / 0 / 70
src/graph/euler_trail/lib.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include "../ds/graph_c/lib.hpp"
4
5 namespace tifa_libs {
6 namespace euler_trail_impl_ {
7 template <bool cyc>
8 48918 CEXP auto run_(u32 n, u32 m, cT_(vvecptu) g, u32 s) NE {
9 48918 std::optional ret(vecptu{});
10 48918 vec<vecptu::const_iterator> its(n);
11
2/2
✓ Branch 3 taken 3680352 times.
✓ Branch 4 taken 48918 times.
 3729270 flt_ (u32, i, 0, n) its[i] = begin(g[i]);
12 48918 veci f(n);
13 48918 if CEXP (!cyc) ++f[s];
14 48918 vecb vis(m);
15 97836 vecptu stk = {{s, -1_u32}};
16
2/2
✓ Branch 1 taken 24520708 times.
✓ Branch 2 taken 48918 times.
 24569626 while (!stk.empty()) {
17 24520708 auto [i, p] = stk.back();
18 24520708 auto& it = its[i];
19
2/2
✓ Branch 3 taken 9793007 times.
✓ Branch 4 taken 14727701 times.
 24520708 if (it == end(g[i])) {
20 9793007 ret->emplace_back(i, p), stk.pop_back();
21 9793007 continue;
22 }
23
2/2
✓ Branch 6 taken 9744089 times.
✓ Branch 7 taken 4983612 times.
 14727701 if (auto [j, e] = *(it++); !vis[e]) --f[i], ++f[j], stk.emplace_back(j, e), vis[e] = true;
24 }
25
6/6
✓ Branch 2 taken 45578 times.
✓ Branch 3 taken 3340 times.
✓ Branch 5 taken 14930 times.
✓ Branch 6 taken 30648 times.
✓ Branch 7 taken 18270 times.
✓ Branch 8 taken 30648 times.
 2963994 if (ret->size() != m + 1 || any_of(f, [](i32 i) { return i < 0; })) ret = std::nullopt;
26 30648 else reverse(ret.value());
27 48918 return ret;
28 48918 }
29 } // namespace euler_trail_impl_
30
31 // @return vector of {v, eid} of Eulerian trail if found
32 // edges[eid[i]] = v[i-1] -> v[i], eid[0] = -1
33 template <bool directed, bool cycle = false>
34 48918 CEXP auto euler_trail(u32 n, vecptu CR edges) NE {
35 97836 vvecptu g(n);
36 48918 vecu deg_in(0);
37 24496 if CEXP (directed) deg_in.resize(n);
38 48918 u32 e = 0;
39
4/4
auto tifa_libs::euler_trail<false, false>(unsigned int, std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&):
✓ Branch 6 taken 5000027 times.
✓ Branch 7 taken 24422 times.
auto tifa_libs::euler_trail<true, false>(unsigned int, std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&):
✓ Branch 6 taken 5000031 times.
✓ Branch 7 taken 24496 times.
 10048976 for (auto [u, v] : edges) {
40 10000058 g[u].emplace_back(v, e);
41 5000031 if CEXP (directed) ++deg_in[v];
42 5000027 else g[v].emplace_back(u, e);
43 10000058 ++e;
44 }
45 48918 u32 s = 0;
46
4/4
auto tifa_libs::euler_trail<false, false>(unsigned int, std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&):
✓ Branch 1 taken 1815765 times.
✓ Branch 2 taken 24422 times.
auto tifa_libs::euler_trail<true, false>(unsigned int, std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&):
✓ Branch 1 taken 1815669 times.
✓ Branch 2 taken 24496 times.
 3680352 flt_ (u32, i, 1, (u32)g.size())
47
4/4
auto tifa_libs::euler_trail<false, false>(unsigned int, std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&):
✓ Branch 2 taken 1311186 times.
✓ Branch 3 taken 504579 times.
auto tifa_libs::euler_trail<true, false>(unsigned int, std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&):
✓ Branch 2 taken 1251212 times.
✓ Branch 3 taken 564457 times.
 3631434 if (!g[i].empty()) s = i;
48
4/4
auto tifa_libs::euler_trail<false, false>(unsigned int, std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&):
✓ Branch 1 taken 1840187 times.
✓ Branch 2 taken 24422 times.
auto tifa_libs::euler_trail<true, false>(unsigned int, std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&):
✓ Branch 1 taken 1840165 times.
✓ Branch 2 taken 24496 times.
 3729270 flt_ (u32, i, 0, (u32)g.size())
49 if CEXP (directed) {
50
2/2
✓ Branch 3 taken 165227 times.
✓ Branch 4 taken 1674938 times.
 1840165 if (deg_in[i] < g[i].size()) s = i;
51
2/2
✓ Branch 2 taken 221254 times.
✓ Branch 3 taken 1618933 times.
 1840187 } else if (g[i].size() & 1) s = i;
52 48918 return euler_trail_impl_::run_<cycle>(n, (u32)edges.size(), g, s);
53 48918 }
54 template <graph_c G>
55 137 CEXP bool is_eulerian(G CR g) NE {
56
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 137 times.
 137 retif_((!g.esize()) [[unlikely]], 1);
57 137 cu32 n = g.vsize();
58
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 137 times.
 137 assert(n == g.din.size());
59
2/2
✓ Branch 0 taken 28486 times.
✓ Branch 1 taken 109 times.
 28595 flt_ (u32, i, 0, n)
60
2/2
✓ Branch 2 taken 28 times.
✓ Branch 3 taken 28458 times.
 28486 if (g.din[i] != g.dout[i]) return false;
61 109 u32 loopv = 0, loope = 0, start = 0;
62
2/2
✓ Branch 0 taken 28458 times.
✓ Branch 1 taken 109 times.
 28567 flt_ (u32, u, 0, n) {
63
2/2
✓ Branch 2 taken 8108 times.
✓ Branch 3 taken 20350 times.
 28458 if (g[u].empty()) continue;
64 20350 bool f = true;
65
2/2
✓ Branch 6 taken 19910724 times.
✓ Branch 7 taken 20350 times.
 19931074 for (start = u; auto v : g[u])
66
2/2
✓ Branch 1 taken 1332906 times.
✓ Branch 2 taken 18577818 times.
 19910724 if (u == (u32)v) ++loope;
67 18577818 else f = false;
68 20350 loopv += f;
69 }
70
8/8
✓ Branch 0 taken 103 times.
✓ Branch 1 taken 6 times.
✓ Branch 2 taken 7 times.
✓ Branch 3 taken 96 times.
✓ Branch 5 taken 1 time.
✓ Branch 6 taken 6 times.
✓ Branch 7 taken 7 times.
✓ Branch 8 taken 102 times.
 109 if (loopv > 1 || (loopv == 1 && loope != g.esize())) return false;
71 102 vecb vis(n);
72 34786 auto f = [&](auto&& f, u32 x) NE -> void {
73
2/2
✓ Branch 6 taken 18710709 times.
✓ Branch 7 taken 17342 times.
 18728051 for (auto v : g[x])
74
2/2
✓ Branch 3 taken 17240 times.
✓ Branch 4 taken 18693469 times.
 18710709 if (!vis[(u32)v]) vis[(u32)v] = true, f(f, (u32)v);
75 };
76 102 vis[start] = true, f(f, start);
77
2/2
✓ Branch 0 taken 25448 times.
✓ Branch 1 taken 100 times.
 25548 flt_ (u32, i, 0, n)
78
6/6
✓ Branch 2 taken 8110 times.
✓ Branch 3 taken 17338 times.
✓ Branch 5 taken 2 times.
✓ Branch 6 taken 8108 times.
✓ Branch 7 taken 2 times.
✓ Branch 8 taken 25446 times.
 25448 if (!vis[i] && g.din[i]) return false;
79 100 return true;
80 102 }
81
82 } // namespace tifa_libs
83