GCC Code Coverage Report

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