GCC Code Coverage Report

Directory: ./
File: Placement/subgraph_mapping.cpp
Date: 2022-10-15 05:10:18
Exec Total Coverage
Lines: 33 35 94.3%
Functions: 2 2 100.0%
Branches: 37 68 54.4%
Decisions: 8 10 80.0%
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 <algorithm>
16 #include <boost/algorithm/minmax_element.hpp>
17 #include <chrono>
18 #include <ctime>
19 #include <sstream>
20 #include <tkassert/Assert.hpp>
21 #include <tklog/TketLog.hpp>
22
23 #include "Architecture/Architecture.hpp"
24 #include "Graphs/Utils.hpp"
25 #include "Placement.hpp"
26 #include "Placement/Placement.hpp"
27 #include "Utils/GraphHeaders.hpp"
28
29 namespace tket {
30
31 64 std::vector<qubit_bimap_t> monomorphism_edge_break(
32 const Architecture& arc, const QubitGraph& q_graph, unsigned max_matches,
33 unsigned timeout) {
34
1/2
✗ Branch 2 not taken.
✓ Branch 3 taken 64 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 64 times.
 64 if (q_graph.n_nodes() > arc.n_nodes()) {
35 ✗ throw ArchitectureInvalidity(
36 ✗ "Interaction graph too large for architecture");
37 }
38
39 Architecture::UndirectedConnGraph undirected_target =
40
2/4
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 64 times.
✗ Branch 5 not taken.
 64 arc.get_undirected_connectivity();
41 QubitGraph::UndirectedConnGraph undirected_pattern =
42
2/4
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 64 times.
✗ Branch 5 not taken.
 64 q_graph.get_undirected_connectivity();
43
44 std::chrono::time_point<std::chrono::steady_clock> end_time =
45
1/2
✓ Branch 3 taken 64 times.
✗ Branch 4 not taken.
 64 std::chrono::steady_clock::now() + std::chrono::milliseconds(timeout);
46
47 while (true) {
48
1/2
✓ Branch 1 taken 115 times.
✗ Branch 2 not taken.
 115 long search_timeout = std::chrono::duration_cast<std::chrono::milliseconds>(
49
1/2
✓ Branch 2 taken 115 times.
✗ Branch 3 not taken.
 115 (end_time - std::chrono::steady_clock::now()) / 2)
50 115 .count();
51
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 113 times.
1/2
✓ Decision 'true' taken 115 times.
✗ Decision 'false' not taken.
 115 if (search_timeout <= 0) search_timeout = 1;
52
53 std::vector<qubit_bimap_t> all_maps = get_unweighted_subgraph_monomorphisms(
54
1/2
✓ Branch 1 taken 115 times.
✗ Branch 2 not taken.
 115 undirected_pattern, undirected_target, max_matches, timeout);
55
1/2
✓ Branch 3 taken 115 times.
✗ Branch 4 not taken.
 115 std::sort(all_maps.begin(), all_maps.end());
56
57
3/4
✓ Branch 3 taken 115 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 3 times.
✓ Branch 7 taken 112 times.
2/2
✓ Decision 'true' taken 3 times.
✓ Decision 'false' taken 112 times.
 115 if (std::chrono::steady_clock::now() >= end_time) {
58
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 std::stringstream ss;
59
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 ss << "subgraph monomorphism reached " << timeout
60
2/4
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 3 times.
✗ Branch 5 not taken.
 3 << " millisecond timeout before reaching set max matches "
61
3/6
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 3 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 3 times.
✗ Branch 9 not taken.
 3 << max_matches << ", instead finding " << all_maps.size()
62 << " matches. "
63
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 "Please change PlacementConfig.timeout to allow more matches.";
64
3/6
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 3 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 3 times.
✗ Branch 9 not taken.
 3 tket_log()->warn(ss.str());
65
2/2
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 1 times.
2/2
✓ Decision 'true' taken 2 times.
✓ Decision 'false' taken 1 times.
 3 if (all_maps.empty()) {
66
1/2
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
 2 throw std::runtime_error("No mappings found before timeout.");
67 }
68 1 return all_maps;
69 3 }
70
2/2
✓ Branch 1 taken 61 times.
✓ Branch 2 taken 51 times.
2/2
✓ Decision 'true' taken 61 times.
✓ Decision 'false' taken 51 times.
 112 if (!all_maps.empty()) {
71 61 return all_maps;
72 }
73 const unsigned current_number_of_edges =
74 51 boost::num_edges(undirected_pattern);
75 // It MUST have found a solution, if no pattern edges!
76 TKET_ASSERT(current_number_of_edges > 0);
77 using edge_t = graphs::utils::edge<QubitGraph::UndirectedConnGraph>;
78
1/2
✓ Branch 1 taken 51 times.
✗ Branch 2 not taken.
 51 auto e_its = boost::edges(undirected_pattern);
79
1/2
✓ Branch 1 taken 51 times.
✗ Branch 2 not taken.
 51 auto max_e_it = boost::first_max_element(
80 e_its.first, e_its.second,
81 616 [&undirected_pattern](const edge_t& lhs, const edge_t& rhs) {
82 308 return undirected_pattern[lhs].weight <
83 308 undirected_pattern[rhs].weight;
84 });
85
2/4
✓ Branch 1 taken 51 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 51 times.
✗ Branch 5 not taken.
 51 graphs::utils::remove_edge(*max_e_it, undirected_pattern, true);
86 TKET_ASSERT(boost::num_edges(undirected_pattern) < current_number_of_edges);
87
2/2
✓ Branch 1 taken 51 times.
✓ Branch 2 taken 62 times.
 166 }
88 66 }
89
90 } // namespace tket
91