| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #include "gasenin_l_djstra/tbb/include/ops_tbb.hpp" | ||
| 2 | |||
| 3 | #include <tbb/tbb.h> | ||
| 4 | |||
| 5 | #include <algorithm> | ||
| 6 | #include <cstddef> | ||
| 7 | #include <vector> | ||
| 8 | |||
| 9 | #include "gasenin_l_djstra/common/include/common.hpp" | ||
| 10 | |||
| 11 | namespace gasenin_l_djstra { | ||
| 12 | |||
| 13 | 12 | GaseninLDjstraTBB::GaseninLDjstraTBB(const InType &in) { | |
| 14 | SetTypeOfTask(GetStaticTypeOfTask()); | ||
| 15 | 12 | GetInput() = in; | |
| 16 | GetOutput() = 0; | ||
| 17 | 12 | } | |
| 18 | |||
| 19 | 12 | bool GaseninLDjstraTBB::ValidationImpl() { | |
| 20 |
2/4✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 12 times.
|
12 | return (GetInput() > 0) && (GetOutput() == 0); |
| 21 | } | ||
| 22 | |||
| 23 | 12 | bool GaseninLDjstraTBB::PreProcessingImpl() { | |
| 24 | 12 | vertex_count_ = GetInput(); | |
| 25 | 12 | adj_.resize(vertex_count_); | |
| 26 |
2/2✓ Branch 0 taken 48 times.
✓ Branch 1 taken 12 times.
|
60 | for (int i = 0; i < vertex_count_ - 1; ++i) { |
| 27 | 48 | adj_[i].emplace_back(i + 1, 1); | |
| 28 | } | ||
| 29 | 12 | dist_.assign(vertex_count_, kInf); | |
| 30 | 12 | dist_[0] = 0; | |
| 31 | 12 | return true; | |
| 32 | } | ||
| 33 | |||
| 34 | 12 | bool GaseninLDjstraTBB::RunImpl() { | |
| 35 | 12 | std::vector<bool> visited(vertex_count_, false); | |
| 36 | |||
| 37 |
2/2✓ Branch 0 taken 60 times.
✓ Branch 1 taken 12 times.
|
72 | for (int i = 0; i < vertex_count_; ++i) { |
| 38 | 60 | int u = -1; | |
| 39 | int min_dist = kInf; | ||
| 40 |
2/2✓ Branch 0 taken 332 times.
✓ Branch 1 taken 60 times.
|
392 | for (int j = 0; j < vertex_count_; ++j) { |
| 41 |
4/4✓ Branch 0 taken 196 times.
✓ Branch 1 taken 136 times.
✓ Branch 2 taken 60 times.
✓ Branch 3 taken 136 times.
|
332 | if (!visited[j] && dist_[j] < min_dist) { |
| 42 | min_dist = dist_[j]; | ||
| 43 | 60 | u = j; | |
| 44 | } | ||
| 45 | } | ||
| 46 |
2/4✓ Branch 0 taken 60 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 60 times.
✗ Branch 3 not taken.
|
60 | if (u == -1 || dist_[u] == kInf) { |
| 47 | break; | ||
| 48 | } | ||
| 49 | visited[u] = true; | ||
| 50 | |||
| 51 | const auto &neighbors = adj_[u]; | ||
| 52 |
1/2✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
|
60 | tbb::parallel_for(static_cast<size_t>(0), neighbors.size(), [&](size_t idx) { |
| 53 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
|
48 | int v = neighbors[idx].first; |
| 54 | 48 | int w = neighbors[idx].second; | |
| 55 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
|
48 | int new_dist = dist_[u] + w; |
| 56 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
|
48 | dist_[v] = std::min(new_dist, dist_[v]); |
| 57 | 48 | }); | |
| 58 | } | ||
| 59 | 12 | return true; | |
| 60 | } | ||
| 61 | |||
| 62 | 12 | bool GaseninLDjstraTBB::PostProcessingImpl() { | |
| 63 | int sum = 0; | ||
| 64 |
2/2✓ Branch 0 taken 60 times.
✓ Branch 1 taken 12 times.
|
72 | for (int d : dist_) { |
| 65 |
1/2✓ Branch 0 taken 60 times.
✗ Branch 1 not taken.
|
60 | if (d < kInf) { |
| 66 | 60 | sum += d; | |
| 67 | } | ||
| 68 | } | ||
| 69 | 12 | GetOutput() = sum; | |
| 70 | 12 | return true; | |
| 71 | } | ||
| 72 | |||
| 73 | } // namespace gasenin_l_djstra | ||
| 74 |