GCC Code Coverage Report

Directory: ./
File: ArchAwareSynth/Path.cpp
Date: 2022-10-15 05:10:18
Warnings: 3 unchecked decisions!
Exec Total Coverage
Lines: 128 129 99.2%
Functions: 10 10 100.0%
Branches: 157 238 66.0%
Decisions: 60 68 88.2%
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 "Path.hpp"
16
17 #include <stdexcept>
18
19 namespace tket {
20
21 namespace aas {
22
23 // The idiomatic way to initialise a PathHandler, and assumes the architecture
24 // is symmetric. The way using a MatrixXb is for internal use. We initialise
25 // without using the distance matrix from Architecture, as we generate distances
26 // using Floyd-Warshall anyway.
27 163 PathHandler::PathHandler(const Architecture &arch)
28
1/2
✓ Branch 2 taken 163 times.
✗ Branch 3 not taken.
 163 : PathHandler(arch.get_connectivity()) {}
29
30 // breaks for devices with n_qubits >= UINT_MAX/2
31 // For internal use.
32
2/4
✓ Branch 2 taken 801 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 801 times.
✗ Branch 6 not taken.
 801 PathHandler::PathHandler(const MatrixXb &connectivity) {
33 801 unsigned n = connectivity.rows();
34 801 size = n;
35
36 801 unsigned approx_infinity = UINT_MAX >> 1;
37
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 801 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
1/2
✓ Decision 'true' taken 801 times.
✗ Decision 'false' not taken.
 801 if (n >= approx_infinity) throw std::out_of_range("Qubit number too large");
38
2/4
✓ Branch 1 taken 801 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 801 times.
✗ Branch 5 not taken.
 801 distance_matrix_ = MatrixXu::Constant(n, n, approx_infinity);
39
2/4
✓ Branch 1 taken 801 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 801 times.
✗ Branch 5 not taken.
 801 path_matrix_ = MatrixXu::Constant(n, n, n); // set all unreachable nodes to n
40
1/2
✓ Branch 1 taken 801 times.
✗ Branch 2 not taken.
 801 connectivity_matrix_ = connectivity;
41
42 // Floyd-Warshall with path reconstruction, see:
43 // https://en.wikipedia.org/wiki/Floyd–Warshall_algorithm#Pseudocode_[11]
44
2/2
✓ Branch 0 taken 5521 times.
✓ Branch 1 taken 801 times.
2/2
✓ Decision 'true' taken 5521 times.
✓ Decision 'false' taken 801 times.
 6322 for (unsigned i = 0; i != n; ++i) {
45
1/2
✓ Branch 1 taken 5521 times.
✗ Branch 2 not taken.
 5521 distance_matrix_(i, i) = 0;
46
1/2
✓ Branch 1 taken 5521 times.
✗ Branch 2 not taken.
 5521 path_matrix_(i, i) = i;
47
2/2
✓ Branch 0 taken 49169 times.
✓ Branch 1 taken 5521 times.
2/2
✓ Decision 'true' taken 49169 times.
✓ Decision 'false' taken 5521 times.
 54690 for (unsigned j = 0; j != n; ++j) {
48
2/2
✓ Branch 0 taken 5521 times.
✓ Branch 1 taken 43648 times.
2/2
✓ Decision 'true' taken 43648 times.
✓ Decision 'false' taken 5521 times.
 49169 if (i == j) continue;
49
3/4
✓ Branch 1 taken 43648 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 6910 times.
✓ Branch 4 taken 36738 times.
2/2
✓ Decision 'true' taken 6910 times.
✓ Decision 'false' taken 36738 times.
 43648 if (connectivity_matrix_(i, j)) {
50
1/2
✓ Branch 1 taken 6910 times.
✗ Branch 2 not taken.
 6910 distance_matrix_(i, j) = 1;
51
1/2
✓ Branch 1 taken 6910 times.
✗ Branch 2 not taken.
 6910 path_matrix_(i, j) = j;
52 }
53 }
54 }
55
2/2
✓ Branch 0 taken 5521 times.
✓ Branch 1 taken 801 times.
2/2
✓ Decision 'true' taken 5521 times.
✓ Decision 'false' taken 801 times.
 6322 for (unsigned k = 0; k != n; ++k) {
56
2/2
✓ Branch 0 taken 49169 times.
✓ Branch 1 taken 5521 times.
2/2
✓ Decision 'true' taken 49169 times.
✓ Decision 'false' taken 5521 times.
 54690 for (unsigned i = 0; i != n; ++i) {
57
2/2
✓ Branch 0 taken 519715 times.
✓ Branch 1 taken 49169 times.
2/2
✓ Decision 'true' taken 519715 times.
✓ Decision 'false' taken 49169 times.
 568884 for (unsigned j = 0; j != n; ++j) {
58
2/4
✓ Branch 1 taken 519715 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 519715 times.
✗ Branch 5 not taken.
 519715 unsigned threshold = distance_matrix_(i, k) + distance_matrix_(k, j);
59
3/4
✓ Branch 1 taken 519715 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 20908 times.
✓ Branch 4 taken 498807 times.
2/2
✓ Decision 'true' taken 20908 times.
✓ Decision 'false' taken 498807 times.
 519715 if (distance_matrix_(i, j) > threshold) {
60
1/2
✓ Branch 1 taken 20908 times.
✗ Branch 2 not taken.
 20908 distance_matrix_(i, j) = threshold;
61
2/4
✓ Branch 1 taken 20908 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 20908 times.
✗ Branch 5 not taken.
 20908 path_matrix_(i, j) = path_matrix_(i, k);
62 }
63 }
64 }
65 }
66 801 }
67
68 88 PathHandler PathHandler::construct_acyclic_handler() const {
69
1/2
✓ Branch 1 taken 88 times.
✗ Branch 2 not taken.
 88 PathHandler acyclic_handler;
70 88 unsigned n = distance_matrix_.rows();
71
1/2
✓ Branch 1 taken 88 times.
✗ Branch 2 not taken.
 88 MatrixXb acyclic_connectivity(n, n);
72
1/2
✓ Branch 2 taken 88 times.
✗ Branch 3 not taken.
 88 std::vector<unsigned> num_neighbours(n, 0);
73
74
2/2
✓ Branch 0 taken 510 times.
✓ Branch 1 taken 88 times.
2/2
✓ Decision 'true' taken 510 times.
✓ Decision 'false' taken 88 times.
 598 for (unsigned i = 0; i != n; ++i) {
75
2/2
✓ Branch 0 taken 3928 times.
✓ Branch 1 taken 510 times.
2/2
✓ Decision 'true' taken 3928 times.
✓ Decision 'false' taken 510 times.
 4438 for (unsigned j = 0; j != n; ++j) {
76
3/4
✓ Branch 1 taken 3928 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 886 times.
✓ Branch 4 taken 3042 times.
2/2
✓ Decision 'true' taken 598 times.
✓ Decision 'false' taken 3330 times.
 3928 if (connectivity_matrix_(i, j)) ++num_neighbours[i];
77 }
78 }
79
80
2/2
✓ Branch 0 taken 510 times.
✓ Branch 1 taken 88 times.
2/2
✓ Decision 'true' taken 510 times.
✓ Decision 'false' taken 88 times.
 598 for (unsigned i = 0; i != n; ++i) {
81
2/2
✓ Branch 0 taken 3928 times.
✓ Branch 1 taken 510 times.
2/2
✓ Decision 'true' taken 3928 times.
✓ Decision 'false' taken 510 times.
 4438 for (unsigned j = 0; j != n; ++j) {
82
1/2
✓ Branch 1 taken 3928 times.
✗ Branch 2 not taken.
 3928 acyclic_connectivity(i, j) = 0;
83 }
84 }
85
86 // find the centre
87 88 unsigned threshold_max_dist = n, max_dist_row = 0, centre_node = 0;
88
89
2/2
✓ Branch 0 taken 510 times.
✓ Branch 1 taken 88 times.
2/2
✓ Decision 'true' taken 510 times.
✓ Decision 'false' taken 88 times.
 598 for (unsigned i = 0; i != n; ++i) {
90
2/2
✓ Branch 0 taken 3928 times.
✓ Branch 1 taken 510 times.
2/2
✓ Decision 'true' taken 3928 times.
✓ Decision 'false' taken 510 times.
 4438 for (unsigned j = 0; j != n; ++j) {
91
3/4
✓ Branch 1 taken 3928 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 912 times.
✓ Branch 4 taken 3016 times.
2/2
✓ Decision 'true' taken 912 times.
✓ Decision 'false' taken 3016 times.
 3928 if (distance_matrix_(i, j) > max_dist_row)
92
1/2
✓ Branch 1 taken 912 times.
✗ Branch 2 not taken.
 912 max_dist_row = distance_matrix_(i, j);
93 }
94
2/2
✓ Branch 0 taken 229 times.
✓ Branch 1 taken 281 times.
2/2
✓ Decision 'true' taken 229 times.
✓ Decision 'false' taken 281 times.
 510 if (max_dist_row < threshold_max_dist) {
95 229 centre_node = i;
96 229 threshold_max_dist = max_dist_row;
97 }
98 510 max_dist_row = 0;
99 }
100
101 // build the acyclic graph outwards from the centre
102
1/2
✓ Branch 2 taken 88 times.
✗ Branch 3 not taken.
 88 std::list<unsigned> current_layer_vertices{centre_node};
103 88 std::list<unsigned> next_layer_vertices;
104 std::vector<std::pair<unsigned, unsigned>> parents_neighbours(
105
1/2
✓ Branch 2 taken 88 times.
✗ Branch 3 not taken.
 88 n); // pair(num_neighbours, parent vertex)
106 std::vector<bool> vertices_in_tree(
107
1/2
✓ Branch 2 taken 88 times.
✗ Branch 3 not taken.
 88 n, 0); // track which vertices are in the acyclic graph
108
1/2
✓ Branch 1 taken 88 times.
✗ Branch 2 not taken.
 88 vertices_in_tree[centre_node] = 1;
109 88 std::pair<unsigned, unsigned> empty_pair{};
110
2/2
✓ Branch 1 taken 277 times.
✓ Branch 2 taken 88 times.
2/2
✓ Decision 'true' taken 277 times.
✓ Decision 'false' taken 88 times.
 365 while (!current_layer_vertices.empty()) {
111
2/2
✓ Branch 5 taken 510 times.
✓ Branch 6 taken 277 times.
2/2
✓ Decision 'true' taken 510 times.
✓ Decision 'false' taken 277 times.
 787 for (unsigned vert : current_layer_vertices) {
112
2/2
✓ Branch 0 taken 3928 times.
✓ Branch 1 taken 510 times.
2/2
✓ Decision 'true' taken 3928 times.
✓ Decision 'false' taken 510 times.
 4438 for (unsigned j = 0; j != n; ++j) {
113
8/10
✓ Branch 1 taken 3928 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 886 times.
✓ Branch 4 taken 3042 times.
✓ Branch 6 taken 886 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 430 times.
✓ Branch 10 taken 456 times.
✓ Branch 11 taken 430 times.
✓ Branch 12 taken 3498 times.
2/2
✓ Decision 'true' taken 430 times.
✓ Decision 'false' taken 3498 times.
 3928 if ((distance_matrix_(vert, j) == 1) && (!vertices_in_tree[j])) {
114 // if first encounter of vertex, add to next layer
115
2/2
✓ Branch 2 taken 422 times.
✓ Branch 3 taken 8 times.
2/2
✓ Decision 'true' taken 422 times.
✓ Decision 'false' taken 8 times.
 430 if (parents_neighbours[j] == empty_pair) {
116
1/2
✓ Branch 1 taken 422 times.
✗ Branch 2 not taken.
 422 next_layer_vertices.push_back(j);
117 422 parents_neighbours[j] = {num_neighbours[vert], vert};
118
119 }
120 // choose parent with most neighbours
121
2/2
✓ Branch 2 taken 2 times.
✓ Branch 3 taken 6 times.
2/2
✓ Decision 'true' taken 2 times.
✓ Decision 'false' taken 6 times.
 8 else if (parents_neighbours[j].first < num_neighbours[vert]) {
122 2 parents_neighbours[j] = {num_neighbours[vert], vert};
123 }
124 }
125 }
126 }
127 277 current_layer_vertices.clear();
128 // add in edges
129
2/2
✓ Branch 4 taken 422 times.
✓ Branch 5 taken 277 times.
2/2
✓ Decision 'true' taken 422 times.
✓ Decision 'false' taken 277 times.
 699 for (unsigned vert : next_layer_vertices) {
130 422 unsigned parent_vertex = parents_neighbours[vert].second;
131
1/2
✓ Branch 1 taken 422 times.
✗ Branch 2 not taken.
 422 acyclic_connectivity(vert, parent_vertex) = 1;
132
1/2
✓ Branch 1 taken 422 times.
✗ Branch 2 not taken.
 422 acyclic_connectivity(parent_vertex, vert) = 1;
133
134
1/2
✓ Branch 1 taken 422 times.
✗ Branch 2 not taken.
 422 current_layer_vertices.push_back(vert);
135
1/2
✓ Branch 1 taken 422 times.
✗ Branch 2 not taken.
 422 vertices_in_tree[vert] = 1;
136 422 parents_neighbours[vert] = {};
137 }
138 277 next_layer_vertices.clear();
139 }
140
141
1/2
✓ Branch 1 taken 88 times.
✗ Branch 2 not taken.
 176 return PathHandler(acyclic_connectivity);
142 88 }
143
144 3 std::list<unsigned> PathHandler::find_path(unsigned i, unsigned j) {
145
1/2
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
 3 std::list<unsigned> path{i};
146
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 3 times.
2/2
✓ Decision 'true' taken 4 times.
✓ Decision 'false' taken 3 times.
 7 while (i != j) {
147
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 i = path_matrix_(i, j);
148
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 path.push_back(i);
149 }
150 3 return path;
151 }
152
153 13 std::vector<Node> find_hampath(const Architecture &arch, long timeout) {
154 13 unsigned n_nodes = arch.n_nodes();
155 13 std::vector<Qubit> arch_qubits;
156
2/2
✓ Branch 0 taken 97 times.
✓ Branch 1 taken 13 times.
2/2
✓ Decision 'true' taken 97 times.
✓ Decision 'false' taken 13 times.
 110 for (unsigned i = 0; i < n_nodes; i++) {
157
2/4
✓ Branch 1 taken 97 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 97 times.
✗ Branch 5 not taken.
 97 arch_qubits.push_back(Qubit(i));
158 }
159
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 QubitGraph q_graph(arch_qubits);
160
2/2
✓ Branch 0 taken 84 times.
✓ Branch 1 taken 13 times.
2/2
✓ Decision 'true' taken 84 times.
✓ Decision 'false' taken 13 times.
 97 for (unsigned i = 0; i != n_nodes - 1; ++i) {
161
3/6
✓ Branch 1 taken 84 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 84 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 84 times.
✗ Branch 8 not taken.
 84 q_graph.add_connection(Qubit(i), Qubit(i + 1));
162 }
163
164 Architecture::UndirectedConnGraph undirected_target =
165
2/4
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 13 times.
✗ Branch 5 not taken.
 13 arch.get_undirected_connectivity();
166 QubitGraph::UndirectedConnGraph undirected_pattern =
167
2/4
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 13 times.
✗ Branch 5 not taken.
 13 q_graph.get_undirected_connectivity();
168 std::vector<qubit_bimap_t> all_maps = get_unweighted_subgraph_monomorphisms(
169
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 undirected_pattern, undirected_target, 1, timeout);
170
171 /* Architecture has no hampath, sad. */
172
2/2
✓ Branch 1 taken 3 times.
✓ Branch 2 taken 10 times.
2/2
✓ Decision 'true' taken 3 times.
✓ Decision 'false' taken 10 times.
 13 if (all_maps.empty()) {
173
2/4
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 3 times.
✗ Branch 6 not taken.
 3 throw NoHamiltonPath(
174 "[AAS]: no Hamilton path found in the given architecture, CNOT "
175 6 "synthesis stopped. Please try an alternative CNotSynthType.");
176 }
177
178 /* Left: line, Right: input architecture. */
179 10 const qubit_bimap_t &qmap = all_maps[0];
180 10 std::vector<Node> hampath;
181
6/10
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 72 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 82 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 82 times.
✗ Branch 11 not taken.
✓ Branch 12 taken 72 times.
✓ Branch 13 taken 10 times.
0/1
? Decision couldn't be analyzed.
 82 for (l_const_iterator_t it = qmap.left.begin(); it != qmap.left.end(); ++it) {
182
2/4
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 72 times.
✗ Branch 5 not taken.
 72 hampath.push_back(it->second);
183 }
184 20 return hampath;
185 25 }
186
187 80 IterationOrder::IterationOrder(const Architecture &arch) {
188 80 std::set<Node> visited_nodes;
189
190 80 Node no = *arch.nodes().begin();
191
192
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 iterationorder.push_back(no);
193
1/2
✓ Branch 1 taken 80 times.
✗ Branch 2 not taken.
 80 visited_nodes.insert(no);
194
195 80 unsigned whilecount = 0;
196
5/6
✓ Branch 2 taken 97 times.
✓ Branch 3 taken 80 times.
✓ Branch 4 taken 97 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 97 times.
✓ Branch 7 taken 80 times.
0/1
? Decision couldn't be analyzed.
 274 while ((visited_nodes.size() < arch.n_nodes()) &&
197 97 (whilecount < arch.n_nodes())) {
198
3/4
✓ Branch 1 taken 97 times.
✗ Branch 2 not taken.
✓ Branch 9 taken 502 times.
✓ Branch 10 taken 97 times.
0/1
? Decision couldn't be analyzed.
 599 for (auto edge : arch.get_all_edges_vec()) {
199
5/6
✓ Branch 1 taken 502 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 443 times.
✓ Branch 4 taken 59 times.
✓ Branch 5 taken 349 times.
✓ Branch 6 taken 153 times.
2/2
✓ Decision 'true' taken 349 times.
✓ Decision 'false' taken 596 times.
 945 if (visited_nodes.count(edge.first) &&
200
3/4
✓ Branch 1 taken 443 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 349 times.
✓ Branch 4 taken 94 times.
 443 (!visited_nodes.count(edge.second))) {
201
1/2
✓ Branch 1 taken 349 times.
✗ Branch 2 not taken.
 349 iterationorder.push_back(edge.second);
202
1/2
✓ Branch 1 taken 349 times.
✗ Branch 2 not taken.
 349 visited_nodes.insert(edge.second);
203
1/2
✓ Branch 1 taken 349 times.
✗ Branch 2 not taken.
 349 edgelist.push_back(edge);
204 153 } else if (
205
5/6
✓ Branch 1 taken 153 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 59 times.
✓ Branch 4 taken 94 times.
✓ Branch 5 taken 30 times.
✓ Branch 6 taken 123 times.
 212 (!visited_nodes.count(edge.first)) &&
206
3/4
✓ Branch 1 taken 59 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 30 times.
✓ Branch 4 taken 29 times.
 59 (visited_nodes.count(edge.second))) {
207
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 iterationorder.push_back(edge.first);
208
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 visited_nodes.insert(edge.first);
209
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 edgelist.push_back(edge);
210 }
211 599 }
212 97 ++whilecount;
213 }
214
215
1/2
✗ Branch 2 not taken.
✓ Branch 3 taken 80 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 80 times.
 80 if (visited_nodes.size() != arch.n_nodes()) {
216 ✗ throw std::logic_error("Unconnected architecture");
217 }
218
219
1/2
✓ Branch 3 taken 80 times.
✗ Branch 4 not taken.
 80 std::reverse(iterationorder.begin(), iterationorder.end());
220 80 }
221
222 28194 MatrixXb PathHandler::get_connectivity_matrix() const {
223 28194 return connectivity_matrix_;
224 }
225
226 15225 MatrixXu PathHandler::get_distance_matrix() const { return distance_matrix_; }
227
228 3208 MatrixXu PathHandler::get_path_matrix() const { return path_matrix_; }
229
230 5386 unsigned PathHandler::get_size() const { return size; }
231
232 } // namespace aas
233 } // namespace tket
234