GCC Code Coverage Report

Directory: ./
File: tasks/chyokotov_a_convex_hull_finding/mpi/src/ops_mpi.cpp
Date: 2026-01-10 02:40:41
Exec Total Coverage
Lines: 207 219 94.5%
Functions: 17 20 85.0%
Branches: 187 266 70.3%
Line Branch Exec Source
1 #include "chyokotov_a_convex_hull_finding/mpi/include/ops_mpi.hpp"
2
3 #include <mpi.h>
4
5 #include <algorithm>
6 #include <array>
7 #include <climits>
8 #include <cstddef>
9 #include <cstdint>
10 #include <queue>
11 #include <ranges>
12 #include <utility>
13 #include <vector>
14
15 #include "chyokotov_a_convex_hull_finding/common/include/common.hpp"
16
17 namespace chyokotov_a_convex_hull_finding {
18
19
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 ChyokotovConvexHullFindingMPI::ChyokotovConvexHullFindingMPI(const InType &in) {
20 SetTypeOfTask(GetStaticTypeOfTask());
21 GetInput().clear();
22
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 GetInput().reserve(in.size());
23
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 12 times.
 40 for (const auto &row : in) {
24
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 GetInput().push_back(row);
25 }
26
27 GetOutput().clear();
28 12 }
29
30 ✗ bool ChyokotovConvexHullFindingMPI::Check(const std::vector<std::vector<int>> &input) {
31 ✗ for (size_t i = 0; i < input.size(); ++i) {
32 ✗ for (size_t j = 0; j < input[0].size(); ++j) {
33 ✗ if ((input[i][j] != 1 && input[i][j] != 0) || (input[0].size() != input[i].size())) {
34 return false;
35 }
36 }
37 }
38 return true;
39 }
40
41 12 bool ChyokotovConvexHullFindingMPI::ValidationImpl() {
42 12 int rank{};
43 12 int is_valid = 1;
44 12 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
45
46 if (rank == 0) {
47 const auto &input = GetInput();
48 if (!input.empty()) {
49 Check(input);
50 }
51 }
52 12 MPI_Bcast(&is_valid, 1, MPI_INT, 0, MPI_COMM_WORLD);
53
54 12 return (is_valid == 1);
55 }
56
57 12 bool ChyokotovConvexHullFindingMPI::PreProcessingImpl() {
58 12 return true;
59 }
60
61 10 std::pair<std::vector<int>, int> ChyokotovConvexHullFindingMPI::DistributeImageData(int rank, int size, int width,
62 int height) {
63 const auto &input = GetInput();
64 auto [start_row, end_row] = CalculateRowDistribution(rank, size, height);
65 10 int local_rows = end_row - start_row;
66
67 20 std::vector<int> local_data(static_cast<size_t>(local_rows) * static_cast<size_t>(width));
68
69
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 if (rank == 0) {
70
1/4
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 5 std::vector<int> send_counts(size);
71
1/4
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 5 std::vector<int> displs(size);
72
73
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 5 times.
 15 for (int i = 0; i < size; i++) {
74 auto [proc_start, proc_end] = CalculateRowDistribution(i, size, height);
75 10 send_counts[i] = (proc_end - proc_start) * width;
76 10 displs[i] = proc_start * width;
77 }
78
79 5 std::vector<int> flat_input;
80
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 5 times.
 19 for (const auto &row : input) {
81 14 flat_input.insert(flat_input.end(), row.begin(), row.end());
82 }
83
84
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 MPI_Scatterv(flat_input.data(), send_counts.data(), displs.data(), MPI_INT, local_data.data(), local_rows * width,
85 MPI_INT, 0, MPI_COMM_WORLD);
86 } else {
87
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 MPI_Scatterv(nullptr, nullptr, nullptr, MPI_INT, local_data.data(), local_rows * width, MPI_INT, 0, MPI_COMM_WORLD);
88 }
89
90 10 return {local_data, local_rows};
91 }
92
93 ✗ std::pair<int, int> ChyokotovConvexHullFindingMPI::CalculateRowDistribution(int rank, int size, int height) {
94 20 int base_rows = height / size;
95 20 int remainder = height % size;
96
97
4/6
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 8 times.
✓ Branch 3 taken 2 times.
✓ Branch 4 taken 8 times.
✓ Branch 5 taken 2 times.
 20 int start_row = (rank * base_rows) + std::min(rank, remainder);
98
6/8
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 8 times.
✓ Branch 5 taken 2 times.
✓ Branch 7 taken 8 times.
✓ Branch 8 taken 2 times.
 46 int end_row = start_row + base_rows + (rank < remainder ? 1 : 0);
99
100 ✗ return {start_row, end_row};
101 }
102
103 10 std::vector<std::vector<std::pair<int, int>>> ChyokotovConvexHullFindingMPI::FindConnectedComponentsMPI(
104 int rank, int size, int start_row, int end_row, int width, int height, const std::vector<int> &local_data) {
105 10 int local_rows = end_row - start_row;
106
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 9 times.
 10 if (local_rows == 0) {
107 1 return {};
108 }
109
110 9 bool has_top = start_row > 0;
111 9 bool has_bottom = end_row < height;
112
4/4
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 5 times.
✓ Branch 3 taken 4 times.
 14 int extended_rows = local_rows + (has_top ? 1 : 0) + (has_bottom ? 1 : 0);
113
114 9 std::vector<int> extended(static_cast<size_t>(extended_rows) * static_cast<size_t>(width), 0);
115
116 int offset = has_top ? 1 : 0;
117
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 9 times.
 23 for (int i = 0; i < local_rows; i++) {
118 14 int src_idx = i * width;
119 14 int dst_idx = (offset + i) * width;
120
1/2
✓ Branch 0 taken 14 times.
✗ Branch 1 not taken.
 14 std::copy_n(&local_data[src_idx], width, &extended[dst_idx]);
121 }
122
123
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 ExchangeBoundaryRows(has_top, has_bottom, rank, size, width, local_data, extended);
124
125 9 int global_y_offset = start_row - (has_top ? 1 : 0);
126
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 auto all = ProcessExtendedRegion(extended, extended_rows, width, global_y_offset);
127
128
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 return FilterLocalComponents(all, start_row, end_row);
129 9 }
130
131 ✗ int64_t ChyokotovConvexHullFindingMPI::Cross(const std::pair<int, int> &a, const std::pair<int, int> &b,
132 const std::pair<int, int> &c) {
133 14 return (static_cast<int64_t>(b.first - a.first) * (c.second - a.second)) -
134 14 (static_cast<int64_t>(b.second - a.second) * (c.first - a.first));
135 }
136
137
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
 2 std::vector<std::pair<int, int>> ChyokotovConvexHullFindingMPI::ConvexHullAndrew(
138 const std::vector<std::pair<int, int>> &points) {
139
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
 2 if (points.size() <= 2) {
140 ✗ return points;
141 }
142
143 2 std::vector<std::pair<int, int>> sorted_points = points;
144 std::ranges::sort(sorted_points);
145
146 auto [first, last] = std::ranges::unique(sorted_points);
147 sorted_points.erase(first, last);
148
149 2 std::vector<std::pair<int, int>> hull;
150
151
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 2 times.
 10 for (const auto &p : sorted_points) {
152
4/4
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 2 times.
✓ Branch 3 taken 4 times.
 10 while (hull.size() >= 2 && Cross(hull[hull.size() - 2], hull.back(), p) >= 0) {
153 hull.pop_back();
154 }
155 hull.push_back(p);
156 }
157
158 size_t lower_size = hull.size();
159
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 2 times.
 10 for (const auto &p : std::ranges::reverse_view(sorted_points)) {
160
4/4
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 4 times.
✓ Branch 3 taken 4 times.
 12 while (hull.size() > lower_size && Cross(hull[hull.size() - 2], hull.back(), p) >= 0) {
161 hull.pop_back();
162 }
163 hull.push_back(p);
164 }
165
166 hull.pop_back();
167 return hull;
168 }
169
170 9 void ChyokotovConvexHullFindingMPI::ExchangeBoundaryRows(bool top, bool bottom, int rank, int size, int width,
171 const std::vector<int> &local, std::vector<int> &ext) {
172
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 5 times.
 9 if (top) {
173 4 std::vector<int> recv(width);
174
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 MPI_Sendrecv(local.data(), width, MPI_INT, rank - 1, 0, recv.data(), width, MPI_INT, rank - 1, 1, MPI_COMM_WORLD,
175 MPI_STATUS_IGNORE);
176 std::ranges::copy(recv.begin(), recv.end(), ext.begin());
177 }
178
179
3/4
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 5 times.
✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
 9 if (bottom && rank + 1 < size) {
180
1/2
✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
 4 std::vector<int> recv(width);
181
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 MPI_Sendrecv(&local[local.size() - width], width, MPI_INT, rank + 1, 1, recv.data(), width, MPI_INT, rank + 1, 0,
182 MPI_COMM_WORLD, MPI_STATUS_IGNORE);
183 std::ranges::copy(recv.begin(), recv.end(), ext.end() - width);
184 }
185 9 }
186
187 9 std::vector<std::vector<std::pair<int, int>>> ChyokotovConvexHullFindingMPI::ProcessExtendedRegion(
188 const std::vector<int> &extended_pixels, int extended_rows, int width, int global_y_offset) {
189
1/2
✓ Branch 2 taken 9 times.
✗ Branch 3 not taken.
 9 std::vector<std::vector<bool>> visited(extended_rows, std::vector<bool>(width, false));
190 9 std::vector<std::vector<std::pair<int, int>>> all_components;
191
192
2/2
✓ Branch 0 taken 22 times.
✓ Branch 1 taken 9 times.
 31 for (int row = 0; row < extended_rows; ++row) {
193
2/2
✓ Branch 0 taken 71 times.
✓ Branch 1 taken 22 times.
 93 for (int col = 0; col < width; ++col) {
194
2/2
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 45 times.
 71 size_t idx = (static_cast<size_t>(row) * static_cast<size_t>(width)) + static_cast<size_t>(col);
195
196
4/4
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 45 times.
✓ Branch 2 taken 16 times.
✓ Branch 3 taken 10 times.
 71 if (extended_pixels[idx] == 1 && !visited[row][col]) {
197
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 auto component = ExtractComponent(col, row, extended_pixels, visited, width, extended_rows, global_y_offset);
198 all_components.push_back(std::move(component));
199 }
200 }
201 }
202
203 9 return all_components;
204 9 }
205
206 16 std::vector<std::pair<int, int>> ChyokotovConvexHullFindingMPI::ExtractComponent(
207 int start_x, int start_y, const std::vector<int> &extended_pixels, std::vector<std::vector<bool>> &visited,
208 int width, int extended_rows, int global_y_offset) {
209
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 std::vector<std::pair<int, int>> component;
210 std::queue<std::pair<int, int>> queue;
211 queue.emplace(start_x, start_y);
212
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
 16 visited[start_y][start_x] = true;
213
214 16 const std::array<std::pair<int, int>, 4> directions = {{{0, -1}, {0, 1}, {-1, 0}, {1, 0}}};
215
216
2/2
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 16 times.
 42 while (!queue.empty()) {
217 auto [x, y] = queue.front();
218 queue.pop();
219
220
1/2
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
 26 component.emplace_back(x, global_y_offset + y);
221
222
2/2
✓ Branch 0 taken 104 times.
✓ Branch 1 taken 26 times.
 130 for (const auto &[dx, dy] : directions) {
223 104 int nx = x + dx;
224 104 int ny = y + dy;
225
226
8/8
✓ Branch 0 taken 97 times.
✓ Branch 1 taken 7 times.
✓ Branch 2 taken 90 times.
✓ Branch 3 taken 7 times.
✓ Branch 4 taken 80 times.
✓ Branch 5 taken 10 times.
✓ Branch 6 taken 72 times.
✓ Branch 7 taken 8 times.
 104 if (nx >= 0 && nx < width && ny >= 0 && ny < extended_rows) {
227
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 48 times.
 72 size_t nidx = (static_cast<size_t>(ny) * static_cast<size_t>(width)) + static_cast<size_t>(nx);
228
229
4/4
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 48 times.
✓ Branch 2 taken 10 times.
✓ Branch 3 taken 14 times.
 72 if (extended_pixels[nidx] == 1 && !visited[ny][nx]) {
230 visited[ny][nx] = true;
231 queue.emplace(nx, ny);
232 }
233 }
234 }
235 }
236
237 16 return component;
238 }
239
240 9 std::vector<std::vector<std::pair<int, int>>> ChyokotovConvexHullFindingMPI::FilterLocalComponents(
241 const std::vector<std::vector<std::pair<int, int>>> &all_components, int start_row, int end_row) {
242 9 std::vector<std::vector<std::pair<int, int>>> local_components;
243
244
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 9 times.
 25 for (const auto &component : all_components) {
245
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16 times.
 16 if (component.empty()) {
246 ✗ continue;
247 }
248
249 16 int min_y = component[0].second;
250
2/2
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 16 times.
 42 for (const auto &[x, y] : component) {
251 26 min_y = std::min(y, min_y);
252 }
253
254
4/4
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 10 times.
✓ Branch 3 taken 2 times.
 16 if (min_y >= start_row && min_y < end_row) {
255
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 local_components.push_back(component);
256 }
257 }
258
259 9 return local_components;
260 ✗ }
261
262 5 void ChyokotovConvexHullFindingMPI::SendHullsToRank0(const std::vector<std::vector<std::pair<int, int>>> &local_hulls) {
263 5 int hull_count = static_cast<int>(local_hulls.size());
264 5 MPI_Send(&hull_count, 1, MPI_INT, 0, 0, MPI_COMM_WORLD);
265
266
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 2 times.
 5 if (hull_count == 0) {
267 3 return;
268 }
269
270 2 std::vector<int> hull_sizes;
271 2 std::vector<int> flat_points;
272
273
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 2 times.
 6 for (const auto &hull : local_hulls) {
274
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
 4 int size = static_cast<int>(hull.size());
275 hull_sizes.push_back(size);
276
277
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 4 times.
 11 for (const auto &[x, y] : hull) {
278 flat_points.push_back(x);
279 flat_points.push_back(y);
280 }
281 }
282
283
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 MPI_Send(hull_sizes.data(), hull_count, MPI_INT, 0, 1, MPI_COMM_WORLD);
284
285 2 int total_points = static_cast<int>(flat_points.size() / 2);
286
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 MPI_Send(&total_points, 1, MPI_INT, 0, 2, MPI_COMM_WORLD);
287
288
1/2
✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
 2 if (total_points > 0) {
289
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 MPI_Send(flat_points.data(), static_cast<int>(flat_points.size()), MPI_INT, 0, 3, MPI_COMM_WORLD);
290 }
291 }
292
293 5 void ChyokotovConvexHullFindingMPI::ReceiveHullsFromRank(int src_rank, std::vector<int> &all_sizes,
294 std::vector<int> &global_flat) {
295 5 int hull_count = 0;
296 5 MPI_Recv(&hull_count, 1, MPI_INT, src_rank, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
297
298
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 2 times.
 5 if (hull_count == 0) {
299 3 return;
300 }
301
302 2 std::vector<int> sizes(static_cast<size_t>(hull_count));
303
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 MPI_Recv(sizes.data(), hull_count, MPI_INT, src_rank, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
304
305 2 all_sizes.insert(all_sizes.end(), sizes.begin(), sizes.end());
306
307 2 int total_points = 0;
308
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 MPI_Recv(&total_points, 1, MPI_INT, src_rank, 2, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
309
310
1/2
✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
 2 if (total_points > 0) {
311
1/4
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 2 std::vector<int> points_data(static_cast<size_t>(total_points) * 2);
312
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 MPI_Recv(points_data.data(), total_points * 2, MPI_INT, src_rank, 3, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
313
314
1/2
✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
 2 global_flat.insert(global_flat.end(), points_data.begin(), points_data.end());
315 }
316 }
317
318 10 std::vector<std::vector<std::pair<int, int>>> ChyokotovConvexHullFindingMPI::GatherHullsOnRank0(
319 int rank, int size, const std::vector<std::vector<std::pair<int, int>>> &local_hulls) {
320
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 if (rank == 0) {
321 5 std::vector<int> all_sizes;
322 5 std::vector<int> global_flat;
323
324
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 5 times.
 11 for (const auto &hull : local_hulls) {
325
1/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 6 all_sizes.push_back(static_cast<int>(hull.size()));
326
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 6 times.
 16 for (const auto &[x, y] : hull) {
327 global_flat.push_back(x);
328 global_flat.push_back(y);
329 }
330 }
331
332
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 for (int src = 1; src < size; ++src) {
333
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 ReceiveHullsFromRank(src, all_sizes, global_flat);
334 }
335
336 5 std::vector<std::vector<std::pair<int, int>>> all_hulls;
337 size_t idx = 0;
338
339
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 5 times.
 15 for (int hull_size : all_sizes) {
340 10 std::vector<std::pair<int, int>> hull;
341
2/2
✓ Branch 0 taken 17 times.
✓ Branch 1 taken 10 times.
 27 for (int i = 0; i < hull_size; ++i, idx += 2) {
342
1/2
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
 17 hull.emplace_back(global_flat[idx], global_flat[idx + 1]);
343 }
344 all_hulls.push_back(std::move(hull));
345 }
346
347 return all_hulls;
348 ✗ }
349 5 SendHullsToRank0(local_hulls);
350 5 return {};
351 }
352
353 8 std::vector<std::vector<std::pair<int, int>>> ChyokotovConvexHullFindingMPI::ReconstructHulls(
354 const std::vector<int> &hull_sizes, const std::vector<int> &flat_points) {
355
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 std::vector<std::vector<std::pair<int, int>>> result;
356
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 result.reserve(hull_sizes.size());
357
358 size_t flat_idx = 0;
359
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 8 times.
 28 for (int hull_size : hull_sizes) {
360 20 std::vector<std::pair<int, int>> hull;
361
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 hull.reserve(static_cast<size_t>(hull_size));
362
363
2/2
✓ Branch 0 taken 34 times.
✓ Branch 1 taken 20 times.
 54 for (int j = 0; j < hull_size; ++j) {
364
1/2
✓ Branch 1 taken 34 times.
✗ Branch 2 not taken.
 34 hull.emplace_back(flat_points[flat_idx], flat_points[flat_idx + 1]);
365 34 flat_idx += 2;
366 }
367
368 result.push_back(std::move(hull));
369 }
370
371 8 return result;
372 ✗ }
373
374 10 std::vector<std::vector<std::pair<int, int>>> ChyokotovConvexHullFindingMPI::BroadcastResultToAllRanks(
375 int rank, const std::vector<std::vector<std::pair<int, int>>> &global_hulls_on_rank0) {
376
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 int total_hulls = (rank == 0) ? static_cast<int>(global_hulls_on_rank0.size()) : 0;
377 10 MPI_Bcast(&total_hulls, 1, MPI_INT, 0, MPI_COMM_WORLD);
378
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 8 times.
 10 if (total_hulls == 0) {
379 2 return {};
380 }
381
382 8 std::vector<int> all_sizes(total_hulls);
383
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 if (rank == 0) {
384
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 4 times.
 14 for (int i = 0; i < total_hulls; ++i) {
385 10 all_sizes[i] = static_cast<int>(global_hulls_on_rank0[i].size());
386 }
387 }
388
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 MPI_Bcast(all_sizes.data(), total_hulls, MPI_INT, 0, MPI_COMM_WORLD);
389
390 8 int total_points = 0;
391
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 if (rank == 0) {
392
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 4 times.
 14 for (int size : all_sizes) {
393 10 total_points += size;
394 }
395 }
396
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 MPI_Bcast(&total_points, 1, MPI_INT, 0, MPI_COMM_WORLD);
397
398
1/4
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 8 std::vector<int> flat_points(static_cast<size_t>(total_points) * 2);
399
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 if (rank == 0) {
400 size_t idx = 0;
401
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 4 times.
 14 for (const auto &hull : global_hulls_on_rank0) {
402
2/2
✓ Branch 0 taken 17 times.
✓ Branch 1 taken 10 times.
 27 for (const auto &[x, y] : hull) {
403 17 flat_points[idx++] = x;
404 17 flat_points[idx++] = y;
405 }
406 }
407 }
408
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 MPI_Bcast(flat_points.data(), total_points * 2, MPI_INT, 0, MPI_COMM_WORLD);
409
410
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 return ReconstructHulls(all_sizes, flat_points);
411 }
412
413 12 bool ChyokotovConvexHullFindingMPI::RunImpl() {
414 12 int rank{};
415 12 int size{};
416
417 12 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
418 12 MPI_Comm_size(MPI_COMM_WORLD, &size);
419
420 12 int n{};
421 12 int m{};
422
423
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 if (rank == 0) {
424 6 n = static_cast<int>(GetInput().size());
425
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 1 times.
 6 if (n != 0) {
426 5 m = static_cast<int>(GetInput()[0].size());
427 }
428 }
429
430 12 MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
431
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 2 times.
 12 if (n == 0) {
432 return true;
433 }
434 10 MPI_Bcast(&m, 1, MPI_INT, 0, MPI_COMM_WORLD);
435
436 10 auto [local_data, local_rows] = DistributeImageData(rank, size, m, n);
437
438
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 2 times.
 10 auto [start_row, end_row] = CalculateRowDistribution(rank, size, n);
439
440
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 auto components = FindConnectedComponentsMPI(rank, size, start_row, end_row, m, n, local_data);
441
442
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 std::vector<std::vector<std::pair<int, int>>> convex_hulls;
443
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 convex_hulls.reserve(components.size());
444
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 for (const auto &component : components) {
445
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 8 times.
 10 if (component.size() >= 3) {
446
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 4 convex_hulls.push_back(ConvexHullAndrew(component));
447
1/2
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
 8 } else if (!component.empty()) {
448
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 convex_hulls.push_back(component);
449 }
450 }
451
452
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 auto global_hulls = GatherHullsOnRank0(rank, size, convex_hulls);
453
454
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 GetOutput() = BroadcastResultToAllRanks(rank, global_hulls);
455
456 return true;
457 10 }
458
459 12 bool ChyokotovConvexHullFindingMPI::PostProcessingImpl() {
460 12 return true;
461 }
462
463 } // namespace chyokotov_a_convex_hull_finding
464