| Line | Branch | Decision | Exec | Source |
|---|---|---|---|---|
| 1 | // Copyright 2019-2022 Cambridge Quantum Computing | |||
| 2 | // | |||
| 3 | // Licensed under the Apache License, Version 2.0 (the "License"); | |||
| 4 | // you may not use this file except in compliance with the License. | |||
| 5 | // You may obtain a copy of the License at | |||
| 6 | // | |||
| 7 | // http://www.apache.org/licenses/LICENSE-2.0 | |||
| 8 | // | |||
| 9 | // Unless required by applicable law or agreed to in writing, software | |||
| 10 | // distributed under the License is distributed on an "AS IS" BASIS, | |||
| 11 | // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |||
| 12 | // See the License for the specific language governing permissions and | |||
| 13 | // limitations under the License. | |||
| 14 | ||||
| 15 | #include "BestTsaWithArch.hpp" | |||
| 16 | ||||
| 17 | #include <tkassert/Assert.hpp> | |||
| 18 | #include <tkrng/RNG.hpp> | |||
| 19 | #include <tktokenswap/BestFullTsa.hpp> | |||
| 20 | ||||
| 21 | #include "DistancesFromArchitecture.hpp" | |||
| 22 | #include "NeighboursFromArchitecture.hpp" | |||
| 23 | ||||
| 24 | namespace tket { | |||
| 25 | ||||
| 26 | using namespace tsa_internal; | |||
| 27 | ||||
| 28 | 2451 | void BestTsaWithArch::append_solution( | ||
| 29 | SwapList& swaps, VertexMapping& vertex_mapping, | |||
| 30 | const ArchitectureMapping& arch_mapping) { | |||
| 31 |
1/2✓ Branch 1 taken 2451 times.
✗ Branch 2 not taken.
|
2451 | DistancesFromArchitecture distances(arch_mapping); | |
| 32 |
1/2✓ Branch 1 taken 2451 times.
✗ Branch 2 not taken.
|
2451 | NeighboursFromArchitecture neighbours(arch_mapping); | |
| 33 |
1/2✓ Branch 1 taken 2451 times.
✗ Branch 2 not taken.
|
2451 | RNG rng; | |
| 34 |
1/2✓ Branch 1 taken 2451 times.
✗ Branch 2 not taken.
|
2451 | RiverFlowPathFinder path_finder(distances, neighbours, rng); | |
| 35 |
2/4✓ Branch 1 taken 2451 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2451 times.
✗ Branch 5 not taken.
|
2451 | BestFullTsa().append_partial_solution( | |
| 36 | swaps, vertex_mapping, distances, neighbours, path_finder); | |||
| 37 | 2451 | } | ||
| 38 | ||||
| 39 | 2 | std::vector<std::pair<Node, Node>> BestTsaWithArch::get_swaps( | ||
| 40 | const Architecture& architecture, const NodeMapping& node_mapping) { | |||
| 41 | 2 | std::vector<std::pair<Node, Node>> swaps; | ||
| 42 | // Before all the conversion and object construction, | |||
| 43 | // doesn't take long to check if it's actually trivial | |||
| 44 | 2 | bool trivial = true; | ||
| 45 |
1/2✓ Branch 5 taken 3 times.
✗ Branch 6 not taken.
|
1/2✓ Decision 'true' taken 3 times.
✗ Decision 'false' not taken.
|
3 | for (const auto& entry : node_mapping) { |
| 46 |
3/4✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 2 times.
✓ Branch 4 taken 1 times.
|
2/2✓ Decision 'true' taken 2 times.
✓ Decision 'false' taken 1 times.
|
3 | if (entry.first != entry.second) { |
| 47 | 2 | trivial = false; | ||
| 48 | 2 | break; | ||
| 49 | } | |||
| 50 | } | |||
| 51 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 2 times.
|
2 | if (trivial) { |
| 52 | ✗ | return swaps; | ||
| 53 | } | |||
| 54 | // Now convert the Nodes into raw vertices for use in TSA objects. | |||
| 55 |
1/2✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
|
2 | const ArchitectureMapping arch_mapping(architecture); | |
| 56 | 2 | VertexMapping vertex_mapping; | ||
| 57 |
2/2✓ Branch 4 taken 27 times.
✓ Branch 5 taken 2 times.
|
2/2✓ Decision 'true' taken 27 times.
✓ Decision 'false' taken 2 times.
|
29 | for (const auto& node_entry : node_mapping) { |
| 58 |
1/2✓ Branch 1 taken 27 times.
✗ Branch 2 not taken.
|
27 | vertex_mapping[arch_mapping.get_vertex(node_entry.first)] = | |
| 59 |
2/4✓ Branch 1 taken 27 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 27 times.
✗ Branch 5 not taken.
|
27 | arch_mapping.get_vertex(node_entry.second); | |
| 60 | } | |||
| 61 | TKET_ASSERT(vertex_mapping.size() == node_mapping.size()); | |||
| 62 |
1/2✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
|
2 | check_mapping(vertex_mapping); | |
| 63 | ||||
| 64 |
1/2✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
|
2 | SwapList raw_swap_list; | |
| 65 |
1/2✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
|
2 | BestTsaWithArch::append_solution(raw_swap_list, vertex_mapping, arch_mapping); | |
| 66 | ||||
| 67 | // Finally, convert the raw swaps back to nodes. | |||
| 68 |
2/4✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
|
2 | swaps.reserve(raw_swap_list.size()); | |
| 69 |
3/4✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 29 times.
✓ Branch 5 taken 2 times.
|
0/1? Decision couldn't be analyzed.
|
31 | for (auto id_opt = raw_swap_list.front_id(); id_opt; |
| 70 |
1/2✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
|
29 | id_opt = raw_swap_list.next(id_opt.value())) { | |
| 71 |
1/2✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
|
29 | const auto& raw_swap = raw_swap_list.at(id_opt.value()); | |
| 72 |
3/6✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 29 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 29 times.
✗ Branch 9 not taken.
|
29 | swaps.emplace_back(std::make_pair( | |
| 73 |
1/2✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
|
29 | arch_mapping.get_node(raw_swap.first), | |
| 74 |
1/2✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
|
29 | arch_mapping.get_node(raw_swap.second))); | |
| 75 | } | |||
| 76 | 2 | return swaps; | ||
| 77 | 2 | } | ||
| 78 | ||||
| 79 | } // namespace tket | |||
| 80 |