| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #include "vasiliev_m_bellman_ford_crs/seq/include/ops_seq.hpp" | ||
| 2 | |||
| 3 | #include <limits> | ||
| 4 | #include <vector> | ||
| 5 | |||
| 6 | #include "vasiliev_m_bellman_ford_crs/common/include/common.hpp" | ||
| 7 | |||
| 8 | namespace vasiliev_m_bellman_ford_crs { | ||
| 9 | |||
| 10 |
1/2✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
|
32 | VasilievMBellmanFordCrsSEQ::VasilievMBellmanFordCrsSEQ(const InType &in) { |
| 11 | SetTypeOfTask(GetStaticTypeOfTask()); | ||
| 12 |
1/2✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
|
32 | GetInput() = in; |
| 13 | 32 | GetOutput() = OutType{}; | |
| 14 | 32 | } | |
| 15 | |||
| 16 |
1/2✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
|
32 | bool VasilievMBellmanFordCrsSEQ::ValidationImpl() { |
| 17 | const auto &in = GetInput(); | ||
| 18 | |||
| 19 |
3/6✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 32 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 32 times.
✗ Branch 5 not taken.
|
32 | if (in.row_ptr.empty() || in.col_ind.empty() || in.vals.empty()) { |
| 20 | return false; | ||
| 21 | } | ||
| 22 | |||
| 23 |
1/2✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
|
32 | if (in.col_ind.size() != in.vals.size()) { |
| 24 | return false; | ||
| 25 | } | ||
| 26 | |||
| 27 | 32 | const int vertices = static_cast<int>(in.row_ptr.size()) - 1; | |
| 28 |
1/2✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
|
32 | if (vertices <= 0) { |
| 29 | return false; | ||
| 30 | } | ||
| 31 | |||
| 32 |
2/4✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 32 times.
|
32 | if (in.source < 0 || in.source >= vertices) { |
| 33 | ✗ | return false; | |
| 34 | } | ||
| 35 | |||
| 36 | return true; | ||
| 37 | } | ||
| 38 | |||
| 39 | 32 | bool VasilievMBellmanFordCrsSEQ::PreProcessingImpl() { | |
| 40 | const auto &in = GetInput(); | ||
| 41 | 32 | const int vertices = static_cast<int>(in.row_ptr.size()) - 1; | |
| 42 | |||
| 43 | 32 | const int inf = std::numeric_limits<int>::max(); | |
| 44 | 32 | GetOutput().assign(vertices, inf); | |
| 45 | 32 | GetOutput()[in.source] = 0; | |
| 46 | |||
| 47 | 32 | return true; | |
| 48 | } | ||
| 49 | |||
| 50 | 32 | bool VasilievMBellmanFordCrsSEQ::RunImpl() { | |
| 51 | const auto &in = GetInput(); | ||
| 52 | auto &dist = GetOutput(); | ||
| 53 | |||
| 54 | 32 | const int vertices = static_cast<int>(in.row_ptr.size()) - 1; | |
| 55 | const int inf = std::numeric_limits<int>::max(); | ||
| 56 | |||
| 57 |
1/2✓ Branch 0 taken 72 times.
✗ Branch 1 not taken.
|
72 | for (int i = 0; i < vertices - 1; i++) { |
| 58 | bool updated = false; | ||
| 59 | |||
| 60 |
2/2✓ Branch 0 taken 360 times.
✓ Branch 1 taken 72 times.
|
432 | for (int vertex = 0; vertex < vertices; vertex++) { |
| 61 |
2/2✓ Branch 0 taken 48 times.
✓ Branch 1 taken 312 times.
|
360 | if (dist[vertex] == inf) { |
| 62 | 48 | continue; | |
| 63 | } | ||
| 64 | |||
| 65 |
2/2✓ Branch 0 taken 360 times.
✓ Branch 1 taken 312 times.
|
672 | for (int edge = in.row_ptr[vertex]; edge < in.row_ptr[vertex + 1]; edge++) { |
| 66 |
2/2✓ Branch 0 taken 144 times.
✓ Branch 1 taken 216 times.
|
360 | int v = in.col_ind[edge]; |
| 67 | 360 | int w = in.vals[edge]; | |
| 68 | |||
| 69 |
2/2✓ Branch 0 taken 144 times.
✓ Branch 1 taken 216 times.
|
360 | if (dist[v] > dist[vertex] + w) { |
| 70 | 144 | dist[v] = dist[vertex] + w; | |
| 71 | updated = true; | ||
| 72 | } | ||
| 73 | } | ||
| 74 | } | ||
| 75 | |||
| 76 |
2/2✓ Branch 0 taken 40 times.
✓ Branch 1 taken 32 times.
|
72 | if (!updated) { |
| 77 | break; | ||
| 78 | } | ||
| 79 | } | ||
| 80 | |||
| 81 | 32 | return true; | |
| 82 | } | ||
| 83 | |||
| 84 | 32 | bool VasilievMBellmanFordCrsSEQ::PostProcessingImpl() { | |
| 85 | 32 | return true; | |
| 86 | } | ||
| 87 | |||
| 88 | } // namespace vasiliev_m_bellman_ford_crs | ||
| 89 |