| 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 "Cycles.hpp" | |||
| 16 | ||||
| 17 | #include <numeric> | |||
| 18 | ||||
| 19 | namespace tket { | |||
| 20 | ||||
| 21 | class CycleError : public std::logic_error { | |||
| 22 | public: | |||
| 23 | ✗ | explicit CycleError(const std::string& message) : std::logic_error(message) {} | ||
| 24 | }; | |||
| 25 | ||||
| 26 | 854 | unsigned Cycle::size() const { return boundary_edges_.size(); } | ||
| 27 | ||||
| 28 | 44 | void Cycle::add_vertex_pair(const std::pair<Vertex, Vertex>& verts) { | ||
| 29 | 44 | frame_vertices.push_back(verts); | ||
| 30 | 44 | } | ||
| 31 | ||||
| 32 | 778 | std::vector<std::pair<Vertex, Vertex>> Cycle::get_frame() const { | ||
| 33 | 778 | return frame_vertices; | ||
| 34 | } | |||
| 35 | ||||
| 36 | 461 | UnitID CycleFinder::unitid_from_unit_frontier( | ||
| 37 | const std::shared_ptr<unit_frontier_t>& u_frontier, const Edge& e) const { | |||
| 38 |
4/8✓ Branch 5 taken 898 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 437 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 898 times.
✗ Branch 12 not taken.
✓ Branch 13 taken 898 times.
✗ Branch 14 not taken.
|
0/1? Decision couldn't be analyzed.
|
898 | for (const std::pair<UnitID, Edge>& pair : u_frontier->get<TagKey>()) { |
| 39 |
3/4✓ Branch 1 taken 898 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 461 times.
✓ Branch 4 taken 437 times.
|
2/2✓ Decision 'true' taken 461 times.
✓ Decision 'false' taken 437 times.
|
898 | if (pair.second == e) { |
| 40 | 461 | return pair.first; | ||
| 41 | } | |||
| 42 | } | |||
| 43 | ✗ | throw CycleError(std::string("Edge not in unit_frontier_t object.")); | ||
| 44 | } | |||
| 45 | ||||
| 46 | 461 | void CycleFinder::update_cycle_out_edges(const UnitID& uid, const Edge& e) { | ||
| 47 |
1/2✓ Branch 5 taken 976 times.
✗ Branch 6 not taken.
|
1/2✓ Decision 'true' taken 976 times.
✗ Decision 'false' not taken.
|
976 | for (std::pair<const Edge, UnitID>& pair : cycle_out_edges) { |
| 48 |
3/4✓ Branch 1 taken 976 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 461 times.
✓ Branch 4 taken 515 times.
|
2/2✓ Decision 'true' taken 461 times.
✓ Decision 'false' taken 515 times.
|
976 | if (pair.second == uid) { |
| 49 |
1/2✓ Branch 1 taken 461 times.
✗ Branch 2 not taken.
|
461 | cycle_out_edges.erase(pair.first); | |
| 50 |
1/2✓ Branch 1 taken 461 times.
✗ Branch 2 not taken.
|
461 | cycle_out_edges[e] = uid; | |
| 51 | 461 | return; | ||
| 52 | } | |||
| 53 | } | |||
| 54 | ✗ | throw CycleError(std::string( | ||
| 55 | ✗ | "UnitID " + uid.repr() + " not in std::map<Edge, UnitID> object.")); | ||
| 56 | return; | |||
| 57 | } | |||
| 58 | ||||
| 59 | ✗ | void Cycle::update_boundary( | ||
| 60 | const Edge& source_edge, const Edge& replacement_edge) { | |||
| 61 |
0/2✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
|
✗ | for (unsigned i = 0; i < boundary_edges_.size(); i++) { | |
| 62 |
0/2✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
|
✗ | if (boundary_edges_[i].second == source_edge) { | |
| 63 | ✗ | boundary_edges_[i].second = replacement_edge; | ||
| 64 | ✗ | return; | ||
| 65 | } | |||
| 66 | } | |||
| 67 | ✗ | throw CycleError("Source Edge matches no edges in boundary to cycle."); | ||
| 68 | return; | |||
| 69 | } | |||
| 70 | ||||
| 71 | 154 | void CycleFinder::erase_keys( | ||
| 72 | const unsigned& to_erase, std::set<unsigned>& erase_from) const { | |||
| 73 | 154 | std::set<unsigned> all_erased; | ||
| 74 |
2/2✓ Branch 5 taken 155 times.
✓ Branch 6 taken 154 times.
|
2/2✓ Decision 'true' taken 155 times.
✓ Decision 'false' taken 154 times.
|
309 | for (const unsigned& key : erase_from) { |
| 75 |
2/2✓ Branch 0 taken 154 times.
✓ Branch 1 taken 1 times.
|
2/2✓ Decision 'true' taken 154 times.
✓ Decision 'false' taken 1 times.
|
155 | if (key <= to_erase) { |
| 76 |
1/2✓ Branch 1 taken 154 times.
✗ Branch 2 not taken.
|
154 | all_erased.insert(key); | |
| 77 | } | |||
| 78 | } | |||
| 79 |
3/4✓ Branch 4 taken 154 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 154 times.
✓ Branch 9 taken 154 times.
|
0/1? Decision couldn't be analyzed.
|
308 | for (const unsigned& key : all_erased) erase_from.erase(key); |
| 80 | 154 | } | ||
| 81 | ||||
| 82 | // Adds a new cycle to bt.key_to_cycle | |||
| 83 | 323 | std::pair<unsigned, std::set<unsigned>> CycleFinder::make_cycle( | ||
| 84 | const Vertex& v, const EdgeVec& out_edges, const CutFrontier& cut) { | |||
| 85 | // Make a new boundary, add it to "all_boundaries", update "boundary_key" map | |||
| 86 | 323 | std::vector<edge_pair_t> new_cycle_boundary; | ||
| 87 | 323 | std::vector<UnitID> new_boundary_uids; | ||
| 88 | 323 | std::set<unsigned> old_boundary_keys; | ||
| 89 | 323 | std::set<unsigned> banned_keys; | ||
| 90 | ||||
| 91 | // Get UnitID, add to uids for new boundary, keep note of all old boundary | |||
| 92 | // keys for merging set new boundary key, add new edges to new boundary update | |||
| 93 | // cycle out edges if the edge can't be found | |||
| 94 |
2/2✓ Branch 5 taken 461 times.
✓ Branch 6 taken 323 times.
|
2/2✓ Decision 'true' taken 461 times.
✓ Decision 'false' taken 323 times.
|
784 | for (const Edge& e : out_edges) { |
| 95 |
1/2✓ Branch 1 taken 461 times.
✗ Branch 2 not taken.
|
461 | UnitID uid = unitid_from_unit_frontier(cut.u_frontier, e); | |
| 96 |
1/2✓ Branch 1 taken 461 times.
✗ Branch 2 not taken.
|
461 | new_boundary_uids.push_back(uid); | |
| 97 |
2/4✓ Branch 1 taken 461 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 461 times.
✗ Branch 5 not taken.
|
461 | old_boundary_keys.insert(bt.uid_to_key[uid]); | |
| 98 | ||||
| 99 | // boundary key associated with given edge e not included | |||
| 100 | // i.e. e's associated in edge isn't a cycle out edge | |||
| 101 | // i.e. some other non-cycle gate has been passed | |||
| 102 |
2/4✓ Branch 1 taken 461 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 461 times.
✗ Branch 5 not taken.
|
2/2✓ Decision 'true' taken 155 times.
✓ Decision 'false' taken 306 times.
|
461 | if (cycle_out_edges.find(circ.get_last_edge(v, e)) == |
| 103 |
2/2✓ Branch 1 taken 155 times.
✓ Branch 2 taken 306 times.
|
922 | cycle_out_edges.end()) { | |
| 104 |
2/4✓ Branch 1 taken 155 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 155 times.
✗ Branch 5 not taken.
|
155 | banned_keys.insert(bt.uid_to_key[uid]); | |
| 105 | } | |||
| 106 |
1/2✓ Branch 1 taken 461 times.
✗ Branch 2 not taken.
|
461 | bt.uid_to_key[uid] = bt.key; | |
| 107 |
2/4✓ Branch 1 taken 461 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 461 times.
✗ Branch 6 not taken.
|
461 | new_cycle_boundary.push_back({circ.get_last_edge(v, e), e}); | |
| 108 |
1/2✓ Branch 1 taken 461 times.
✗ Branch 2 not taken.
|
461 | update_cycle_out_edges(uid, e); | |
| 109 | 461 | } | ||
| 110 | ||||
| 111 |
1/2✓ Branch 3 taken 323 times.
✗ Branch 4 not taken.
|
323 | std::vector<unsigned> op_indices(out_edges.size()); | |
| 112 | 323 | std::iota(op_indices.begin(), op_indices.end(), 0); | ||
| 113 | // Edges in port ordering | |||
| 114 | Cycle new_cycle( | |||
| 115 |
4/8✓ Branch 1 taken 323 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 323 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 323 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 323 times.
✗ Branch 12 not taken.
|
969 | new_cycle_boundary, {{circ.get_OpType_from_Vertex(v), op_indices, v}}); | |
| 116 |
2/4✓ Branch 1 taken 323 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 323 times.
✗ Branch 5 not taken.
|
323 | bt.key_to_cycle[bt.key] = {new_cycle}; | |
| 117 | ||||
| 118 |
1/2✓ Branch 1 taken 323 times.
✗ Branch 2 not taken.
|
323 | bt.history.push_back(new_boundary_uids); | |
| 119 |
2/2✓ Branch 5 taken 154 times.
✓ Branch 6 taken 323 times.
|
2/2✓ Decision 'true' taken 154 times.
✓ Decision 'false' taken 323 times.
|
477 | for (const unsigned& key : banned_keys) { |
| 120 |
1/2✓ Branch 1 taken 154 times.
✗ Branch 2 not taken.
|
154 | erase_keys(key, old_boundary_keys); | |
| 121 | } | |||
| 122 | std::pair<unsigned, std::set<unsigned>> return_keys = { | |||
| 123 |
1/2✓ Branch 1 taken 323 times.
✗ Branch 2 not taken.
|
323 | bt.key, old_boundary_keys}; | |
| 124 | 323 | bt.key++; | ||
| 125 | 646 | return return_keys; | ||
| 126 | 323 | } | ||
| 127 | ||||
| 128 | // "old_keys" returned gives keys for boundaries to be merged together | |||
| 129 | // these "old_keys" are keys corresponding to boundaries UnitIDs in new boundary | |||
| 130 | // were in previously if two keys in passed old_keys have overlapping UnitIDs, | |||
| 131 | // then they cannot be merged in this case, remove the 'earlier' boundary from | |||
| 132 | // keys to be merged | |||
| 133 | 170 | void CycleFinder::order_keys( | ||
| 134 | unsigned& new_key, std::set<unsigned>& old_keys) const { | |||
| 135 | 170 | std::set<unsigned> bad_keys; | ||
| 136 |
2/2✓ Branch 3 taken 300 times.
✓ Branch 4 taken 170 times.
|
2/2✓ Decision 'true' taken 300 times.
✓ Decision 'false' taken 170 times.
|
470 | for (std::set<unsigned>::iterator it = old_keys.begin(); it != old_keys.end(); |
| 137 | 300 | ++it) { | ||
| 138 | 300 | std::set<unsigned>::iterator jt = it; | ||
| 139 |
1/2✓ Branch 1 taken 300 times.
✗ Branch 2 not taken.
|
300 | std::advance(jt, 1); | |
| 140 | // if either std::vector<UnitID> has common UnitIDs then one is causally | |||
| 141 | // blocked. remove smaller key from keys from set as not a candidate for | |||
| 142 | // merging into | |||
| 143 |
2/2✓ Branch 3 taken 130 times.
✓ Branch 4 taken 300 times.
|
2/2✓ Decision 'true' taken 130 times.
✓ Decision 'false' taken 300 times.
|
430 | for (; jt != old_keys.end(); ++jt) |
| 144 |
2/2✓ Branch 7 taken 391 times.
✓ Branch 8 taken 130 times.
|
2/2✓ Decision 'true' taken 391 times.
✓ Decision 'false' taken 130 times.
|
521 | for (const UnitID& u0 : bt.history[*it]) |
| 145 |
2/2✓ Branch 7 taken 415 times.
✓ Branch 8 taken 391 times.
|
2/2✓ Decision 'true' taken 415 times.
✓ Decision 'false' taken 391 times.
|
806 | for (const UnitID& u1 : bt.history[*jt]) |
| 146 |
2/4✓ Branch 1 taken 415 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 415 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 415 times.
|
415 | if (u0 == u1) { |
| 147 | ✗ | bad_keys.insert(*it); | ||
| 148 | ✗ | goto new_loop; | ||
| 149 | } | |||
| 150 | ||||
| 151 | 300 | new_loop : {} | ||
| 152 | } | |||
| 153 | ||||
| 154 |
1/4✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 170 times.
|
0/1? Decision couldn't be analyzed.
|
170 | for (const unsigned& key : bad_keys) old_keys.erase(key); |
| 155 |
1/2✓ Branch 1 taken 170 times.
✗ Branch 2 not taken.
|
170 | old_keys.insert(new_key); | |
| 156 | 170 | } | ||
| 157 | ||||
| 158 | 300 | void Cycle::update_coms_indices( | ||
| 159 | const std::map<unsigned, unsigned>& new_indices) { | |||
| 160 |
2/2✓ Branch 5 taken 306 times.
✓ Branch 6 taken 300 times.
|
2/2✓ Decision 'true' taken 306 times.
✓ Decision 'false' taken 300 times.
|
606 | for (CycleCom& com : coms_) { |
| 161 |
2/2✓ Branch 4 taken 412 times.
✓ Branch 5 taken 306 times.
|
2/2✓ Decision 'true' taken 412 times.
✓ Decision 'false' taken 306 times.
|
718 | for (unsigned& index : com.indices) { |
| 162 |
1/2✓ Branch 1 taken 412 times.
✗ Branch 2 not taken.
|
412 | index = new_indices.at(index); | |
| 163 | } | |||
| 164 | } | |||
| 165 | 300 | } | ||
| 166 | ||||
| 167 | // new cycle is made | |||
| 168 | // it may need to be immediately merged into other cycles | |||
| 169 | // 1) check for overlap of UnitID between cycles of "old_keys" | |||
| 170 | // if overlap, remove lowest value key from set | |||
| 171 | // 2) add "new_key" to "old_keys", merge all boundaries into corresponding | |||
| 172 | // boundary to highest value "old_key" | |||
| 173 | 300 | void Cycle::merge(Cycle& new_cycle) { | ||
| 174 | // iterate through edges in boundary of new_cycle | |||
| 175 | 300 | std::map<unsigned, unsigned> new_indices; | ||
| 176 |
2/2✓ Branch 1 taken 436 times.
✓ Branch 2 taken 300 times.
|
2/2✓ Decision 'true' taken 436 times.
✓ Decision 'false' taken 300 times.
|
736 | for (unsigned i = 0; i < new_cycle.boundary_edges_.size(); i++) { |
| 177 | 436 | bool match = false; | ||
| 178 |
2/2✓ Branch 1 taken 838 times.
✓ Branch 2 taken 131 times.
|
2/2✓ Decision 'true' taken 838 times.
✓ Decision 'false' taken 131 times.
|
969 | for (unsigned j = 0; j < boundary_edges_.size(); j++) { |
| 179 | // if in edge of boundary of new_cycle matches out of edge *this, update | |||
| 180 | // *this out edge | |||
| 181 |
3/4✓ Branch 3 taken 838 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 305 times.
✓ Branch 6 taken 533 times.
|
2/2✓ Decision 'true' taken 305 times.
✓ Decision 'false' taken 533 times.
|
838 | if (boundary_edges_[j].second == new_cycle.boundary_edges_[i].first) { |
| 182 | 305 | boundary_edges_[j].second = new_cycle.boundary_edges_[i].second; | ||
| 183 | // As CycleCom are labelled by basic indexing system, where indexing is | |||
| 184 | // related to position edge has in boundary Update CycleCom in new_cycle | |||
| 185 | // s.t. edges with index i now have index j update commands in new_cycle | |||
| 186 | // to match edgesindexing of *this for now, store new indexing | |||
| 187 |
1/2✓ Branch 1 taken 305 times.
✗ Branch 2 not taken.
|
305 | new_indices[i] = j; | |
| 188 | 305 | match = true; | ||
| 189 | 305 | break; | ||
| 190 | } | |||
| 191 | } | |||
| 192 |
2/2✓ Branch 0 taken 131 times.
✓ Branch 1 taken 305 times.
|
2/2✓ Decision 'true' taken 131 times.
✓ Decision 'false' taken 305 times.
|
436 | if (!match) { |
| 193 |
1/2✓ Branch 2 taken 131 times.
✗ Branch 3 not taken.
|
131 | boundary_edges_.push_back(new_cycle.boundary_edges_[i]); | |
| 194 |
1/2✓ Branch 2 taken 131 times.
✗ Branch 3 not taken.
|
131 | new_indices[i] = boundary_edges_.size() - 1; | |
| 195 | } | |||
| 196 | } | |||
| 197 | // update CycleCom indices in new_cycle | |||
| 198 |
1/2✓ Branch 1 taken 300 times.
✗ Branch 2 not taken.
|
300 | new_cycle.update_coms_indices(new_indices); | |
| 199 |
1/2✓ Branch 5 taken 300 times.
✗ Branch 6 not taken.
|
300 | coms_.insert(coms_.end(), new_cycle.coms_.begin(), new_cycle.coms_.end()); | |
| 200 | 300 | } | ||
| 201 | ||||
| 202 | 170 | void CycleFinder::merge_cycles(unsigned new_key, std::set<unsigned>& old_keys) { | ||
| 203 | // boundary_keys is a std::set<unsigned> so is ordered | |||
| 204 |
1/2✓ Branch 1 taken 170 times.
✗ Branch 2 not taken.
|
170 | order_keys(new_key, old_keys); | |
| 205 | // all cycles corresponding to keys in boundary_keys should be merged into | |||
| 206 | // boundary with smallest value | |||
| 207 | 170 | std::set<unsigned>::iterator it = old_keys.begin(); | ||
| 208 | 170 | unsigned base_key = *it; | ||
| 209 |
1/2✓ Branch 1 taken 170 times.
✗ Branch 2 not taken.
|
170 | std::advance(it, 1); | |
| 210 |
2/2✓ Branch 3 taken 300 times.
✓ Branch 4 taken 170 times.
|
2/2✓ Decision 'true' taken 300 times.
✓ Decision 'false' taken 170 times.
|
470 | for (; it != old_keys.end(); ++it) { |
| 211 | 300 | unsigned merge_key = *it; | ||
| 212 |
3/6✓ Branch 1 taken 300 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 300 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 300 times.
✗ Branch 8 not taken.
|
300 | bt.key_to_cycle[base_key].merge(bt.key_to_cycle[merge_key]); | |
| 213 |
1/2✓ Branch 1 taken 300 times.
✗ Branch 2 not taken.
|
300 | bt.key_to_cycle.erase(merge_key); | |
| 214 | // update bt.history for "base_key" | |||
| 215 |
2/2✓ Branch 6 taken 442 times.
✓ Branch 7 taken 300 times.
|
2/2✓ Decision 'true' taken 442 times.
✓ Decision 'false' taken 300 times.
|
742 | for (const UnitID& u0 : bt.history[merge_key]) { |
| 216 |
1/2✓ Branch 1 taken 442 times.
✗ Branch 2 not taken.
|
442 | bt.uid_to_key[u0] = base_key; | |
| 217 |
2/2✓ Branch 6 taken 1338 times.
✓ Branch 7 taken 131 times.
|
2/2✓ Decision 'true' taken 1338 times.
✓ Decision 'false' taken 131 times.
|
1469 | for (const UnitID& u1 : bt.history[base_key]) |
| 218 |
3/4✓ Branch 1 taken 1338 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 311 times.
✓ Branch 4 taken 1027 times.
|
2/2✓ Decision 'true' taken 442 times.
✓ Decision 'false' taken 896 times.
|
1338 | if (u0 == u1) break; |
| 219 |
1/2✓ Branch 2 taken 442 times.
✗ Branch 3 not taken.
|
442 | bt.history[base_key].push_back(u0); | |
| 220 | } | |||
| 221 | } | |||
| 222 | 170 | } | ||
| 223 | ||||
| 224 | 204 | void CycleFinder::extend_cycles(const CutFrontier& cut) { | ||
| 225 | // For each vertex in slice | |||
| 226 | // Make a new "cycle" | |||
| 227 | // If any in edge to new cycle matches an out edge to a previous cycle, | |||
| 228 | // attempt to merge cycles together | |||
| 229 |
2/2✓ Branch 6 taken 323 times.
✓ Branch 7 taken 204 times.
|
2/2✓ Decision 'true' taken 323 times.
✓ Decision 'false' taken 204 times.
|
527 | for (const Vertex& v : *cut.slice) { |
| 230 |
1/2✓ Branch 1 taken 323 times.
✗ Branch 2 not taken.
|
323 | EdgeVec in_edges = circ.get_in_edges_of_type(v, EdgeType::Quantum); | |
| 231 |
1/2✓ Branch 1 taken 323 times.
✗ Branch 2 not taken.
|
323 | EdgeVec out_edges = circ.get_out_edges_of_type(v, EdgeType::Quantum); | |
| 232 | // Compare EdgeType::Quantum "in_edges" of vertex in slice to collection of | |||
| 233 | // out edges from "active" boundaries If an "in_edge" is not equivalent to | |||
| 234 | // an out edge from "active" boundary, implies vertex needs to start a new | |||
| 235 | // boundary | |||
| 236 | std::pair<unsigned, std::set<unsigned>> all_keys = | |||
| 237 |
1/2✓ Branch 1 taken 323 times.
✗ Branch 2 not taken.
|
323 | make_cycle(v, out_edges, cut); | |
| 238 |
2/2✓ Branch 1 taken 170 times.
✓ Branch 2 taken 153 times.
|
2/2✓ Decision 'true' taken 170 times.
✓ Decision 'false' taken 153 times.
|
323 | if (all_keys.second.size() > 0) { |
| 239 |
1/2✓ Branch 1 taken 170 times.
✗ Branch 2 not taken.
|
170 | merge_cycles(all_keys.first, all_keys.second); | |
| 240 | } | |||
| 241 | 323 | } | ||
| 242 | 204 | } | ||
| 243 | ||||
| 244 | 19 | std::vector<Cycle> CycleFinder::get_cycles() { | ||
| 245 | 923 | std::function<bool(Op_ptr)> skip_func = [&](Op_ptr op) { | ||
| 246 |
1/2✓ Branch 4 taken 923 times.
✗ Branch 5 not taken.
|
923 | return (cycle_types_.find(op->get_type()) == cycle_types_.end()); | |
| 247 | 19 | }; | ||
| 248 | ||||
| 249 |
1/2✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
|
19 | Circuit::SliceIterator slice_iter(circ, skip_func); | |
| 250 | 19 | bt.key = 0; | ||
| 251 | ||||
| 252 | // initialization | |||
| 253 |
2/4✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 19 times.
✗ Branch 6 not taken.
|
1/2✓ Decision 'true' taken 19 times.
✗ Decision 'false' not taken.
|
19 | if (!(*slice_iter).empty()) { |
| 254 | 19 | for (const std::pair<UnitID, Edge>& pair : | ||
| 255 |
5/8✓ Branch 5 taken 49 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 49 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 68 times.
✗ Branch 12 not taken.
✓ Branch 13 taken 49 times.
✓ Branch 14 taken 19 times.
|
87 | slice_iter.cut_.u_frontier->get<TagKey>()) { | |
| 256 | 49 | Edge in_edge = pair.second; | ||
| 257 |
2/4✓ Branch 1 taken 49 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 49 times.
✗ Branch 4 not taken.
|
1/2✓ Decision 'true' taken 49 times.
✗ Decision 'false' not taken.
|
49 | if (circ.get_edgetype(in_edge) != EdgeType::Classical) { |
| 258 |
1/2✓ Branch 1 taken 49 times.
✗ Branch 2 not taken.
|
49 | Vertex in_vert = circ.source(pair.second); | |
| 259 | ||||
| 260 | // if vertex is type from types, then vertex is in slice and need | |||
| 261 | // in_edge. else can ignore. | |||
| 262 |
2/4✓ Branch 1 taken 49 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 49 times.
✗ Branch 5 not taken.
|
2/2✓ Decision 'true' taken 36 times.
✓ Decision 'false' taken 13 times.
|
49 | if (cycle_types_.find(circ.get_OpType_from_Vertex(in_vert)) != |
| 263 |
2/2✓ Branch 2 taken 36 times.
✓ Branch 3 taken 13 times.
|
98 | cycle_types_.end()) { | |
| 264 |
1/2✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
|
36 | in_edge = circ.get_last_edge(in_vert, pair.second); | |
| 265 | } | |||
| 266 | ||||
| 267 |
1/2✓ Branch 2 taken 49 times.
✗ Branch 3 not taken.
|
49 | cycle_out_edges.insert({in_edge, pair.first}); | |
| 268 |
1/2✓ Branch 2 taken 49 times.
✗ Branch 3 not taken.
|
49 | bt.uid_to_key.insert({pair.first, bt.key}); | |
| 269 |
3/6✓ Branch 3 taken 49 times.
✗ Branch 4 not taken.
✓ Branch 8 taken 49 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 49 times.
✗ Branch 12 not taken.
|
147 | Cycle new_cycle({{in_edge, in_edge}}, {{}}); | |
| 270 |
2/4✓ Branch 1 taken 49 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 49 times.
✗ Branch 5 not taken.
|
49 | bt.key_to_cycle[bt.key] = new_cycle; | |
| 271 |
4/8✓ Branch 3 taken 49 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 49 times.
✗ Branch 7 not taken.
✓ Branch 10 taken 49 times.
✓ Branch 11 taken 49 times.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
|
98 | bt.history.push_back({pair.first}); | |
| 272 | 49 | bt.key++; | ||
| 273 | 49 | } | ||
| 274 | } | |||
| 275 | // extend cycles automatically merges cycles that can be merge due to | |||
| 276 | // overlapping multi-qubit gates | |||
| 277 |
1/2✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
|
19 | extend_cycles(slice_iter.cut_); | |
| 278 |
1/2✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
|
19 | cycle_out_edges = {}; | |
| 279 | 19 | for (const std::pair<UnitID, Edge>& pair : | ||
| 280 |
4/6✓ Branch 5 taken 49 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 68 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 49 times.
✓ Branch 11 taken 19 times.
|
87 | slice_iter.cut_.u_frontier->get<TagKey>()) { | |
| 281 |
2/4✓ Branch 2 taken 49 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 49 times.
✗ Branch 7 not taken.
|
49 | cycle_out_edges.insert({pair.second, pair.first}); | |
| 282 | } | |||
| 283 | } | |||
| 284 |
3/4✓ Branch 1 taken 205 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 186 times.
✓ Branch 4 taken 19 times.
|
0/1? Decision couldn't be analyzed.
|
205 | while (!slice_iter.finished()) { |
| 285 |
1/2✓ Branch 3 taken 186 times.
✗ Branch 4 not taken.
|
372 | slice_iter.cut_ = circ.next_cut( | |
| 286 | 186 | slice_iter.cut_.u_frontier, slice_iter.cut_.b_frontier, skip_func); | ||
| 287 |
3/4✓ Branch 1 taken 186 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 185 times.
✓ Branch 6 taken 1 times.
|
2/2✓ Decision 'true' taken 185 times.
✓ Decision 'false' taken 1 times.
|
186 | if (!(*slice_iter).empty()) { |
| 288 |
1/2✓ Branch 1 taken 185 times.
✗ Branch 2 not taken.
|
185 | extend_cycles(slice_iter.cut_); | |
| 289 | } | |||
| 290 | } | |||
| 291 | ||||
| 292 | // Skim Cycle type from CycleHistory.key_to_cycle | |||
| 293 | // Discard any Cycles with only Input Gates | |||
| 294 | 19 | std::vector<Cycle> output_cycles; | ||
| 295 |
3/4✓ Branch 4 taken 72 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 72 times.
✓ Branch 9 taken 19 times.
|
0/1? Decision couldn't be analyzed.
|
91 | for (std::pair<unsigned, Cycle> entry : bt.key_to_cycle) { |
| 296 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 72 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 72 times.
|
72 | if (entry.second.coms_.size() == 0) { |
| 297 | ✗ | throw CycleError(std::string("Cycle with no internal gates.")); | ||
| 298 | } | |||
| 299 |
2/4✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 72 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 72 times.
|
72 | if (entry.second.boundary_edges_[0].first == |
| 300 | 72 | entry.second.boundary_edges_[0].second) { | ||
| 301 | ✗ | continue; | ||
| 302 | } | |||
| 303 |
3/6✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 72 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 72 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 72 times.
|
72 | if (entry.second.size() > circ.n_qubits()) { |
| 304 | ✗ | throw CycleError( | ||
| 305 | ✗ | std::string("Cycle has a larger frame than Circuit has qubits.")); | ||
| 306 | } | |||
| 307 |
1/2✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
|
72 | output_cycles.push_back(entry.second); | |
| 308 |
1/2✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
|
72 | } | |
| 309 | 38 | return output_cycles; | ||
| 310 | 19 | } | ||
| 311 | } // namespace tket | |||
| 312 |