GCC Code Coverage Report

Directory: ./
File: tasks/zorin_d_bellman_ford/mpi/src/ops_mpi.cpp
Date: 2026-01-27 01:59:34
Exec Total Coverage
Lines: 48 48 100.0%
Functions: 6 6 100.0%
Branches: 31 46 67.4%
Line Branch Exec Source
1 #include "zorin_d_bellman_ford/mpi/include/ops_mpi.hpp"
2
3 #include <mpi.h>
4
5 #include <algorithm>
6 #include <cstddef>
7 #include <cstdint>
8 #include <utility>
9 #include <vector>
10
11 #include "zorin_d_bellman_ford/common/include/common.hpp"
12
13 namespace zorin_d_bellman_ford {
14
15
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 ZorinDBellmanFordMPI::ZorinDBellmanFordMPI(const InType &in) {
16 SetTypeOfTask(GetStaticTypeOfTask());
17 GetInput() = in;
18 6 }
19
20 6 bool ZorinDBellmanFordMPI::ValidationImpl() {
21 const auto &graph = GetInput().graph;
22
23
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (graph.vertex_count <= 0) {
24 return false;
25 }
26
2/4
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
 6 if (GetInput().source < 0 || GetInput().source >= graph.vertex_count) {
27 return false;
28 }
29
30
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (graph.row_ptr.size() != static_cast<std::size_t>(graph.vertex_count) + 1) {
31 return false;
32 }
33
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (graph.row_ptr.front() != 0) {
34 return false;
35 }
36
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (graph.col_idx.size() != graph.weights.size()) {
37 return false;
38 }
39
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (graph.row_ptr.back() != static_cast<int>(std::ssize(graph.col_idx))) {
40 return false;
41 }
42
43
2/4
✓ Branch 0 taken 960 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 960 times.
✗ Branch 3 not taken.
 960 if (!std::ranges::all_of(graph.col_idx, [&](int v) { return v >= 0 && v < graph.vertex_count; })) {
44 return false;
45 }
46 return true;
47 }
48
49 6 bool ZorinDBellmanFordMPI::PreProcessingImpl() {
50 6 const int vertex_count = GetInput().graph.vertex_count;
51 auto &dist = GetOutput();
52 6 dist.assign(static_cast<std::size_t>(vertex_count), kInf);
53 6 dist[static_cast<std::size_t>(GetInput().source)] = 0;
54 6 return true;
55 }
56
57 134 bool ZorinDBellmanFordMPI::RelaxIteration(int rank, int size, const GraphCrs &graph,
58 const std::vector<std::int64_t> &dist, std::vector<std::int64_t> &dist_next) {
59 bool updated = false;
60 134 const int vertex_count = graph.vertex_count;
61
62
2/2
✓ Branch 0 taken 5200 times.
✓ Branch 1 taken 134 times.
 5334 for (int vertex = rank; vertex < vertex_count; vertex += size) {
63
2/2
✓ Branch 0 taken 2126 times.
✓ Branch 1 taken 3074 times.
 5200 const std::int64_t du = dist[static_cast<std::size_t>(vertex)];
64
2/2
✓ Branch 0 taken 2126 times.
✓ Branch 1 taken 3074 times.
 5200 if (du >= kInf / 2) {
65 2126 continue;
66 }
67
68 3074 const int begin = graph.row_ptr[static_cast<std::size_t>(vertex)];
69 3074 const int end = graph.row_ptr[static_cast<std::size_t>(vertex) + 1];
70
71
2/2
✓ Branch 0 taken 9222 times.
✓ Branch 1 taken 3074 times.
 12296 for (int edge = begin; edge < end; ++edge) {
72
2/2
✓ Branch 0 taken 1108 times.
✓ Branch 1 taken 8114 times.
 9222 const int to = graph.col_idx[static_cast<std::size_t>(edge)];
73 9222 const std::int64_t cand = du + static_cast<std::int64_t>(graph.weights[static_cast<std::size_t>(edge)]);
74
2/2
✓ Branch 0 taken 1108 times.
✓ Branch 1 taken 8114 times.
 9222 if (cand < dist_next[static_cast<std::size_t>(to)]) {
75 1108 dist_next[static_cast<std::size_t>(to)] = cand;
76 updated = true;
77 }
78 }
79 }
80 134 return updated;
81 }
82
83 6 bool ZorinDBellmanFordMPI::RunImpl() {
84 6 int rank = 0;
85 6 int size = 0;
86 6 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
87 6 MPI_Comm_size(MPI_COMM_WORLD, &size);
88
89 6 const auto &graph = GetInput().graph;
90 6 const int vertex_count = graph.vertex_count;
91
92 6 std::vector<std::int64_t> dist = GetOutput();
93
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 std::vector<std::int64_t> dist_next(dist);
94
95
1/2
✓ Branch 0 taken 134 times.
✗ Branch 1 not taken.
 134 for (int iter = 0; iter < vertex_count - 1; ++iter) {
96
1/2
✓ Branch 1 taken 134 times.
✗ Branch 2 not taken.
 134 dist_next = dist;
97
98 134 const bool local_updated = RelaxIteration(rank, size, graph, dist, dist_next);
99
100
1/2
✓ Branch 1 taken 134 times.
✗ Branch 2 not taken.
 134 MPI_Allreduce(dist_next.data(), dist.data(), vertex_count, MPI_LONG, MPI_MIN, MPI_COMM_WORLD);
101
102
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 125 times.
 134 int updated = local_updated ? 1 : 0;
103
1/2
✓ Branch 1 taken 134 times.
✗ Branch 2 not taken.
 134 MPI_Allreduce(MPI_IN_PLACE, &updated, 1, MPI_INT, MPI_MAX, MPI_COMM_WORLD);
104
105
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 6 times.
 134 if (updated == 0) {
106 break;
107 }
108 }
109
110 GetOutput() = std::move(dist);
111 6 return true;
112 }
113
114 6 bool ZorinDBellmanFordMPI::PostProcessingImpl() {
115 6 return !GetOutput().empty();
116 }
117
118 } // namespace zorin_d_bellman_ford
119