| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #include "zorin_d_bellman_ford/seq/include/ops_seq.hpp" | ||
| 2 | |||
| 3 | #include <cstddef> | ||
| 4 | #include <cstdint> | ||
| 5 | |||
| 6 | #include "zorin_d_bellman_ford/common/include/common.hpp" | ||
| 7 | |||
| 8 | namespace zorin_d_bellman_ford { | ||
| 9 | |||
| 10 |
1/2✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
|
24 | ZorinDBellmanFordSEQ::ZorinDBellmanFordSEQ(const InType &in) { |
| 11 | SetTypeOfTask(GetStaticTypeOfTask()); | ||
| 12 | GetInput() = in; | ||
| 13 | 24 | } | |
| 14 | |||
| 15 | 24 | bool ZorinDBellmanFordSEQ::ValidationImpl() { | |
| 16 | const auto &graph = GetInput().graph; | ||
| 17 | |||
| 18 |
1/2✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
|
24 | if (graph.vertex_count <= 0) { |
| 19 | return false; | ||
| 20 | } | ||
| 21 |
2/4✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
|
24 | if (GetInput().source < 0 || GetInput().source >= graph.vertex_count) { |
| 22 | return false; | ||
| 23 | } | ||
| 24 | |||
| 25 |
1/2✓ Branch 0 taken 24 times.
✗ Branch 1 not taken.
|
24 | if (graph.row_ptr.size() != static_cast<std::size_t>(graph.vertex_count) + 1) { |
| 26 | return false; | ||
| 27 | } | ||
| 28 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
|
24 | if (graph.col_idx.size() != graph.weights.size()) { |
| 29 | ✗ | return false; | |
| 30 | } | ||
| 31 | return true; | ||
| 32 | } | ||
| 33 | |||
| 34 | 24 | bool ZorinDBellmanFordSEQ::PreProcessingImpl() { | |
| 35 | 24 | const int vertex_count = GetInput().graph.vertex_count; | |
| 36 | auto &dist = GetOutput(); | ||
| 37 | 24 | dist.assign(static_cast<std::size_t>(vertex_count), kInf); | |
| 38 | 24 | dist[static_cast<std::size_t>(GetInput().source)] = 0; | |
| 39 | 24 | return true; | |
| 40 | } | ||
| 41 | |||
| 42 | 24 | bool ZorinDBellmanFordSEQ::RunImpl() { | |
| 43 | const auto &graph = GetInput().graph; | ||
| 44 | 24 | const int vertex_count = graph.vertex_count; | |
| 45 | auto &dist = GetOutput(); | ||
| 46 | |||
| 47 |
1/2✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
|
48 | for (int iter = 0; iter < vertex_count - 1; ++iter) { |
| 48 | bool updated = false; | ||
| 49 | |||
| 50 |
2/2✓ Branch 0 taken 2560 times.
✓ Branch 1 taken 48 times.
|
2608 | for (int vertex = 0; vertex < vertex_count; ++vertex) { |
| 51 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 2560 times.
|
2560 | const std::int64_t du = dist[static_cast<std::size_t>(vertex)]; |
| 52 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 2560 times.
|
2560 | if (du >= kInf / 2) { |
| 53 | ✗ | continue; | |
| 54 | } | ||
| 55 | |||
| 56 | 2560 | const int begin = graph.row_ptr[static_cast<std::size_t>(vertex)]; | |
| 57 | 2560 | const int end = graph.row_ptr[static_cast<std::size_t>(vertex) + 1]; | |
| 58 | |||
| 59 |
2/2✓ Branch 0 taken 7680 times.
✓ Branch 1 taken 2560 times.
|
10240 | for (int edge = begin; edge < end; ++edge) { |
| 60 |
2/2✓ Branch 0 taken 2232 times.
✓ Branch 1 taken 5448 times.
|
7680 | const int to = graph.col_idx[static_cast<std::size_t>(edge)]; |
| 61 | 7680 | const std::int64_t cand = du + static_cast<std::int64_t>(graph.weights[static_cast<std::size_t>(edge)]); | |
| 62 |
2/2✓ Branch 0 taken 2232 times.
✓ Branch 1 taken 5448 times.
|
7680 | if (cand < dist[static_cast<std::size_t>(to)]) { |
| 63 | 2232 | dist[static_cast<std::size_t>(to)] = cand; | |
| 64 | updated = true; | ||
| 65 | } | ||
| 66 | } | ||
| 67 | } | ||
| 68 |
2/2✓ Branch 0 taken 24 times.
✓ Branch 1 taken 24 times.
|
48 | if (!updated) { |
| 69 | break; | ||
| 70 | } | ||
| 71 | } | ||
| 72 | 24 | return true; | |
| 73 | } | ||
| 74 | |||
| 75 | 24 | bool ZorinDBellmanFordSEQ::PostProcessingImpl() { | |
| 76 | 24 | return !GetOutput().empty(); | |
| 77 | } | ||
| 78 | |||
| 79 | } // namespace zorin_d_bellman_ford | ||
| 80 |