GCC Code Coverage Report

Directory: ./
File: tasks/baranov_a_dijkstra_crs/mpi/src/ops_mpi.cpp
Date: 2026-01-27 01:59:34
Exec Total Coverage
Lines: 125 140 89.3%
Functions: 13 13 100.0%
Branches: 93 142 65.5%
Line Branch Exec Source
1 #include "baranov_a_dijkstra_crs/mpi/include/ops_mpi.hpp"
2
3 #include <mpi.h>
4
5 #include <cmath>
6 #include <cstddef>
7 #include <limits>
8 #include <vector>
9
10 #include "baranov_a_dijkstra_crs/common/include/common.hpp"
11
12 namespace baranov_a_dijkstra_crs {
13
14 namespace {
15 void CalculateVertexDistribution(int world_rank, int world_size, int total_vertices, int &local_start, int &local_end,
16 int &local_count) {
17 84 int vertices_per_process = total_vertices / world_size;
18 84 int remainder = total_vertices % world_size;
19
20 84 if (world_rank < remainder) {
21 27 local_start = world_rank * (vertices_per_process + 1);
22 27 local_end = local_start + vertices_per_process + 1;
23 } else {
24 57 local_start = (remainder * (vertices_per_process + 1)) + ((world_rank - remainder) * vertices_per_process);
25 57 local_end = local_start + vertices_per_process;
26 }
27 84 local_count = local_end - local_start;
28 }
29
30 void InitializeVertexOwnership(std::vector<int> &vertex_ownership, int total_vertices, int world_size) {
31 28 vertex_ownership.resize(total_vertices);
32
4/4
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 101 times.
✓ Branch 3 taken 27 times.
 130 for (int i = 0; i < total_vertices; ++i) {
33 102 vertex_ownership[i] = i % world_size;
34 }
35 }
36
37 27 void CopyLocalEdges(const GraphData &graph, int local_start, int local_end, int total_vertices,
38 std::vector<int> &local_columns, std::vector<double> &local_values) {
39
1/2
✓ Branch 0 taken 27 times.
✗ Branch 1 not taken.
 27 int start_edge = graph.offsets[local_start];
40
1/2
✓ Branch 0 taken 27 times.
✗ Branch 1 not taken.
 27 int end_edge = (local_end <= total_vertices) ? graph.offsets[local_end] : graph.offsets[total_vertices];
41 27 int total_edges = end_edge - start_edge;
42
43
2/2
✓ Branch 0 taken 22 times.
✓ Branch 1 taken 5 times.
 27 if (total_edges > 0) {
44 22 local_columns.resize(total_edges);
45 22 local_values.resize(total_edges);
46
47
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 22 times.
 78 for (int i = 0; i < total_edges; ++i) {
48
1/2
✓ Branch 0 taken 56 times.
✗ Branch 1 not taken.
 56 if (start_edge + i < static_cast<int>(graph.columns.size())) {
49 56 local_columns[i] = graph.columns[start_edge + i];
50 56 local_values[i] = graph.values[start_edge + i];
51 }
52 }
53 } else {
54 local_columns.clear();
55 local_values.clear();
56 }
57 27 }
58
59 28 void InitializeGlobalDist(std::vector<double> &global_dist, int total_vertices, int source, bool i_own_source) {
60
1/2
✓ Branch 0 taken 28 times.
✗ Branch 1 not taken.
 28 if (total_vertices > 0) {
61 28 global_dist.resize(total_vertices, std::numeric_limits<double>::infinity());
62
5/8
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 14 times.
✓ Branch 2 taken 14 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 14 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 14 times.
✗ Branch 7 not taken.
 28 if (i_own_source && !global_dist.empty() && source >= 0 && static_cast<std::size_t>(source) < global_dist.size()) {
63 14 global_dist[source] = 0.0;
64 }
65 }
66 28 }
67
68 101 bool ProcessNeighbors(const std::vector<double> &local_dist, int global_v, const std::vector<int> &local_offsets, int i,
69 const std::vector<int> &local_columns, const std::vector<double> &local_values,
70 int total_vertices, std::vector<double> &new_dist) {
71 bool changed = false;
72 101 int start = local_offsets[i];
73 101 int end = local_offsets[i + 1];
74
75
2/2
✓ Branch 0 taken 135 times.
✓ Branch 1 taken 101 times.
 236 for (int idx = start; idx < end; ++idx) {
76
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 135 times.
 135 if (static_cast<std::size_t>(idx) >= local_columns.size()) {
77 ✗ continue;
78 }
79
80 135 int neighbor = local_columns[idx];
81 135 double weight = local_values[idx];
82
83
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 135 times.
 135 if (neighbor < 0 || neighbor >= total_vertices) {
84 ✗ continue;
85 }
86
87
2/2
✓ Branch 0 taken 42 times.
✓ Branch 1 taken 93 times.
 135 double new_distance = local_dist[global_v] + weight;
88
2/2
✓ Branch 0 taken 42 times.
✓ Branch 1 taken 93 times.
 135 if (new_distance < new_dist[neighbor]) {
89 42 new_dist[neighbor] = new_distance;
90 changed = true;
91 }
92 }
93 101 return changed;
94 }
95
96 78 bool ProcessLocalVertices(const std::vector<double> &local_dist, const std::vector<int> &local_offsets,
97 const std::vector<int> &local_columns, const std::vector<double> &local_values,
98 int local_start, int local_num_vertices, int total_vertices, std::vector<double> &new_dist) {
99 bool changed = false;
100
101
3/4
✓ Branch 0 taken 77 times.
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 77 times.
✗ Branch 3 not taken.
 78 if (local_num_vertices <= 0 || local_start >= total_vertices || local_dist.empty()) {
102 return changed;
103 }
104
105
2/2
✓ Branch 0 taken 152 times.
✓ Branch 1 taken 77 times.
 229 for (int i = 0; i < local_num_vertices; ++i) {
106 152 int global_v = local_start + i;
107
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 152 times.
 152 if (global_v >= total_vertices) {
108 ✗ continue;
109 }
110
111
2/2
✓ Branch 0 taken 51 times.
✓ Branch 1 taken 101 times.
 152 if (local_dist[global_v] >= std::numeric_limits<double>::infinity()) {
112 51 continue;
113 }
114
115
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 101 times.
 101 if (i >= static_cast<int>(local_offsets.size()) - 1) {
116 ✗ continue;
117 }
118
119 101 changed = ProcessNeighbors(local_dist, global_v, local_offsets, i, local_columns, local_values, total_vertices,
120
2/2
✓ Branch 0 taken 29 times.
✓ Branch 1 taken 72 times.
 101 new_dist) ||
121 changed;
122 }
123
124 return changed;
125 }
126
127 50 bool UpdateDistances(std::vector<double> &global_dist, std::vector<double> &local_dist, std::vector<double> &new_dist,
128 int total_vertices) {
129 50 MPI_Allreduce(new_dist.data(), global_dist.data(), total_vertices, MPI_DOUBLE, MPI_MIN, MPI_COMM_WORLD);
130
131
3/6
✓ Branch 0 taken 50 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 50 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 50 times.
✗ Branch 5 not taken.
 50 if (!global_dist.empty() && !local_dist.empty() && global_dist.size() == local_dist.size()) {
132 50 local_dist.assign(global_dist.begin(), global_dist.end());
133 }
134
135
3/6
✓ Branch 0 taken 50 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 50 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 50 times.
✗ Branch 5 not taken.
 50 if (!global_dist.empty() && !new_dist.empty() && global_dist.size() == new_dist.size()) {
136 50 new_dist.assign(global_dist.begin(), global_dist.end());
137 }
138
139 50 return true;
140 }
141
142 28 bool InitializeDistances(const GraphData &graph, int world_rank, int world_size, std::vector<double> &global_dist,
143 std::vector<double> &local_dist, std::vector<double> &new_dist, int &source_owner) {
144 28 const int total_vertices = graph.num_vertices;
145
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 19 times.
 28 const int source = graph.source_vertex;
146
147 int local_start = 0;
148 int local_end = 0;
149 int local_num_vertices = 0;
150 CalculateVertexDistribution(world_rank, world_size, total_vertices, local_start, local_end, local_num_vertices);
151
152
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 28 times.
 28 if (local_end > total_vertices) {
153 local_end = total_vertices;
154 ✗ local_num_vertices = local_end - local_start;
155 }
156
157
6/8
✓ Branch 0 taken 28 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 27 times.
✓ Branch 3 taken 1 times.
✓ Branch 4 taken 14 times.
✓ Branch 5 taken 13 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 14 times.
 28 bool i_own_source = (total_vertices > 0 && local_num_vertices > 0 && source >= local_start && source < local_end);
158 28 InitializeGlobalDist(global_dist, total_vertices, source, i_own_source);
159
160
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 14 times.
 28 int my_has_source = i_own_source ? world_rank : -1;
161 28 MPI_Allreduce(&my_has_source, &source_owner, 1, MPI_INT, MPI_MAX, MPI_COMM_WORLD);
162
163
2/4
✓ Branch 0 taken 28 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 28 times.
✗ Branch 3 not taken.
 28 if (source_owner >= 0 && !global_dist.empty()) {
164 28 MPI_Bcast(global_dist.data(), total_vertices, MPI_DOUBLE, source_owner, MPI_COMM_WORLD);
165 }
166
167
1/2
✓ Branch 0 taken 28 times.
✗ Branch 1 not taken.
 28 if (global_dist.empty()) {
168 return false;
169 }
170
171 if (!global_dist.empty()) {
172 28 local_dist = global_dist;
173 28 new_dist = global_dist;
174 } else {
175 local_dist.clear();
176 new_dist.clear();
177 }
178
179 return true;
180 }
181
182 28 bool PerformDijkstraIterations(const std::vector<double> &local_dist, const std::vector<int> &local_offsets,
183 const std::vector<int> &local_columns, const std::vector<double> &local_values,
184 int local_start, int local_num_vertices, int total_vertices,
185 std::vector<double> &global_dist, std::vector<double> &new_dist) {
186 28 std::vector<double> current_local_dist = local_dist;
187
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 std::vector<double> current_new_dist = new_dist;
188
189
1/2
✓ Branch 0 taken 78 times.
✗ Branch 1 not taken.
 78 for (int iter = 0; iter < total_vertices; ++iter) {
190 78 bool changed = ProcessLocalVertices(current_local_dist, local_offsets, local_columns, local_values, local_start,
191 local_num_vertices, total_vertices, current_new_dist);
192
193 78 int global_changed = 0;
194
2/2
✓ Branch 0 taken 50 times.
✓ Branch 1 taken 28 times.
 78 int local_changed_int = changed ? 1 : 0;
195
1/2
✓ Branch 1 taken 78 times.
✗ Branch 2 not taken.
 78 MPI_Allreduce(&local_changed_int, &global_changed, 1, MPI_INT, MPI_MAX, MPI_COMM_WORLD);
196
197
2/2
✓ Branch 0 taken 50 times.
✓ Branch 1 taken 28 times.
 78 if (global_changed == 0) {
198 break;
199 }
200
201
2/4
✓ Branch 0 taken 50 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 50 times.
✗ Branch 3 not taken.
 50 if (!current_new_dist.empty() && !global_dist.empty()) {
202
1/2
✓ Branch 1 taken 50 times.
✗ Branch 2 not taken.
 50 UpdateDistances(global_dist, current_local_dist, current_new_dist, total_vertices);
203 }
204 }
205
206 28 return true;
207 }
208 } // namespace
209
210
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 BaranovADijkstraCRSMPI::BaranovADijkstraCRSMPI(const InType &in) {
211 SetTypeOfTask(GetStaticTypeOfTask());
212
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 GetInput() = in;
213 28 GetOutput() = std::vector<double>();
214 28 }
215
216 28 bool BaranovADijkstraCRSMPI::ValidationImpl() {
217 const auto &input = GetInput();
218
1/2
✓ Branch 0 taken 28 times.
✗ Branch 1 not taken.
 28 if (input.num_vertices <= 0) {
219 return false;
220 }
221
2/4
✓ Branch 0 taken 28 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 28 times.
✗ Branch 3 not taken.
 28 if (input.source_vertex < 0 || input.source_vertex >= input.num_vertices) {
222 return false;
223 }
224
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 28 times.
 28 if (input.offsets.size() != static_cast<std::size_t>(input.num_vertices) + 1) {
225 ✗ return false;
226 }
227 return true;
228 }
229
230 28 bool BaranovADijkstraCRSMPI::PreProcessingImpl() {
231 28 MPI_Comm_size(MPI_COMM_WORLD, &world_size_);
232 28 MPI_Comm_rank(MPI_COMM_WORLD, &world_rank_);
233 28 return true;
234 }
235
236
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 19 times.
 28 void BaranovADijkstraCRSMPI::DistributeGraphData() {
237 const auto &graph = GetInput();
238 28 const int total_vertices = graph.num_vertices;
239
240 int local_start = 0;
241 int local_end = 0;
242
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 19 times.
 28 CalculateVertexDistribution(world_rank_, world_size_, total_vertices, local_start, local_end, local_num_vertices_);
243
244
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 28 times.
 28 if (local_end > total_vertices) {
245 local_end = total_vertices;
246 ✗ local_num_vertices_ = local_end - local_start;
247 }
248
249
3/4
✓ Branch 0 taken 27 times.
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 27 times.
 28 if (local_num_vertices_ <= 0 || local_start >= total_vertices) {
250 local_offsets_.clear();
251 local_columns_.clear();
252 local_values_.clear();
253 1 InitializeVertexOwnership(vertex_ownership_, total_vertices, world_size_);
254 return;
255 }
256
257 27 InitializeVertexOwnership(vertex_ownership_, total_vertices, world_size_);
258 27 local_offsets_.resize(static_cast<std::size_t>(local_num_vertices_) + 1);
259
260
2/2
✓ Branch 0 taken 78 times.
✓ Branch 1 taken 27 times.
 105 for (int i = 0; i <= local_num_vertices_; ++i) {
261 78 int global_idx = local_start + i;
262
1/2
✓ Branch 0 taken 78 times.
✗ Branch 1 not taken.
 78 if (global_idx <= total_vertices) {
263 78 local_offsets_[static_cast<std::size_t>(i)] =
264 78 graph.offsets[static_cast<std::size_t>(global_idx)] - graph.offsets[static_cast<std::size_t>(local_start)];
265 } else {
266 ✗ local_offsets_[static_cast<std::size_t>(i)] = graph.offsets[static_cast<std::size_t>(total_vertices)] -
267 ✗ graph.offsets[static_cast<std::size_t>(local_start)];
268 }
269 }
270
271 27 CopyLocalEdges(graph, local_start, local_end, total_vertices, local_columns_, local_values_);
272 }
273
274
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 28 times.
 28 bool BaranovADijkstraCRSMPI::RunImpl() {
275 const auto &graph = GetInput();
276 28 const int total_vertices = graph.num_vertices;
277
278
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 28 times.
 28 if (total_vertices <= 0) {
279 ✗ GetOutput() = std::vector<double>();
280 ✗ MPI_Barrier(MPI_COMM_WORLD);
281 ✗ return true;
282 }
283
284 28 DistributeGraphData();
285
286 28 std::vector<double> global_dist;
287 28 std::vector<double> local_dist;
288 28 std::vector<double> new_dist;
289 28 int source_owner = -1;
290
291
2/4
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 28 times.
 28 if (!InitializeDistances(graph, world_rank_, world_size_, global_dist, local_dist, new_dist, source_owner)) {
292 ✗ GetOutput() = std::vector<double>();
293 ✗ MPI_Barrier(MPI_COMM_WORLD);
294 return true;
295 }
296
297 int local_start = 0;
298 int local_end = 0;
299
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 19 times.
 28 CalculateVertexDistribution(world_rank_, world_size_, total_vertices, local_start, local_end, local_num_vertices_);
300
301
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 28 times.
 28 if (local_end > total_vertices) {
302 local_end = total_vertices;
303 ✗ local_num_vertices_ = local_end - local_start;
304 }
305
306
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 PerformDijkstraIterations(local_dist, local_offsets_, local_columns_, local_values_, local_start, local_num_vertices_,
307 total_vertices, global_dist, new_dist);
308
309
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 GetOutput() = global_dist;
310
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 MPI_Barrier(MPI_COMM_WORLD);
311 return true;
312 }
313
314 28 bool BaranovADijkstraCRSMPI::PostProcessingImpl() {
315 28 return true;
316 }
317
318 } // namespace baranov_a_dijkstra_crs
319