GCC Code Coverage Report

Directory: ./
File: Mapping/LexicographicalComparison.cpp
Date: 2022-10-15 05:10:18
Exec Total Coverage
Lines: 61 61 100.0%
Functions: 5 5 100.0%
Branches: 63 98 64.3%
Decisions: 23 24 95.8%
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/LexicographicalComparison.hpp"
16
17 namespace tket {
18
19 22436 LexicographicalComparison::LexicographicalComparison(
20 const ArchitecturePtr& _architecture,
21 22436 const interacting_nodes_t& _interacting_nodes)
22
1/2
✓ Branch 3 taken 22436 times.
✗ Branch 4 not taken.
 22436 : architecture_(_architecture), interacting_nodes_(_interacting_nodes) {
23
1/2
✓ Branch 2 taken 22436 times.
✗ Branch 3 not taken.
 22436 unsigned diameter = this->architecture_->get_diameter();
24
25
1/2
✓ Branch 2 taken 22436 times.
✗ Branch 3 not taken.
 22436 lexicographical_distances_t distance_vector(diameter, 0);
26
2/2
✓ Branch 5 taken 57175 times.
✓ Branch 6 taken 22435 times.
2/2
✓ Decision 'true' taken 57175 times.
✓ Decision 'false' taken 22435 times.
 79610 for (const auto& interaction : this->interacting_nodes_) {
27 // If Node not in architecture, don't add
28
4/6
✓ Branch 2 taken 57175 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 57175 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 1 times.
✓ Branch 7 taken 57174 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 114349 times.
 114350 if (!this->architecture_->node_exists(interaction.first) ||
29
3/4
✓ Branch 2 taken 57175 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 1 times.
✓ Branch 5 taken 57174 times.
 57175 !this->architecture_->node_exists(interaction.second)) {
30
2/4
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 1 times.
✗ Branch 6 not taken.
 1 throw LexicographicalComparisonError(
31 2 "Constructor passed some interacting node not in architecture.");
32 }
33 // key->value already copied, assign reverse to map for later ease
34
1/2
✓ Branch 1 taken 57174 times.
✗ Branch 2 not taken.
 57174 this->interacting_nodes_[interaction.second] = interaction.first;
35 57174 unsigned distance = this->architecture_->get_distance(
36
1/2
✓ Branch 1 taken 57174 times.
✗ Branch 2 not taken.
 57174 interaction.first, interaction.second);
37
1/2
✓ Branch 0 taken 57174 times.
✗ Branch 1 not taken.
1/2
✓ Decision 'true' taken 57174 times.
✗ Decision 'false' not taken.
 57174 if (distance > 0) {
38 57174 ++distance_vector[diameter - distance];
39 }
40 }
41
1/2
✓ Branch 1 taken 22435 times.
✗ Branch 2 not taken.
 22435 this->lexicographical_distances = distance_vector;
42 22439 }
43
44 131057 void LexicographicalComparison::increment_distances(
45 lexicographical_distances_t& distances,
46 const std::pair<Node, Node>& interaction, int increment) const {
47 const unsigned distances_index =
48 131057 this->architecture_->get_diameter() -
49 131057 this->architecture_->get_distance(interaction.first, interaction.second);
50
6/6
✓ Branch 1 taken 61348 times.
✓ Branch 2 taken 69709 times.
✓ Branch 3 taken 1 times.
✓ Branch 4 taken 61347 times.
✓ Branch 5 taken 1 times.
✓ Branch 6 taken 131056 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 131056 times.
 131057 if (distances[distances_index] == 0 && increment < 0) {
51
2/4
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 1 times.
✗ Branch 6 not taken.
 1 throw LexicographicalComparisonError(
52 "Negative increment value is larger than value held at index, "
53 2 "modification not allowed.");
54 }
55 131056 distances[distances_index] += increment;
56 131056 }
57
58 /**
59 * getter
60 */
61 lexicographical_distances_t
62 4 LexicographicalComparison::get_lexicographical_distances() const {
63 4 return this->lexicographical_distances;
64 }
65
66 /**
67 * get_updated_distances
68 * updates the "distance vector" (this->lexicographical_distances) to reflect
69 * the distance between interacting logical qubits given that the logical qubits
70 * present in "swap" have swapped physical qubits (Node)
71 */
72 75159 lexicographical_distances_t LexicographicalComparison::get_updated_distances(
73 const swap_t& swap) const {
74 // make a copy of base lexicographical distances
75
1/2
✓ Branch 1 taken 75159 times.
✗ Branch 2 not taken.
 75159 lexicographical_distances_t copy = this->lexicographical_distances;
76
3/4
✓ Branch 1 taken 75159 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 4423 times.
✓ Branch 4 taken 70736 times.
2/2
✓ Decision 'true' taken 4423 times.
✓ Decision 'false' taken 70736 times.
 75159 if (swap.first == swap.second) {
77 4423 return copy;
78 }
79
1/2
✓ Branch 1 taken 70736 times.
✗ Branch 2 not taken.
 70736 auto iq_it = this->interacting_nodes_.find(swap.first);
80 // first condition => first node not interacting with self, so update
81 // distances
82
2/2
✓ Branch 2 taken 62071 times.
✓ Branch 3 taken 8665 times.
2/2
✓ Decision 'true' taken 62071 times.
✓ Decision 'false' taken 8665 times.
 70736 if (iq_it != this->interacting_nodes_.end()) {
83 // update distances due to first swap node and qubit its interating with
84 // (assuming swap)
85 62071 Node interacting = iq_it->second;
86
3/4
✓ Branch 1 taken 62071 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 61498 times.
✓ Branch 4 taken 573 times.
2/2
✓ Decision 'true' taken 61498 times.
✓ Decision 'false' taken 573 times.
 62071 if (interacting != swap.second) {
87
1/2
✓ Branch 2 taken 61498 times.
✗ Branch 3 not taken.
 61498 increment_distances(copy, {swap.first, interacting}, -2);
88 // updates distances due to second swap node and qubit first is
89 // interacting with
90
1/2
✓ Branch 2 taken 61498 times.
✗ Branch 3 not taken.
 61498 increment_distances(copy, {swap.second, interacting}, 2);
91 }
92 62071 }
93
1/2
✓ Branch 1 taken 70736 times.
✗ Branch 2 not taken.
 70736 iq_it = this->interacting_nodes_.find(swap.second);
94 // => second node not interacting with self
95
2/2
✓ Branch 2 taken 4602 times.
✓ Branch 3 taken 66134 times.
2/2
✓ Decision 'true' taken 4602 times.
✓ Decision 'false' taken 66134 times.
 70736 if (iq_it != this->interacting_nodes_.end()) {
96 4602 Node interacting = iq_it->second;
97
3/4
✓ Branch 1 taken 4602 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 4029 times.
✓ Branch 4 taken 573 times.
2/2
✓ Decision 'true' taken 4029 times.
✓ Decision 'false' taken 573 times.
 4602 if (interacting != swap.first) {
98 // update distances due to second node and qubit its interacting with
99
1/2
✓ Branch 2 taken 4029 times.
✗ Branch 3 not taken.
 4029 increment_distances(copy, {swap.second, interacting}, -2);
100 // update distannces due to frist node and qubit second node is
101 // interacting with
102
1/2
✓ Branch 2 taken 4029 times.
✗ Branch 3 not taken.
 4029 increment_distances(copy, {swap.first, interacting}, 2);
103 }
104 4602 }
105 70736 return copy;
106 }
107
108 /**
109 * remove_swaps_lexicographical
110 * value x at index i of this->lexicographical_distancs => x logical qubits
111 * distance (diameter - i) away from the logical qubit they should be
112 * interacting with For each swap (swap_t) in "candidate_swaps" a
113 * new distances object is created given interacting_qubits Each distance for
114 * each swap is lexicographically compared If a distance is lexicographically
115 * larger than any other its corresponding swap is removed from candidate_swaps
116 * Therefore swaps remaining in candidate_swaps after this process are
117 * lexicographically identical for implied logical->physical qubit mapping and
118 * interacting logical
119 */
120 22428 void LexicographicalComparison::remove_swaps_lexicographical(
121 swap_set_t& candidate_swaps) const {
122 22428 auto it = candidate_swaps.begin();
123 lexicographical_distances_t winning_distances =
124
1/2
✓ Branch 2 taken 22428 times.
✗ Branch 3 not taken.
 22428 this->get_updated_distances(*it);
125
1/2
✓ Branch 4 taken 22428 times.
✗ Branch 5 not taken.
 67284 swap_set_t preserved_swaps = {*it};
126 22428 ++it;
127
2/2
✓ Branch 3 taken 52722 times.
✓ Branch 4 taken 22428 times.
2/2
✓ Decision 'true' taken 52722 times.
✓ Decision 'false' taken 22428 times.
 75150 for (; it != candidate_swaps.end(); ++it) {
128 lexicographical_distances_t comparison_distances =
129
1/2
✓ Branch 2 taken 52722 times.
✗ Branch 3 not taken.
 52722 this->get_updated_distances(*it);
130
131
3/4
✓ Branch 2 taken 52722 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 4172 times.
✓ Branch 6 taken 48550 times.
2/2
✓ Decision 'true' taken 8344 times.
✓ Decision 'false' taken 44378 times.
 52722 if (comparison_distances < winning_distances) {
132
3/6
✓ Branch 3 taken 4172 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 4172 times.
✓ Branch 6 taken 4172 times.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
 8344 preserved_swaps = {*it};
133
1/2
✓ Branch 1 taken 4172 times.
✗ Branch 2 not taken.
 4172 winning_distances = comparison_distances;
134
3/4
✓ Branch 1 taken 48550 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 35995 times.
✓ Branch 4 taken 12555 times.
2/2
✓ Decision 'true' taken 35995 times.
✓ Decision 'false' taken 12555 times.
 48550 } else if (comparison_distances == winning_distances) {
135
1/2
✓ Branch 2 taken 35995 times.
✗ Branch 3 not taken.
 35995 preserved_swaps.insert(*it);
136 }
137 52722 }
138
1/2
✓ Branch 1 taken 22428 times.
✗ Branch 2 not taken.
 22428 candidate_swaps = preserved_swaps;
139 22428 }
140 } // namespace tket
141