GCC Code Coverage Report

Directory: ./
File: Mapping/LexiRoute.cpp
Date: 2022-10-15 05:10:18
Warnings: 5 unchecked decisions!
Exec Total Coverage
Lines: 325 332 97.9%
Functions: 13 13 100.0%
Branches: 382 604 63.2%
Decisions: 76 92 82.6%
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 "Mapping/LexiRoute.hpp"
16
17 #include "Mapping/MappingFrontier.hpp"
18 #include "Utils/Json.hpp"
19
20 namespace tket {
21
22 5725 LexiRoute::LexiRoute(
23 const ArchitecturePtr& _architecture,
24 5725 MappingFrontier_ptr& _mapping_frontier)
25 5725 : architecture_(_architecture), mapping_frontier_(_mapping_frontier) {
26 // set initial logical->physical labelling
27
3/4
✓ Branch 2 taken 5725 times.
✗ Branch 3 not taken.
✓ Branch 9 taken 114004 times.
✓ Branch 10 taken 5725 times.
0/1
? Decision couldn't be analyzed.
 119729 for (const Qubit& qb : this->mapping_frontier_->circuit_.all_qubits()) {
28
1/2
✓ Branch 2 taken 114004 times.
✗ Branch 3 not taken.
 114004 this->labelling_.insert({qb, qb});
29
1/2
✓ Branch 1 taken 114004 times.
✗ Branch 2 not taken.
 114004 Node n(qb);
30 // store which Node have been asigned to Circuit already
31
3/4
✓ Branch 2 taken 114004 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 99969 times.
✓ Branch 5 taken 14035 times.
2/2
✓ Decision 'true' taken 99969 times.
✓ Decision 'false' taken 14035 times.
 114004 if (this->architecture_->node_exists(n)) {
32
1/2
✓ Branch 1 taken 99969 times.
✗ Branch 2 not taken.
 99969 this->assigned_nodes_.insert(n);
33 }
34 119729 }
35 5725 }
36
37 408 bool LexiRoute::assign_at_distance(
38 const UnitID& assignee, const Node& root, unsigned distances) {
39 408 node_set_t valid_nodes;
40 408 for (const Node& neighbour :
41
3/4
✓ Branch 2 taken 408 times.
✗ Branch 3 not taken.
✓ Branch 9 taken 1230 times.
✓ Branch 10 taken 408 times.
 2046 this->architecture_->nodes_at_distance(root, distances)) {
42 // A node is unassigned if it's empty or holding an ancilla
43
3/4
✓ Branch 2 taken 1230 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 844 times.
✓ Branch 6 taken 386 times.
2/2
✓ Decision 'true' taken 401 times.
✓ Decision 'false' taken 1673 times.
 2074 if (this->assigned_nodes_.find(neighbour) == this->assigned_nodes_.end() ||
44
3/4
✓ Branch 2 taken 844 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 15 times.
✓ Branch 5 taken 829 times.
 1688 this->mapping_frontier_->ancilla_nodes_.find(neighbour) !=
45
2/2
✓ Branch 3 taken 401 times.
✓ Branch 4 taken 829 times.
 2918 this->mapping_frontier_->ancilla_nodes_.end()) {
46
1/2
✓ Branch 1 taken 401 times.
✗ Branch 2 not taken.
 401 valid_nodes.insert(neighbour);
47 }
48 408 }
49
2/2
✓ Branch 1 taken 139 times.
✓ Branch 2 taken 269 times.
2/2
✓ Decision 'true' taken 139 times.
✓ Decision 'false' taken 269 times.
 408 if (valid_nodes.size() == 1) {
50 139 auto it = valid_nodes.begin();
51 // If the node to be assigned holds an ancilla
52
1/2
✓ Branch 3 taken 139 times.
✗ Branch 4 not taken.
2/2
✓ Decision 'true' taken 5 times.
✓ Decision 'false' taken 134 times.
 139 if (this->mapping_frontier_->ancilla_nodes_.find(*it) !=
53
2/2
✓ Branch 3 taken 5 times.
✓ Branch 4 taken 134 times.
 278 this->mapping_frontier_->ancilla_nodes_.end()) {
54 // => node *it is already present in circuit, but as an ancilla
55 // Merge the logical qubit to the end of the ancilla.
56 // notice that the merge_ancilla updates the qubit maps.
57
1/2
✓ Branch 3 taken 5 times.
✗ Branch 4 not taken.
 5 this->mapping_frontier_->merge_ancilla(assignee, *it);
58
1/2
✓ Branch 3 taken 5 times.
✗ Branch 4 not taken.
 5 this->mapping_frontier_->ancilla_nodes_.erase(*it);
59
1/2
✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
 5 this->labelling_.erase(*it);
60
1/2
✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
 5 this->labelling_[assignee] = *it;
61 } else {
62
1/2
✓ Branch 2 taken 134 times.
✗ Branch 3 not taken.
 134 this->labelling_[assignee] = *it;
63
1/2
✓ Branch 2 taken 134 times.
✗ Branch 3 not taken.
 134 this->assigned_nodes_.insert(*it);
64 // Assignee is a UnitID obtained from the circuit
65 // so we need to use the initial map to find the associated qubit.
66
1/2
✓ Branch 3 taken 134 times.
✗ Branch 4 not taken.
 536 this->mapping_frontier_->update_bimaps(
67
1/2
✓ Branch 3 taken 134 times.
✗ Branch 4 not taken.
 402 this->mapping_frontier_->get_qubit_from_circuit_uid(assignee), *it);
68 }
69 139 return true;
70 }
71
2/2
✓ Branch 1 taken 103 times.
✓ Branch 2 taken 166 times.
2/2
✓ Decision 'true' taken 103 times.
✓ Decision 'false' taken 166 times.
 269 if (valid_nodes.size() > 1) {
72 103 auto it = valid_nodes.begin();
73 lexicographical_distances_t winning_distances =
74
2/4
✓ Branch 3 taken 103 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 103 times.
✗ Branch 7 not taken.
 103 this->architecture_->get_distances(*it);
75 103 Node preserved_node = *it;
76 103 ++it;
77
2/2
✓ Branch 3 taken 159 times.
✓ Branch 4 taken 103 times.
2/2
✓ Decision 'true' taken 159 times.
✓ Decision 'false' taken 103 times.
 262 for (; it != valid_nodes.end(); ++it) {
78 lexicographical_distances_t comparison_distances =
79
2/4
✓ Branch 3 taken 159 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 159 times.
✗ Branch 7 not taken.
 159 this->architecture_->get_distances(*it);
80
3/4
✓ Branch 2 taken 159 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 21 times.
✓ Branch 6 taken 138 times.
2/2
✓ Decision 'true' taken 21 times.
✓ Decision 'false' taken 138 times.
 159 if (comparison_distances < winning_distances) {
81 21 preserved_node = *it;
82
1/2
✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
 21 winning_distances = comparison_distances;
83 }
84 159 }
85
1/2
✓ Branch 2 taken 103 times.
✗ Branch 3 not taken.
2/2
✓ Decision 'true' taken 8 times.
✓ Decision 'false' taken 95 times.
 103 if (this->mapping_frontier_->ancilla_nodes_.find(preserved_node) !=
86
2/2
✓ Branch 3 taken 8 times.
✓ Branch 4 taken 95 times.
 206 this->mapping_frontier_->ancilla_nodes_.end()) {
87 // => node *it is already present in circuit, but as an ancilla
88 // Merge the logical qubit to the end of the ancilla.
89
1/2
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
 8 this->mapping_frontier_->merge_ancilla(assignee, preserved_node);
90
1/2
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
 8 this->mapping_frontier_->ancilla_nodes_.erase(preserved_node);
91
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 this->labelling_.erase(preserved_node);
92
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 this->labelling_[assignee] = preserved_node;
93 } else {
94 // add ancilla case
95
1/2
✓ Branch 1 taken 95 times.
✗ Branch 2 not taken.
 95 this->labelling_[assignee] = preserved_node;
96
1/2
✓ Branch 1 taken 95 times.
✗ Branch 2 not taken.
 95 this->assigned_nodes_.insert(preserved_node);
97
1/2
✓ Branch 3 taken 95 times.
✗ Branch 4 not taken.
 285 this->mapping_frontier_->update_bimaps(
98
1/2
✓ Branch 2 taken 95 times.
✗ Branch 3 not taken.
 190 this->mapping_frontier_->get_qubit_from_circuit_uid(assignee),
99 preserved_node);
100 }
101 103 return true;
102 103 }
103 166 return false;
104 408 }
105
106 218 bool LexiRoute::update_labelling() {
107 // iterate through interacting qubits, assigning them to an Architecture Node
108 // if they aren't already
109 218 bool relabelled = false;
110
2/2
✓ Branch 5 taken 845 times.
✓ Branch 6 taken 215 times.
2/2
✓ Decision 'true' taken 845 times.
✓ Decision 'false' taken 215 times.
 1060 for (const auto& pair : this->interacting_uids_) {
111 bool uid_0_exist =
112
3/6
✓ Branch 2 taken 845 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 845 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 845 times.
✗ Branch 9 not taken.
 845 this->architecture_->node_exists(Node(this->labelling_[pair.first]));
113 bool uid_1_exist =
114
3/6
✓ Branch 2 taken 845 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 845 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 845 times.
✗ Branch 9 not taken.
 845 this->architecture_->node_exists(Node(this->labelling_[pair.second]));
115
4/4
✓ Branch 0 taken 775 times.
✓ Branch 1 taken 70 times.
✓ Branch 2 taken 164 times.
✓ Branch 3 taken 611 times.
2/2
✓ Decision 'true' taken 234 times.
✓ Decision 'false' taken 611 times.
 845 if (!uid_0_exist || !uid_1_exist) {
116 234 relabelled = true;
117 }
118
4/4
✓ Branch 0 taken 70 times.
✓ Branch 1 taken 775 times.
✓ Branch 2 taken 32 times.
✓ Branch 3 taken 38 times.
2/2
✓ Decision 'true' taken 32 times.
✓ Decision 'false' taken 813 times.
 845 if (!uid_0_exist && !uid_1_exist) {
119 // Place one on free unassigned qubit
120 // Then place second later
121 // condition => No ancilla qubits assigned, so don't check
122
2/2
✓ Branch 1 taken 20 times.
✓ Branch 2 taken 12 times.
2/2
✓ Decision 'true' taken 20 times.
✓ Decision 'false' taken 12 times.
 32 if (this->assigned_nodes_.size() == 0) {
123 // find nodes with best averaged distance to other nodes
124 // place it there...
125 std::set<Node> max_degree_nodes =
126
1/2
✓ Branch 2 taken 20 times.
✗ Branch 3 not taken.
 20 this->architecture_->max_degree_nodes();
127 20 auto it = max_degree_nodes.begin();
128 lexicographical_distances_t winning_distances =
129
2/4
✓ Branch 3 taken 20 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 20 times.
✗ Branch 7 not taken.
 20 this->architecture_->get_distances(*it);
130 20 Node preserved_node = Node(*it);
131 20 ++it;
132
2/2
✓ Branch 3 taken 111 times.
✓ Branch 4 taken 20 times.
2/2
✓ Decision 'true' taken 111 times.
✓ Decision 'false' taken 20 times.
 131 for (; it != max_degree_nodes.end(); ++it) {
133 lexicographical_distances_t comparison_distances =
134
2/4
✓ Branch 3 taken 111 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 111 times.
✗ Branch 7 not taken.
 111 this->architecture_->get_distances(*it);
135
3/4
✓ Branch 2 taken 111 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 3 times.
✓ Branch 6 taken 108 times.
2/2
✓ Decision 'true' taken 3 times.
✓ Decision 'false' taken 108 times.
 111 if (comparison_distances < winning_distances) {
136 3 preserved_node = Node(*it);
137
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 winning_distances = comparison_distances;
138 }
139 111 }
140
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 this->labelling_[pair.first] = preserved_node;
141
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 this->assigned_nodes_.insert(preserved_node);
142 // Update bimaps
143
1/2
✓ Branch 3 taken 20 times.
✗ Branch 4 not taken.
 40 this->mapping_frontier_->update_bimaps(
144
1/2
✓ Branch 2 taken 20 times.
✗ Branch 3 not taken.
 40 this->mapping_frontier_->get_qubit_from_circuit_uid(pair.first),
145 preserved_node);
146 20 uid_0_exist = true;
147 // given best node, do something
148 20 } else {
149 // Assign uid_0 to an unassigned node that is
150 // 1. adjacent to the already assigned nodes
151 // 2. has an unassigned neighbour
152 12 auto root_it = this->assigned_nodes_.begin();
153
6/6
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 11 times.
✓ Branch 4 taken 29 times.
✓ Branch 5 taken 1 times.
✓ Branch 6 taken 29 times.
✓ Branch 7 taken 12 times.
0/1
? Decision couldn't be analyzed.
 41 while (!uid_0_exist && root_it != this->assigned_nodes_.end()) {
154 29 Node root = *root_it;
155
1/2
✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
 29 uid_0_exist = this->assign_at_distance(pair.first, root, 1);
156 29 ++root_it;
157 29 }
158
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 11 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 11 times.
 12 if (!uid_0_exist) {
159
2/4
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 1 times.
✗ Branch 6 not taken.
 1 throw LexiRouteError(
160 2 "Unable to assign physical qubit - no free qubits remaining.");
161 }
162 }
163 }
164
3/4
✓ Branch 0 taken 38 times.
✓ Branch 1 taken 806 times.
✓ Branch 2 taken 38 times.
✗ Branch 3 not taken.
2/2
✓ Decision 'true' taken 38 times.
✓ Decision 'false' taken 806 times.
 844 if (!uid_0_exist && uid_1_exist) {
165
2/4
✓ Branch 1 taken 38 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 38 times.
✗ Branch 5 not taken.
 38 Node root(this->labelling_[pair.second]);
166
3/4
✓ Branch 2 taken 72 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 70 times.
✓ Branch 5 taken 2 times.
0/1
? Decision couldn't be analyzed.
 72 for (unsigned k = 1; k <= this->architecture_->get_diameter(); k++) {
167
1/2
✓ Branch 1 taken 70 times.
✗ Branch 2 not taken.
 70 uid_0_exist = this->assign_at_distance(pair.first, root, k);
168
2/2
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 34 times.
2/2
✓ Decision 'true' taken 36 times.
✓ Decision 'false' taken 34 times.
 70 if (uid_0_exist) {
169 36 break;
170 }
171 }
172
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 36 times.
2/2
✓ Decision 'true' taken 2 times.
✓ Decision 'false' taken 36 times.
 38 if (!uid_0_exist) {
173
2/4
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 2 times.
✗ Branch 6 not taken.
 2 throw LexiRouteError(
174 4 "Unable to assign physical qubit - no free qubits remaining.");
175 }
176 38 }
177
3/4
✓ Branch 0 taken 842 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 195 times.
✓ Branch 3 taken 647 times.
2/2
✓ Decision 'true' taken 195 times.
✓ Decision 'false' taken 647 times.
 842 if (uid_0_exist && !uid_1_exist) {
178
2/4
✓ Branch 1 taken 195 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 195 times.
✗ Branch 5 not taken.
 195 Node root(this->labelling_[pair.first]);
179
2/4
✓ Branch 2 taken 309 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 309 times.
✗ Branch 5 not taken.
0/1
? Decision couldn't be analyzed.
 309 for (unsigned k = 1; k <= this->architecture_->get_diameter(); k++) {
180
1/2
✓ Branch 1 taken 309 times.
✗ Branch 2 not taken.
 309 uid_1_exist = this->assign_at_distance(pair.second, root, k);
181
2/2
✓ Branch 0 taken 195 times.
✓ Branch 1 taken 114 times.
2/2
✓ Decision 'true' taken 195 times.
✓ Decision 'false' taken 114 times.
 309 if (uid_1_exist) {
182 195 break;
183 }
184 }
185
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 195 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 195 times.
 195 if (!uid_1_exist) {
186 ✗ throw LexiRouteError(
187 ✗ "Unable to assign physical qubit - no free qubits remaining.");
188 }
189 195 }
190 }
191 215 return relabelled;
192 }
193
194 /**
195 * LexiRoute::set_interacting_uids
196 * Updates this->interacting_uids_ with all "interacting" pairs
197 * of UnitID in this->mapping_frontier_
198 */
199 31278 bool LexiRoute::set_interacting_uids(
200 AssignedOnly assigned_only, CheckRoutingValidity route_check,
201 CheckLabellingValidity label_check) {
202 // return types
203 31278 this->interacting_uids_.clear();
204 31278 bool all_placed = true;
205 31278 for (auto it =
206 31278 this->mapping_frontier_->linear_boundary->get<TagKey>().begin();
207
3/4
✓ Branch 5 taken 1110296 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 1079021 times.
✓ Branch 8 taken 31275 times.
 1110296 it != this->mapping_frontier_->linear_boundary->get<TagKey>().end();
208
1/2
✓ Branch 1 taken 1079018 times.
✗ Branch 2 not taken.
 1079018 ++it) {
209 1079021 Edge e0 = this->mapping_frontier_->circuit_.get_nth_out_edge(
210
3/6
✓ Branch 1 taken 1079021 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1079021 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 1079021 times.
✗ Branch 8 not taken.
 1079021 it->second.first, it->second.second);
211
1/2
✓ Branch 2 taken 1079021 times.
✗ Branch 3 not taken.
 1079021 Vertex v0 = this->mapping_frontier_->circuit_.target(e0);
212 // should never be input vertex, so can always use in_edges
213
1/2
✓ Branch 2 taken 1079021 times.
✗ Branch 3 not taken.
 1079021 Op_ptr op = this->mapping_frontier_->circuit_.get_Op_ptr_from_Vertex(v0);
214
1/2
✓ Branch 2 taken 1079021 times.
✗ Branch 3 not taken.
1/2
✓ Decision 'true' taken 1079021 times.
✗ Decision 'false' not taken.
 1079021 if (op->get_type() != OpType::Barrier) {
215
1/2
✓ Branch 2 taken 1079021 times.
✗ Branch 3 not taken.
 1079021 int n_edges = this->mapping_frontier_->circuit_.n_in_edges_of_type(
216 1079021 v0, EdgeType::Quantum);
217 // make forwards = backwards
218
2/2
✓ Branch 0 taken 629571 times.
✓ Branch 1 taken 449450 times.
2/2
✓ Decision 'true' taken 629571 times.
✓ Decision 'false' taken 449450 times.
 1079021 if (n_edges == 2) {
219 629571 auto jt = it;
220
1/2
✓ Branch 1 taken 629571 times.
✗ Branch 2 not taken.
 629571 ++jt;
221
1/2
✓ Branch 1 taken 8737435 times.
✗ Branch 2 not taken.
1/2
✓ Decision 'true' taken 8737435 times.
✗ Decision 'false' not taken.
 9367006 while (jt !=
222
2/2
✓ Branch 4 taken 8107867 times.
✓ Branch 5 taken 629568 times.
 17474870 this->mapping_frontier_->linear_boundary->get<TagKey>().end()) {
223 // i.e. if vertices match
224 8107867 Edge e1 = this->mapping_frontier_->circuit_.get_nth_out_edge(
225
3/6
✓ Branch 1 taken 8107867 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 8107867 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 8107867 times.
✗ Branch 8 not taken.
 8107867 jt->second.first, jt->second.second);
226
1/2
✓ Branch 2 taken 8107867 times.
✗ Branch 3 not taken.
 8107867 Vertex v1 = this->mapping_frontier_->circuit_.target(e1);
227
2/2
✓ Branch 0 taken 43599 times.
✓ Branch 1 taken 8064268 times.
2/2
✓ Decision 'true' taken 43599 times.
✓ Decision 'false' taken 8064268 times.
 8107867 if (v0 == v1) {
228 // we can assume a qubit will only be in one interaction
229 // we can assume from how we iterate through pairs that each qubit
230 // will only be found in one match
231 bool node0_exists =
232
3/6
✓ Branch 2 taken 43599 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 43599 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 43599 times.
✗ Branch 9 not taken.
 43599 this->architecture_->node_exists(Node(it->first));
233 bool node1_exists =
234
3/6
✓ Branch 2 taken 43599 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 43599 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 43599 times.
✗ Branch 9 not taken.
 43599 this->architecture_->node_exists(Node(jt->first));
235
12/16
✓ Branch 0 taken 43499 times.
✓ Branch 1 taken 100 times.
✓ Branch 2 taken 43076 times.
✓ Branch 3 taken 423 times.
✓ Branch 6 taken 43076 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 43076 times.
✗ Branch 10 not taken.
✓ Branch 11 taken 7 times.
✓ Branch 12 taken 43069 times.
✓ Branch 13 taken 43076 times.
✓ Branch 14 taken 523 times.
✓ Branch 16 taken 530 times.
✓ Branch 17 taken 43069 times.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
2/2
✓ Decision 'true' taken 530 times.
✓ Decision 'false' taken 43069 times.
 43599 if (!node0_exists || !node1_exists || op->get_desc().is_box()) {
236 530 all_placed = false;
237
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 527 times.
0/1
? Decision couldn't be analyzed.
 530 if (route_check == CheckRoutingValidity::Yes) return false;
238 }
239
240
4/4
✓ Branch 0 taken 28593 times.
✓ Branch 1 taken 15003 times.
✓ Branch 2 taken 28563 times.
✓ Branch 3 taken 30 times.
2/2
✓ Decision 'true' taken 43307 times.
✓ Decision 'false' taken 289 times.
 43596 if (assigned_only == AssignedOnly::No ||
241
2/2
✓ Branch 0 taken 28304 times.
✓ Branch 1 taken 259 times.
 28563 (node0_exists && node1_exists)) {
242
3/6
✓ Branch 1 taken 43307 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 43307 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 43307 times.
✗ Branch 9 not taken.
 43307 interacting_uids_.insert({it->first, jt->first});
243
3/6
✓ Branch 1 taken 43307 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 43307 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 43307 times.
✗ Branch 9 not taken.
 43307 interacting_uids_.insert({jt->first, it->first});
244 }
245 }
246
1/2
✓ Branch 1 taken 8107864 times.
✗ Branch 2 not taken.
 8107864 ++jt;
247 }
248 }
249 }
250
2/2
✓ Branch 1 taken 1079018 times.
✓ Branch 2 taken 3 times.
 1079021 }
251
252 // conditions for proceeding with labelling
253
2/2
✓ Branch 0 taken 2965 times.
✓ Branch 1 taken 28310 times.
2/2
✓ Decision 'true' taken 2965 times.
✓ Decision 'false' taken 28310 times.
 31275 if (label_check == CheckLabellingValidity::Yes) {
254
2/2
✓ Branch 0 taken 2747 times.
✓ Branch 1 taken 218 times.
2/2
✓ Decision 'true' taken 2747 times.
✓ Decision 'false' taken 218 times.
 2965 if (all_placed) {
255 2747 return true;
256 } else {
257 218 return false;
258 }
259 }
260 // this should have left early when first found
261
2/2
✓ Branch 0 taken 2757 times.
✓ Branch 1 taken 25553 times.
2/2
✓ Decision 'true' taken 2757 times.
✓ Decision 'false' taken 25553 times.
 28310 if (route_check == CheckRoutingValidity::Yes) {
262
1/2
✓ Branch 0 taken 2757 times.
✗ Branch 1 not taken.
1/2
✓ Decision 'true' taken 2757 times.
✗ Decision 'false' not taken.
 2757 if (all_placed) {
263
1/2
✓ Branch 1 taken 2757 times.
✗ Branch 2 not taken.
1/2
✓ Decision 'true' taken 2757 times.
✗ Decision 'false' not taken.
 2757 if (interacting_uids_.size() > 0) {
264 2757 return true;
265 }
266 ✗ return false;
267 } else {
268 ✗ return false;
269 }
270 }
271 // => either route_check true and all_placed so valid
272 // or !route_check and !label_check so return true and discard
273 25553 return true;
274 }
275
276 2757 swap_set_t LexiRoute::get_candidate_swaps() {
277 2757 swap_set_t candidate_swaps;
278
2/2
✓ Branch 5 taken 9480 times.
✓ Branch 6 taken 2757 times.
2/2
✓ Decision 'true' taken 9480 times.
✓ Decision 'false' taken 2757 times.
 12237 for (const auto& interaction : this->interacting_uids_) {
279
2/4
✓ Branch 1 taken 9480 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 9480 times.
✗ Branch 5 not taken.
 9480 Node assigned_first = Node(this->labelling_[interaction.first]);
280 std::vector<Node> adjacent_uids_0 =
281
1/2
✓ Branch 2 taken 9480 times.
✗ Branch 3 not taken.
 9480 this->architecture_->nodes_at_distance(assigned_first, 1);
282 TKET_ASSERT(adjacent_uids_0.size() != 0);
283
2/2
✓ Branch 5 taken 22246 times.
✓ Branch 6 taken 9480 times.
2/2
✓ Decision 'true' taken 22246 times.
✓ Decision 'false' taken 9480 times.
 31726 for (const Node& neighbour : adjacent_uids_0) {
284
1/2
✓ Branch 2 taken 22246 times.
✗ Branch 3 not taken.
2/2
✓ Decision 'true' taken 20091 times.
✓ Decision 'false' taken 2155 times.
 22246 if (candidate_swaps.find({neighbour, assigned_first}) ==
285
2/2
✓ Branch 1 taken 20091 times.
✓ Branch 2 taken 2155 times.
 44492 candidate_swaps.end()) {
286
1/2
✓ Branch 2 taken 20091 times.
✗ Branch 3 not taken.
 20091 candidate_swaps.insert({assigned_first, neighbour});
287 }
288 }
289
2/4
✓ Branch 1 taken 9480 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 9480 times.
✗ Branch 5 not taken.
 9480 Node assigned_second = Node(this->labelling_[interaction.second]);
290 std::vector<Node> adjacent_uids_1 =
291
1/2
✓ Branch 2 taken 9480 times.
✗ Branch 3 not taken.
 9480 this->architecture_->nodes_at_distance(assigned_second, 1);
292 TKET_ASSERT(adjacent_uids_1.size() != 0);
293
2/2
✓ Branch 5 taken 22246 times.
✓ Branch 6 taken 9480 times.
2/2
✓ Decision 'true' taken 22246 times.
✓ Decision 'false' taken 9480 times.
 31726 for (const Node& neighbour : adjacent_uids_1) {
294
1/2
✓ Branch 2 taken 22246 times.
✗ Branch 3 not taken.
2/2
✓ Decision 'true' taken 20091 times.
✓ Decision 'false' taken 2155 times.
 22246 if (candidate_swaps.find({neighbour, assigned_second}) ==
295
2/2
✓ Branch 1 taken 20091 times.
✓ Branch 2 taken 2155 times.
 44492 candidate_swaps.end()) {
296
1/2
✓ Branch 2 taken 20091 times.
✗ Branch 3 not taken.
 20091 candidate_swaps.insert({assigned_second, neighbour});
297 }
298 }
299 9480 }
300 2757 return candidate_swaps;
301 }
302
303 1959 bool is_vertex_CX(const Circuit& circ_, const Vertex& v) {
304 1959 OpType ot = circ_.get_OpType_from_Vertex(v);
305
2/2
✓ Branch 0 taken 201 times.
✓ Branch 1 taken 1758 times.
2/2
✓ Decision 'true' taken 201 times.
✓ Decision 'false' taken 1758 times.
 1959 if (ot != OpType::CX) {
306
2/2
✓ Branch 0 taken 99 times.
✓ Branch 1 taken 102 times.
2/2
✓ Decision 'true' taken 99 times.
✓ Decision 'false' taken 102 times.
 201 if (ot == OpType::Conditional) {
307 const Conditional& b =
308 99 static_cast<const Conditional&>(*circ_.get_Op_ptr_from_Vertex(v));
309
2/2
✓ Branch 4 taken 33 times.
✓ Branch 5 taken 66 times.
2/2
✓ Decision 'true' taken 33 times.
✓ Decision 'false' taken 66 times.
 99 if (b.get_op()->get_type() != OpType::CX) {
310 33 return false;
311 }
312 } else {
313 102 return false;
314 }
315 }
316 1824 return true;
317 }
318
319 2757 std::pair<bool, bool> LexiRoute::check_bridge(
320 const std::pair<Node, Node>& swap, unsigned lookahead) {
321 2757 std::pair<bool, bool> output = {false, false};
322 // first confirm whether it even has an interaction
323
1/2
✓ Branch 1 taken 2757 times.
✗ Branch 2 not taken.
 2757 auto it = this->interacting_uids_.find(swap.first);
324
1/2
✓ Branch 2 taken 2757 times.
✗ Branch 3 not taken.
1/2
✓ Decision 'true' taken 2757 times.
✗ Decision 'false' not taken.
 2757 if (it != this->interacting_uids_.end()) { // => in interaction
325
4/6
✓ Branch 3 taken 2757 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 2757 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 1576 times.
✓ Branch 10 taken 1181 times.
 2757 if (this->architecture_->get_distance(swap.first, Node(it->second)) ==
326 2) { // => could be bridge
327 // below should always return correct object given prior checks
328 VertPort vp =
329
2/4
✓ Branch 3 taken 1576 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 1576 times.
✗ Branch 7 not taken.
 1576 (*this->mapping_frontier_->linear_boundary->find(swap.first)).second;
330
1/2
✓ Branch 2 taken 1576 times.
✗ Branch 3 not taken.
 1576 Edge out_edge = this->mapping_frontier_->circuit_.get_nth_out_edge(
331 vp.first, vp.second);
332 3152 output.first = is_vertex_CX(
333
1/2
✓ Branch 1 taken 1576 times.
✗ Branch 2 not taken.
 1576 this->mapping_frontier_->circuit_,
334
1/2
✓ Branch 2 taken 1576 times.
✗ Branch 3 not taken.
 3152 this->mapping_frontier_->circuit_.target(out_edge));
335 }
336 }
337 // repeat for second swap
338
1/2
✓ Branch 1 taken 2757 times.
✗ Branch 2 not taken.
 2757 it = this->interacting_uids_.find(swap.second);
339
2/2
✓ Branch 2 taken 427 times.
✓ Branch 3 taken 2330 times.
 2757 if (it != this->interacting_uids_.end()) {
340
4/6
✓ Branch 3 taken 427 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 427 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 383 times.
✓ Branch 10 taken 44 times.
 427 if (this->architecture_->get_distance(swap.second, Node(it->second)) == 2) {
341 VertPort vp =
342
2/4
✓ Branch 3 taken 383 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 383 times.
✗ Branch 7 not taken.
 383 (*this->mapping_frontier_->linear_boundary->find(swap.second)).second;
343
1/2
✓ Branch 2 taken 383 times.
✗ Branch 3 not taken.
 383 Edge out_edge = this->mapping_frontier_->circuit_.get_nth_out_edge(
344 vp.first, vp.second);
345 766 output.second = is_vertex_CX(
346
1/2
✓ Branch 1 taken 383 times.
✗ Branch 2 not taken.
 383 this->mapping_frontier_->circuit_,
347
1/2
✓ Branch 2 taken 383 times.
✗ Branch 3 not taken.
 766 this->mapping_frontier_->circuit_.target(out_edge));
348 }
349 }
350
8/8
✓ Branch 0 taken 1464 times.
✓ Branch 1 taken 1293 times.
✓ Branch 2 taken 1142 times.
✓ Branch 3 taken 322 times.
✓ Branch 4 taken 1293 times.
✓ Branch 5 taken 1142 times.
✓ Branch 6 taken 1255 times.
✓ Branch 7 taken 38 times.
 2757 if ((output.first && output.second) || (!output.first && !output.second)) {
351 1577 return {0, 0};
352 }
353 // implies conditions are set to at least check if BRIDGE is better
354 swap_set_t candidate_swaps = {
355 swap,
356 1180 {swap.first,
357
1/2
✓ Branch 4 taken 1180 times.
✗ Branch 5 not taken.
 4720 swap.first}}; // second swap here will just compare the base case
358
359 // as with best swap finder, we create a set of candidate swap gates and
360 // then find best, except with only 2 swap (best swap and no swap)
361
2/2
✓ Branch 1 taken 4485 times.
✓ Branch 2 taken 1180 times.
 5665 while (candidate_swaps.size() > 1 /*some lookahead parameter*/) {
362
1/2
✓ Branch 2 taken 4485 times.
✗ Branch 3 not taken.
 4485 this->mapping_frontier_->advance_next_2qb_slice(lookahead);
363 // true bool means it only sets interacting uids if both uids are in
364 // architecture
365
1/2
✓ Branch 1 taken 4485 times.
✗ Branch 2 not taken.
 4485 this->set_interacting_uids(
366 AssignedOnly::Yes, CheckRoutingValidity::No,
367 CheckLabellingValidity::No);
368 // if 0, just take first swap rather than place
369
2/2
✓ Branch 1 taken 62 times.
✓ Branch 2 taken 4423 times.
 4485 if (this->interacting_uids_.size() == 0) {
370
3/6
✓ Branch 4 taken 62 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 62 times.
✓ Branch 7 taken 62 times.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
 124 candidate_swaps = {*candidate_swaps.begin()};
371 } else {
372 4423 interacting_nodes_t convert_uids;
373
2/2
✓ Branch 4 taken 11908 times.
✓ Branch 5 taken 4423 times.
 16331 for (const auto& p : this->interacting_uids_) {
374
1/2
✓ Branch 2 taken 11908 times.
✗ Branch 3 not taken.
 11908 convert_uids.insert(
375
2/4
✓ Branch 1 taken 11908 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 11908 times.
✗ Branch 5 not taken.
 23816 {Node(this->labelling_[p.first]),
376
2/4
✓ Branch 1 taken 11908 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 11908 times.
✗ Branch 5 not taken.
 23816 Node(this->labelling_[p.second])});
377 }
378
1/2
✓ Branch 1 taken 4423 times.
✗ Branch 2 not taken.
 4423 LexicographicalComparison lookahead_lc(this->architecture_, convert_uids);
379
1/2
✓ Branch 1 taken 4423 times.
✗ Branch 2 not taken.
 4423 lookahead_lc.remove_swaps_lexicographical(candidate_swaps);
380 4423 }
381 }
382 // condition implies bridge is chosen
383 // if both remained then lexicographically equivalent under given conditions
384 // so either can be added with same consequences (for given hyper
385 // parameters)
386
3/4
✓ Branch 3 taken 1180 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 878 times.
✓ Branch 6 taken 302 times.
 1180 if (*candidate_swaps.begin() == swap) {
387 878 output = {0, 0};
388 }
389 1180 return output;
390 1180 }
391
392 // Returns the distance between n1 and p1 and the distance between n2 and p2,
393 // distance ordered (greatest first)
394 40176 const std::pair<size_t, size_t> LexiRoute::pair_distances(
395 const Node& p0_first, const Node& p0_second, const Node& p1_first,
396 const Node& p1_second) const {
397 {
398
1/2
✓ Branch 2 taken 40176 times.
✗ Branch 3 not taken.
 40176 const bool valid = this->architecture_->node_exists(p0_first) &&
399
2/4
✓ Branch 2 taken 40176 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 40176 times.
✗ Branch 5 not taken.
 40176 this->architecture_->node_exists(p0_second) &&
400
3/6
✓ Branch 0 taken 40176 times.
✗ Branch 1 not taken.
✓ Branch 4 taken 40176 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 40176 times.
✗ Branch 7 not taken.
 120528 this->architecture_->node_exists(p1_first) &&
401
2/4
✓ Branch 2 taken 40176 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 40176 times.
✗ Branch 5 not taken.
 40176 this->architecture_->node_exists(p1_second);
402 TKET_ASSERT(valid);
403 }
404
1/2
✓ Branch 2 taken 40176 times.
✗ Branch 3 not taken.
 40176 size_t curr_dist1 = this->architecture_->get_distance(p0_first, p0_second);
405
1/2
✓ Branch 2 taken 40176 times.
✗ Branch 3 not taken.
 40176 size_t curr_dist2 = this->architecture_->get_distance(p1_first, p1_second);
406
1/2
✓ Branch 1 taken 31248 times.
✗ Branch 2 not taken.
 31248 return (curr_dist1 > curr_dist2) ? std::make_pair(curr_dist1, curr_dist2)
407
3/4
✓ Branch 0 taken 31248 times.
✓ Branch 1 taken 8928 times.
✓ Branch 3 taken 8928 times.
✗ Branch 4 not taken.
 80352 : std::make_pair(curr_dist2, curr_dist1);
408 }
409
410 2757 void LexiRoute::remove_swaps_decreasing(swap_set_t& swaps) {
411 2757 swap_set_t remaining_swaps;
412
2/4
✓ Branch 1 taken 2757 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2757 times.
✗ Branch 5 not taken.
 2757 Node pair_first, pair_second;
413
2/2
✓ Branch 5 taken 20091 times.
✓ Branch 6 taken 2757 times.
 22848 for (const auto& swap : swaps) {
414
1/2
✓ Branch 1 taken 20091 times.
✗ Branch 2 not taken.
 20091 auto it = this->interacting_uids_.find(swap.first);
415 // => swap.first is in interaction
416
1/2
✓ Branch 2 taken 20091 times.
✗ Branch 3 not taken.
 20091 if (it != this->interacting_uids_.end()) {
417 // find its pair
418
1/2
✓ Branch 2 taken 20091 times.
✗ Branch 3 not taken.
 20091 pair_first = Node(it->second);
419 } else {
420 // => not interacting, assign pair to self (will give lexicographic
421 // distance 0)
422 ✗ pair_first = swap.first;
423 }
424 // => UnitID in SWAP are interacting
425
3/4
✓ Branch 1 taken 20091 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 3 times.
✓ Branch 4 taken 20088 times.
 20091 if (pair_first == swap.second) {
426 11450 continue;
427 }
428
1/2
✓ Branch 1 taken 20088 times.
✗ Branch 2 not taken.
 20088 auto jt = this->interacting_uids_.find(swap.second);
429 // => swap.second is in interaction
430
2/2
✓ Branch 2 taken 2152 times.
✓ Branch 3 taken 17936 times.
 20088 if (jt != this->interacting_uids_.end()) {
431
1/2
✓ Branch 2 taken 2152 times.
✗ Branch 3 not taken.
 2152 pair_second = Node(jt->second);
432 } else {
433 17936 pair_second = swap.second;
434 }
435 // => UnitID in SWAP are interacting
436 // Check should alrady be done with earlier continue
437 TKET_ASSERT(pair_second != swap.first);
438
439 const std::pair<size_t, size_t>& curr_dists =
440
1/2
✓ Branch 1 taken 20088 times.
✗ Branch 2 not taken.
 20088 this->pair_distances(swap.first, pair_first, swap.second, pair_second);
441 const std::pair<size_t, size_t>& news_dists =
442
1/2
✓ Branch 1 taken 20088 times.
✗ Branch 2 not taken.
 20088 this->pair_distances(swap.second, pair_first, swap.first, pair_second);
443
2/2
✓ Branch 3 taken 11447 times.
✓ Branch 4 taken 8641 times.
 20088 if (news_dists >= curr_dists) {
444 11447 continue;
445 }
446
1/2
✓ Branch 1 taken 8641 times.
✗ Branch 2 not taken.
 8641 remaining_swaps.insert(swap);
447 }
448 2757 }
449
450 2965 bool LexiRoute::solve_labelling() {
451 2965 bool all_labelled = this->set_interacting_uids(
452 AssignedOnly::No, CheckRoutingValidity::No, CheckLabellingValidity::Yes);
453
2/2
✓ Branch 0 taken 218 times.
✓ Branch 1 taken 2747 times.
 2965 if (!all_labelled) {
454 218 this->update_labelling();
455 215 this->mapping_frontier_->update_linear_boundary_uids(this->labelling_);
456 215 return true;
457 }
458 2747 return false;
459 }
460
461 2760 bool LexiRoute::solve(unsigned lookahead) {
462 // work out if valid
463
464
1/2
✓ Branch 1 taken 2760 times.
✗ Branch 2 not taken.
 2760 bool all_labelled = this->set_interacting_uids(
465 AssignedOnly::No, CheckRoutingValidity::Yes, CheckLabellingValidity::No);
466
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 2757 times.
 2760 if (!all_labelled) {
467 3 return false;
468 }
469
470 // store a copy of the original this->mapping_frontier_->quantum_boundray
471 // this object will be updated and reset throughout the swap picking procedure
472 // so need to return it to original setting at end
473
1/2
✓ Branch 1 taken 2757 times.
✗ Branch 2 not taken.
 2757 unit_vertport_frontier_t copy;
474 2757 for (const std::pair<UnitID, VertPort>& pair :
475
4/6
✓ Branch 6 taken 55569 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 58326 times.
✗ Branch 10 not taken.
✓ Branch 11 taken 55569 times.
✓ Branch 12 taken 2757 times.
 61083 this->mapping_frontier_->linear_boundary->get<TagKey>()) {
476
2/4
✓ Branch 2 taken 55569 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 55569 times.
✗ Branch 7 not taken.
 55569 copy.insert({pair.first, pair.second});
477 }
478
1/2
✓ Branch 1 taken 2757 times.
✗ Branch 2 not taken.
 2757 swap_set_t candidate_swaps = this->get_candidate_swaps();
479
1/2
✓ Branch 1 taken 2757 times.
✗ Branch 2 not taken.
 2757 this->remove_swaps_decreasing(candidate_swaps);
480 TKET_ASSERT(candidate_swaps.size() != 0);
481 // Only want to substitute a single swap
482 // check next layer of interacting qubits and remove swaps until only one
483 // lexicographically superior swap is left
484 2757 unsigned counter = 0;
485
6/6
✓ Branch 1 taken 18220 times.
✓ Branch 2 taken 2539 times.
✓ Branch 3 taken 18100 times.
✓ Branch 4 taken 120 times.
✓ Branch 5 taken 18100 times.
✓ Branch 6 taken 2659 times.
 20759 while (candidate_swaps.size() > 1 && counter < lookahead) {
486 // if 0, just take first swap rather than place
487
2/2
✓ Branch 1 taken 98 times.
✓ Branch 2 taken 18002 times.
 18100 if (this->interacting_uids_.size() == 0) {
488 98 break;
489 } else {
490 18002 interacting_nodes_t convert_uids;
491
2/2
✓ Branch 4 taken 45228 times.
✓ Branch 5 taken 18002 times.
 63230 for (const auto& p : this->interacting_uids_) {
492
1/2
✓ Branch 2 taken 45228 times.
✗ Branch 3 not taken.
 45228 convert_uids.insert(
493
2/4
✓ Branch 1 taken 45228 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 45228 times.
✗ Branch 5 not taken.
 90456 {Node(this->labelling_[p.first]),
494
2/4
✓ Branch 1 taken 45228 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 45228 times.
✗ Branch 5 not taken.
 90456 Node(this->labelling_[p.second])});
495 }
496
1/2
✓ Branch 1 taken 18002 times.
✗ Branch 2 not taken.
 18002 LexicographicalComparison lookahead_lc(this->architecture_, convert_uids);
497
1/2
✓ Branch 1 taken 18002 times.
✗ Branch 2 not taken.
 18002 lookahead_lc.remove_swaps_lexicographical(candidate_swaps);
498 18002 }
499 18002 counter++;
500
1/2
✓ Branch 2 taken 18002 times.
✗ Branch 3 not taken.
 18002 this->mapping_frontier_->advance_next_2qb_slice(lookahead);
501 // true bool means it only sets interacting uids if both uids are in
502 // architecture
503
1/2
✓ Branch 1 taken 18002 times.
✗ Branch 2 not taken.
 18002 this->set_interacting_uids(
504 AssignedOnly::Yes, CheckRoutingValidity::No,
505 CheckLabellingValidity::No);
506 }
507 // find best swap
508 2757 auto it = candidate_swaps.end();
509 2757 --it;
510
511 2757 std::pair<Node, Node> chosen_swap = *it;
512
1/2
✓ Branch 2 taken 2757 times.
✗ Branch 3 not taken.
 2757 this->mapping_frontier_->set_linear_boundary(copy);
513
514
1/2
✓ Branch 1 taken 2757 times.
✗ Branch 2 not taken.
 2757 this->set_interacting_uids(
515 AssignedOnly::No, CheckRoutingValidity::No, CheckLabellingValidity::No);
516
1/2
✓ Branch 1 taken 2757 times.
✗ Branch 2 not taken.
 2757 std::pair<bool, bool> check = this->check_bridge(chosen_swap, lookahead);
517 // set for final time, to allow gates to be correctly inserted, but then leave
518 // as is
519 // insert gates
520
1/2
✓ Branch 2 taken 2757 times.
✗ Branch 3 not taken.
 2757 this->mapping_frontier_->set_linear_boundary(copy);
521
4/4
✓ Branch 0 taken 2473 times.
✓ Branch 1 taken 284 times.
✓ Branch 2 taken 2455 times.
✓ Branch 3 taken 18 times.
 2757 if (!check.first && !check.second) {
522 // update circuit with new swap
523 // final_labelling is initial labelling permuted by single swap
524
525 // if false, SWAP is identical to last SWAP added without any gates realised
526
3/4
✓ Branch 2 taken 2455 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 7 times.
✓ Branch 5 taken 2448 times.
 2455 if (!this->mapping_frontier_->add_swap(
527 chosen_swap.first, chosen_swap.second)) {
528 // only need to reset in bridge case
529
1/2
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
 7 this->set_interacting_uids(
530 AssignedOnly::No, CheckRoutingValidity::No,
531 CheckLabellingValidity::No);
532 // if SWAP has both Nodes in interaction default takes first
533 // this could be inefficient compared to other SWAP, however
534 // this failsafe is expected to be called extremely rarely (once in
535 // thousands) on very dense circuits for very symmetrical architectures so
536 // doesn't largely matter
537
1/2
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
 7 auto it = this->interacting_uids_.find(chosen_swap.first);
538 24 auto add_path_swaps = [this](const Node& source, const Node& target) {
539
1/2
✓ Branch 2 taken 7 times.
✗ Branch 3 not taken.
 7 auto path = this->architecture_->get_path(source, target);
540 7 auto path_it_0 = path.begin() + 1;
541 7 auto path_it_1 = path.begin();
542 // adds a SWAP between each pair of adjacent nodes on path
543
2/2
✓ Branch 2 taken 17 times.
✓ Branch 3 taken 7 times.
 24 while (path_it_0 != path.end()) {
544
1/2
✓ Branch 4 taken 17 times.
✗ Branch 5 not taken.
 17 this->mapping_frontier_->add_swap(*path_it_0, *path_it_1);
545 17 ++path_it_0;
546 17 ++path_it_1;
547 }
548 7 };
549
1/2
✓ Branch 2 taken 7 times.
✗ Branch 3 not taken.
 7 if (it != this->interacting_uids_.end()) {
550
2/4
✓ Branch 2 taken 7 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 7 times.
✗ Branch 6 not taken.
 7 add_path_swaps(chosen_swap.first, Node(it->second));
551 } else {
552 ✗ it = this->interacting_uids_.find(chosen_swap.second);
553 TKET_ASSERT(it != this->interacting_uids_.end());
554 ✗ add_path_swaps(chosen_swap.second, Node(it->second));
555 }
556 }
557
558 2455 } else {
559 // only need to reset in bridge case
560
1/2
✓ Branch 1 taken 302 times.
✗ Branch 2 not taken.
 302 this->set_interacting_uids(
561 AssignedOnly::No, CheckRoutingValidity::No, CheckLabellingValidity::No);
562
563 302 auto add_ordered_bridge = [&](const Node& n) {
564
1/2
✓ Branch 3 taken 302 times.
✗ Branch 4 not taken.
 302 auto it0 = this->mapping_frontier_->linear_boundary->find(n);
565 // this should implicitly be the case if this logic is reached
566 TKET_ASSERT(it0 != this->mapping_frontier_->linear_boundary->end());
567
568
2/4
✓ Branch 1 taken 302 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 302 times.
✗ Branch 5 not taken.
 302 Node other_node = Node(this->interacting_uids_[n]);
569
1/2
✓ Branch 3 taken 302 times.
✗ Branch 4 not taken.
 302 auto it1 = this->mapping_frontier_->linear_boundary->find(other_node);
570 // this should implicitly be the case if this logic is reached
571 TKET_ASSERT(it1 != this->mapping_frontier_->linear_boundary->end());
572
573
1/2
✓ Branch 2 taken 302 times.
✗ Branch 3 not taken.
 302 auto path = this->architecture_->get_path(n, other_node);
574 302 Node central = Node(path[1]);
575
576 302 Edge n_edge = this->mapping_frontier_->circuit_.get_nth_out_edge(
577
3/6
✓ Branch 1 taken 302 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 302 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 302 times.
✗ Branch 8 not taken.
 302 it0->second.first, it0->second.second);
578 302 Edge other_edge = this->mapping_frontier_->circuit_.get_nth_out_edge(
579
3/6
✓ Branch 1 taken 302 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 302 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 302 times.
✗ Branch 8 not taken.
 302 it1->second.first, it1->second.second);
580
581 unsigned port0 =
582
1/2
✓ Branch 2 taken 302 times.
✗ Branch 3 not taken.
 302 this->mapping_frontier_->circuit_.get_target_port(n_edge);
583 unsigned port1 =
584
1/2
✓ Branch 2 taken 302 times.
✗ Branch 3 not taken.
 302 this->mapping_frontier_->circuit_.get_target_port(other_edge);
585 // compare port ordering to get control vs target
586 TKET_ASSERT(port0 != port1);
587
2/2
✓ Branch 0 taken 142 times.
✓ Branch 1 taken 160 times.
 302 if (port0 < port1) {
588
1/2
✓ Branch 2 taken 142 times.
✗ Branch 3 not taken.
 142 this->mapping_frontier_->add_bridge(n, central, other_node);
589 } else {
590
1/2
✓ Branch 2 taken 160 times.
✗ Branch 3 not taken.
 160 this->mapping_frontier_->add_bridge(other_node, central, n);
591 }
592 302 };
593
594
2/2
✓ Branch 0 taken 284 times.
✓ Branch 1 taken 18 times.
 302 if (check.first) {
595
1/2
✓ Branch 1 taken 284 times.
✗ Branch 2 not taken.
 284 add_ordered_bridge(chosen_swap.first);
596 }
597
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 284 times.
 302 if (check.second) {
598
1/2
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
 18 add_ordered_bridge(chosen_swap.second);
599 }
600 }
601 2757 return true;
602 2757 }
603
604 } // namespace tket
605