| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include <cstddef> | ||
| 4 | #include <cstdint> | ||
| 5 | #include <limits> | ||
| 6 | #include <string> | ||
| 7 | #include <tuple> | ||
| 8 | #include <vector> | ||
| 9 | |||
| 10 | #include "task/include/task.hpp" | ||
| 11 | |||
| 12 | namespace zorin_d_bellman_ford { | ||
| 13 | |||
| 14 | struct GraphCrs { | ||
| 15 | int vertex_count{}; | ||
| 16 | std::vector<int> row_ptr; | ||
| 17 | std::vector<int> col_idx; | ||
| 18 | std::vector<int> weights; | ||
| 19 | }; | ||
| 20 | |||
| 21 |
1/2✓ Branch 2 taken 30 times.
✗ Branch 3 not taken.
|
150 | struct InType { |
| 22 | GraphCrs graph; | ||
| 23 | int source{}; | ||
| 24 | }; | ||
| 25 | |||
| 26 | using OutType = std::vector<std::int64_t>; | ||
| 27 | using TestType = std::tuple<int, std::string>; | ||
| 28 | using BaseTask = ppc::task::Task<InType, OutType>; | ||
| 29 | |||
| 30 | constexpr std::int64_t kInf = std::numeric_limits<std::int64_t>::max() / 4; | ||
| 31 | |||
| 32 | 30 | inline GraphCrs MakeGraphCrsDeterministic(int vertex_count, int edges_per_vertex) { | |
| 33 | 30 | GraphCrs graph; | |
| 34 | 30 | graph.vertex_count = vertex_count; | |
| 35 |
1/2✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
|
30 | graph.row_ptr.resize(static_cast<std::size_t>(vertex_count) + 1, 0); |
| 36 | |||
| 37 | 30 | const int edges = edges_per_vertex > 0 ? edges_per_vertex : 1; | |
| 38 | 30 | const std::size_t total_edges = static_cast<std::size_t>(vertex_count) * static_cast<std::size_t>(edges); | |
| 39 | |||
| 40 |
1/2✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
|
30 | graph.col_idx.reserve(total_edges); |
| 41 |
1/2✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
|
30 | graph.weights.reserve(total_edges); |
| 42 | |||
| 43 | int edge_pos = 0; | ||
| 44 |
2/2✓ Branch 0 taken 1600 times.
✓ Branch 1 taken 30 times.
|
1630 | for (int vertex = 0; vertex < vertex_count; ++vertex) { |
| 45 | 1600 | graph.row_ptr[static_cast<std::size_t>(vertex)] = edge_pos; | |
| 46 |
2/2✓ Branch 0 taken 4800 times.
✓ Branch 1 taken 1600 times.
|
6400 | for (int k = 1; k <= edges; ++k) { |
| 47 | 4800 | const int to = (vertex + k) % vertex_count; | |
| 48 |
1/2✓ Branch 0 taken 4800 times.
✗ Branch 1 not taken.
|
4800 | const int weight = 1 + ((vertex * 31 + to * 17 + k * 13) % 20); |
| 49 | graph.col_idx.push_back(to); | ||
| 50 | graph.weights.push_back(weight); | ||
| 51 | 4800 | ++edge_pos; | |
| 52 | } | ||
| 53 | } | ||
| 54 | 30 | graph.row_ptr[static_cast<std::size_t>(vertex_count)] = edge_pos; | |
| 55 | 30 | return graph; | |
| 56 | ✗ | } | |
| 57 | |||
| 58 | inline InType MakeInput(int vertex_count, int edges_per_vertex, int source) { | ||
| 59 | 30 | return InType{.graph = MakeGraphCrsDeterministic(vertex_count, edges_per_vertex), .source = source}; | |
| 60 | } | ||
| 61 | |||
| 62 | } // namespace zorin_d_bellman_ford | ||
| 63 |