GCC Code Coverage Report

Directory: ./
File: tasks/potashnik_m_short_ways_bellford/common/include/common.hpp
Date: 2026-01-10 02:40:41
Exec Total Coverage
Lines: 44 45 97.8%
Functions: 4 4 100.0%
Branches: 24 26 92.3%
Line Branch Exec Source
1 #pragma once
2
3 #include <algorithm>
4 #include <cmath>
5 #include <vector>
6
7 #include "task/include/task.hpp"
8
9 namespace potashnik_m_short_ways_bellford {
10
11 // CRS Graph class
12 class Graph {
13 public:
14 int n;
15
16 std::vector<int> row_ptr;
17 std::vector<int> col_ind;
18 std::vector<int> weights;
19
1/2
✓ Branch 1 taken 50 times.
✗ Branch 2 not taken.
 100 Graph() : n(0) {}
20 50 explicit Graph(int n_vertices) : n(n_vertices), row_ptr(n_vertices + 1, 0) {}
21
22 50 void BuildGraph(const std::vector<int> &src, const std::vector<int> &dst, const std::vector<int> &w) {
23 50 int m = static_cast<int>(src.size());
24
25
2/2
✓ Branch 0 taken 1560 times.
✓ Branch 1 taken 50 times.
 1610 for (int i = 0; i < m; i++) {
26 1560 row_ptr[src[i] + 1]++;
27 }
28
29
2/2
✓ Branch 0 taken 570 times.
✓ Branch 1 taken 50 times.
 620 for (int i = 0; i < n; i++) {
30 570 row_ptr[i + 1] += row_ptr[i];
31 }
32
33 50 col_ind.resize(m);
34 50 weights.resize(m);
35 50 std::vector<int> cur = row_ptr;
36
37
2/2
✓ Branch 0 taken 1560 times.
✓ Branch 1 taken 50 times.
 1610 for (int i = 0; i < m; i++) {
38 1560 int u = src[i];
39 1560 int pos = cur[u]++;
40
41 1560 col_ind[pos] = dst[i];
42 1560 weights[pos] = w[i];
43 }
44 50 }
45
46 [[nodiscard]] int Begin(int u) const {
47 9462 return row_ptr[u];
48 }
49 [[nodiscard]] int End(int u) const {
50
2/2
✓ Branch 0 taken 28310 times.
✓ Branch 1 taken 9462 times.
 37772 return row_ptr[u + 1];
51 }
52 };
53
54 9462 inline void IterateThroughVertex(const Graph &g, int u, const std::vector<int> &dist, std::vector<int> &dist_out) {
55
2/2
✓ Branch 0 taken 28310 times.
✓ Branch 1 taken 9462 times.
 37772 for (int i = g.Begin(u); i < g.End(u); i++) {
56
2/2
✓ Branch 0 taken 6493 times.
✓ Branch 1 taken 21817 times.
 28310 int v = g.col_ind[i];
57 28310 int w = g.weights[i];
58
59 28310 int new_dist = dist[u] + w;
60
2/2
✓ Branch 0 taken 6493 times.
✓ Branch 1 taken 21817 times.
 34803 dist_out[v] = std::min(new_dist, dist_out[v]);
61 }
62 9462 }
63
64 50 inline Graph GenerateGraph(int n) {
65 50 Graph g(n);
66 50 std::vector<int> src;
67 50 std::vector<int> dst;
68 50 std::vector<int> w;
69 50 int layers = static_cast<int>(std::sqrt(n));
70 50 layers = std::max(layers, 1);
71 50 int layer_size = n / layers;
72
2/2
✓ Branch 0 taken 90 times.
✓ Branch 1 taken 50 times.
 140 for (int lidx = 0; lidx < layers - 1; lidx++) {
73 90 int start_u = lidx * layer_size;
74 90 int end_u = (lidx + 1) * layer_size;
75 int start_v = (lidx + 1) * layer_size;
76 90 int end_v = (lidx + 2) * layer_size;
77 90 end_v = std::min(end_v, n);
78
2/2
✓ Branch 0 taken 360 times.
✓ Branch 1 taken 90 times.
 450 for (int uidx = start_u; uidx < end_u; uidx++) {
79
2/2
✓ Branch 0 taken 1560 times.
✓ Branch 1 taken 360 times.
 1920 for (int vidx = start_v; vidx < end_v; vidx++) {
80 src.push_back(uidx);
81 dst.push_back(vidx);
82
2/2
✓ Branch 0 taken 1270 times.
✓ Branch 1 taken 290 times.
 1560 int weight = ((uidx * 13 + vidx * 7) % 10) + 1;
83 w.push_back(weight);
84 }
85 }
86 }
87
1/2
✓ Branch 1 taken 50 times.
✗ Branch 2 not taken.
 50 g.BuildGraph(src, dst, w);
88 50 return g;
89 ✗ }
90
91 using InType = Graph; // Graph
92 using OutType = std::vector<int>; // Vector of shortest paths
93 using TestType = int; // Amount of vertices
94 using BaseTask = ppc::task::Task<InType, OutType>;
95
96 } // namespace potashnik_m_short_ways_bellford
97