GCC Code Coverage Report

Directory: ./
File: tasks/pankov_a_path_dejikstra/tbb/src/ops_tbb.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 46 46 100.0%
Functions: 7 7 100.0%
Branches: 38 78 48.7%
Line Branch Exec Source
1 #include "pankov_a_path_dejikstra/tbb/include/ops_tbb.hpp"
2
3 #include <oneapi/tbb/blocked_range.h>
4 #include <oneapi/tbb/parallel_for.h>
5
6 #include <algorithm>
7 #include <cstddef>
8 #include <functional>
9 #include <queue>
10 #include <utility>
11 #include <vector>
12
13 #include "pankov_a_path_dejikstra/common/include/common.hpp"
14
15 namespace pankov_a_path_dejikstra {
16 namespace {
17
18 using AdjList = std::vector<std::vector<std::pair<Vertex, Weight>>>;
19
20 12 OutType DijkstraSeq(Vertex source, const AdjList &adjacency) {
21
1/2
✓ Branch 2 taken 12 times.
✗ Branch 3 not taken.
 12 OutType distance(adjacency.size(), kInfinity);
22 using QueueNode = std::pair<Weight, Vertex>;
23 std::priority_queue<QueueNode, std::vector<QueueNode>, std::greater<>> min_queue;
24
25
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 distance[source] = 0;
26
1/4
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 12 min_queue.emplace(0, source);
27
28
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 12 times.
 84 while (!min_queue.empty()) {
29 72 const auto [current_dist, u] = min_queue.top();
30 72 min_queue.pop();
31
32
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 60 times.
 72 if (current_dist != distance[u]) {
33 12 continue;
34 }
35
36
2/2
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 60 times.
 124 for (const auto &[v, weight] : adjacency[u]) {
37
3/4
✓ Branch 0 taken 64 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 60 times.
✓ Branch 3 taken 4 times.
 64 if (current_dist <= kInfinity - weight && current_dist + weight < distance[v]) {
38 60 distance[v] = current_dist + weight;
39
1/2
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
 60 min_queue.emplace(distance[v], v);
40 }
41 }
42 }
43
44 12 return distance;
45 }
46
47 } // namespace
48
49
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 PankovAPathDejikstraTBB::PankovAPathDejikstraTBB(const InType &in) {
50 SetTypeOfTask(GetStaticTypeOfTask());
51 GetInput() = in;
52 GetOutput().clear();
53 12 }
54
55 12 bool PankovAPathDejikstraTBB::ValidationImpl() {
56 const InType &input = GetInput();
57
2/4
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 12 times.
✗ Branch 3 not taken.
 12 if (input.n == 0 || input.source >= input.n) {
58 return false;
59 }
60
61 const auto edge_valid = [&input](const Edge &e) {
62 64 const auto [from, to, weight] = e;
63
3/6
✓ Branch 0 taken 64 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 64 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 64 times.
✗ Branch 5 not taken.
 64 return from < input.n && to < input.n && weight >= 0;
64 };
65 return std::ranges::all_of(input.edges, edge_valid);
66 }
67
68 12 bool PankovAPathDejikstraTBB::PreProcessingImpl() {
69 const InType &input = GetInput();
70 12 adjacency_.assign(input.n, {});
71
72 12 std::vector<Edge> sorted_edges = input.edges;
73
4/22
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✓ Branch 18 taken 8 times.
✓ Branch 19 taken 44 times.
✓ Branch 20 taken 4 times.
✓ Branch 21 taken 44 times.
 100 std::ranges::sort(sorted_edges, [](const Edge &lhs, const Edge &rhs) { return std::get<0>(lhs) < std::get<0>(rhs); });
74
75
1/4
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 12 std::vector<std::size_t> offsets(input.n + 1, 0);
76 std::size_t edge_idx = 0;
77
2/2
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 12 times.
 76 for (Vertex from = 0; from < input.n; from++) {
78 64 offsets[from] = edge_idx;
79
4/4
✓ Branch 0 taken 100 times.
✓ Branch 1 taken 28 times.
✓ Branch 2 taken 64 times.
✓ Branch 3 taken 36 times.
 128 while (edge_idx < sorted_edges.size() && std::get<0>(sorted_edges[edge_idx]) == from) {
80 64 edge_idx++;
81 }
82 }
83 12 offsets[input.n] = edge_idx;
84
85 auto &adjacency = adjacency_;
86
2/6
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 12 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 76 tbb::parallel_for(tbb::blocked_range<std::size_t>(0, input.n), [&](const tbb::blocked_range<std::size_t> &range) {
87
2/2
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 64 times.
 128 for (std::size_t from = range.begin(); from < range.end(); ++from) {
88 64 const std::size_t begin = offsets[from];
89 64 const std::size_t end = offsets[from + 1];
90 64 adjacency[from].reserve(end - begin);
91
2/2
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 64 times.
 128 for (std::size_t i = begin; i < end; i++) {
92 64 const auto &[edge_from, to, weight] = sorted_edges[i];
93 (void)edge_from;
94 64 adjacency[from].emplace_back(to, weight);
95 }
96 }
97 64 });
98
99 GetOutput().clear();
100 12 return true;
101 }
102
103
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 bool PankovAPathDejikstraTBB::RunImpl() {
104 const InType &input = GetInput();
105
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 if (adjacency_.size() != input.n) {
106 return false;
107 }
108 24 GetOutput() = DijkstraSeq(input.source, adjacency_);
109 12 return GetOutput().size() == input.n;
110 }
111
112 12 bool PankovAPathDejikstraTBB::PostProcessingImpl() {
113 12 return GetOutput().size() == GetInput().n;
114 }
115
116 } // namespace pankov_a_path_dejikstra
117