GCC Code Coverage Report

Directory: ./
File: ArchAwareSynth/SteinerTree.cpp
Date: 2022-10-15 05:10:18
Exec Total Coverage
Lines: 430 478 90.0%
Functions: 23 23 100.0%
Branches: 391 664 58.9%
Decisions: 42 72 58.3%
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 "SteinerTree.hpp"
16
17 namespace tket {
18 namespace aas {
19
20 // Steiner Tree generation follows the method of Takahashi and
21 // Matsuyama et al. see
22 // https://en.wikipedia.org/wiki/Steiner_tree_problem#Approximating_the_Steiner_tree
23 856 SteinerTree::SteinerTree(
24 const PathHandler& pathhandler, std::list<unsigned>& nodes_to_add,
25 856 unsigned root_node) {
26 856 root = root_node;
27 856 last_operation_cost = 0;
28
1/2
✓ Branch 1 taken 856 times.
✗ Branch 2 not taken.
 856 init_tree(pathhandler, nodes_to_add);
29
2/2
✓ Branch 1 taken 510 times.
✓ Branch 2 taken 856 times.
2/2
✓ Decision 'true' taken 510 times.
✓ Decision 'false' taken 856 times.
 1366 while (!nodes_to_add.empty()) {
30
1/2
✓ Branch 1 taken 510 times.
✗ Branch 2 not taken.
 510 add_closest_node_to_tree(pathhandler, nodes_to_add);
31 }
32
1/2
✓ Branch 1 taken 856 times.
✗ Branch 2 not taken.
 856 tree_cost = calculate_cost();
33 856 }
34
35 856 unsigned SteinerTree::calculate_cost() const {
36 856 unsigned cost = 0;
37
2/2
✓ Branch 5 taken 6689 times.
✓ Branch 6 taken 856 times.
2/2
✓ Decision 'true' taken 6689 times.
✓ Decision 'false' taken 856 times.
 7545 for (SteinerNodeType nt : node_types) {
38
4/4
✓ Branch 0 taken 556 times.
✓ Branch 1 taken 392 times.
✓ Branch 2 taken 1507 times.
✓ Branch 3 taken 4234 times.
 6689 switch (nt) {
39
1/1
✓ Decision 'true' taken 556 times.
 556 case SteinerNodeType::ZeroInTree: {
40 556 cost += 2;
41 556 break;
42 }
43
1/1
✓ Decision 'true' taken 392 times.
 392 case SteinerNodeType::OneInTree: {
44 392 ++cost;
45 392 break;
46 }
47
1/1
✓ Decision 'true' taken 1507 times.
 1507 case SteinerNodeType::Leaf: {
48 1507 ++cost;
49 1507 break;
50 }
51
0/1
✗ Decision 'true' not taken.
 4234 default: {
52 // no action occurs
53 4234 break;
54 }
55 }
56 }
57
1/2
✓ Branch 0 taken 856 times.
✗ Branch 1 not taken.
1/2
✓ Decision 'true' taken 856 times.
✗ Decision 'false' not taken.
 856 if (cost > 0) --cost;
58 856 return cost;
59 }
60
61 666 unsigned SteinerTree::get_max_element() const {
62 666 unsigned maxelement = 0;
63
2/2
✓ Branch 1 taken 5609 times.
✓ Branch 2 taken 666 times.
2/2
✓ Decision 'true' taken 5609 times.
✓ Decision 'false' taken 666 times.
 6275 for (unsigned i = 0; i < node_types.size(); ++i) {
64
2/2
✓ Branch 1 taken 1773 times.
✓ Branch 2 taken 3836 times.
2/2
✓ Decision 'true' taken 666 times.
✓ Decision 'false' taken 4943 times.
 5609 if (node_types[i] != SteinerNodeType::OutOfTree) maxelement = i;
65 }
66 666 return maxelement;
67 }
68
69 668 std::vector<unsigned> SteinerTree::nodes() const {
70 668 std::vector<unsigned> tree_nodes;
71
2/2
✓ Branch 1 taken 5619 times.
✓ Branch 2 taken 668 times.
2/2
✓ Decision 'true' taken 5619 times.
✓ Decision 'false' taken 668 times.
 6287 for (unsigned i = 0; i < node_types.size(); ++i) {
72
2/2
✓ Branch 1 taken 1779 times.
✓ Branch 2 taken 3840 times.
2/2
✓ Decision 'true' taken 1779 times.
✓ Decision 'false' taken 3840 times.
 5619 if (node_types[i] != SteinerNodeType::OutOfTree) {
73
1/2
✓ Branch 1 taken 1779 times.
✗ Branch 2 not taken.
 1779 tree_nodes.push_back(i);
74 }
75 }
76 668 return tree_nodes;
77 }
78
79 856 void SteinerTree::init_tree(
80 const PathHandler& pathhandler, std::list<unsigned>& nodes_to_add) {
81
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 856 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 856 times.
 856 if (nodes_to_add.empty())
82 ✗ throw std::logic_error("Cannot initialise empty Steiner Tree.");
83
84 856 unsigned n = pathhandler.get_connectivity_matrix().rows();
85
1/2
✓ Branch 2 taken 856 times.
✗ Branch 3 not taken.
 856 node_types = std::vector<SteinerNodeType>(n, SteinerNodeType::OutOfTree);
86
1/2
✓ Branch 2 taken 856 times.
✗ Branch 3 not taken.
 856 num_neighbours = std::vector<unsigned>(n, 0);
87
2/2
✓ Branch 1 taken 323 times.
✓ Branch 2 taken 533 times.
2/2
✓ Decision 'true' taken 323 times.
✓ Decision 'false' taken 533 times.
 856 if (nodes_to_add.size() == 1) {
88 323 node_types[nodes_to_add.front()] =
89 SteinerNodeType::Leaf; // A single root is considered a leaf
90 323 tree_nodes = nodes_to_add;
91 323 nodes_to_add.clear();
92
1/2
✓ Branch 1 taken 533 times.
✗ Branch 2 not taken.
1/2
✓ Decision 'true' taken 533 times.
✗ Decision 'false' not taken.
 533 } else if (nodes_to_add.size() > 1) {
93 // determine the shortest path
94 533 unsigned node1 = nodes_to_add.front(), node2 = nodes_to_add.back();
95
2/4
✓ Branch 1 taken 533 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 533 times.
✗ Branch 5 not taken.
 533 unsigned min_distance = pathhandler.get_distance_matrix()(node1, node2);
96
2/2
✓ Branch 5 taken 1576 times.
✓ Branch 6 taken 533 times.
2/2
✓ Decision 'true' taken 1576 times.
✓ Decision 'false' taken 533 times.
 2109 for (unsigned no1 : nodes_to_add) {
97
2/2
✓ Branch 5 taken 6532 times.
✓ Branch 6 taken 1576 times.
2/2
✓ Decision 'true' taken 6532 times.
✓ Decision 'false' taken 1576 times.
 8108 for (unsigned no2 : nodes_to_add) {
98
2/2
✓ Branch 0 taken 4956 times.
✓ Branch 1 taken 1576 times.
2/2
✓ Decision 'true' taken 4956 times.
✓ Decision 'false' taken 1576 times.
 6532 if (no1 != no2) {
99
2/4
✓ Branch 1 taken 4956 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 4956 times.
✗ Branch 5 not taken.
 4956 unsigned distance = pathhandler.get_distance_matrix()(no1, no2);
100
2/2
✓ Branch 0 taken 217 times.
✓ Branch 1 taken 4739 times.
2/2
✓ Decision 'true' taken 217 times.
✓ Decision 'false' taken 4739 times.
 4956 if (distance < min_distance) {
101 217 node1 = no1;
102 217 node2 = no2;
103 217 min_distance = distance;
104 }
105 }
106 }
107 }
108 // neighbours must both be leaves
109
4/6
✓ Branch 1 taken 533 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 533 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 346 times.
✓ Branch 8 taken 187 times.
2/2
✓ Decision 'true' taken 346 times.
✓ Decision 'false' taken 187 times.
 533 if (pathhandler.get_distance_matrix()(node1, node2) == 1) {
110 346 node_types[node1] = SteinerNodeType::Leaf;
111 346 node_types[node2] = SteinerNodeType::Leaf;
112 346 num_neighbours[node1] = 1;
113 346 num_neighbours[node2] = 1;
114
1/2
✓ Branch 1 taken 346 times.
✗ Branch 2 not taken.
 346 tree_nodes.push_back(node1);
115
1/2
✓ Branch 1 taken 346 times.
✗ Branch 2 not taken.
 346 tree_nodes.push_back(node2);
116
117 }
118 // otherwise, 0 nodes exist between.
119 else {
120 187 node_types[node1] = SteinerNodeType::Leaf;
121 187 num_neighbours[node1] = 1;
122
1/2
✓ Branch 1 taken 187 times.
✗ Branch 2 not taken.
 187 tree_nodes.push_back(node1);
123
1/2
✓ Branch 1 taken 187 times.
✗ Branch 2 not taken.
 187 add_path_to_tree(pathhandler, node1, node2);
124 }
125 533 nodes_to_add.remove(node1);
126 533 nodes_to_add.remove(node2);
127 }
128 856 }
129
130 697 void SteinerTree::add_path_to_tree(
131 const PathHandler& pathhandler, unsigned node_in_tree,
132 unsigned node_to_add) {
133 // last node is a leaf, with one neighbor
134 697 node_types[node_to_add] = SteinerNodeType::Leaf;
135 697 num_neighbours[node_to_add] = 1;
136 697 tree_nodes.push_back(node_to_add);
137
138
2/4
✓ Branch 1 taken 697 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 697 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 1394 times.
 1394 if ((node_in_tree == pathhandler.get_size()) ||
139
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 697 times.
 697 (node_to_add == pathhandler.get_size())) {
140
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ throw std::logic_error("searching for a node which is not in the tree");
141 }
142
143
2/4
✓ Branch 2 taken 697 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 697 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 1394 times.
 1394 if (pathhandler.get_distance_matrix()(node_in_tree, node_to_add) <
144
2/4
✓ Branch 1 taken 697 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 697 times.
✗ Branch 5 not taken.
 697 pathhandler.get_distance_matrix()(node_to_add, node_in_tree)) {
145
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (pathhandler.get_path_matrix()(node_to_add, node_in_tree) ==
146 ✗ pathhandler.get_size()) {
147 ✗ node_in_tree = pathhandler.get_path_matrix()(node_in_tree, node_to_add);
148 } else {
149 ✗ node_in_tree = pathhandler.get_path_matrix()(node_to_add, node_in_tree);
150 }
151
152
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if ((node_in_tree == pathhandler.get_size()) ||
153 ✗ (node_to_add == pathhandler.get_size())) {
154
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ throw std::logic_error("searching for a node which is not in the tree");
155 }
156
157
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ while (node_in_tree != node_to_add) {
158 // node in a path = zero node, it has two neighbbors
159 ✗ node_types[node_in_tree] = SteinerNodeType::ZeroInTree;
160 ✗ tree_nodes.push_back(node_in_tree);
161 ✗ num_neighbours[node_in_tree] = 2;
162
163
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (pathhandler.get_path_matrix()(node_to_add, node_in_tree) ==
164 ✗ pathhandler.get_size()) {
165 ✗ node_in_tree = pathhandler.get_path_matrix()(node_in_tree, node_to_add);
166 } else {
167 ✗ node_in_tree = pathhandler.get_path_matrix()(node_to_add, node_in_tree);
168 }
169
170
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if ((node_in_tree == pathhandler.get_size()) ||
171 ✗ (node_to_add == pathhandler.get_size())) {
172
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ throw std::logic_error("searching for a node which is not in the tree");
173 }
174 }
175 } else {
176
2/4
✓ Branch 2 taken 697 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 697 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 1394 times.
 1394 if (pathhandler.get_path_matrix()(node_to_add, node_in_tree) ==
177
1/2
✓ Branch 1 taken 697 times.
✗ Branch 2 not taken.
 697 pathhandler.get_size()) {
178 ✗ node_to_add = pathhandler.get_path_matrix()(node_in_tree, node_to_add);
179 } else {
180
1/2
✓ Branch 2 taken 697 times.
✗ Branch 3 not taken.
 697 node_to_add = pathhandler.get_path_matrix()(node_to_add, node_in_tree);
181 }
182
183
2/4
✓ Branch 1 taken 697 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 697 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 1394 times.
 1394 if ((node_in_tree == pathhandler.get_size()) ||
184
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 697 times.
 697 (node_to_add == pathhandler.get_size())) {
185
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ throw std::logic_error("searching for a node which is not in the tree");
186 }
187
188
2/2
✓ Branch 0 taken 556 times.
✓ Branch 1 taken 697 times.
2/2
✓ Decision 'true' taken 556 times.
✓ Decision 'false' taken 697 times.
 1253 while (node_in_tree != node_to_add) {
189 556 node_types[node_to_add] =
190 SteinerNodeType::ZeroInTree; // node in a path = zero node
191
192 556 tree_nodes.push_back(node_to_add);
193
194 556 num_neighbours[node_to_add] = 2; // it has two neighbbors
195
196
2/4
✓ Branch 2 taken 556 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 556 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 1112 times.
 1112 if (pathhandler.get_path_matrix()(node_to_add, node_in_tree) ==
197
1/2
✓ Branch 1 taken 556 times.
✗ Branch 2 not taken.
 556 pathhandler.get_size()) {
198 ✗ node_to_add = pathhandler.get_path_matrix()(node_in_tree, node_to_add);
199 } else {
200
1/2
✓ Branch 2 taken 556 times.
✗ Branch 3 not taken.
 556 node_to_add = pathhandler.get_path_matrix()(node_to_add, node_in_tree);
201 }
202
203
2/4
✓ Branch 1 taken 556 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 556 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 1112 times.
 1112 if ((node_in_tree == pathhandler.get_size()) ||
204
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 556 times.
 556 (node_to_add == pathhandler.get_size())) {
205
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ throw std::logic_error("searching for a node which is not in the tree");
206 }
207 }
208 }
209 697 }
210
211 510 void SteinerTree::add_closest_node_to_tree(
212 const PathHandler& pathhandler, std::list<unsigned>& nodes_to_add) {
213 510 unsigned closest_node = 0;
214 510 unsigned distant_node = UINT_MAX; // initialise to "infinity"
215 unsigned closest_tree_node(
216 510 tree_nodes.front()); // closest steiner point to the nodes we want to add
217
218 510 std::list<unsigned>::iterator itr1;
219 510 std::list<unsigned>::iterator itr2;
220
221 // take the two closest points (one of the tree, the other among the
222 // nodes_to_add)
223
2/2
✓ Branch 5 taken 1435 times.
✓ Branch 6 taken 510 times.
2/2
✓ Decision 'true' taken 1435 times.
✓ Decision 'false' taken 510 times.
 1945 for (unsigned node_to_add : nodes_to_add) {
224
2/2
✓ Branch 5 taken 6017 times.
✓ Branch 6 taken 1435 times.
2/2
✓ Decision 'true' taken 6017 times.
✓ Decision 'false' taken 1435 times.
 7452 for (unsigned tree_node : tree_nodes) {
225
4/6
✓ Branch 1 taken 6017 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 6017 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 1755 times.
✓ Branch 8 taken 4262 times.
 6017 if (pathhandler.get_distance_matrix()(tree_node, node_to_add) <
226 distant_node) // graph is oriented, we want distance
227 // tree->nodes_to_add
228 {
229 1755 closest_node = node_to_add;
230 1755 closest_tree_node = tree_node;
231 1755 distant_node =
232
2/4
✓ Branch 1 taken 1755 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1755 times.
✗ Branch 5 not taken.
 1755 pathhandler.get_distance_matrix()(tree_node, node_to_add);
233 }
234 }
235 }
236 510 nodes_to_add.remove(closest_node);
237
238 // if the node of the tree is a leaf, then its a one node after adding the
239 // new node
240
2/2
✓ Branch 1 taken 392 times.
✓ Branch 2 taken 118 times.
 510 if (node_types[closest_tree_node] == SteinerNodeType::Leaf) {
241 392 node_types[closest_tree_node] = SteinerNodeType::OneInTree;
242 }
243 510 ++num_neighbours[closest_tree_node];
244
1/2
✓ Branch 1 taken 510 times.
✗ Branch 2 not taken.
 510 add_path_to_tree(pathhandler, closest_tree_node, closest_node);
245 510 }
246
247 // assumes i & j are neighbouring vertices
248 2185 int SteinerTree::cost_of_operation(unsigned i, unsigned j) const {
249 2185 SteinerNodeType i_type = node_types[i];
250 2185 SteinerNodeType j_type = node_types[j];
251
252 // tedious case analysis
253
4/5
✓ Branch 0 taken 200 times.
✓ Branch 1 taken 1249 times.
✓ Branch 2 taken 600 times.
✓ Branch 3 taken 136 times.
✗ Branch 4 not taken.
 2185 switch (i_type) {
254 200 case SteinerNodeType::ZeroInTree: {
255
1/2
✓ Branch 0 taken 200 times.
✗ Branch 1 not taken.
 200 switch (j_type) {
256 200 case SteinerNodeType::ZeroInTree:
257 case SteinerNodeType::OneInTree:
258 case SteinerNodeType::Leaf:
259 case SteinerNodeType::OutOfTree: {
260 200 return 0;
261 }
262 ✗ default: {
263 ✗ throw InvalidCostCalculation(
264 ✗ "[AAS]: Invalid cost calculation, wrong SteinerNodeType");
265 }
266 }
267 }
268 1249 case SteinerNodeType::OneInTree: {
269
2/3
✓ Branch 0 taken 1083 times.
✓ Branch 1 taken 166 times.
✗ Branch 2 not taken.
 1249 switch (j_type) {
270 1083 case SteinerNodeType::ZeroInTree:
271 case SteinerNodeType::Leaf: {
272 1083 return -1;
273 }
274 166 case SteinerNodeType::OneInTree:
275 case SteinerNodeType::OutOfTree: {
276 166 return 1;
277 }
278 ✗ default: {
279 ✗ throw InvalidCostCalculation(
280 ✗ "[AAS]: Invalid cost calculation, wrong SteinerNodeType");
281 }
282 }
283 }
284 600 case SteinerNodeType::Leaf: {
285
2/3
✓ Branch 0 taken 465 times.
✓ Branch 1 taken 135 times.
✗ Branch 2 not taken.
 600 switch (j_type) {
286 465 case SteinerNodeType::ZeroInTree:
287 case SteinerNodeType::Leaf: {
288 465 return -1;
289 }
290 135 case SteinerNodeType::OneInTree:
291 case SteinerNodeType::OutOfTree: {
292 135 return 1;
293 }
294 ✗ default: {
295 ✗ throw InvalidCostCalculation(
296 ✗ "[AAS]: Invalid cost calculation, wrong SteinerNodeType");
297 }
298 }
299 }
300 136 case SteinerNodeType::OutOfTree: {
301
1/2
✓ Branch 0 taken 136 times.
✗ Branch 1 not taken.
 136 switch (j_type) {
302 136 case SteinerNodeType::ZeroInTree:
303 case SteinerNodeType::OneInTree:
304 case SteinerNodeType::Leaf:
305 case SteinerNodeType::OutOfTree: {
306 136 return 0;
307 }
308 ✗ default: {
309 ✗ throw InvalidCostCalculation(
310 ✗ "[AAS]: Invalid cost calculation, wrong SteinerNodeType");
311 }
312 }
313 }
314 ✗ default: {
315 ✗ throw InvalidCostCalculation(
316 ✗ "[AAS]: Invalid cost calculation, wrong SteinerNodeType");
317 }
318 }
319 }
320
321 308 OperationList SteinerTree::operations_available(
322 const PathHandler& pathhandler) const {
323 308 OperationList operations;
324
2/2
✓ Branch 1 taken 2459 times.
✓ Branch 2 taken 308 times.
 2767 for (unsigned i = 0; i != node_types.size(); ++i) {
325
2/2
✓ Branch 1 taken 23709 times.
✓ Branch 2 taken 2459 times.
 26168 for (unsigned j = 0; j != node_types.size(); ++j) {
326
2/2
✓ Branch 0 taken 2459 times.
✓ Branch 1 taken 21250 times.
 23709 if (i == j) continue;
327
4/6
✓ Branch 1 taken 21250 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 21250 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 16948 times.
✓ Branch 8 taken 4302 times.
 21250 if (!pathhandler.get_connectivity_matrix()(i, j)) continue;
328
329
4/4
✓ Branch 1 taken 3157 times.
✓ Branch 2 taken 1145 times.
✓ Branch 3 taken 2477 times.
✓ Branch 4 taken 1825 times.
 7459 if (node_types[i] == SteinerNodeType::OneInTree ||
330
2/2
✓ Branch 1 taken 1332 times.
✓ Branch 2 taken 1825 times.
 3157 node_types[i] == SteinerNodeType::Leaf) {
331
4/4
✓ Branch 1 taken 2402 times.
✓ Branch 2 taken 75 times.
✓ Branch 3 taken 780 times.
✓ Branch 4 taken 1697 times.
 4879 if (node_types[j] == SteinerNodeType::ZeroInTree ||
332
2/2
✓ Branch 1 taken 705 times.
✓ Branch 2 taken 1697 times.
 2402 node_types[j] == SteinerNodeType::Leaf) {
333
1/2
✓ Branch 2 taken 780 times.
✗ Branch 3 not taken.
 780 operations.push_back({i, j});
334 }
335 }
336 }
337 }
338 308 return operations;
339 }
340
341 2159 void SteinerTree::add_row(unsigned i, unsigned j) {
342 /* CNOT with control j and target i */
343 2159 SteinerNodeType i_type = node_types[i];
344 2159 SteinerNodeType j_type = node_types[j];
345
346 2159 last_operation_cost = cost_of_operation(i, j);
347 2159 tree_cost += last_operation_cost;
348
349
4/5
✓ Branch 0 taken 197 times.
✓ Branch 1 taken 1244 times.
✓ Branch 2 taken 590 times.
✓ Branch 3 taken 128 times.
✗ Branch 4 not taken.
 2159 switch (i_type) {
350 197 case SteinerNodeType::ZeroInTree: {
351 // no action occurs
352 197 break;
353 }
354
4/5
✓ Branch 0 taken 115 times.
✓ Branch 1 taken 155 times.
✓ Branch 2 taken 965 times.
✓ Branch 3 taken 9 times.
✗ Branch 4 not taken.
 1244 case SteinerNodeType::OneInTree: {
355 switch (j_type) {
356 115 case SteinerNodeType::ZeroInTree: {
357 115 node_types[j] = SteinerNodeType::OneInTree;
358 115 break;
359 }
360 155 case SteinerNodeType::OneInTree: {
361 155 node_types[j] = SteinerNodeType::ZeroInTree;
362 155 break;
363 }
364 965 case SteinerNodeType::Leaf: {
365 TKET_ASSERT(num_neighbours[i] != 0);
366 TKET_ASSERT(num_neighbours[j] != 0);
367 965 node_types[j] = SteinerNodeType::OutOfTree;
368 965 num_neighbours[i] -= 1;
369 965 num_neighbours[j] -= 1;
370
2/2
✓ Branch 1 taken 701 times.
✓ Branch 2 taken 264 times.
 965 if (num_neighbours[i] == 1) {
371 701 node_types[i] = SteinerNodeType::Leaf;
372 }
373 965 break;
374 }
375 9 case SteinerNodeType::OutOfTree: {
376 9 node_types[j] = SteinerNodeType::Leaf;
377 9 node_types[i] = SteinerNodeType::OneInTree;
378 9 num_neighbours[i] += 1;
379 9 num_neighbours[j] += 1;
380 9 break;
381 }
382 ✗ default: {
383 ✗ throw InvalidRowOperation(
384 "[AAS]: Invalid row operation, invalid combination "
385 ✗ "SteinerNodeType in add_row");
386 }
387 }
388 1244 break;
389 }
390
4/5
✓ Branch 0 taken 179 times.
✓ Branch 1 taken 94 times.
✓ Branch 2 taken 281 times.
✓ Branch 3 taken 36 times.
✗ Branch 4 not taken.
 590 case SteinerNodeType::Leaf: {
391 switch (j_type) {
392 179 case SteinerNodeType::ZeroInTree: {
393 179 node_types[j] = SteinerNodeType::OneInTree;
394 179 break;
395 }
396 94 case SteinerNodeType::OneInTree: {
397 94 node_types[j] = SteinerNodeType::ZeroInTree;
398 94 break;
399 }
400 // only happens when there are 2 vertices lefts
401 281 case SteinerNodeType::Leaf: {
402 TKET_ASSERT(num_neighbours[i] != 0);
403 TKET_ASSERT(num_neighbours[j] != 0);
404 281 node_types[j] = SteinerNodeType::OutOfTree;
405 281 node_types[i] = SteinerNodeType::OutOfTree;
406 281 num_neighbours[i] -= 1;
407 281 num_neighbours[j] -= 1;
408 281 break;
409 }
410 36 case SteinerNodeType::OutOfTree: {
411 36 node_types[j] = SteinerNodeType::Leaf;
412 36 node_types[i] = SteinerNodeType::OneInTree;
413 36 num_neighbours[i] += 1;
414 36 num_neighbours[j] += 1;
415 36 break;
416 }
417 ✗ default: {
418 // Invalid combination of nodes types in add row operation
419 TKET_ASSERT(false);
420 }
421 }
422 }
423 case SteinerNodeType::OutOfTree: {
424 // no action occurs
425 718 break;
426 }
427 ✗ default: {
428 TKET_ASSERT(!"Invalid combination of nodes types in add row operation");
429 }
430 }
431 2159 }
432
433 2291 bool SteinerTree::fully_reduced() const { return tree_cost == 0; }
434
435 528 static std::pair<unsigned, std::vector<unsigned>> steiner_reduce(
436 Circuit& circ, DiagMatrix& CNOT_matrix, const PathHandler& paths,
437 unsigned col, unsigned root, std::list<unsigned>& nodes, bool upper,
438 CNotSynthType cnottype) {
439 528 std::pair<unsigned, std::vector<unsigned>> result;
440
441
1/2
✓ Branch 1 taken 528 times.
✗ Branch 2 not taken.
 528 PathHandler directed_paths;
442
443
1/2
✓ Branch 1 taken 528 times.
✗ Branch 2 not taken.
 528 std::list<unsigned> fresh_node_list(nodes);
444
445
2/2
✓ Branch 0 taken 416 times.
✓ Branch 1 taken 112 times.
 528 if (upper) {
446
1/2
✓ Branch 1 taken 416 times.
✗ Branch 2 not taken.
 416 MatrixXb directed_connectivity = paths.get_connectivity_matrix();
447
2/2
✓ Branch 1 taken 3056 times.
✓ Branch 2 taken 416 times.
 3472 for (unsigned i = 0; i < directed_connectivity.rows(); ++i) {
448
2/2
✓ Branch 1 taken 28250 times.
✓ Branch 2 taken 3056 times.
 31306 for (unsigned j = 0; j < directed_connectivity.cols(); ++j) {
449
3/4
✓ Branch 0 taken 12597 times.
✓ Branch 1 taken 15653 times.
✓ Branch 3 taken 12597 times.
✗ Branch 4 not taken.
 28250 if (i < root) directed_connectivity(i, j) = 0;
450
3/4
✓ Branch 0 taken 12597 times.
✓ Branch 1 taken 15653 times.
✓ Branch 3 taken 12597 times.
✗ Branch 4 not taken.
 28250 if (j < root) directed_connectivity(i, j) = 0;
451 }
452 }
453
454
1/2
✓ Branch 1 taken 416 times.
✗ Branch 2 not taken.
 416 directed_paths = PathHandler(directed_connectivity);
455 416 } else {
456
1/2
✓ Branch 1 taken 112 times.
✗ Branch 2 not taken.
 112 MatrixXb directed_connectivity = paths.get_connectivity_matrix();
457
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 111 times.
 112 if (cnottype == CNotSynthType::HamPath) {
458
2/2
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 1 times.
 5 for (unsigned i = 0; i < directed_connectivity.rows(); ++i) {
459
2/2
✓ Branch 1 taken 16 times.
✓ Branch 2 taken 4 times.
 20 for (unsigned j = 0; j < directed_connectivity.cols(); ++j) {
460
3/4
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 10 times.
✓ Branch 3 taken 6 times.
✗ Branch 4 not taken.
 16 if (j > i) directed_connectivity(i, j) = 0;
461
5/6
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 3 times.
✓ Branch 2 taken 10 times.
✓ Branch 3 taken 3 times.
✓ Branch 5 taken 10 times.
✗ Branch 6 not taken.
 16 if ((j + 1 != i) && (j != i + 1)) directed_connectivity(i, j) = 0;
462 }
463 }
464 }
465
466
1/2
✓ Branch 1 taken 112 times.
✗ Branch 2 not taken.
 112 directed_paths = PathHandler(directed_connectivity);
467 112 }
468
1/2
✓ Branch 1 taken 528 times.
✗ Branch 2 not taken.
 528 SteinerTree cnot_tree = SteinerTree(directed_paths, fresh_node_list, root);
469
470 // make list of edges, starting from root to leaves of tree
471 528 std::list<std::pair<unsigned, unsigned>> parent_child_list;
472
1/2
✓ Branch 2 taken 528 times.
✗ Branch 3 not taken.
 528 std::set<unsigned> possible_parents{root};
473 528 unsigned n_edges = cnot_tree.tree_nodes.size();
474
1/2
✓ Branch 0 taken 528 times.
✗ Branch 1 not taken.
 528 if (n_edges > 0) --n_edges;
475
1/2
✓ Branch 2 taken 528 times.
✗ Branch 3 not taken.
 528 std::set<unsigned> visited_parents{root};
476 528 unsigned counterwhile = 0;
477
4/4
✓ Branch 1 taken 550 times.
✓ Branch 2 taken 528 times.
✓ Branch 3 taken 550 times.
✓ Branch 4 taken 528 times.
 1628 while ((parent_child_list.size() < n_edges) &&
478
1/2
✓ Branch 0 taken 550 times.
✗ Branch 1 not taken.
 550 (counterwhile < n_edges * n_edges)) {
479 550 ++counterwhile;
480 550 std::set<unsigned> new_parents;
481
482
2/2
✓ Branch 5 taken 2676 times.
✓ Branch 6 taken 550 times.
 3226 for (unsigned node : cnot_tree.tree_nodes) {
483
2/2
✓ Branch 5 taken 3052 times.
✓ Branch 6 taken 2676 times.
 5728 for (unsigned parent : possible_parents) {
484
4/6
✓ Branch 1 taken 3052 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 3052 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 946 times.
✓ Branch 8 taken 2106 times.
 3052 if (directed_paths.get_connectivity_matrix()(parent, node)) {
485
3/4
✓ Branch 2 taken 946 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 614 times.
✓ Branch 6 taken 332 times.
 946 if (visited_parents.find(node) == visited_parents.end()) {
486
1/2
✓ Branch 1 taken 614 times.
✗ Branch 2 not taken.
 614 new_parents.insert(node);
487
1/2
✓ Branch 1 taken 614 times.
✗ Branch 2 not taken.
 614 visited_parents.insert(node);
488
1/2
✓ Branch 2 taken 614 times.
✗ Branch 3 not taken.
 614 parent_child_list.push_back({parent, node});
489 }
490 }
491 }
492 }
493
494
1/2
✓ Branch 1 taken 550 times.
✗ Branch 2 not taken.
 550 possible_parents = new_parents;
495 550 }
496
497 /* Remove zeros */
498
2/2
✓ Branch 0 taken 416 times.
✓ Branch 1 taken 112 times.
 528 if (upper) {
499 416 std::list<std::pair<unsigned, unsigned>> zeros;
500
2/2
✓ Branch 7 taken 315 times.
✓ Branch 8 taken 416 times.
 731 for (auto& [s0, s1] : parent_child_list) {
501
3/4
✓ Branch 1 taken 315 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 168 times.
✓ Branch 4 taken 147 times.
 315 if (!CNOT_matrix._matrix(s0, col)) {
502
1/2
✓ Branch 2 taken 168 times.
✗ Branch 3 not taken.
 168 zeros.push_back({s0, s1});
503 }
504 }
505
2/2
✓ Branch 1 taken 168 times.
✓ Branch 2 taken 416 times.
 584 while (!zeros.empty()) {
506 168 std::pair<unsigned, unsigned> s_pair = zeros.back();
507 168 unsigned s0 = s_pair.first, s1 = s_pair.second;
508 168 zeros.pop_back();
509
3/4
✓ Branch 1 taken 168 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 164 times.
✓ Branch 4 taken 4 times.
 168 if (!CNOT_matrix._matrix(s0, col)) {
510
1/2
✓ Branch 1 taken 164 times.
✗ Branch 2 not taken.
 164 CNOT_matrix.row_add(s1, s0);
511
2/4
✓ Branch 3 taken 164 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 164 times.
✗ Branch 7 not taken.
 164 circ.add_op<unsigned>(OpType::CX, {s1, s0});
512 }
513 }
514 416 parent_child_list.reverse();
515
2/2
✓ Branch 6 taken 315 times.
✓ Branch 7 taken 416 times.
 731 for (auto& [s0, s1] : parent_child_list) {
516
1/2
✓ Branch 1 taken 315 times.
✗ Branch 2 not taken.
 315 CNOT_matrix.row_add(s0, s1);
517
2/4
✓ Branch 3 taken 315 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 315 times.
✗ Branch 7 not taken.
 315 circ.add_op<unsigned>(OpType::CX, {s0, s1});
518 }
519 416 } else {
520
2/2
✓ Branch 7 taken 299 times.
✓ Branch 8 taken 112 times.
 411 for (auto& [s0, s1] : parent_child_list) {
521
3/4
✓ Branch 1 taken 299 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 122 times.
✓ Branch 4 taken 177 times.
 299 if (!CNOT_matrix._matrix(s1, col)) {
522
1/2
✓ Branch 1 taken 122 times.
✗ Branch 2 not taken.
 122 CNOT_matrix.row_add(s0, s1);
523
2/4
✓ Branch 3 taken 122 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 122 times.
✗ Branch 7 not taken.
 122 circ.add_op<unsigned>(OpType::CX, {s0, s1});
524 }
525 }
526 112 parent_child_list.reverse();
527
2/2
✓ Branch 6 taken 299 times.
✓ Branch 7 taken 112 times.
 411 for (auto& [s0, s1] : parent_child_list) {
528
1/2
✓ Branch 1 taken 299 times.
✗ Branch 2 not taken.
 299 CNOT_matrix.row_add(s0, s1);
529
2/4
✓ Branch 3 taken 299 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 299 times.
✗ Branch 7 not taken.
 299 circ.add_op<unsigned>(OpType::CX, {s0, s1});
530 }
531 }
532
1/2
✓ Branch 1 taken 528 times.
✗ Branch 2 not taken.
 528 result.first = cnot_tree.get_max_element();
533
1/2
✓ Branch 1 taken 528 times.
✗ Branch 2 not taken.
 528 result.second = cnot_tree.nodes();
534 1056 return result;
535 528 }
536
537 138 static std::pair<unsigned, std::vector<unsigned>> steiner_reduce_rec(
538 Circuit& circ, DiagMatrix& CNOT_matrix, const PathHandler& paths,
539 unsigned col, unsigned root, std::list<unsigned>& nodes) {
540 138 std::pair<unsigned, std::vector<unsigned>> result;
541
542
1/2
✓ Branch 1 taken 138 times.
✗ Branch 2 not taken.
 138 std::list<unsigned> fresh_node_list(nodes);
543
544
1/2
✓ Branch 1 taken 138 times.
✗ Branch 2 not taken.
 138 SteinerTree cnot_tree = SteinerTree(paths, fresh_node_list, root);
545
546 // make list of edges, starting from root to leaves of tree
547 138 std::list<std::pair<unsigned, unsigned>> parent_child_list;
548
1/2
✓ Branch 2 taken 138 times.
✗ Branch 3 not taken.
 138 std::set<unsigned> possible_parents{root};
549 138 unsigned n_edges = cnot_tree.tree_nodes.size();
550
1/2
✓ Branch 0 taken 138 times.
✗ Branch 1 not taken.
 138 if (n_edges > 0) --n_edges;
551
1/2
✓ Branch 2 taken 138 times.
✗ Branch 3 not taken.
 138 std::set<unsigned> visited_parents{root};
552 138 unsigned counterwhile = 0;
553
4/4
✓ Branch 1 taken 416 times.
✓ Branch 2 taken 138 times.
✓ Branch 3 taken 416 times.
✓ Branch 4 taken 138 times.
 970 while ((parent_child_list.size() < n_edges) &&
554
1/2
✓ Branch 0 taken 416 times.
✗ Branch 1 not taken.
 416 (counterwhile < n_edges * n_edges)) {
555 416 ++counterwhile;
556 416 std::set<unsigned> new_parents;
557
558
2/2
✓ Branch 5 taken 2148 times.
✓ Branch 6 taken 416 times.
 2564 for (unsigned node : cnot_tree.tree_nodes) {
559
2/2
✓ Branch 5 taken 2508 times.
✓ Branch 6 taken 2148 times.
 4656 for (unsigned parent : possible_parents) {
560
4/6
✓ Branch 1 taken 2508 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2508 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 820 times.
✓ Branch 8 taken 1688 times.
 2508 if (paths.get_connectivity_matrix()(parent, node)) {
561
3/4
✓ Branch 2 taken 820 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 493 times.
✓ Branch 6 taken 327 times.
 820 if (visited_parents.find(node) == visited_parents.end()) {
562
1/2
✓ Branch 1 taken 493 times.
✗ Branch 2 not taken.
 493 new_parents.insert(node);
563
1/2
✓ Branch 1 taken 493 times.
✗ Branch 2 not taken.
 493 visited_parents.insert(node);
564
1/2
✓ Branch 2 taken 493 times.
✗ Branch 3 not taken.
 493 parent_child_list.push_back({parent, node});
565 }
566 }
567 }
568 }
569
570
1/2
✓ Branch 1 taken 416 times.
✗ Branch 2 not taken.
 416 possible_parents = new_parents;
571 416 }
572
573 /* Remove zeros */
574
2/2
✓ Branch 7 taken 493 times.
✓ Branch 8 taken 138 times.
 631 for (auto& [s0, s1] : parent_child_list) {
575
3/4
✓ Branch 1 taken 493 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 293 times.
✓ Branch 4 taken 200 times.
 493 if (!CNOT_matrix._matrix(s1, col)) {
576
1/2
✓ Branch 1 taken 293 times.
✗ Branch 2 not taken.
 293 CNOT_matrix.row_add(s0, s1);
577
2/4
✓ Branch 3 taken 293 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 293 times.
✗ Branch 7 not taken.
 293 circ.add_op<unsigned>(OpType::CX, {s0, s1});
578 }
579 }
580 138 parent_child_list.reverse();
581
2/2
✓ Branch 6 taken 493 times.
✓ Branch 7 taken 138 times.
 631 for (auto& [s0, s1] : parent_child_list) {
582
1/2
✓ Branch 1 taken 493 times.
✗ Branch 2 not taken.
 493 CNOT_matrix.row_add(s0, s1);
583
2/4
✓ Branch 3 taken 493 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 493 times.
✗ Branch 7 not taken.
 493 circ.add_op<unsigned>(OpType::CX, {s0, s1});
584 }
585
1/2
✓ Branch 1 taken 138 times.
✗ Branch 2 not taken.
 138 result.first = cnot_tree.get_max_element();
586
1/2
✓ Branch 1 taken 138 times.
✗ Branch 2 not taken.
 138 result.second = cnot_tree.nodes();
587 276 return result;
588 138 }
589
590 77 void aas_cnot_synth_rec(
591 DiagMatrix& CNOT_matrix, const PathHandler& paths,
592 std::vector<unsigned>& pivot_cols, Circuit& cnot_circuit,
593 std::vector<unsigned> usablenodes = {}) {
594 // order usable nodes from highest to lowest element, the list should already
595 // be close to the opposite of this order anyway.
596 77 std::sort(usablenodes.begin(), usablenodes.end());
597 77 std::reverse(usablenodes.begin(), usablenodes.end());
598
2/2
✓ Branch 5 taken 450 times.
✓ Branch 6 taken 77 times.
 527 for (unsigned current_row : usablenodes) {
599 450 unsigned pivot = pivot_cols[current_row];
600
601 450 std::list<unsigned> nodes;
602
603
2/2
✓ Branch 0 taken 3223 times.
✓ Branch 1 taken 450 times.
 3673 for (unsigned r = 0; r != current_row; ++r) {
604
3/4
✓ Branch 1 taken 3223 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 200 times.
✓ Branch 4 taken 3023 times.
 3223 if (CNOT_matrix._matrix(r, pivot)) {
605
1/2
✓ Branch 1 taken 200 times.
✗ Branch 2 not taken.
 200 nodes.push_back(r);
606 }
607 }
608 450 unsigned max_node_in_tree = 0;
609 450 std::vector<unsigned> new_usable_nodes;
610
2/2
✓ Branch 1 taken 138 times.
✓ Branch 2 taken 312 times.
 450 if (!nodes.empty()) {
611
1/2
✓ Branch 1 taken 138 times.
✗ Branch 2 not taken.
 138 nodes.push_back(current_row);
612 std::pair<unsigned, std::vector<unsigned>> res = steiner_reduce_rec(
613
1/2
✓ Branch 1 taken 138 times.
✗ Branch 2 not taken.
 138 cnot_circuit, CNOT_matrix, paths, pivot, current_row, nodes);
614 138 max_node_in_tree = res.first;
615
1/2
✓ Branch 1 taken 138 times.
✗ Branch 2 not taken.
 138 new_usable_nodes = res.second;
616 138 }
617
618
2/2
✓ Branch 0 taken 59 times.
✓ Branch 1 taken 391 times.
 450 if (max_node_in_tree > current_row) {
619
2/4
✓ Branch 1 taken 59 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 59 times.
✗ Branch 5 not taken.
 59 aas_cnot_synth_rec(
620 CNOT_matrix, paths, pivot_cols, cnot_circuit, new_usable_nodes);
621 }
622 450 }
623 77 }
624
625 // see https://arxiv.org/abs/2004.06052 and https://github.com/Quantomatic/pyzx
626 // for more information.
627 75 Circuit aas_CNOT_synth(
628 DiagMatrix& CNOT_matrix, const PathHandler& paths, CNotSynthType cnottype) {
629 75 unsigned pivot = 0;
630 75 unsigned max_node_in_tree = 0;
631
2/4
✓ Branch 2 taken 75 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 75 times.
✗ Branch 6 not taken.
 75 std::vector<unsigned> usable_nodes(paths.get_size());
632 75 std::iota(usable_nodes.begin(), usable_nodes.end(), 0);
633
634 75 std::vector<unsigned> pivot_cols;
635
2/4
✓ Branch 2 taken 75 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 75 times.
✗ Branch 6 not taken.
 75 Circuit cnot_circuit(paths.get_size());
636
3/4
✓ Branch 1 taken 491 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 416 times.
✓ Branch 4 taken 75 times.
 491 for (unsigned current_row = 0; current_row != CNOT_matrix.n_rows();
637 ++current_row) {
638 416 bool found_pivot = false;
639 416 std::list<unsigned> nodes;
640
6/8
✓ Branch 0 taken 416 times.
✓ Branch 1 taken 416 times.
✓ Branch 3 taken 416 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 416 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 416 times.
✓ Branch 8 taken 416 times.
 832 while ((!found_pivot) && pivot < CNOT_matrix.n_cols()) {
641
3/4
✓ Branch 1 taken 2152 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1736 times.
✓ Branch 4 taken 416 times.
 2152 for (unsigned r = current_row; r != CNOT_matrix.n_rows(); ++r) {
642
3/4
✓ Branch 1 taken 1736 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 567 times.
✓ Branch 4 taken 1169 times.
 1736 if (CNOT_matrix._matrix(r, pivot)) {
643
1/2
✓ Branch 1 taken 567 times.
✗ Branch 2 not taken.
 567 nodes.push_back(r);
644 }
645 }
646
1/2
✓ Branch 1 taken 416 times.
✗ Branch 2 not taken.
 416 if (!nodes.empty()) {
647
1/2
✓ Branch 1 taken 416 times.
✗ Branch 2 not taken.
 416 pivot_cols.push_back(pivot);
648 416 found_pivot = true;
649 } else {
650 ✗ ++pivot;
651 }
652 }
653
654 // can't try any more pivots
655
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 416 times.
 416 if (!found_pivot)
656 ✗ throw std::logic_error("Could not find pivot node in CNOT synthesis.");
657
658
1/2
✓ Branch 3 taken 416 times.
✗ Branch 4 not taken.
 416 bool row_not_in_notes = std::none_of(
659 nodes.cbegin(), nodes.cend(),
660 466 [current_row](unsigned no) { return no == current_row; });
661
662
3/4
✓ Branch 0 taken 74 times.
✓ Branch 1 taken 342 times.
✓ Branch 3 taken 74 times.
✗ Branch 4 not taken.
 416 if (row_not_in_notes) nodes.push_front(current_row);
663 std::pair<unsigned, std::vector<unsigned>> res = steiner_reduce(
664 cnot_circuit, CNOT_matrix, paths, pivot, current_row, nodes, true,
665
1/2
✓ Branch 1 taken 416 times.
✗ Branch 2 not taken.
 416 cnottype);
666
667 416 max_node_in_tree = res.first;
668
1/2
✓ Branch 1 taken 416 times.
✗ Branch 2 not taken.
 416 usable_nodes = res.second;
669 416 ++pivot;
670 416 }
671
672 75 unsigned current_row = pivot_cols.size() - 1;
673
2/2
✓ Branch 0 taken 341 times.
✓ Branch 1 taken 75 times.
 416 while (current_row > 0) {
674 341 std::list<unsigned> nodes;
675
2/4
✓ Branch 1 taken 341 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 341 times.
✗ Branch 4 not taken.
 341 if (CNOT_matrix.is_id_until_columns(current_row)) {
676 341 pivot = pivot_cols[current_row];
677
678
2/2
✓ Branch 0 taken 1320 times.
✓ Branch 1 taken 341 times.
 1661 for (unsigned r = 0; r != current_row; ++r) {
679
3/4
✓ Branch 1 taken 1320 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 177 times.
✓ Branch 4 taken 1143 times.
 1320 if (CNOT_matrix._matrix(r, pivot)) {
680
1/2
✓ Branch 1 taken 177 times.
✗ Branch 2 not taken.
 177 nodes.push_back(r);
681 }
682 }
683
2/2
✓ Branch 1 taken 112 times.
✓ Branch 2 taken 229 times.
 341 if (!nodes.empty()) {
684
1/2
✓ Branch 1 taken 112 times.
✗ Branch 2 not taken.
 112 nodes.push_back(current_row);
685
686 std::pair<unsigned, std::vector<unsigned>> res = steiner_reduce(
687 cnot_circuit, CNOT_matrix, paths, pivot, current_row, nodes, false,
688
1/2
✓ Branch 1 taken 112 times.
✗ Branch 2 not taken.
 112 cnottype);
689
690 112 max_node_in_tree = res.first;
691
1/2
✓ Branch 1 taken 112 times.
✗ Branch 2 not taken.
 112 usable_nodes = res.second;
692 112 } else {
693 229 max_node_in_tree = 0;
694 229 std::iota(usable_nodes.begin(), usable_nodes.end(), 0);
695 }
696 }
697
698
3/4
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 323 times.
✓ Branch 2 taken 18 times.
✗ Branch 3 not taken.
 341 if ((max_node_in_tree > current_row) && (cnottype == CNotSynthType::Rec)) {
699
2/4
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 18 times.
✗ Branch 5 not taken.
 18 aas_cnot_synth_rec(
700 CNOT_matrix, paths, pivot_cols, cnot_circuit, usable_nodes);
701 }
702
703 341 --current_row;
704
705 TKET_ASSERT(CNOT_matrix.is_id_until_columns(current_row));
706 341 }
707
708 // when constructing circuit, we want to
709 // prepend gates, but it is easier to append and then take the dagger.
710 150 return cnot_circuit;
711 75 }
712
713 5 Circuit CNotSwapSynth::get_circuit() { return circ; }
714
715 542 void CNotSwapSynth::add_swap(unsigned first, unsigned second) {
716 542 CNOT_matrix.row_add(first, second);
717 542 CNOT_matrix.row_add(second, first);
718 542 CNOT_matrix.row_add(first, second);
719
2/4
✓ Branch 3 taken 542 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 542 times.
✗ Branch 7 not taken.
 542 circ.add_op<unsigned>(OpType::CX, {first, second});
720
2/4
✓ Branch 3 taken 542 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 542 times.
✗ Branch 7 not taken.
 542 circ.add_op<unsigned>(OpType::CX, {second, first});
721
2/4
✓ Branch 3 taken 542 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 542 times.
✗ Branch 7 not taken.
 542 circ.add_op<unsigned>(OpType::CX, {first, second});
722 542 }
723
724 3 Circuit aas_CNOT_synth_SWAP(DiagMatrix& CNOT_matrix, const PathHandler& paths) {
725
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 CNotSwapSynth cnot(paths, CNOT_matrix);
726 TKET_ASSERT(cnot.valid_result());
727
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 6 return cnot.get_circuit();
728 3 }
729
730 5 CNotSwapSynth::CNotSwapSynth(
731 5 const PathHandler& pathhandler, const DiagMatrix& CNOT_mat)
732 5 : paths(pathhandler),
733
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 CNOT_matrix(CNOT_mat),
734
3/6
✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 5 times.
✗ Branch 6 not taken.
✓ Branch 9 taken 5 times.
✗ Branch 10 not taken.
 5 circ(Circuit(paths.get_size())) {
735
3/4
✓ Branch 1 taken 54 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 49 times.
✓ Branch 4 taken 5 times.
 54 for (unsigned current_row = 0; current_row != CNOT_matrix.n_rows();
736 ++current_row) {
737
3/4
✓ Branch 1 taken 49 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 10 times.
✓ Branch 4 taken 39 times.
 49 if (!CNOT_matrix._matrix(current_row, current_row)) {
738 // try to find element equal to 1
739 // and set diagonal element to 1
740 10 unsigned one = current_row;
741
3/4
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 18 times.
✓ Branch 4 taken 10 times.
 28 while (!CNOT_matrix._matrix(one, current_row)) {
742 18 ++one;
743 }
744
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 unsigned current_node = swap_to_root(one, current_row);
745
746 // remove the 1 with the use of the root
747
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 CNOT_matrix.row_add(current_node, current_row);
748
2/4
✓ Branch 3 taken 10 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 10 times.
✗ Branch 7 not taken.
 10 circ.add_op<unsigned>(OpType::CX, {current_node, current_row});
749
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 cleanup_swaps();
750 }
751
752
2/4
✓ Branch 1 taken 49 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 49 times.
 49 if (!CNOT_matrix._matrix(current_row, current_row)) {
753 ✗ throw std::logic_error(
754 "The given matrix is not invertible, the input was not created by a "
755 ✗ "cnot circuit");
756 }
757
758
3/4
✓ Branch 1 taken 295 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 246 times.
✓ Branch 4 taken 49 times.
 295 for (unsigned r = current_row + 1; r != CNOT_matrix.n_rows(); ++r) {
759
3/4
✓ Branch 1 taken 246 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 66 times.
✓ Branch 4 taken 180 times.
 246 if (CNOT_matrix._matrix(r, current_row)) {
760
1/2
✓ Branch 1 taken 66 times.
✗ Branch 2 not taken.
 66 unsigned current_node = swap_to_root(r, current_row);
761
762
1/2
✓ Branch 1 taken 66 times.
✗ Branch 2 not taken.
 66 CNOT_matrix.row_add(current_row, current_node);
763
2/4
✓ Branch 3 taken 66 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 66 times.
✗ Branch 7 not taken.
 66 circ.add_op<unsigned>(OpType::CX, {current_row, current_node});
764
1/2
✓ Branch 1 taken 66 times.
✗ Branch 2 not taken.
 66 cleanup_swaps();
765 }
766 }
767 }
768 // end of upper creation
769
770
3/4
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 44 times.
✓ Branch 4 taken 5 times.
 49 for (unsigned current_row = CNOT_matrix.n_rows() - 1; current_row > 0;
771 --current_row) {
772
2/2
✓ Branch 0 taken 246 times.
✓ Branch 1 taken 44 times.
 290 for (unsigned r = 0; r < current_row; ++r) {
773
3/4
✓ Branch 1 taken 246 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 55 times.
✓ Branch 4 taken 191 times.
 246 if (CNOT_matrix._matrix(r, current_row)) {
774
1/2
✓ Branch 1 taken 55 times.
✗ Branch 2 not taken.
 55 unsigned current_node = swap_to_root(r, current_row);
775
776
1/2
✓ Branch 1 taken 55 times.
✗ Branch 2 not taken.
 55 CNOT_matrix.row_add(current_row, current_node);
777
2/4
✓ Branch 3 taken 55 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 55 times.
✗ Branch 7 not taken.
 55 circ.add_op<unsigned>(OpType::CX, {current_row, current_node});
778
779
1/2
✓ Branch 1 taken 55 times.
✗ Branch 2 not taken.
 55 cleanup_swaps();
780 }
781 }
782 }
783 5 }
784
785 131 void CNotSwapSynth::cleanup_swaps() {
786
2/2
✓ Branch 1 taken 271 times.
✓ Branch 2 taken 131 times.
 402 while (!swaps.empty()) {
787 271 std::pair<unsigned, unsigned> swap = swaps.top();
788 271 swaps.pop();
789
1/2
✓ Branch 1 taken 271 times.
✗ Branch 2 not taken.
 271 add_swap(swap.first, swap.second);
790 }
791 131 }
792
793 131 unsigned CNotSwapSynth::swap_to_root(
794 unsigned start_node, unsigned current_row) {
795 131 unsigned current_node = start_node;
796
797
4/6
✓ Branch 1 taken 402 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 402 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 271 times.
✓ Branch 8 taken 131 times.
 402 while (paths.get_path_matrix()(current_node, current_row) != current_row) {
798
2/4
✓ Branch 1 taken 271 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 271 times.
✗ Branch 5 not taken.
 271 unsigned new_node = paths.get_path_matrix()(current_node, current_row);
799
1/2
✓ Branch 1 taken 271 times.
✗ Branch 2 not taken.
 271 add_swap(current_node, new_node);
800
801
1/2
✓ Branch 2 taken 271 times.
✗ Branch 3 not taken.
 271 swaps.push({current_node, new_node});
802 271 current_node = new_node;
803 }
804 131 return current_node;
805 }
806
807 5 bool CNotSwapSynth::valid_result() { return CNOT_matrix.is_id(); }
808
809 } // namespace aas
810 } // namespace tket
811