GCC Code Coverage Report

Directory: ./
File: tasks/pankov_a_path_dejikstra/all/src/ops_all.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 81 83 97.6%
Functions: 9 9 100.0%
Branches: 51 86 59.3%
Line Branch Exec Source
1 #include "pankov_a_path_dejikstra/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4
5 #include <algorithm>
6 #include <array>
7 #include <cstddef>
8 #include <cstdint>
9 #include <functional>
10 #include <queue>
11 #include <utility>
12 #include <vector>
13
14 #include "pankov_a_path_dejikstra/common/include/common.hpp"
15
16 namespace pankov_a_path_dejikstra {
17 namespace {
18
19 using AdjList = std::vector<std::vector<std::pair<Vertex, Weight>>>;
20
21 3 OutType DijkstraSeq(Vertex source, const AdjList &adjacency) {
22
1/2
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
 3 OutType distance(adjacency.size(), kInfinity);
23 using QueueNode = std::pair<Weight, Vertex>;
24 std::priority_queue<QueueNode, std::vector<QueueNode>, std::greater<>> min_queue;
25
26
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 distance[source] = 0;
27
1/4
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 3 min_queue.emplace(0, source);
28
29
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 3 times.
 21 while (!min_queue.empty()) {
30 18 const auto [current_dist, u] = min_queue.top();
31 18 min_queue.pop();
32
33
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 15 times.
 18 if (current_dist != distance[u]) {
34 3 continue;
35 }
36
37
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 15 times.
 31 for (const auto &[v, weight] : adjacency[u]) {
38
3/4
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 15 times.
✓ Branch 3 taken 1 times.
 16 if (current_dist <= kInfinity - weight && current_dist + weight < distance[v]) {
39 15 distance[v] = current_dist + weight;
40
1/2
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
 15 min_queue.emplace(distance[v], v);
41 }
42 }
43 }
44
45 3 return distance;
46 }
47
48 3 std::vector<std::int64_t> PackEdges(const std::vector<Edge> &edges) {
49 3 std::vector<std::int64_t> packed(edges.size() * 3);
50
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 3 times.
 19 for (std::size_t i = 0; i < edges.size(); ++i) {
51 const auto &[from, to, weight] = edges[i];
52 16 const std::size_t offset = i * 3;
53 16 packed[offset] = static_cast<std::int64_t>(from);
54 16 packed[offset + 1] = static_cast<std::int64_t>(to);
55 16 packed[offset + 2] = static_cast<std::int64_t>(weight);
56 }
57 3 return packed;
58 }
59
60 6 std::vector<Edge> UnpackEdges(const std::vector<std::int64_t> &packed) {
61 6 std::vector<Edge> edges(packed.size() / 3);
62
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 6 times.
 38 for (std::size_t i = 0; i < edges.size(); ++i) {
63 32 const std::size_t offset = i * 3;
64 32 edges[i] = {static_cast<Vertex>(packed[offset]), static_cast<Vertex>(packed[offset + 1]),
65 32 static_cast<Weight>(packed[offset + 2])};
66 }
67 6 return edges;
68 }
69
70 6 AdjList BuildAdjacency(Vertex vertices_count, const std::vector<Edge> &edges) {
71 6 AdjList adjacency(vertices_count);
72
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 6 times.
 38 for (const auto &[from, to, weight] : edges) {
73
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 adjacency[from].emplace_back(to, weight);
74 }
75 6 return adjacency;
76 ✗ }
77
78 } // namespace
79
80
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 PankovAPathDejikstraALL::PankovAPathDejikstraALL(const InType &in) {
81 SetTypeOfTask(GetStaticTypeOfTask());
82 GetInput() = in;
83 GetOutput().clear();
84 6 }
85
86 6 bool PankovAPathDejikstraALL::ValidationImpl() {
87 6 int rank = 0;
88 6 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
89
90 6 int is_valid = 1;
91
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (rank == 0) {
92 const InType &input = GetInput();
93
2/4
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 3 times.
 3 if (input.n == 0 || input.source >= input.n) {
94 ✗ is_valid = 0;
95 } else {
96 const auto edge_valid = [&input](const Edge &e) {
97 16 const auto [from, to, weight] = e;
98
3/6
✓ Branch 0 taken 16 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 16 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 16 times.
✗ Branch 5 not taken.
 16 return from < input.n && to < input.n && weight >= 0;
99 };
100
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
 3 is_valid = std::ranges::all_of(input.edges, edge_valid) ? 1 : 0;
101 }
102 }
103
104 6 MPI_Bcast(&is_valid, 1, MPI_INT, 0, MPI_COMM_WORLD);
105 6 return is_valid == 1;
106 }
107
108 6 bool PankovAPathDejikstraALL::PreProcessingImpl() {
109 6 int rank = 0;
110 6 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
111
112 6 std::array<std::uint64_t, 3> metadata{};
113 6 std::vector<std::int64_t> packed_edges;
114
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (rank == 0) {
115 const InType &input = GetInput();
116 3 metadata[0] = static_cast<std::uint64_t>(input.n);
117
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 metadata[1] = static_cast<std::uint64_t>(input.source);
118 3 metadata[2] = static_cast<std::uint64_t>(input.edges.size());
119
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 6 packed_edges = PackEdges(input.edges);
120 }
121
122
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Bcast(metadata.data(), static_cast<int>(metadata.size()), MPI_UINT64_T, 0, MPI_COMM_WORLD);
123
124 6 vertices_count_ = static_cast<Vertex>(metadata[0]);
125 6 source_ = static_cast<Vertex>(metadata[1]);
126
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 packed_edges.resize(static_cast<std::size_t>(metadata[2]) * 3);
127
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (!packed_edges.empty()) {
128
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Bcast(packed_edges.data(), static_cast<int>(packed_edges.size()), MPI_LONG, 0, MPI_COMM_WORLD);
129 }
130
131
3/8
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 6 times.
✗ Branch 5 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 6 times.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
 12 adjacency_ = BuildAdjacency(vertices_count_, UnpackEdges(packed_edges));
132 GetOutput().clear();
133 6 return true;
134 }
135
136 6 bool PankovAPathDejikstraALL::RunImpl() {
137 6 OutType distances;
138 6 int rank = 0;
139
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
140
141
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (rank == 0) {
142
1/2
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
 3 if (adjacency_.size() != vertices_count_) {
143 return false;
144 }
145
1/4
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 6 distances = DijkstraSeq(source_, adjacency_);
146 }
147
148 6 auto output_size = static_cast<std::uint64_t>(distances.size());
149
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Bcast(&output_size, 1, MPI_UINT64_T, 0, MPI_COMM_WORLD);
150
151
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 GetOutput().assign(static_cast<std::size_t>(output_size), kInfinity);
152
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (rank == 0) {
153 GetOutput() = std::move(distances);
154 }
155
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (!GetOutput().empty()) {
156
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Bcast(GetOutput().data(), static_cast<int>(GetOutput().size()), MPI_INT, 0, MPI_COMM_WORLD);
157 }
158
159 6 return GetOutput().size() == vertices_count_;
160 }
161
162 6 bool PankovAPathDejikstraALL::PostProcessingImpl() {
163 6 return GetOutput().size() == vertices_count_;
164 }
165
166 } // namespace pankov_a_path_dejikstra
167