GCC Code Coverage Report

Directory: ./
File: Placement/RelabelledGraphWSM.hpp
Date: 2022-10-15 05:10:18
Warnings: 1 unchecked decisions!
Exec Total Coverage
Lines: 36 37 97.3%
Functions: 10 10 100.0%
Branches: 37 164 22.6%
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 #pragma once
16 #include <stdexcept>
17 #include <tkassert/Assert.hpp>
18 #include <tkwsm/Common/GeneralUtils.hpp>
19 #include <tkwsm/GraphTheoretic/GeneralStructs.hpp>
20
21 #include "Placement/Placement.hpp"
22
23 namespace tket {
24 namespace WeightedSubgraphMonomorphism {
25
26 /** Intended for use with Architecture and QubitGraph, which are similar
27 * but different types. Calculate new VertexWSM vertex labels.
28 */
29 template <class VertexType, class GraphType>
30 class RelabelledGraphWSM {
31 public:
32 512 explicit RelabelledGraphWSM(const GraphType& graph) {
33 // Get the new vertex integer labels.
34
2/4
✓ Branch 1 taken 256 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 256 times.
✗ Branch 5 not taken.
 512 m_original_vertices.reserve(boost::num_vertices(graph));
35 {
36
1/2
✓ Branch 1 taken 256 times.
✗ Branch 2 not taken.
 512 const auto vertex_iter_pair = boost::vertices(graph);
37 512 for (auto citer = vertex_iter_pair.first;
38
4/6
✓ Branch 1 taken 4066 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 4322 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 4066 times.
✓ Branch 7 taken 256 times.
 8644 citer != vertex_iter_pair.second; ++citer) {
39 // Add the vertex to the map keys.
40
3/6
✓ Branch 1 taken 4066 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 4066 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 4066 times.
✗ Branch 8 not taken.
 8132 m_old_to_new_vertex_map[graph[*citer]];
41 }
42 // Now add the new vertex labels.
43
2/2
✓ Branch 5 taken 4066 times.
✓ Branch 6 taken 256 times.
2/2
✓ Decision 'true' taken 4066 times.
✓ Decision 'false' taken 256 times.
 8644 for (auto& entry : m_old_to_new_vertex_map) {
44 8132 entry.second = m_original_vertices.size();
45
1/2
✓ Branch 1 taken 4066 times.
✗ Branch 2 not taken.
 8132 m_original_vertices.emplace_back(entry.first);
46 }
47 }
48 // Get the newly labelled edges.
49
1/2
✓ Branch 1 taken 256 times.
✗ Branch 2 not taken.
 512 const auto edge_iter_pair = boost::edges(graph);
50
3/4
✓ Branch 1 taken 5297 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 5041 times.
✓ Branch 4 taken 256 times.
0/1
? Decision couldn't be analyzed.
 10594 for (auto citer = edge_iter_pair.first; citer != edge_iter_pair.second;
51 10082 ++citer) {
52
2/4
✓ Branch 1 taken 5041 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 5041 times.
✗ Branch 5 not taken.
 10082 m_relabelled_edges_and_weights[get_edge(
53
3/6
✓ Branch 1 taken 5041 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 5041 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 5041 times.
✗ Branch 9 not taken.
 10082 get_relabelled_vertex(graph[boost::source(*citer, graph)]),
54
4/8
✓ Branch 1 taken 5041 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 5041 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 5041 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 5041 times.
✗ Branch 12 not taken.
 20164 get_relabelled_vertex(graph[boost::target(*citer, graph)]))] = 1;
55 }
56 // Now, classify the vertices into isolated and nonisolated categories
57
2/2
✓ Branch 5 taken 5041 times.
✓ Branch 6 taken 256 times.
2/2
✓ Decision 'true' taken 5041 times.
✓ Decision 'false' taken 256 times.
 10594 for (const auto& relabelled_edge_entry : m_relabelled_edges_and_weights) {
58 10082 const auto& relabelled_edge = relabelled_edge_entry.first;
59
1/2
✓ Branch 1 taken 5041 times.
✗ Branch 2 not taken.
 10082 m_relabelled_nonisolated_vertices.insert(relabelled_edge.first);
60
1/2
✓ Branch 1 taken 5041 times.
✗ Branch 2 not taken.
 10082 m_relabelled_nonisolated_vertices.insert(relabelled_edge.second);
61 }
62
2/2
✓ Branch 5 taken 4066 times.
✓ Branch 6 taken 256 times.
2/2
✓ Decision 'true' taken 4066 times.
✓ Decision 'false' taken 256 times.
 8644 for (const auto& entry : m_old_to_new_vertex_map) {
63
3/4
✓ Branch 1 taken 4066 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 12 times.
✓ Branch 4 taken 4054 times.
2/2
✓ Decision 'true' taken 24 times.
✓ Decision 'false' taken 8108 times.
 8132 if (m_relabelled_nonisolated_vertices.count(entry.second) == 0) {
64
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 24 m_relabelled_isolated_vertices.insert(entry.second);
65 }
66 }
67
1/104
✗ Branch 3 not taken.
✓ Branch 4 taken 256 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
✗ Branch 24 not taken.
✗ Branch 25 not taken.
✗ Branch 27 not taken.
✗ Branch 28 not taken.
✗ Branch 30 not taken.
✗ Branch 31 not taken.
✗ Branch 33 not taken.
✗ Branch 34 not taken.
✗ Branch 36 not taken.
✗ Branch 37 not taken.
✗ Branch 39 not taken.
✗ Branch 40 not taken.
✗ Branch 42 not taken.
✗ Branch 43 not taken.
✗ Branch 46 not taken.
✗ Branch 47 not taken.
✗ Branch 50 not taken.
✗ Branch 51 not taken.
✗ Branch 53 not taken.
✗ Branch 54 not taken.
✗ Branch 60 not taken.
✗ Branch 61 not taken.
✗ Branch 64 not taken.
✗ Branch 65 not taken.
✗ Branch 67 not taken.
✗ Branch 68 not taken.
✗ Branch 70 not taken.
✗ Branch 71 not taken.
✗ Branch 73 not taken.
✗ Branch 74 not taken.
✗ Branch 76 not taken.
✗ Branch 77 not taken.
✗ Branch 79 not taken.
✗ Branch 80 not taken.
✗ Branch 82 not taken.
✗ Branch 83 not taken.
✗ Branch 85 not taken.
✗ Branch 86 not taken.
✗ Branch 88 not taken.
✗ Branch 89 not taken.
✗ Branch 91 not taken.
✗ Branch 92 not taken.
✗ Branch 95 not taken.
✗ Branch 96 not taken.
✗ Branch 98 not taken.
✗ Branch 99 not taken.
✗ Branch 101 not taken.
✗ Branch 102 not taken.
✗ Branch 104 not taken.
✗ Branch 105 not taken.
✗ Branch 107 not taken.
✗ Branch 108 not taken.
✗ Branch 111 not taken.
✗ Branch 112 not taken.
✗ Branch 115 not taken.
✗ Branch 116 not taken.
✗ Branch 118 not taken.
✗ Branch 119 not taken.
✗ Branch 124 not taken.
✗ Branch 125 not taken.
✗ Branch 127 not taken.
✗ Branch 128 not taken.
✗ Branch 130 not taken.
✗ Branch 131 not taken.
✗ Branch 133 not taken.
✗ Branch 134 not taken.
✗ Branch 136 not taken.
✗ Branch 137 not taken.
✗ Branch 139 not taken.
✗ Branch 140 not taken.
✗ Branch 142 not taken.
✗ Branch 143 not taken.
✗ Branch 145 not taken.
✗ Branch 146 not taken.
✗ Branch 148 not taken.
✗ Branch 149 not taken.
✗ Branch 151 not taken.
✗ Branch 152 not taken.
✗ Branch 154 not taken.
✗ Branch 155 not taken.
✗ Branch 157 not taken.
✗ Branch 158 not taken.
✗ Branch 160 not taken.
✗ Branch 161 not taken.
✗ Branch 164 not taken.
✗ Branch 165 not taken.
✗ Branch 168 not taken.
✗ Branch 169 not taken.
✗ Branch 171 not taken.
✗ Branch 172 not taken.
 512 TKET_ASSERT(
68 m_old_to_new_vertex_map.size() ==
69 m_relabelled_isolated_vertices.size() +
70 m_relabelled_nonisolated_vertices.size());
71 512 }
72
73 1226 const GraphEdgeWeights& get_relabelled_edges_and_weights() const {
74 1226 return m_relabelled_edges_and_weights;
75 }
76
77 70254 const std::set<VertexWSM>& get_relabelled_isolated_vertices() const {
78 70254 return m_relabelled_isolated_vertices;
79 }
80
81 1666 const std::set<VertexWSM>& get_relabelled_nonisolated_vertices() const {
82 1666 return m_relabelled_nonisolated_vertices;
83 }
84
85 // element [i] is the vertex which has been relabelled i.
86 979164 const std::vector<VertexType>& get_original_vertices() const {
87 979164 return m_original_vertices;
88 }
89
90 10210 VertexWSM get_relabelled_vertex(const VertexType& original_vertex) const {
91 const auto v_opt =
92 10210 get_optional_value(m_old_to_new_vertex_map, original_vertex);
93 10210 if (!v_opt) {
94 ✗ throw std::runtime_error("Original vertex has no new label");
95 }
96 10210 return v_opt.value();
97 }
98
99 private:
100 std::vector<VertexType> m_original_vertices;
101 std::map<VertexType, VertexWSM> m_old_to_new_vertex_map;
102 std::set<VertexWSM> m_relabelled_isolated_vertices;
103 std::set<VertexWSM> m_relabelled_nonisolated_vertices;
104
105 // All edge weights will be 1, since we're only considering
106 // unweighted problems.
107 GraphEdgeWeights m_relabelled_edges_and_weights;
108 };
109
110 } // namespace WeightedSubgraphMonomorphism
111 } // namespace tket
112