| 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 | #include "Mapping/BoxDecomposition.hpp" | |||
| 15 | ||||
| 16 | #include "Mapping/MappingFrontier.hpp" | |||
| 17 | ||||
| 18 | namespace tket { | |||
| 19 | ||||
| 20 | 5 | BoxDecomposition::BoxDecomposition( | ||
| 21 | const ArchitecturePtr &_architecture, | |||
| 22 | 5 | MappingFrontier_ptr &_mapping_frontier) | ||
| 23 | 5 | : architecture_(_architecture), mapping_frontier_(_mapping_frontier) {} | ||
| 24 | ||||
| 25 | 5 | bool BoxDecomposition::solve() { | ||
| 26 | // Box type vertices are later removed from DAG | |||
| 27 | 5 | VertexList bin; | ||
| 28 | 5 | bool modified = false; | ||
| 29 | std::shared_ptr<unit_frontier_t> frontier_edges = | |||
| 30 | frontier_convert_vertport_to_edge( | |||
| 31 | 10 | this->mapping_frontier_->circuit_, | ||
| 32 |
1/2✓ Branch 3 taken 5 times.
✗ Branch 4 not taken.
|
5 | this->mapping_frontier_->linear_boundary); | |
| 33 | CutFrontier next_cut = | |||
| 34 |
1/2✓ Branch 3 taken 5 times.
✗ Branch 4 not taken.
|
5 | this->mapping_frontier_->circuit_.next_q_cut(frontier_edges); | |
| 35 |
2/2✓ Branch 6 taken 5 times.
✓ Branch 7 taken 5 times.
|
2/2✓ Decision 'true' taken 5 times.
✓ Decision 'false' taken 5 times.
|
10 | for (Vertex &vert : *next_cut.slice) { |
| 36 |
1/2✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
|
5 | Op_ptr op = this->mapping_frontier_->circuit_.get_Op_ptr_from_Vertex(vert); | |
| 37 |
6/12✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 5 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 1 times.
✓ Branch 8 taken 4 times.
✓ Branch 9 taken 1 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 5 times.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
|
2/2✓ Decision 'true' taken 5 times.
✓ Decision 'false' taken 7 times.
|
12 | if (op->get_desc().is_box() || |
| 38 | 1 | (op->get_type() == OpType::Conditional && | ||
| 39 |
9/18✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 1 times.
✗ Branch 10 not taken.
✓ Branch 11 taken 1 times.
✗ Branch 12 not taken.
✓ Branch 13 taken 1 times.
✓ Branch 14 taken 4 times.
✓ Branch 16 taken 1 times.
✓ Branch 17 taken 4 times.
✓ Branch 19 taken 5 times.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
✗ Branch 24 not taken.
✗ Branch 25 not taken.
|
6 | static_cast<const Conditional &>(*op).get_op()->get_desc().is_box())) { | |
| 40 |
2/4✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 5 times.
✗ Branch 5 not taken.
|
5 | if (this->mapping_frontier_->circuit_.substitute_box_vertex( | |
| 41 | vert, Circuit::VertexDeletion::No)) { | |||
| 42 | 5 | modified = true; | ||
| 43 |
1/2✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
|
5 | bin.push_back(vert); | |
| 44 | } | |||
| 45 | } | |||
| 46 | 5 | } | ||
| 47 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 5 times.
|
5 | if (!modified) { | |
| 48 | ✗ | return false; | ||
| 49 | } | |||
| 50 | // Delete vertices | |||
| 51 |
1/2✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
|
5 | this->mapping_frontier_->circuit_.remove_vertices( | |
| 52 | bin, Circuit::GraphRewiring::No, Circuit::VertexDeletion::Yes); | |||
| 53 | 5 | return true; | ||
| 54 | 5 | } | ||
| 55 | ||||
| 56 | 5 | BoxDecompositionRoutingMethod::BoxDecompositionRoutingMethod(){}; | ||
| 57 | ||||
| 58 | 3 | std::pair<bool, unit_map_t> BoxDecompositionRoutingMethod::routing_method( | ||
| 59 | MappingFrontier_ptr &mapping_frontier, | |||
| 60 | const ArchitecturePtr &architecture) const { | |||
| 61 |
1/2✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
|
3 | BoxDecomposition bd(architecture, mapping_frontier); | |
| 62 |
1/2✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
|
3 | bool modified = bd.solve(); | |
| 63 |
1/2✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
|
6 | return {modified, {}}; | |
| 64 | 3 | } | ||
| 65 | ||||
| 66 | 4 | nlohmann::json BoxDecompositionRoutingMethod::serialize() const { | ||
| 67 | 4 | nlohmann::json j; | ||
| 68 |
2/4✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 4 times.
✗ Branch 5 not taken.
|
4 | j["name"] = "BoxDecompositionRoutingMethod"; | |
| 69 | 4 | return j; | ||
| 70 | } | |||
| 71 | ||||
| 72 | 3 | BoxDecompositionRoutingMethod BoxDecompositionRoutingMethod::deserialize( | ||
| 73 | const nlohmann::json & /*j*/) { | |||
| 74 | 3 | return BoxDecompositionRoutingMethod(); | ||
| 75 | } | |||
| 76 | ||||
| 77 | } // namespace tket | |||
| 78 |