| 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 <tkwsm/EndToEndWrappers/MainSolver.hpp> | |||
| 16 | ||||
| 17 | #include "Placement/Placement.hpp" | |||
| 18 | #include "RelabelledGraphWSM.hpp" | |||
| 19 | ||||
| 20 | namespace tket { | |||
| 21 | ||||
| 22 | using namespace WeightedSubgraphMonomorphism; | |||
| 23 | ||||
| 24 | using RelabelledPatternGraph = | |||
| 25 | RelabelledGraphWSM<Qubit, QubitGraph::UndirectedConnGraph>; | |||
| 26 | using RelabelledTargetGraph = | |||
| 27 | RelabelledGraphWSM<Node, Architecture::UndirectedConnGraph>; | |||
| 28 | using BimapValue = qubit_bimap_t::value_type; | |||
| 29 | ||||
| 30 | // Where should isolated pattern vertices be assigned? | |||
| 31 | // They might NOT have been isolated originally; it may be | |||
| 32 | // that we deliberately erased some pattern edges. | |||
| 33 | // Thus, we still want them connected to useful target components, | |||
| 34 | // so assign to nonisolated target vertices first. | |||
| 35 | 34860 | static void assign_isolated_pattern_vertices( | ||
| 36 | qubit_bimap_t& map, const RelabelledPatternGraph& relabelled_pattern_graph, | |||
| 37 | const RelabelledTargetGraph& relabelled_target_graph) { | |||
| 38 |
2/2✓ Branch 2 taken 34835 times.
✓ Branch 3 taken 25 times.
|
2/2✓ Decision 'true' taken 34835 times.
✓ Decision 'false' taken 25 times.
|
34860 | if (relabelled_pattern_graph.get_relabelled_isolated_vertices().empty()) { |
| 39 | 34835 | return; | ||
| 40 | } | |||
| 41 | // The PV assigned so far must be exactly the nonisolated ones. | |||
| 42 |
2/106✓ Branch 1 taken 25 times.
✗ Branch 2 not taken.
✗ Branch 5 not taken.
✓ Branch 6 taken 25 times.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
✗ Branch 29 not taken.
✗ Branch 30 not taken.
✗ Branch 32 not taken.
✗ Branch 33 not taken.
✗ Branch 35 not taken.
✗ Branch 36 not taken.
✗ Branch 38 not taken.
✗ Branch 39 not taken.
✗ Branch 41 not taken.
✗ Branch 42 not taken.
✗ Branch 44 not taken.
✗ Branch 45 not taken.
✗ Branch 48 not taken.
✗ Branch 49 not taken.
✗ Branch 52 not taken.
✗ Branch 53 not taken.
✗ Branch 55 not taken.
✗ Branch 56 not taken.
✗ Branch 62 not taken.
✗ Branch 63 not taken.
✗ Branch 66 not taken.
✗ Branch 67 not taken.
✗ Branch 69 not taken.
✗ Branch 70 not taken.
✗ Branch 72 not taken.
✗ Branch 73 not taken.
✗ Branch 75 not taken.
✗ Branch 76 not taken.
✗ Branch 78 not taken.
✗ Branch 79 not taken.
✗ Branch 81 not taken.
✗ Branch 82 not taken.
✗ Branch 84 not taken.
✗ Branch 85 not taken.
✗ Branch 87 not taken.
✗ Branch 88 not taken.
✗ Branch 90 not taken.
✗ Branch 91 not taken.
✗ Branch 93 not taken.
✗ Branch 94 not taken.
✗ Branch 97 not taken.
✗ Branch 98 not taken.
✗ Branch 100 not taken.
✗ Branch 101 not taken.
✗ Branch 103 not taken.
✗ Branch 104 not taken.
✗ Branch 106 not taken.
✗ Branch 107 not taken.
✗ Branch 109 not taken.
✗ Branch 110 not taken.
✗ Branch 113 not taken.
✗ Branch 114 not taken.
✗ Branch 117 not taken.
✗ Branch 118 not taken.
✗ Branch 120 not taken.
✗ Branch 121 not taken.
✗ Branch 126 not taken.
✗ Branch 127 not taken.
✗ Branch 129 not taken.
✗ Branch 130 not taken.
✗ Branch 132 not taken.
✗ Branch 133 not taken.
✗ Branch 135 not taken.
✗ Branch 136 not taken.
✗ Branch 138 not taken.
✗ Branch 139 not taken.
✗ Branch 141 not taken.
✗ Branch 142 not taken.
✗ Branch 144 not taken.
✗ Branch 145 not taken.
✗ Branch 147 not taken.
✗ Branch 148 not taken.
✗ Branch 150 not taken.
✗ Branch 151 not taken.
✗ Branch 153 not taken.
✗ Branch 154 not taken.
✗ Branch 156 not taken.
✗ Branch 157 not taken.
✗ Branch 159 not taken.
✗ Branch 160 not taken.
✗ Branch 162 not taken.
✗ Branch 163 not taken.
✗ Branch 166 not taken.
✗ Branch 167 not taken.
✗ Branch 170 not taken.
✗ Branch 171 not taken.
✗ Branch 173 not taken.
✗ Branch 174 not taken.
|
25 | TKET_ASSERT( | |
| 43 | map.size() == | |||
| 44 | relabelled_pattern_graph.get_relabelled_nonisolated_vertices().size()); | |||
| 45 | ||||
| 46 | // Also, all PV so far must have been assigned to nonisolated TV. | |||
| 47 |
2/106✓ Branch 1 taken 25 times.
✗ Branch 2 not taken.
✗ Branch 5 not taken.
✓ Branch 6 taken 25 times.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
✗ Branch 29 not taken.
✗ Branch 30 not taken.
✗ Branch 32 not taken.
✗ Branch 33 not taken.
✗ Branch 35 not taken.
✗ Branch 36 not taken.
✗ Branch 38 not taken.
✗ Branch 39 not taken.
✗ Branch 41 not taken.
✗ Branch 42 not taken.
✗ Branch 44 not taken.
✗ Branch 45 not taken.
✗ Branch 48 not taken.
✗ Branch 49 not taken.
✗ Branch 52 not taken.
✗ Branch 53 not taken.
✗ Branch 55 not taken.
✗ Branch 56 not taken.
✗ Branch 62 not taken.
✗ Branch 63 not taken.
✗ Branch 66 not taken.
✗ Branch 67 not taken.
✗ Branch 69 not taken.
✗ Branch 70 not taken.
✗ Branch 72 not taken.
✗ Branch 73 not taken.
✗ Branch 75 not taken.
✗ Branch 76 not taken.
✗ Branch 78 not taken.
✗ Branch 79 not taken.
✗ Branch 81 not taken.
✗ Branch 82 not taken.
✗ Branch 84 not taken.
✗ Branch 85 not taken.
✗ Branch 87 not taken.
✗ Branch 88 not taken.
✗ Branch 90 not taken.
✗ Branch 91 not taken.
✗ Branch 93 not taken.
✗ Branch 94 not taken.
✗ Branch 97 not taken.
✗ Branch 98 not taken.
✗ Branch 100 not taken.
✗ Branch 101 not taken.
✗ Branch 103 not taken.
✗ Branch 104 not taken.
✗ Branch 106 not taken.
✗ Branch 107 not taken.
✗ Branch 109 not taken.
✗ Branch 110 not taken.
✗ Branch 113 not taken.
✗ Branch 114 not taken.
✗ Branch 117 not taken.
✗ Branch 118 not taken.
✗ Branch 120 not taken.
✗ Branch 121 not taken.
✗ Branch 126 not taken.
✗ Branch 127 not taken.
✗ Branch 129 not taken.
✗ Branch 130 not taken.
✗ Branch 132 not taken.
✗ Branch 133 not taken.
✗ Branch 135 not taken.
✗ Branch 136 not taken.
✗ Branch 138 not taken.
✗ Branch 139 not taken.
✗ Branch 141 not taken.
✗ Branch 142 not taken.
✗ Branch 144 not taken.
✗ Branch 145 not taken.
✗ Branch 147 not taken.
✗ Branch 148 not taken.
✗ Branch 150 not taken.
✗ Branch 151 not taken.
✗ Branch 153 not taken.
✗ Branch 154 not taken.
✗ Branch 156 not taken.
✗ Branch 157 not taken.
✗ Branch 159 not taken.
✗ Branch 160 not taken.
✗ Branch 162 not taken.
✗ Branch 163 not taken.
✗ Branch 166 not taken.
✗ Branch 167 not taken.
✗ Branch 170 not taken.
✗ Branch 171 not taken.
✗ Branch 173 not taken.
✗ Branch 174 not taken.
|
25 | TKET_ASSERT( | |
| 48 | map.size() <= | |||
| 49 | relabelled_target_graph.get_relabelled_nonisolated_vertices().size()); | |||
| 50 | ||||
| 51 | 25 | std::set<VertexWSM> unused_target_vertices; | ||
| 52 | bool refilled_with_isolated_tv; | |||
| 53 |
2/4✓ Branch 1 taken 25 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 25 times.
✗ Branch 4 not taken.
|
2/2✓ Decision 'true' taken 25 times.
✓ Decision 'false' taken 25 times.
|
50 | if (map.size() < |
| 54 | 25 | relabelled_target_graph.get_relabelled_nonisolated_vertices().size()) { | ||
| 55 | 25 | refilled_with_isolated_tv = false; | ||
| 56 | unused_target_vertices = | |||
| 57 |
1/2✓ Branch 2 taken 25 times.
✗ Branch 3 not taken.
|
25 | relabelled_target_graph.get_relabelled_nonisolated_vertices(); | |
| 58 |
7/12✓ Branch 1 taken 25 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 25 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 64 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 64 times.
✗ Branch 11 not taken.
✓ Branch 13 taken 89 times.
✗ Branch 14 not taken.
✓ Branch 15 taken 64 times.
✓ Branch 16 taken 25 times.
|
0/1? Decision couldn't be analyzed.
|
89 | for (const auto& entry : map.left) { |
| 59 | // We CANNOT have assigned a nonisolated pattern vertex | |||
| 60 | // to an isolated target vertex. | |||
| 61 | const VertexWSM new_pv = | |||
| 62 |
1/2✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
|
64 | relabelled_pattern_graph.get_relabelled_vertex(entry.first); | |
| 63 | const VertexWSM new_tv = | |||
| 64 |
1/2✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
|
64 | relabelled_target_graph.get_relabelled_vertex(entry.second); | |
| 65 |
2/106✓ Branch 2 taken 64 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 64 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
✗ Branch 31 not taken.
✗ Branch 32 not taken.
✗ Branch 34 not taken.
✗ Branch 35 not taken.
✗ Branch 37 not taken.
✗ Branch 38 not taken.
✗ Branch 40 not taken.
✗ Branch 41 not taken.
✗ Branch 43 not taken.
✗ Branch 44 not taken.
✗ Branch 47 not taken.
✗ Branch 48 not taken.
✗ Branch 51 not taken.
✗ Branch 52 not taken.
✗ Branch 54 not taken.
✗ Branch 55 not taken.
✗ Branch 61 not taken.
✗ Branch 62 not taken.
✗ Branch 65 not taken.
✗ Branch 66 not taken.
✗ Branch 68 not taken.
✗ Branch 69 not taken.
✗ Branch 71 not taken.
✗ Branch 72 not taken.
✗ Branch 74 not taken.
✗ Branch 75 not taken.
✗ Branch 77 not taken.
✗ Branch 78 not taken.
✗ Branch 80 not taken.
✗ Branch 81 not taken.
✗ Branch 83 not taken.
✗ Branch 84 not taken.
✗ Branch 86 not taken.
✗ Branch 87 not taken.
✗ Branch 89 not taken.
✗ Branch 90 not taken.
✗ Branch 92 not taken.
✗ Branch 93 not taken.
✗ Branch 96 not taken.
✗ Branch 97 not taken.
✗ Branch 99 not taken.
✗ Branch 100 not taken.
✗ Branch 102 not taken.
✗ Branch 103 not taken.
✗ Branch 105 not taken.
✗ Branch 106 not taken.
✗ Branch 108 not taken.
✗ Branch 109 not taken.
✗ Branch 112 not taken.
✗ Branch 113 not taken.
✗ Branch 116 not taken.
✗ Branch 117 not taken.
✗ Branch 119 not taken.
✗ Branch 120 not taken.
✗ Branch 125 not taken.
✗ Branch 126 not taken.
✗ Branch 128 not taken.
✗ Branch 129 not taken.
✗ Branch 131 not taken.
✗ Branch 132 not taken.
✗ Branch 134 not taken.
✗ Branch 135 not taken.
✗ Branch 137 not taken.
✗ Branch 138 not taken.
✗ Branch 140 not taken.
✗ Branch 141 not taken.
✗ Branch 143 not taken.
✗ Branch 144 not taken.
✗ Branch 146 not taken.
✗ Branch 147 not taken.
✗ Branch 149 not taken.
✗ Branch 150 not taken.
✗ Branch 152 not taken.
✗ Branch 153 not taken.
✗ Branch 155 not taken.
✗ Branch 156 not taken.
✗ Branch 158 not taken.
✗ Branch 159 not taken.
✗ Branch 161 not taken.
✗ Branch 162 not taken.
✗ Branch 165 not taken.
✗ Branch 166 not taken.
✗ Branch 169 not taken.
✗ Branch 170 not taken.
✗ Branch 172 not taken.
✗ Branch 173 not taken.
|
64 | TKET_ASSERT( | |
| 66 | relabelled_pattern_graph.get_relabelled_nonisolated_vertices().count( | |||
| 67 | new_pv) != 0); | |||
| 68 |
2/106✓ Branch 2 taken 64 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 64 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
✗ Branch 31 not taken.
✗ Branch 32 not taken.
✗ Branch 34 not taken.
✗ Branch 35 not taken.
✗ Branch 37 not taken.
✗ Branch 38 not taken.
✗ Branch 40 not taken.
✗ Branch 41 not taken.
✗ Branch 43 not taken.
✗ Branch 44 not taken.
✗ Branch 47 not taken.
✗ Branch 48 not taken.
✗ Branch 51 not taken.
✗ Branch 52 not taken.
✗ Branch 54 not taken.
✗ Branch 55 not taken.
✗ Branch 61 not taken.
✗ Branch 62 not taken.
✗ Branch 65 not taken.
✗ Branch 66 not taken.
✗ Branch 68 not taken.
✗ Branch 69 not taken.
✗ Branch 71 not taken.
✗ Branch 72 not taken.
✗ Branch 74 not taken.
✗ Branch 75 not taken.
✗ Branch 77 not taken.
✗ Branch 78 not taken.
✗ Branch 80 not taken.
✗ Branch 81 not taken.
✗ Branch 83 not taken.
✗ Branch 84 not taken.
✗ Branch 86 not taken.
✗ Branch 87 not taken.
✗ Branch 89 not taken.
✗ Branch 90 not taken.
✗ Branch 92 not taken.
✗ Branch 93 not taken.
✗ Branch 96 not taken.
✗ Branch 97 not taken.
✗ Branch 99 not taken.
✗ Branch 100 not taken.
✗ Branch 102 not taken.
✗ Branch 103 not taken.
✗ Branch 105 not taken.
✗ Branch 106 not taken.
✗ Branch 108 not taken.
✗ Branch 109 not taken.
✗ Branch 112 not taken.
✗ Branch 113 not taken.
✗ Branch 116 not taken.
✗ Branch 117 not taken.
✗ Branch 119 not taken.
✗ Branch 120 not taken.
✗ Branch 125 not taken.
✗ Branch 126 not taken.
✗ Branch 128 not taken.
✗ Branch 129 not taken.
✗ Branch 131 not taken.
✗ Branch 132 not taken.
✗ Branch 134 not taken.
✗ Branch 135 not taken.
✗ Branch 137 not taken.
✗ Branch 138 not taken.
✗ Branch 140 not taken.
✗ Branch 141 not taken.
✗ Branch 143 not taken.
✗ Branch 144 not taken.
✗ Branch 146 not taken.
✗ Branch 147 not taken.
✗ Branch 149 not taken.
✗ Branch 150 not taken.
✗ Branch 152 not taken.
✗ Branch 153 not taken.
✗ Branch 155 not taken.
✗ Branch 156 not taken.
✗ Branch 158 not taken.
✗ Branch 159 not taken.
✗ Branch 161 not taken.
✗ Branch 162 not taken.
✗ Branch 165 not taken.
✗ Branch 166 not taken.
✗ Branch 169 not taken.
✗ Branch 170 not taken.
✗ Branch 172 not taken.
✗ Branch 173 not taken.
|
64 | TKET_ASSERT( | |
| 69 | relabelled_target_graph.get_relabelled_nonisolated_vertices().count( | |||
| 70 | new_tv) != 0); | |||
| 71 | TKET_ASSERT(unused_target_vertices.erase(new_tv) == 1); | |||
| 72 | } | |||
| 73 | } else { | |||
| 74 | ✗ | refilled_with_isolated_tv = true; | ||
| 75 | unused_target_vertices = | |||
| 76 | ✗ | relabelled_target_graph.get_relabelled_isolated_vertices(); | ||
| 77 | } | |||
| 78 | 25 | for (VertexWSM isolated_pv : | ||
| 79 |
2/2✓ Branch 5 taken 36 times.
✓ Branch 6 taken 25 times.
|
86 | relabelled_pattern_graph.get_relabelled_isolated_vertices()) { | |
| 80 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 36 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 36 times.
|
36 | if (unused_target_vertices.empty()) { |
| 81 | // We cannot run out of vertices. | |||
| 82 | TKET_ASSERT(!refilled_with_isolated_tv); | |||
| 83 | ✗ | refilled_with_isolated_tv = true; | ||
| 84 | unused_target_vertices = | |||
| 85 | ✗ | relabelled_target_graph.get_relabelled_isolated_vertices(); | ||
| 86 | TKET_ASSERT(!unused_target_vertices.empty()); | |||
| 87 | } | |||
| 88 | 36 | const VertexWSM next_tv = *unused_target_vertices.cbegin(); | ||
| 89 |
1/2✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
|
36 | unused_target_vertices.erase(next_tv); | |
| 90 | ||||
| 91 |
1/2✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
|
36 | map.insert(BimapValue( | |
| 92 |
2/4✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 36 times.
✗ Branch 5 not taken.
|
36 | relabelled_pattern_graph.get_original_vertices().at(isolated_pv), | |
| 93 |
1/2✓ Branch 2 taken 36 times.
✗ Branch 3 not taken.
|
36 | relabelled_target_graph.get_original_vertices().at(next_tv))); | |
| 94 | } | |||
| 95 | 25 | } | ||
| 96 | ||||
| 97 | 119 | static void write_solver_solutions( | ||
| 98 | std::vector<qubit_bimap_t>& all_maps, | |||
| 99 | const std::vector<SolutionWSM>& solutions, | |||
| 100 | const RelabelledPatternGraph& relabelled_pattern_graph, | |||
| 101 | const RelabelledTargetGraph& relabelled_target_graph) { | |||
| 102 | TKET_ASSERT(all_maps.empty()); | |||
| 103 | 119 | all_maps.resize(solutions.size()); | ||
| 104 | const WeightWSM expected_weight = | |||
| 105 | 119 | relabelled_pattern_graph.get_relabelled_edges_and_weights().size(); | ||
| 106 | ||||
| 107 |
2/2✓ Branch 1 taken 34858 times.
✓ Branch 2 taken 119 times.
|
2/2✓ Decision 'true' taken 34858 times.
✓ Decision 'false' taken 119 times.
|
34977 | for (unsigned ii = 0; ii < solutions.size(); ++ii) { |
| 108 | 34858 | const auto& solution = solutions[ii]; | ||
| 109 | 34858 | auto& map = all_maps[ii]; | ||
| 110 | TKET_ASSERT(solution.scalar_product == expected_weight); | |||
| 111 | TKET_ASSERT(solution.total_p_edges_weight == expected_weight); | |||
| 112 |
2/2✓ Branch 4 taken 227326 times.
✓ Branch 5 taken 34858 times.
|
2/2✓ Decision 'true' taken 227326 times.
✓ Decision 'false' taken 34858 times.
|
262184 | for (const auto& relabelled_pv_tv : solution.assignments) { |
| 113 |
1/2✓ Branch 1 taken 227326 times.
✗ Branch 2 not taken.
|
227326 | map.insert(BimapValue( | |
| 114 |
1/2✓ Branch 1 taken 227326 times.
✗ Branch 2 not taken.
|
227326 | relabelled_pattern_graph.get_original_vertices().at( | |
| 115 |
1/2✓ Branch 1 taken 227326 times.
✗ Branch 2 not taken.
|
227326 | relabelled_pv_tv.first), | |
| 116 | 454652 | relabelled_target_graph.get_original_vertices().at( | ||
| 117 |
1/2✓ Branch 1 taken 227326 times.
✗ Branch 2 not taken.
|
227326 | relabelled_pv_tv.second))); | |
| 118 | } | |||
| 119 | 34858 | assign_isolated_pattern_vertices( | ||
| 120 | map, relabelled_pattern_graph, relabelled_target_graph); | |||
| 121 |
2/106✓ Branch 1 taken 34858 times.
✗ Branch 2 not taken.
✗ Branch 5 not taken.
✓ Branch 6 taken 34858 times.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
✗ Branch 29 not taken.
✗ Branch 30 not taken.
✗ Branch 32 not taken.
✗ Branch 33 not taken.
✗ Branch 35 not taken.
✗ Branch 36 not taken.
✗ Branch 38 not taken.
✗ Branch 39 not taken.
✗ Branch 41 not taken.
✗ Branch 42 not taken.
✗ Branch 44 not taken.
✗ Branch 45 not taken.
✗ Branch 48 not taken.
✗ Branch 49 not taken.
✗ Branch 52 not taken.
✗ Branch 53 not taken.
✗ Branch 55 not taken.
✗ Branch 56 not taken.
✗ Branch 62 not taken.
✗ Branch 63 not taken.
✗ Branch 66 not taken.
✗ Branch 67 not taken.
✗ Branch 69 not taken.
✗ Branch 70 not taken.
✗ Branch 72 not taken.
✗ Branch 73 not taken.
✗ Branch 75 not taken.
✗ Branch 76 not taken.
✗ Branch 78 not taken.
✗ Branch 79 not taken.
✗ Branch 81 not taken.
✗ Branch 82 not taken.
✗ Branch 84 not taken.
✗ Branch 85 not taken.
✗ Branch 87 not taken.
✗ Branch 88 not taken.
✗ Branch 90 not taken.
✗ Branch 91 not taken.
✗ Branch 93 not taken.
✗ Branch 94 not taken.
✗ Branch 97 not taken.
✗ Branch 98 not taken.
✗ Branch 100 not taken.
✗ Branch 101 not taken.
✗ Branch 103 not taken.
✗ Branch 104 not taken.
✗ Branch 106 not taken.
✗ Branch 107 not taken.
✗ Branch 109 not taken.
✗ Branch 110 not taken.
✗ Branch 113 not taken.
✗ Branch 114 not taken.
✗ Branch 117 not taken.
✗ Branch 118 not taken.
✗ Branch 120 not taken.
✗ Branch 121 not taken.
✗ Branch 126 not taken.
✗ Branch 127 not taken.
✗ Branch 129 not taken.
✗ Branch 130 not taken.
✗ Branch 132 not taken.
✗ Branch 133 not taken.
✗ Branch 135 not taken.
✗ Branch 136 not taken.
✗ Branch 138 not taken.
✗ Branch 139 not taken.
✗ Branch 141 not taken.
✗ Branch 142 not taken.
✗ Branch 144 not taken.
✗ Branch 145 not taken.
✗ Branch 147 not taken.
✗ Branch 148 not taken.
✗ Branch 150 not taken.
✗ Branch 151 not taken.
✗ Branch 153 not taken.
✗ Branch 154 not taken.
✗ Branch 156 not taken.
✗ Branch 157 not taken.
✗ Branch 159 not taken.
✗ Branch 160 not taken.
✗ Branch 162 not taken.
✗ Branch 163 not taken.
✗ Branch 166 not taken.
✗ Branch 167 not taken.
✗ Branch 170 not taken.
✗ Branch 171 not taken.
✗ Branch 173 not taken.
✗ Branch 174 not taken.
|
34858 | TKET_ASSERT( | |
| 122 | map.size() == relabelled_pattern_graph.get_original_vertices().size()); | |||
| 123 | } | |||
| 124 | 119 | } | ||
| 125 | ||||
| 126 | /** | |||
| 127 | * \cond Somehow doxygen 1.9.1 complains about this. Tell it to be quiet. | |||
| 128 | */ | |||
| 129 | ||||
| 130 | 128 | std::vector<qubit_bimap_t> get_unweighted_subgraph_monomorphisms( | ||
| 131 | const QubitGraph::UndirectedConnGraph& pattern_graph, | |||
| 132 | const Architecture::UndirectedConnGraph& target_graph, unsigned max_matches, | |||
| 133 | unsigned timeout_ms) { | |||
| 134 | 128 | std::vector<qubit_bimap_t> all_maps; | ||
| 135 | ||||
| 136 |
1/2✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
|
128 | const RelabelledPatternGraph relabelled_pattern_graph(pattern_graph); | |
| 137 |
1/2✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
|
128 | const RelabelledTargetGraph relabelled_target_graph(target_graph); | |
| 138 | ||||
| 139 | 128 | if (relabelled_pattern_graph.get_relabelled_edges_and_weights().size() > | ||
| 140 |
1/2✓ Branch 2 taken 121 times.
✗ Branch 3 not taken.
|
249 | relabelled_target_graph.get_relabelled_edges_and_weights().size() || | |
| 141 | 121 | relabelled_pattern_graph.get_relabelled_nonisolated_vertices().size() > | ||
| 142 | 121 | relabelled_target_graph.get_relabelled_nonisolated_vertices() | ||
| 143 |
4/4✓ Branch 0 taken 121 times.
✓ Branch 1 taken 7 times.
✓ Branch 3 taken 7 times.
✓ Branch 4 taken 121 times.
|
370 | .size() || | |
| 144 | ||||
| 145 | 121 | relabelled_pattern_graph.get_relabelled_isolated_vertices().size() + | ||
| 146 | 121 | relabelled_pattern_graph.get_relabelled_nonisolated_vertices() | ||
| 147 | 121 | .size() > | ||
| 148 |
1/2✗ Branch 2 not taken.
✓ Branch 3 taken 121 times.
|
242 | relabelled_target_graph.get_relabelled_isolated_vertices().size() + | |
| 149 | 121 | relabelled_target_graph.get_relabelled_nonisolated_vertices() | ||
| 150 | 121 | .size()) { | ||
| 151 | // The problem is trivially insoluble. | |||
| 152 | 7 | return all_maps; | ||
| 153 | } | |||
| 154 | ||||
| 155 |
2/2✓ Branch 2 taken 2 times.
✓ Branch 3 taken 119 times.
|
2/2✓ Decision 'true' taken 2 times.
✓ Decision 'false' taken 119 times.
|
121 | if (relabelled_pattern_graph.get_relabelled_nonisolated_vertices().empty()) { |
| 156 | // Trivial special case: all pattern vertices are isolated! | |||
| 157 |
1/2✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
|
2 | all_maps.resize(1); | |
| 158 |
1/2✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
|
2 | assign_isolated_pattern_vertices( | |
| 159 | 2 | all_maps[0], relabelled_pattern_graph, relabelled_target_graph); | ||
| 160 | 2 | return all_maps; | ||
| 161 | } | |||
| 162 | ||||
| 163 |
1/2✓ Branch 1 taken 119 times.
✗ Branch 2 not taken.
|
119 | MainSolverParameters solver_parameters; | |
| 164 | 119 | solver_parameters.terminate_with_first_full_solution = false; | ||
| 165 | 119 | solver_parameters.for_multiple_full_solutions_the_max_number_to_obtain = | ||
| 166 | 119 | max_matches; | ||
| 167 | 119 | solver_parameters.timeout_ms = timeout_ms; | ||
| 168 | ||||
| 169 | const MainSolver main_solver( | |||
| 170 | relabelled_pattern_graph.get_relabelled_edges_and_weights(), | |||
| 171 | relabelled_target_graph.get_relabelled_edges_and_weights(), | |||
| 172 |
1/2✓ Branch 3 taken 119 times.
✗ Branch 4 not taken.
|
119 | solver_parameters); | |
| 173 | ||||
| 174 |
1/2✓ Branch 1 taken 119 times.
✗ Branch 2 not taken.
|
119 | const auto& solution_data = main_solver.get_solution_data(); | |
| 175 | ||||
| 176 | 119 | write_solver_solutions( | ||
| 177 |
1/2✓ Branch 1 taken 119 times.
✗ Branch 2 not taken.
|
119 | all_maps, solution_data.solutions, relabelled_pattern_graph, | |
| 178 | relabelled_target_graph); | |||
| 179 | ||||
| 180 | 119 | return all_maps; | ||
| 181 | 128 | } | ||
| 182 | ||||
| 183 | /** | |||
| 184 | * \endcond | |||
| 185 | */ | |||
| 186 | ||||
| 187 | } // namespace tket | |||
| 188 |