GCC Code Coverage Report

Directory: ./
File: Placement/NeighbourPlacements.cpp
Date: 2022-10-15 05:10:18
Warnings: 3 unchecked decisions!
Exec Total Coverage
Lines: 91 91 100.0%
Functions: 6 6 100.0%
Branches: 109 178 61.2%
Decisions: 28 34 82.4%
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 "NeighbourPlacements.hpp"
16
17 #include <cstdlib>
18 #include <sstream>
19 #include <string>
20 #include <tklog/TketLog.hpp>
21 #include <tktokenswap/SwapListOptimiser.hpp>
22
23 namespace tket {
24
25 17 NeighbourPlacements::NeighbourPlacements(
26 17 const Architecture& arc, const qubit_mapping_t& init_map)
27
3/6
✓ Branch 2 taken 17 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 17 times.
✗ Branch 7 not taken.
✓ Branch 10 taken 17 times.
✗ Branch 11 not taken.
 17 : arc_(arc), init_map_(init_map), u_to_node_(), rng_() {
28
1/2
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
 17 auto nodes = arc_.get_all_nodes_vec();
29
2/2
✓ Branch 1 taken 54 times.
✓ Branch 2 taken 17 times.
2/2
✓ Decision 'true' taken 54 times.
✓ Decision 'false' taken 17 times.
 71 for (unsigned i = 0; i < nodes.size(); ++i) {
30
2/4
✓ Branch 2 taken 54 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 54 times.
✗ Branch 6 not taken.
 54 u_to_node_.left.insert({i, nodes[i]});
31 }
32 17 }
33
34 27 NeighbourPlacements::ResultVec NeighbourPlacements::get(
35 unsigned dist, unsigned n, bool optimise, unsigned seed,
36 unsigned max_tries) {
37
1/2
✓ Branch 1 taken 27 times.
✗ Branch 2 not taken.
 27 rng_.set_seed(seed);
38
39 // define a comparison function for placements
40 27 std::vector<Qubit> keys;
41
2/2
✓ Branch 8 taken 84 times.
✓ Branch 9 taken 27 times.
2/2
✓ Decision 'true' taken 84 times.
✓ Decision 'false' taken 27 times.
 111 for (auto [k, v] : init_map_) {
42
1/2
✓ Branch 1 taken 84 times.
✗ Branch 2 not taken.
 84 keys.push_back(k);
43 84 }
44 141 auto map_compare = [&keys](
45 const qubit_mapping_t& a, const qubit_mapping_t& b) {
46
2/2
✓ Branch 6 taken 266 times.
✓ Branch 7 taken 44 times.
2/2
✓ Decision 'true' taken 266 times.
✓ Decision 'false' taken 44 times.
 310 for (auto k : keys) {
47
5/8
✓ Branch 1 taken 266 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 266 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 266 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 63 times.
✓ Branch 10 taken 203 times.
2/2
✓ Decision 'true' taken 63 times.
✓ Decision 'false' taken 203 times.
 266 if (a.at(k) < b.at(k)) {
48 63 return true;
49
5/8
✓ Branch 1 taken 203 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 203 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 203 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 34 times.
✓ Branch 10 taken 169 times.
2/2
✓ Decision 'true' taken 34 times.
✓ Decision 'false' taken 169 times.
 203 } else if (a.at(k) > b.at(k)) {
50 34 return false;
51 }
52
2/2
✓ Branch 1 taken 169 times.
✓ Branch 2 taken 97 times.
 266 }
53 44 return false;
54 27 };
55 // set of all generated placement maps
56
1/2
✓ Branch 2 taken 27 times.
✗ Branch 3 not taken.
 27 std::set<qubit_mapping_t, decltype(map_compare)> placements(map_compare);
57
58 27 ResultVec resvec;
59
2/2
✓ Branch 0 taken 37 times.
✓ Branch 1 taken 27 times.
2/2
✓ Decision 'true' taken 37 times.
✓ Decision 'false' taken 27 times.
 64 for (unsigned i = 0; i < n; ++i) {
60 37 unsigned n_unsuccessful = 0;
61
2/2
✓ Branch 0 taken 58 times.
✓ Branch 1 taken 1 times.
2/2
✓ Decision 'true' taken 58 times.
✓ Decision 'false' taken 1 times.
 59 while (n_unsuccessful < max_tries) {
62
1/2
✓ Branch 1 taken 58 times.
✗ Branch 2 not taken.
 58 Result res = gen_result(dist, optimise, max_tries);
63
3/4
✓ Branch 1 taken 58 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 36 times.
✓ Branch 4 taken 22 times.
2/2
✓ Decision 'true' taken 36 times.
✓ Decision 'false' taken 22 times.
 58 if (!placements.contains(res.map)) {
64
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 36 resvec.push_back(res);
65
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 36 placements.insert(res.map);
66 36 break;
67 }
68 22 ++n_unsuccessful;
69
2/2
✓ Branch 1 taken 22 times.
✓ Branch 2 taken 36 times.
 58 }
70
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 36 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 36 times.
 37 if (n_unsuccessful == max_tries) {
71
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 std::stringstream ss;
72
3/6
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 times.
✗ Branch 8 not taken.
 1 ss << "Could not generate " << n << " distinct placements";
73
3/6
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 1 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 1 times.
✗ Branch 9 not taken.
 1 tket_log()->warn(ss.str());
74 1 }
75 }
76 54 return resvec;
77 27 }
78
79 58 NeighbourPlacements::Result NeighbourPlacements::gen_result(
80 unsigned dist, bool optimise, unsigned max_tries) {
81
1/2
✓ Branch 1 taken 58 times.
✗ Branch 2 not taken.
 58 SwapList swaps;
82 58 tsa_internal::SwapListOptimiser optimiser;
83
84 // it might be impossible to find `dist` non-trivial swaps
85 58 unsigned n_unsuccessful = 0;
86
87
7/8
✓ Branch 1 taken 219 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 162 times.
✓ Branch 4 taken 57 times.
✓ Branch 5 taken 161 times.
✓ Branch 6 taken 1 times.
✓ Branch 7 taken 161 times.
✓ Branch 8 taken 58 times.
0/1
? Decision couldn't be analyzed.
 219 while (swaps.size() < dist && n_unsuccessful < max_tries) {
88
1/2
✓ Branch 1 taken 161 times.
✗ Branch 2 not taken.
 161 Swap new_swap = gen_swap();
89
90
2/2
✓ Branch 0 taken 118 times.
✓ Branch 1 taken 43 times.
2/2
✓ Decision 'true' taken 118 times.
✓ Decision 'false' taken 43 times.
 161 if (optimise) {
91
1/2
✓ Branch 1 taken 118 times.
✗ Branch 2 not taken.
 118 SwapList swaps_candidate = swaps;
92
1/2
✓ Branch 1 taken 118 times.
✗ Branch 2 not taken.
 118 swaps_candidate.push_back(new_swap);
93
1/2
✓ Branch 1 taken 118 times.
✗ Branch 2 not taken.
 118 optimiser.full_optimise(swaps_candidate);
94
4/6
✓ Branch 1 taken 118 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 118 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 79 times.
✓ Branch 7 taken 39 times.
2/2
✓ Decision 'true' taken 79 times.
✓ Decision 'false' taken 39 times.
 118 if (swaps_candidate.size() > swaps.size()) {
95 79 swaps = std::move(swaps_candidate);
96 79 n_unsuccessful = 0;
97 } else {
98 39 ++n_unsuccessful;
99 }
100 118 } else {
101
1/2
✓ Branch 1 taken 43 times.
✗ Branch 2 not taken.
 43 swaps.push_back(new_swap);
102 }
103 }
104
105
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 57 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 57 times.
 58 if (n_unsuccessful == max_tries) {
106
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 std::stringstream ss;
107
3/6
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 times.
✗ Branch 8 not taken.
0/1
? Decision couldn't be analyzed.
 1 ss << "Unable to generate " << dist << " swaps for given architecture";
108
3/6
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 1 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 1 times.
✗ Branch 9 not taken.
 1 tket_log()->warn(ss.str());
109 1 }
110
111
2/4
✓ Branch 1 taken 58 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 58 times.
✗ Branch 5 not taken.
 174 return convert_to_res(swaps.to_vector());
112 58 }
113
114 161 Swap NeighbourPlacements::gen_swap() {
115
1/2
✓ Branch 1 taken 161 times.
✗ Branch 2 not taken.
 161 auto edges = arc_.get_all_edges_vec();
116 161 unsigned m = edges.size();
117
1/2
✓ Branch 1 taken 161 times.
✗ Branch 2 not taken.
 161 auto [n1, n2] = edges[rng_.get_size_t(m - 1)];
118
2/4
✓ Branch 1 taken 161 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 161 times.
✗ Branch 5 not taken.
 161 Swap new_swap{u_to_node_.right.at(n1), u_to_node_.right.at(n2)};
119 161 return new_swap;
120 161 }
121
122 58 NeighbourPlacements::Result NeighbourPlacements::convert_to_res(
123 const SwapVec& swaps) {
124 58 NodeSwapVec node_swaps;
125
2/2
✓ Branch 6 taken 122 times.
✓ Branch 7 taken 58 times.
2/2
✓ Decision 'true' taken 122 times.
✓ Decision 'false' taken 58 times.
 180 for (auto [u1, u2] : swaps) {
126
3/6
✓ Branch 1 taken 122 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 122 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 122 times.
✗ Branch 9 not taken.
 122 node_swaps.push_back({u_to_node_.left.at(u1), u_to_node_.left.at(u2)});
127 }
128
129
1/2
✓ Branch 2 taken 58 times.
✗ Branch 3 not taken.
 58 qubit_bimap_t qubit_to_node;
130
1/2
✓ Branch 3 taken 58 times.
✗ Branch 4 not taken.
 58 qubit_to_node.left.insert(init_map_.begin(), init_map_.end());
131
2/2
✓ Branch 8 taken 122 times.
✓ Branch 9 taken 58 times.
2/2
✓ Decision 'true' taken 122 times.
✓ Decision 'false' taken 58 times.
 180 for (auto [n1, n2] : node_swaps) {
132
1/2
✓ Branch 1 taken 122 times.
✗ Branch 2 not taken.
 122 const Qubit q1 = qubit_to_node.right.at(n1);
133
1/2
✓ Branch 1 taken 122 times.
✗ Branch 2 not taken.
 122 const Qubit q2 = qubit_to_node.right.at(n2);
134
1/2
✓ Branch 1 taken 122 times.
✗ Branch 2 not taken.
 122 qubit_to_node.left.erase(q1);
135
1/2
✓ Branch 1 taken 122 times.
✗ Branch 2 not taken.
 122 qubit_to_node.left.erase(q2);
136
2/4
✓ Branch 1 taken 122 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 122 times.
✗ Branch 5 not taken.
 122 qubit_to_node.left.insert({q1, n2});
137
2/4
✓ Branch 1 taken 122 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 122 times.
✗ Branch 5 not taken.
 122 qubit_to_node.left.insert({q2, n1});
138 122 }
139 58 qubit_mapping_t map;
140
7/12
✓ Branch 1 taken 58 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 58 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 188 times.
✗ Branch 8 not taken.
✓ Branch 11 taken 188 times.
✗ Branch 12 not taken.
✓ Branch 14 taken 246 times.
✗ Branch 15 not taken.
✓ Branch 16 taken 188 times.
✓ Branch 17 taken 58 times.
0/1
? Decision couldn't be analyzed.
 246 for (auto [k, v] : qubit_to_node.left) {
141
1/2
✓ Branch 2 taken 188 times.
✗ Branch 3 not taken.
 188 map.insert({k, v});
142 188 }
143
2/4
✓ Branch 1 taken 58 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 58 times.
✗ Branch 5 not taken.
 116 return {map, node_swaps};
144 58 }
145
146 } // namespace tket
147