GCC Code Coverage Report

Directory: src/
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 97.3% 71 / 0 / 73
Functions: 100.0% 5 / 0 / 5
Branches: 36.9% 66 / 0 / 179
graph/make_st_dag.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include <vector>
4 #include <array>
5 #include <utility>
6 #include <cassert>
7
8 // Direct a graph into a DAG so that given source and sink are the unique sources/sinks.
9 // If there are any biconnected components not on the path from the source to
10 // the sink, they will not be output, modify the code if necessary.
11 // Returns a topological sort. Back out the edge directions yourself.
12 20546 inline std::vector<int> make_st_dag(const std::vector<std::vector<int>>& adj, int source = -1, int sink = -1) {
13
1/2
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 20546 times.
 20546 int N = int(adj.size());
14
15 // What's even going on lol
16
1/4
✗ Branch 3 → 4 not taken.
✗ Branch 3 → 5 not taken.
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 20546 times.
 20546 if (N == 0) return {};
17
18 // Make some arbitrary choices as defaults
19
1/7
✗ Branch 5 → 6 not taken.
✗ Branch 5 → 8 not taken.
✗ Branch 6 → 7 not taken.
✗ Branch 6 → 8 not taken.
✓ Branch 6 → 10 taken 20546 times.
✗ Branch 7 → 8 not taken.
✗ Branch 7 → 10 not taken.
 20546 if (source == -1 && sink == -1) source = 0;
20 ✗ if (source == -1) source = adj[sink].empty() ? sink : adj[sink][0];
21
1/8
✗ Branch 10 → 11 not taken.
✓ Branch 10 → 14 taken 20546 times.
✗ Branch 11 → 12 not taken.
✗ Branch 11 → 13 not taken.
✗ Branch 17 → 18 not taken.
✗ Branch 17 → 26 not taken.
✗ Branch 20 → 21 not taken.
✗ Branch 20 → 22 not taken.
 20546 if (sink == -1) sink = adj[source].empty() ? source : adj[source][0];
22
23
1/2
✓ Branch 15 → 16 taken 20546 times.
✗ Branch 28 → 29 not taken.
 20546 std::vector<int> depth(N, -1);
24
1/2
✓ Branch 15 → 16 taken 20546 times.
✗ Branch 32 → 33 not taken.
 20546 std::vector<int> lowval(N);
25
2/3
✓ Branch 16 → 17 taken 20546 times.
✓ Branch 17 → 18 taken 20546 times.
✗ Branch 36 → 37 not taken.
 20546 std::vector<bool> has_sink(N);
26
1/2
✓ Branch 17 → 18 taken 20546 times.
✗ Branch 40 → 41 not taken.
 20546 std::vector<std::vector<int>> ch(N);
27 1620557 [&](this auto&& self, int cur, int prv) -> void {
28
4/10
void make_st_dag(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > const&, int, int)::{lambda(auto:1&&, int, int)#1}::operator()<{lambda(auto:1&&, int, int)#1}&>(this {lambda(auto:1&&, int, int)#1}&, int, int):
✓ Branch 2 → 3 taken 1558919 times.
✗ Branch 2 → 4 not taken.
✗ Branch 2 → 5 not taken.
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 1558919 times.
void make_st_dag(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > const&, int, int)::{lambda(auto:1&&, int, int)#1}::operator()<{lambda(auto:1&&, int, int)#1}>(this {lambda(auto:1&&, int, int)#1}&&, int, int):
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 20546 times.
✗ Branch 2 → 5 not taken.
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 20546 times.
 1579465 depth[cur] = prv != -1 ? depth[prv] + 1 : 0;
29 1579465 lowval[cur] = depth[cur];
30
2/4
void make_st_dag(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > const&, int, int)::{lambda(auto:1&&, int, int)#1}::operator()<{lambda(auto:1&&, int, int)#1}&>(this {lambda(auto:1&&, int, int)#1}&, int, int):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 1558919 times.
void make_st_dag(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > const&, int, int)::{lambda(auto:1&&, int, int)#1}::operator()<{lambda(auto:1&&, int, int)#1}>(this {lambda(auto:1&&, int, int)#1}&&, int, int):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 20546 times.
 1579465 ch[cur].reserve(adj[cur].size());
31 1579465 has_sink[cur] = (cur == sink);
32
4/8
void make_st_dag(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > const&, int, int)::{lambda(auto:1&&, int, int)#1}::operator()<{lambda(auto:1&&, int, int)#1}&>(this {lambda(auto:1&&, int, int)#1}&, int, int):
✓ Branch 23 → 9 taken 9856893 times.
✓ Branch 23 → 24 taken 1558919 times.
✗ Branch 54 → 18 not taken.
✗ Branch 54 → 55 not taken.
void make_st_dag(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > const&, int, int)::{lambda(auto:1&&, int, int)#1}::operator()<{lambda(auto:1&&, int, int)#1}>(this {lambda(auto:1&&, int, int)#1}&&, int, int):
✓ Branch 23 → 9 taken 458997 times.
✓ Branch 23 → 24 taken 20546 times.
✗ Branch 54 → 18 not taken.
✗ Branch 54 → 55 not taken.
 11895355 for (int nxt : adj[cur]) {
33
3/8
void make_st_dag(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > const&, int, int)::{lambda(auto:1&&, int, int)#1}::operator()<{lambda(auto:1&&, int, int)#1}&>(this {lambda(auto:1&&, int, int)#1}&, int, int):
✓ Branch 9 → 10 taken 1886019 times.
✓ Branch 9 → 11 taken 7970874 times.
✗ Branch 20 → 21 not taken.
✗ Branch 20 → 22 not taken.
void make_st_dag(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > const&, int, int)::{lambda(auto:1&&, int, int)#1}::operator()<{lambda(auto:1&&, int, int)#1}>(this {lambda(auto:1&&, int, int)#1}&&, int, int):
✗ Branch 9 → 10 not taken.
✓ Branch 9 → 11 taken 458997 times.
✗ Branch 20 → 21 not taken.
✗ Branch 20 → 22 not taken.
 10315890 if (nxt == prv) continue;
34
4/8
void make_st_dag(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > const&, int, int)::{lambda(auto:1&&, int, int)#1}::operator()<{lambda(auto:1&&, int, int)#1}&>(this {lambda(auto:1&&, int, int)#1}&, int, int):
✓ Branch 11 → 12 taken 1538308 times.
✓ Branch 11 → 18 taken 6432566 times.
✗ Branch 23 → 24 not taken.
✗ Branch 23 → 37 not taken.
void make_st_dag(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > const&, int, int)::{lambda(auto:1&&, int, int)#1}::operator()<{lambda(auto:1&&, int, int)#1}>(this {lambda(auto:1&&, int, int)#1}&&, int, int):
✓ Branch 11 → 12 taken 20611 times.
✓ Branch 11 → 18 taken 438386 times.
✗ Branch 23 → 24 not taken.
✗ Branch 23 → 37 not taken.
 8429871 if (depth[nxt] == -1) {
35
0/2
void make_st_dag(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > const&, int, int)::{lambda(auto:1&&, int, int)#1}::operator()<{lambda(auto:1&&, int, int)#1}&>(this {lambda(auto:1&&, int, int)#1}&, int, int):
✗ Branch 25 → 26 not taken.
void make_st_dag(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > const&, int, int)::{lambda(auto:1&&, int, int)#1}::operator()<{lambda(auto:1&&, int, int)#1}>(this {lambda(auto:1&&, int, int)#1}&&, int, int):
✗ Branch 25 → 26 not taken.
 1558919 ch[cur].push_back(nxt);
36
0/2
void make_st_dag(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > const&, int, int)::{lambda(auto:1&&, int, int)#1}::operator()<{lambda(auto:1&&, int, int)#1}&>(this {lambda(auto:1&&, int, int)#1}&, int, int):
✗ Branch 26 → 27 not taken.
void make_st_dag(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > const&, int, int)::{lambda(auto:1&&, int, int)#1}::operator()<{lambda(auto:1&&, int, int)#1}>(this {lambda(auto:1&&, int, int)#1}&&, int, int):
✗ Branch 26 → 27 not taken.
 1558919 self(nxt, cur);
37
3/4
void make_st_dag(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > const&, int, int)::{lambda(auto:1&&, int, int)#1}::operator()<{lambda(auto:1&&, int, int)#1}&>(this {lambda(auto:1&&, int, int)#1}&, int, int):
✓ Branch 14 → 15 taken 963088 times.
✓ Branch 14 → 16 taken 575220 times.
void make_st_dag(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > const&, int, int)::{lambda(auto:1&&, int, int)#1}::operator()<{lambda(auto:1&&, int, int)#1}>(this {lambda(auto:1&&, int, int)#1}&&, int, int):
✗ Branch 14 → 15 not taken.
✓ Branch 14 → 16 taken 20611 times.
 1558919 lowval[cur] = std::min(lowval[cur], lowval[nxt]);
38
4/8
void make_st_dag(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > const&, int, int)::{lambda(auto:1&&, int, int)#1}::operator()<{lambda(auto:1&&, int, int)#1}&>(this {lambda(auto:1&&, int, int)#1}&, int, int):
✓ Branch 16 → 17 taken 842682 times.
✓ Branch 16 → 22 taken 695626 times.
✗ Branch 33 → 34 not taken.
✗ Branch 33 → 45 not taken.
void make_st_dag(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > const&, int, int)::{lambda(auto:1&&, int, int)#1}::operator()<{lambda(auto:1&&, int, int)#1}>(this {lambda(auto:1&&, int, int)#1}&&, int, int):
✓ Branch 16 → 17 taken 19065 times.
✓ Branch 16 → 22 taken 1546 times.
✗ Branch 33 → 34 not taken.
✗ Branch 33 → 45 not taken.
 1558919 if (has_sink[nxt]) has_sink[cur] = true;
39
3/8
void make_st_dag(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > const&, int, int)::{lambda(auto:1&&, int, int)#1}::operator()<{lambda(auto:1&&, int, int)#1}&>(this {lambda(auto:1&&, int, int)#1}&, int, int):
✓ Branch 18 → 19 taken 3271926 times.
✓ Branch 18 → 22 taken 3160640 times.
✗ Branch 39 → 40 not taken.
✗ Branch 39 → 45 not taken.
void make_st_dag(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > const&, int, int)::{lambda(auto:1&&, int, int)#1}::operator()<{lambda(auto:1&&, int, int)#1}>(this {lambda(auto:1&&, int, int)#1}&&, int, int):
✗ Branch 18 → 19 not taken.
✓ Branch 18 → 22 taken 438386 times.
✗ Branch 39 → 40 not taken.
✗ Branch 39 → 45 not taken.
 6870952 } else if (depth[nxt] < depth[cur]) {
40
2/4
void make_st_dag(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > const&, int, int)::{lambda(auto:1&&, int, int)#1}::operator()<{lambda(auto:1&&, int, int)#1}&>(this {lambda(auto:1&&, int, int)#1}&, int, int):
✓ Branch 19 → 20 taken 446792 times.
✓ Branch 19 → 21 taken 2825134 times.
void make_st_dag(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > const&, int, int)::{lambda(auto:1&&, int, int)#1}::operator()<{lambda(auto:1&&, int, int)#1}>(this {lambda(auto:1&&, int, int)#1}&&, int, int):
✗ Branch 19 → 20 not taken.
✗ Branch 19 → 21 not taken.
 3718718 lowval[cur] = std::min(lowval[cur], depth[nxt]);
41 } else {
42 // down edge
43 }
44 }
45
1/2
✓ Branch 18 → 19 taken 20546 times.
✗ Branch 42 → 43 not taken.
 1600011 }(source, -1);
46
47 // true is after, false is before
48
2/3
✓ Branch 19 → 20 taken 20546 times.
✓ Branch 20 → 21 taken 20546 times.
✗ Branch 45 → 46 not taken.
 20546 std::vector<bool> edge_dir(N, false);
49
1/2
✓ Branch 20 → 21 taken 20546 times.
✗ Branch 49 → 50 not taken.
 20546 std::vector<int> lst_nxt(N, -1);
50 1439313 auto lst = [&](this auto&& self, int cur) -> std::array<int, 2> {
51 1398221 std::array<int, 2> res{cur, cur};
52
4/8
std::array<int, 2ul> make_st_dag(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > const&, int, int)::{lambda(auto:1&&, int)#1}::operator()<{lambda(auto:1&&, int)#1}&>(this {lambda(auto:1&&, int)#1}&, int):
✓ Branch 18 → 3 taken 1444661 times.
✓ Branch 18 → 19 taken 1377675 times.
✗ Branch 51 → 5 not taken.
✗ Branch 51 → 52 not taken.
std::array<int, 2ul> make_st_dag(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > const&, int, int)::{lambda(auto:1&&, int)#1}::operator()<{lambda(auto:1&&, int)#1}>(this {lambda(auto:1&&, int)#1}&&, int):
✓ Branch 18 → 3 taken 20611 times.
✓ Branch 18 → 19 taken 20546 times.
✗ Branch 51 → 5 not taken.
✗ Branch 51 → 52 not taken.
 2863493 for (int nxt : ch[cur]) {
53 // If we're on the path to the sink, mark it as downwards.
54
55 // Comment out this line to direct extra bcc's as extra sinks
56
7/20
std::array<int, 2ul> make_st_dag(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > const&, int, int)::{lambda(auto:1&&, int)#1}::operator()<{lambda(auto:1&&, int)#1}&>(this {lambda(auto:1&&, int)#1}&, int):
✓ Branch 3 → 4 taken 601979 times.
✓ Branch 3 → 6 taken 842682 times.
✓ Branch 4 → 5 taken 86051 times.
✓ Branch 4 → 6 taken 515928 times.
✗ Branch 9 → 10 not taken.
✗ Branch 9 → 14 not taken.
✗ Branch 12 → 13 not taken.
✗ Branch 12 → 14 not taken.
✗ Branch 15 → 16 not taken.
✗ Branch 15 → 17 not taken.
std::array<int, 2ul> make_st_dag(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > const&, int, int)::{lambda(auto:1&&, int)#1}::operator()<{lambda(auto:1&&, int)#1}>(this {lambda(auto:1&&, int)#1}&&, int):
✓ Branch 3 → 4 taken 1546 times.
✓ Branch 3 → 6 taken 19065 times.
✓ Branch 4 → 5 taken 1546 times.
✗ Branch 4 → 6 not taken.
✗ Branch 9 → 10 not taken.
✗ Branch 9 → 14 not taken.
✗ Branch 12 → 13 not taken.
✗ Branch 12 → 14 not taken.
✗ Branch 15 → 16 not taken.
✗ Branch 15 → 17 not taken.
 1465272 if (!has_sink[nxt] && lowval[nxt] >= depth[cur]) continue;
57
58
6/24
std::array<int, 2ul> make_st_dag(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > const&, int, int)::{lambda(auto:1&&, int)#1}::operator()<{lambda(auto:1&&, int)#1}&>(this {lambda(auto:1&&, int)#1}&, int):
✓ Branch 6 → 7 taken 515928 times.
✓ Branch 6 → 10 taken 842682 times.
✓ Branch 7 → 8 taken 515928 times.
✗ Branch 7 → 10 not taken.
✓ Branch 8 → 9 taken 12761 times.
✓ Branch 8 → 10 taken 503167 times.
✗ Branch 19 → 20 not taken.
✗ Branch 19 → 27 not taken.
✗ Branch 22 → 23 not taken.
✗ Branch 22 → 27 not taken.
✗ Branch 26 → 27 not taken.
✗ Branch 26 → 28 not taken.
std::array<int, 2ul> make_st_dag(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > const&, int, int)::{lambda(auto:1&&, int)#1}::operator()<{lambda(auto:1&&, int)#1}>(this {lambda(auto:1&&, int)#1}&&, int):
✗ Branch 6 → 7 not taken.
✓ Branch 6 → 10 taken 19065 times.
✗ Branch 7 → 8 not taken.
✗ Branch 7 → 10 not taken.
✗ Branch 8 → 9 not taken.
✗ Branch 8 → 10 not taken.
✗ Branch 19 → 20 not taken.
✗ Branch 19 → 27 not taken.
✗ Branch 22 → 23 not taken.
✗ Branch 22 → 27 not taken.
✗ Branch 26 → 27 not taken.
✗ Branch 26 → 28 not taken.
 1377675 bool d = (has_sink[nxt] || lowval[nxt] >= depth[cur]) ? true : !edge_dir[lowval[nxt]];
59 1377675 edge_dir[depth[cur]] = d;
60
61
0/2
std::array<int, 2ul> make_st_dag(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > const&, int, int)::{lambda(auto:1&&, int)#1}::operator()<{lambda(auto:1&&, int)#1}&>(this {lambda(auto:1&&, int)#1}&, int):
✗ Branch 32 → 33 not taken.
std::array<int, 2ul> make_st_dag(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > const&, int, int)::{lambda(auto:1&&, int)#1}::operator()<{lambda(auto:1&&, int)#1}>(this {lambda(auto:1&&, int)#1}&&, int):
✗ Branch 32 → 33 not taken.
 1377675 auto ch_res = self(nxt);
62
63 // Join res and ch
64
3/8
std::array<int, 2ul> make_st_dag(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > const&, int, int)::{lambda(auto:1&&, int)#1}::operator()<{lambda(auto:1&&, int)#1}&>(this {lambda(auto:1&&, int)#1}&, int):
✓ Branch 12 → 13 taken 503167 times.
✓ Branch 12 → 16 taken 855443 times.
✗ Branch 33 → 34 not taken.
✗ Branch 33 → 35 not taken.
std::array<int, 2ul> make_st_dag(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > const&, int, int)::{lambda(auto:1&&, int)#1}::operator()<{lambda(auto:1&&, int)#1}>(this {lambda(auto:1&&, int)#1}&&, int):
✗ Branch 12 → 13 not taken.
✓ Branch 12 → 16 taken 19065 times.
✗ Branch 33 → 34 not taken.
✗ Branch 33 → 35 not taken.
 1377675 if (!d) std::swap(res, ch_res);
65 1377675 lst_nxt[std::exchange(res[1], ch_res[1])] = ch_res[0];
66 }
67 1398221 return res;
68
0/1
✗ Branch 51 → 52 not taken.
 20546 }(source);
69
70
1/2
✓ Branch 22 → 23 taken 20546 times.
✗ Branch 52 → 53 not taken.
 20546 std::vector<int> res; res.reserve(N);
71 20546 int cur = lst[0];
72
2/4
✓ Branch 26 → 24 taken 1398221 times.
✓ Branch 26 → 27 taken 20546 times.
✗ Branch 58 → 55 not taken.
✗ Branch 58 → 59 not taken.
 1418767 while (cur != -1) {
73
1/2
✓ Branch 24 → 25 taken 1398221 times.
✗ Branch 55 → 56 not taken.
 1398221 res.push_back(cur);
74 1398221 cur = lst_nxt[cur];
75 }
76 20546 return res;
77 20546 }
78