GCC Code Coverage Report

Directory: ./
File: tasks/vasiliev_m_bellman_ford_crs/mpi/src/ops_mpi.cpp
Date: 2026-01-27 01:59:34
Exec Total Coverage
Lines: 60 61 98.4%
Functions: 7 7 100.0%
Branches: 41 64 64.1%
Line Branch Exec Source
1 #include "vasiliev_m_bellman_ford_crs/mpi/include/ops_mpi.hpp"
2
3 #include <mpi.h>
4
5 #include <limits>
6 #include <vector>
7
8 #include "vasiliev_m_bellman_ford_crs/common/include/common.hpp"
9
10 namespace vasiliev_m_bellman_ford_crs {
11
12
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 VasilievMBellmanFordCrsMPI::VasilievMBellmanFordCrsMPI(const InType &in) {
13 SetTypeOfTask(GetStaticTypeOfTask());
14
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 GetInput() = in;
15 8 GetOutput() = OutType{};
16 8 }
17
18
1/2
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
 8 bool VasilievMBellmanFordCrsMPI::ValidationImpl() {
19 const auto &in = GetInput();
20
21
3/6
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 8 times.
✗ Branch 5 not taken.
 8 if (in.row_ptr.empty() || in.col_ind.empty() || in.vals.empty()) {
22 return false;
23 }
24
25
1/2
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
 8 if (in.col_ind.size() != in.vals.size()) {
26 return false;
27 }
28
29 8 const int vertices = static_cast<int>(in.row_ptr.size()) - 1;
30
1/2
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
 8 if (vertices <= 0) {
31 return false;
32 }
33
34
2/4
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 8 times.
 8 if (in.source < 0 || in.source >= vertices) {
35 ✗ return false;
36 }
37
38 return true;
39 }
40
41 8 bool VasilievMBellmanFordCrsMPI::PreProcessingImpl() {
42 const auto &in = GetInput();
43 8 const int vertices = static_cast<int>(in.row_ptr.size()) - 1;
44
45 8 const int inf = std::numeric_limits<int>::max();
46 8 GetOutput().assign(vertices, inf);
47 8 GetOutput()[in.source] = 0;
48
49 8 return true;
50 }
51
52 8 bool VasilievMBellmanFordCrsMPI::RunImpl() {
53 const auto &in = GetInput();
54 auto &dist = GetOutput();
55
56 8 int rank = 0;
57 8 int size = 1;
58 8 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
59 8 MPI_Comm_size(MPI_COMM_WORLD, &size);
60
61 8 const int vertices = static_cast<int>(in.row_ptr.size()) - 1;
62
63 8 std::vector<int> counts(size);
64
1/4
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 8 std::vector<int> displs(size);
65
66
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 if (rank == 0) {
67 4 CalcCountsAndDispls(vertices, size, counts, displs);
68 }
69
70
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 MPI_Bcast(counts.data(), size, MPI_INT, 0, MPI_COMM_WORLD);
71
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 MPI_Bcast(displs.data(), size, MPI_INT, 0, MPI_COMM_WORLD);
72
73
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 int start = displs[rank];
74 8 int end = start + counts[rank];
75
76
1/4
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 8 std::vector<int> local_dist(vertices);
77
78
2/2
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 2 times.
 28 for (int i = 0; i < vertices - 1; i++) {
79
1/2
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
 26 local_dist = dist;
80
81
1/2
✓ Branch 2 taken 26 times.
✗ Branch 3 not taken.
 26 int local_updated = RelaxLocalEdges(start, end, in, dist, local_dist);
82
83
1/2
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
 26 MPI_Allreduce(local_dist.data(), dist.data(), vertices, MPI_INT, MPI_MIN, MPI_COMM_WORLD);
84
85 26 int global_updated = 0;
86
1/2
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
 26 MPI_Allreduce(&local_updated, &global_updated, 1, MPI_INT, MPI_SUM, MPI_COMM_WORLD);
87
88
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 6 times.
 26 if (global_updated == 0) {
89 break;
90 }
91 }
92
93 8 return true;
94 }
95
96 8 bool VasilievMBellmanFordCrsMPI::PostProcessingImpl() {
97 8 return true;
98 }
99
100 4 void VasilievMBellmanFordCrsMPI::CalcCountsAndDispls(int n, int size, std::vector<int> &counts,
101 std::vector<int> &displs) {
102 4 int chunk = n / size;
103 4 int remain = n % size;
104
105
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 4 times.
 12 for (int i = 0; i < size; i++) {
106
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 2 times.
 14 counts[i] = chunk + (i < remain ? 1 : 0);
107 }
108
109 4 displs[0] = 0;
110
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 for (int i = 1; i < size; i++) {
111 4 displs[i] = displs[i - 1] + counts[i - 1];
112 }
113 4 }
114
115 26 int VasilievMBellmanFordCrsMPI::RelaxLocalEdges(int start, int end, const InType &in, const std::vector<int> &dist,
116 std::vector<int> &local_dist) {
117 const int inf = std::numeric_limits<int>::max();
118 int local_updated = 0;
119
120
2/2
✓ Branch 0 taken 65 times.
✓ Branch 1 taken 26 times.
 91 for (int vertex = start; vertex < end; vertex++) {
121
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 35 times.
 65 if (dist[vertex] == inf) {
122 30 continue;
123 }
124
125
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 35 times.
 83 for (int edge = in.row_ptr[vertex]; edge < in.row_ptr[vertex + 1]; edge++) {
126
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 30 times.
 48 int v = in.col_ind[edge];
127 48 int w = in.vals[edge];
128
129
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 30 times.
 48 if (local_dist[v] > dist[vertex] + w) {
130 18 local_dist[v] = dist[vertex] + w;
131 local_updated = 1;
132 }
133 }
134 }
135
136 26 return local_updated;
137 }
138
139 } // namespace vasiliev_m_bellman_ford_crs
140