GCC Code Coverage Report

Directory: ./
File: Architecture/SubgraphMonomorphisms.cpp
Date: 2022-10-15 05:10:18
Warnings: 1 unchecked decisions!
Exec Total Coverage
Lines: 59 67 88.1%
Functions: 3 4 75.0%
Branches: 42 172 24.4%
Decisions: 19 26 73.1%
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 "SubgraphMonomorphisms.hpp"
16
17 #include <set>
18 #include <tkassert/Assert.hpp>
19 #include <tkwsm/EndToEndWrappers/MainSolver.hpp>
20
21 namespace tket {
22
23 using namespace WeightedSubgraphMonomorphism;
24
25 6 static GraphEdgeWeights get_weight_one_edges(
26 const std::vector<Swap>& edges, size_t number_of_vertices) {
27 6 GraphEdgeWeights result;
28
2/2
✓ Branch 4 taken 45 times.
✓ Branch 5 taken 6 times.
2/2
✓ Decision 'true' taken 45 times.
✓ Decision 'false' taken 6 times.
 51 for (const auto& edge : edges) {
29 TKET_ASSERT(edge.first < number_of_vertices);
30 TKET_ASSERT(edge.second < number_of_vertices);
31
2/4
✓ Branch 1 taken 45 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 45 times.
✗ Branch 5 not taken.
 45 result[get_edge(edge.first, edge.second)] = 1;
32 }
33 TKET_ASSERT(edges.size() == result.size());
34 6 return result;
35 }
36
37 3 static void add_solver_solutions(
38 const std::vector<SolutionWSM>& solutions, size_t pattern_n_vertices,
39 size_t target_n_vertices, SubgraphMonomorphisms& monomorphisms) {
40
1/2
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
 3 monomorphisms.mappings.reserve(solutions.size());
41
42 // The solver ignores isolated vertices, so we'll fill them in separately.
43 3 std::set<size_t> used_pattern_vertices;
44 3 std::set<size_t> used_pattern_vertices_copy;
45 3 std::set<size_t> used_target_vertices;
46
47
2/2
✓ Branch 5 taken 36 times.
✓ Branch 6 taken 3 times.
2/2
✓ Decision 'true' taken 36 times.
✓ Decision 'false' taken 3 times.
 39 for (const auto& solution : solutions) {
48
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 36 monomorphisms.mappings.emplace_back();
49
1/2
✓ Branch 2 taken 36 times.
✗ Branch 3 not taken.
 36 monomorphisms.mappings.back().resize(pattern_n_vertices);
50 36 used_pattern_vertices.clear();
51 36 used_target_vertices.clear();
52
2/2
✓ Branch 4 taken 180 times.
✓ Branch 5 taken 36 times.
2/2
✓ Decision 'true' taken 180 times.
✓ Decision 'false' taken 36 times.
 216 for (const auto& pair : solution.assignments) {
53 180 const auto& pv = pair.first;
54 180 const auto& tv = pair.second;
55 TKET_ASSERT(used_pattern_vertices.insert(pv).second);
56 TKET_ASSERT(used_target_vertices.insert(tv).second);
57
2/2
✓ Branch 1 taken 165 times.
✓ Branch 2 taken 15 times.
1/2
✓ Decision 'true' taken 180 times.
✗ Decision 'false' not taken.
 180 if (!used_pattern_vertices_copy.empty()) {
58 // It's always the same nonisolated pattern vertices.
59 TKET_ASSERT(used_pattern_vertices_copy.count(pv) != 0);
60 }
61 // The architecture mapping guarantees
62 // contiguous vertex numbers {0,1,2,...,N}
63 TKET_ASSERT(pv < pattern_n_vertices);
64 TKET_ASSERT(tv < target_n_vertices);
65 180 monomorphisms.mappings.back()[pv] = tv;
66 }
67
2/2
✓ Branch 1 taken 3 times.
✓ Branch 2 taken 33 times.
2/2
✓ Decision 'true' taken 3 times.
✓ Decision 'false' taken 33 times.
 36 if (used_pattern_vertices_copy.empty()) {
68
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 used_pattern_vertices_copy = used_pattern_vertices;
69 } else {
70
1/104
✗ Branch 2 not taken.
✓ Branch 3 taken 33 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ 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 45 not taken.
✗ Branch 46 not taken.
✗ Branch 49 not taken.
✗ Branch 50 not taken.
✗ Branch 52 not taken.
✗ Branch 53 not taken.
✗ Branch 59 not taken.
✗ Branch 60 not taken.
✗ Branch 63 not taken.
✗ Branch 64 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 94 not taken.
✗ Branch 95 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 110 not taken.
✗ Branch 111 not taken.
✗ Branch 114 not taken.
✗ Branch 115 not taken.
✗ Branch 117 not taken.
✗ Branch 118 not taken.
✗ Branch 123 not taken.
✗ Branch 124 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 163 not taken.
✗ Branch 164 not taken.
✗ Branch 167 not taken.
✗ Branch 168 not taken.
✗ Branch 170 not taken.
✗ Branch 171 not taken.
 33 TKET_ASSERT(
71 used_pattern_vertices_copy.size() == used_pattern_vertices.size());
72 }
73
74 // Now, fill in isolated p-vertex values.
75 36 size_t next_tv = 0;
76
2/2
✓ Branch 0 taken 216 times.
✓ Branch 1 taken 36 times.
2/2
✓ Decision 'true' taken 216 times.
✓ Decision 'false' taken 36 times.
 252 for (size_t pv = 0; pv < pattern_n_vertices; ++pv) {
77 // We could save time by saving the isolated PVs,
78 // but surely not worth it
79
3/4
✓ Branch 1 taken 216 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 180 times.
✓ Branch 4 taken 36 times.
2/2
✓ Decision 'true' taken 180 times.
✓ Decision 'false' taken 36 times.
 216 if (used_pattern_vertices.count(pv) != 0) {
80 180 continue;
81 }
82
3/4
✓ Branch 1 taken 120 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 84 times.
✓ Branch 4 taken 36 times.
0/1
? Decision couldn't be analyzed.
 120 while (used_target_vertices.count(next_tv) != 0) {
83 84 ++next_tv;
84 }
85 36 monomorphisms.mappings.back()[pv] = next_tv;
86 36 ++next_tv;
87 }
88 }
89 3 }
90
91 // Strictly speaking, we should go through all (T choose k) subsets
92 // of target vertices, and all permutations of k pattern vertices,
93 // but don't bother for now - just give one solution.
94 ✗ static void fill_with_all_isolated_pattern_vertices(
95 SubgraphMonomorphisms& monomorphisms, size_t pattern_n_vertices) {
96 ✗ monomorphisms.mappings.resize(1);
97 ✗ monomorphisms.mappings[0].resize(pattern_n_vertices);
98
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ for (size_t ii = 0; ii < pattern_n_vertices; ++ii) {
99 ✗ monomorphisms.mappings[0][ii] = ii;
100 }
101 }
102
103 4 SubgraphMonomorphisms::SubgraphMonomorphisms(
104 const ArchitectureMapping& pattern_arch_mapping,
105 const ArchitectureMapping& target_arch_mapping,
106 4 const Parameters& parameters)
107 4 : time_taken_ms(0) {
108
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 3 times.
 4 if (parameters.max_number_of_mappings == 0) {
109 1 return;
110 }
111
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 const auto pattern_n_vertices = pattern_arch_mapping.number_of_vertices();
112
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 const auto target_n_vertices = target_arch_mapping.number_of_vertices();
113
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 3 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 3 times.
 4 if (pattern_n_vertices > target_n_vertices) {
114 1 return;
115 }
116
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 const auto pattern_edges = pattern_arch_mapping.get_edges();
117
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 const auto target_edges = target_arch_mapping.get_edges();
118
1/2
✗ Branch 2 not taken.
✓ Branch 3 taken 3 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 3 times.
 3 if (pattern_edges.size() > target_edges.size()) {
119 ✗ return;
120 }
121
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 3 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 3 times.
 3 if (pattern_edges.empty()) {
122 // A pointless special case: all pattern vertices are isolated!
123 ✗ fill_with_all_isolated_pattern_vertices(*this, pattern_n_vertices);
124 ✗ return;
125 }
126 const auto pattern_edges_and_weights =
127
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 get_weight_one_edges(pattern_edges, pattern_n_vertices);
128 const auto target_edges_and_weights =
129
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 get_weight_one_edges(target_edges, target_n_vertices);
130
131
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 MainSolverParameters solver_parameters;
132 3 solver_parameters.terminate_with_first_full_solution = false;
133 3 solver_parameters.for_multiple_full_solutions_the_max_number_to_obtain =
134 3 parameters.max_number_of_mappings;
135 3 solver_parameters.timeout_ms = parameters.timeout_ms;
136
137 const MainSolver main_solver(
138
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 pattern_edges_and_weights, target_edges_and_weights, solver_parameters);
139
140
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 const auto& solution_data = main_solver.get_solution_data();
141
142 3 time_taken_ms =
143 3 solution_data.initialisation_time_ms + solution_data.search_time_ms;
144
145 3 add_solver_solutions(
146
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 solution_data.solutions, pattern_n_vertices, target_n_vertices, *this);
147
2/4
✓ Branch 4 taken 3 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 3 times.
✗ Branch 8 not taken.
 3 }
148
149 } // namespace tket
150