GCC Code Coverage Report

Directory: ./
File: tasks/morozova_s_connected_components/mpi/src/ops_mpi.cpp
Date: 2026-02-23 23:20:07
Exec Total Coverage
Lines: 150 156 96.2%
Functions: 17 18 94.4%
Branches: 138 192 71.9%
Line Branch Exec Source
1 #include "morozova_s_connected_components/mpi/include/ops_mpi.hpp"
2
3 #include <mpi.h>
4
5 #include <algorithm>
6 #include <array>
7 #include <cstddef>
8 #include <queue>
9 #include <unordered_map>
10 #include <utility>
11 #include <vector>
12
13 #include "morozova_s_connected_components/common/include/common.hpp"
14
15 namespace morozova_s_connected_components {
16
17 namespace {
18 constexpr int kLabelOffset = 1000000;
19 constexpr int kTagLocal = 0;
20 constexpr int kTagFinal = 1;
21
22 constexpr std::array<std::pair<int, int>, 8> kShifts = {
23 {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}}};
24 } // namespace
25
26
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 MorozovaSConnectedComponentsMPI::MorozovaSConnectedComponentsMPI(const InType &in) {
27 SetTypeOfTask(GetStaticTypeOfTask());
28
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 GetInput() = in;
29 GetOutput() = {};
30 8 }
31
32
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8 times.
 8 bool MorozovaSConnectedComponentsMPI::ValidationImpl() {
33 const auto &input = GetInput();
34
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8 times.
 8 if (input.empty()) {
35 return true;
36 }
37 const size_t cols = input.front().size();
38
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 72 times.
 80 for (const auto &row : input) {
39
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 72 times.
 72 if (row.size() != cols) {
40 return false;
41 }
42
2/2
✓ Branch 0 taken 688 times.
✓ Branch 1 taken 72 times.
 760 for (int v : row) {
43
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 688 times.
 688 if (v != 0 && v != 1) {
44 return false;
45 }
46 }
47 }
48 return true;
49 }
50
51
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8 times.
 8 bool MorozovaSConnectedComponentsMPI::PreProcessingImpl() {
52 8 rows_ = static_cast<int>(GetInput().size());
53
54
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8 times.
 8 if (rows_ == 0) {
55 ✗ cols_ = 0;
56 GetOutput().clear();
57 ✗ return true;
58 }
59
60 8 cols_ = static_cast<int>(GetInput().front().size());
61
62 auto &output = GetOutput();
63 8 output.resize(rows_);
64
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 8 times.
 80 for (int i = 0; i < rows_; ++i) {
65 72 output[i].assign(cols_, 0);
66 }
67
68 return true;
69 }
70
71 8 void MorozovaSConnectedComponentsMPI::InitMPI() {
72 8 MPI_Comm_rank(MPI_COMM_WORLD, &rank_);
73 8 MPI_Comm_size(MPI_COMM_WORLD, &size_);
74 8 rows_per_proc_ = rows_ / size_;
75 8 remainder_ = rows_ % size_;
76 8 }
77
78 ✗ std::pair<int, int> MorozovaSConnectedComponentsMPI::ComputeRowRange() const {
79
1/4
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 8 const int start = (rank_ * rows_per_proc_) + std::min(rank_, remainder_);
80
1/4
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 8 const int end = start + rows_per_proc_ + (rank_ < remainder_ ? 1 : 0);
81 ✗ return {start, end};
82 }
83
84 156 std::vector<std::pair<int, int>> MorozovaSConnectedComponentsMPI::GetNeighbors(int row, int col) {
85 156 std::vector<std::pair<int, int>> neighbors;
86 const auto &input = GetInput();
87
2/2
✓ Branch 0 taken 1248 times.
✓ Branch 1 taken 156 times.
 1404 for (const auto &[dr, dc] : kShifts) {
88 1248 const int nr = row + dr;
89 1248 const int nc = col + dc;
90
10/10
✓ Branch 0 taken 1206 times.
✓ Branch 1 taken 42 times.
✓ Branch 2 taken 1146 times.
✓ Branch 3 taken 60 times.
✓ Branch 4 taken 1108 times.
✓ Branch 5 taken 38 times.
✓ Branch 6 taken 1053 times.
✓ Branch 7 taken 55 times.
✓ Branch 8 taken 456 times.
✓ Branch 9 taken 597 times.
 1248 if (nr >= 0 && nr < rows_ && nc >= 0 && nc < cols_ && input[nr][nc] == 1) {
91
1/2
✓ Branch 1 taken 456 times.
✗ Branch 2 not taken.
 456 neighbors.emplace_back(nr, nc);
92 }
93 }
94 156 return neighbors;
95 }
96
97 42 void MorozovaSConnectedComponentsMPI::FloodFill(int row, int col, int label) {
98 auto &output = GetOutput();
99 std::queue<std::pair<int, int>> q;
100 q.emplace(row, col);
101 42 output[row][col] = label;
102
2/2
✓ Branch 0 taken 156 times.
✓ Branch 1 taken 42 times.
 198 while (!q.empty()) {
103 const auto [r, c] = q.front();
104 q.pop();
105
3/4
✓ Branch 1 taken 156 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 456 times.
✓ Branch 4 taken 156 times.
 612 for (const auto &[nr, nc] : GetNeighbors(r, c)) {
106
2/2
✓ Branch 0 taken 114 times.
✓ Branch 1 taken 342 times.
 456 if (output[nr][nc] == 0) {
107
1/2
✓ Branch 1 taken 114 times.
✗ Branch 2 not taken.
 114 output[nr][nc] = label;
108 q.emplace(nr, nc);
109 }
110 }
111 }
112 42 }
113
114 8 void MorozovaSConnectedComponentsMPI::ComputeLocalComponents(int start_row, int end_row, int base_label) {
115 const auto &input = GetInput();
116 auto &output = GetOutput();
117 int local_label = 1;
118
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 8 times.
 44 for (int i = start_row; i < end_row; ++i) {
119
2/2
✓ Branch 0 taken 344 times.
✓ Branch 1 taken 36 times.
 380 for (int j = 0; j < cols_; ++j) {
120
4/4
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 248 times.
✓ Branch 2 taken 42 times.
✓ Branch 3 taken 54 times.
 344 if (input[i][j] == 1 && output[i][j] == 0) {
121 42 FloodFill(i, j, base_label + local_label);
122 42 ++local_label;
123 }
124 }
125 }
126 8 }
127
128 4 void MorozovaSConnectedComponentsMPI::GatherLocalResults() {
129 auto &output = GetOutput();
130
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 for (int proc = 1; proc < size_; ++proc) {
131
1/2
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
 4 const int ps = (proc * rows_per_proc_) + std::min(proc, remainder_);
132
1/2
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
 4 const int pe = ps + rows_per_proc_ + (proc < remainder_ ? 1 : 0);
133 4 const int pr = pe - ps;
134
1/2
✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
 4 std::vector<int> buf(static_cast<size_t>(pr) * static_cast<size_t>(cols_));
135 MPI_Status status;
136
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 MPI_Recv(buf.data(), static_cast<int>(buf.size()), MPI_INT, proc, kTagLocal, MPI_COMM_WORLD, &status);
137 4 int count = 0;
138
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 MPI_Get_count(&status, MPI_INT, &count);
139
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
 4 if (static_cast<size_t>(count) != buf.size()) {
140 return;
141 }
142
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 4 times.
 22 for (int i = 0; i < pr; ++i) {
143 18 const ptrdiff_t offset = static_cast<ptrdiff_t>(i) * static_cast<ptrdiff_t>(cols_);
144 18 std::copy(buf.begin() + offset, buf.begin() + offset + cols_, output[ps + i].begin());
145 }
146 }
147 }
148
149 108 bool MorozovaSConnectedComponentsMPI::TryProcessBoundaryCell(int proc, int j, int dj,
150 std::unordered_map<int, int> &parent) {
151 const auto &input = GetInput();
152 const auto &output = GetOutput();
153
1/2
✓ Branch 0 taken 108 times.
✗ Branch 1 not taken.
 108 const int br = (proc * rows_per_proc_) + std::min(proc, remainder_);
154
155
2/4
✓ Branch 0 taken 108 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 108 times.
 108 if (br <= 0 || br >= rows_) {
156 return false;
157 }
158
159 108 const int nj = j + dj;
160
4/4
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 104 times.
✓ Branch 2 taken 4 times.
✓ Branch 3 taken 100 times.
 108 if (nj < 0 || nj >= cols_) {
161 return false;
162 }
163
164
4/4
✓ Branch 0 taken 61 times.
✓ Branch 1 taken 39 times.
✓ Branch 2 taken 21 times.
✓ Branch 3 taken 18 times.
 100 if (input[br - 1][j] != 1 || input[br][nj] != 1) {
165 return false;
166 }
167
168 18 const int a = output[br - 1][j];
169 18 const int b = output[br][nj];
170
171
3/6
✗ Branch 0 not taken.
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 18 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 18 times.
 18 if (a == 0 || b == 0 || a == b) {
172 return false;
173 }
174
175
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 18 times.
 18 int root_a = a;
176 auto it = parent.find(a);
177
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 18 times.
 18 if (it != parent.end()) {
178 ✗ root_a = it->second;
179 }
180
181
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 3 times.
 18 int root_b = b;
182 it = parent.find(b);
183
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 3 times.
 18 if (it != parent.end()) {
184 15 root_b = it->second;
185 }
186
187
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 15 times.
 18 if (root_a != root_b) {
188 3 parent[std::max(root_a, root_b)] = std::min(root_a, root_b);
189 }
190
191 return true;
192 }
193
194 96 int MorozovaSConnectedComponentsMPI::FindRoot(std::unordered_map<int, int> &parent, int v) {
195 96 int root = v;
196 96 std::vector<int> path;
197
3/4
✓ Branch 0 taken 31 times.
✓ Branch 1 taken 96 times.
✓ Branch 2 taken 31 times.
✗ Branch 3 not taken.
 158 while (parent.contains(root) && parent[root] != root) {
198 path.push_back(root);
199 31 root = parent[root];
200 }
201
2/2
✓ Branch 0 taken 31 times.
✓ Branch 1 taken 96 times.
 127 for (int node : path) {
202
1/2
✓ Branch 1 taken 31 times.
✗ Branch 2 not taken.
 31 parent[node] = root;
203 }
204
2/2
✓ Branch 0 taken 31 times.
✓ Branch 1 taken 65 times.
 127 return root;
205 }
206
207 4 void MorozovaSConnectedComponentsMPI::MergeBoundaries() {
208 auto &output = GetOutput();
209 std::unordered_map<int, int> parent;
210
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 for (int proc = 1; proc < size_; ++proc) {
211
1/2
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
 4 const int br = (proc * rows_per_proc_) + std::min(proc, remainder_);
212
2/4
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
 4 if (br <= 0 || br >= rows_) {
213 ✗ continue;
214 }
215
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 4 times.
 40 for (int j = 0; j < cols_; ++j) {
216
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 36 TryProcessBoundaryCell(proc, j, -1, parent);
217
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 36 TryProcessBoundaryCell(proc, j, 0, parent);
218
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 36 TryProcessBoundaryCell(proc, j, 1, parent);
219 }
220 }
221
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 4 times.
 40 for (int i = 0; i < rows_; ++i) {
222
2/2
✓ Branch 0 taken 344 times.
✓ Branch 1 taken 36 times.
 380 for (int j = 0; j < cols_; ++j) {
223
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 248 times.
 344 int &v = output[i][j];
224
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 248 times.
 344 if (v > 0) {
225
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 v = FindRoot(parent, v);
226 }
227 }
228 }
229 4 }
230
231 4 void MorozovaSConnectedComponentsMPI::NormalizeLabels() {
232 auto &output = GetOutput();
233 std::unordered_map<int, int> remap;
234 int next = 1;
235
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 4 times.
 40 for (auto &row : output) {
236
2/2
✓ Branch 0 taken 344 times.
✓ Branch 1 taken 36 times.
 380 for (int &v : row) {
237
2/2
✓ Branch 0 taken 248 times.
✓ Branch 1 taken 96 times.
 344 if (v > 0) {
238 auto it = remap.find(v);
239
2/2
✓ Branch 0 taken 39 times.
✓ Branch 1 taken 57 times.
 96 if (it == remap.end()) {
240
2/4
✓ Branch 1 taken 39 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 39 times.
✗ Branch 5 not taken.
 39 remap[v] = next++;
241 39 v = remap[v];
242 } else {
243 57 v = it->second;
244 }
245 }
246 }
247 }
248 4 }
249
250 4 void MorozovaSConnectedComponentsMPI::BroadcastResult() {
251 auto &output = GetOutput();
252 4 std::vector<int> flat(static_cast<size_t>(rows_) * static_cast<size_t>(cols_));
253
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 4 times.
 40 for (int i = 0; i < rows_; ++i) {
254 36 const ptrdiff_t offset = static_cast<ptrdiff_t>(i) * static_cast<ptrdiff_t>(cols_);
255 36 std::copy(output[i].begin(), output[i].end(), flat.begin() + offset);
256 }
257
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 for (int proc = 1; proc < size_; ++proc) {
258
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 MPI_Send(flat.data(), static_cast<int>(flat.size()), MPI_INT, proc, kTagFinal, MPI_COMM_WORLD);
259 }
260 4 }
261
262 4 void MorozovaSConnectedComponentsMPI::SendLocalResult(int start_row, int end_row) {
263 const auto &output = GetOutput();
264 4 const int lr = end_row - start_row;
265 4 std::vector<int> send(static_cast<size_t>(lr) * static_cast<size_t>(cols_));
266
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 4 times.
 22 for (int i = 0; i < lr; ++i) {
267 18 const ptrdiff_t offset = static_cast<ptrdiff_t>(i) * static_cast<ptrdiff_t>(cols_);
268 18 std::copy(output[start_row + i].begin(), output[start_row + i].end(), send.begin() + offset);
269 }
270
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 MPI_Send(send.data(), static_cast<int>(send.size()), MPI_INT, 0, kTagLocal, MPI_COMM_WORLD);
271 4 }
272
273 4 void MorozovaSConnectedComponentsMPI::ReceiveFinalResult() {
274 auto &output = GetOutput();
275
1/2
✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
 4 std::vector<int> recv(static_cast<size_t>(rows_) * static_cast<size_t>(cols_));
276 MPI_Status status;
277
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 MPI_Recv(recv.data(), static_cast<int>(recv.size()), MPI_INT, 0, kTagFinal, MPI_COMM_WORLD, &status);
278 4 int count = 0;
279
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 MPI_Get_count(&status, MPI_INT, &count);
280
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
 4 if (static_cast<size_t>(count) != recv.size()) {
281 return;
282 }
283
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 4 times.
 40 for (int i = 0; i < rows_; ++i) {
284 36 const ptrdiff_t offset = static_cast<ptrdiff_t>(i) * static_cast<ptrdiff_t>(cols_);
285 36 std::copy(recv.begin() + offset, recv.begin() + offset + cols_, output[i].begin());
286 }
287 }
288
289 8 bool MorozovaSConnectedComponentsMPI::RunImpl() {
290 8 InitMPI();
291
2/4
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
 8 if (rows_ == 0 || cols_ == 0) {
292 return true;
293 }
294 const auto [start, end] = ComputeRowRange();
295 8 ComputeLocalComponents(start, end, rank_ * kLabelOffset);
296
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 if (rank_ == 0) {
297 4 GatherLocalResults();
298 4 MergeBoundaries();
299 4 NormalizeLabels();
300 4 BroadcastResult();
301 } else {
302 4 SendLocalResult(start, end);
303 4 ReceiveFinalResult();
304 }
305 return true;
306 }
307
308
1/2
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
 8 bool MorozovaSConnectedComponentsMPI::PostProcessingImpl() {
309 auto &output = GetOutput();
310
1/2
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
 8 if (output.empty()) {
311 return true;
312 }
313 8 int max_label = 0;
314
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 8 times.
 80 for (const auto &row : output) {
315
2/2
✓ Branch 0 taken 688 times.
✓ Branch 1 taken 72 times.
 760 for (int v : row) {
316 688 max_label = std::max(max_label, v);
317 }
318 }
319 8 output.push_back({max_label});
320 8 return true;
321 }
322
323 } // namespace morozova_s_connected_components
324