GCC Code Coverage Report

Directory: ./
File: Graphs/ColouringPriority.cpp
Date: 2022-10-15 05:10:18
Exec Total Coverage
Lines: 45 45 100.0%
Functions: 5 6 83.3%
Branches: 30 44 68.2%
Decisions: 19 20 95.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 "ColouringPriority.hpp"
16
17 #include <sstream>
18 #include <stdexcept>
19 #include <tkassert/Assert.hpp>
20
21 #include "AdjacencyData.hpp"
22
23 using std::map;
24 using std::set;
25 using std::size_t;
26 using std::string;
27 using std::vector;
28
29 namespace tket {
30 namespace graphs {
31
32 302476 static void fill_initial_node_sequence(
33 ColouringPriority::Nodes& nodes, const AdjacencyData& adjacency_data,
34 const set<size_t>& vertices_in_component,
35 const set<size_t>& initial_clique) {
36 302476 nodes.reserve(vertices_in_component.size());
37 302476 nodes.clear();
38
39 try {
40
2/2
✓ Branch 4 taken 336746 times.
✓ Branch 5 taken 302476 times.
2/2
✓ Decision 'true' taken 336746 times.
✓ Decision 'false' taken 302476 times.
 639222 for (size_t clique_vertex : initial_clique) {
41 // GCOVR_EXCL_START
42 if (vertices_in_component.count(clique_vertex) == 0) {
43 std::stringstream ss;
44 ss << "initial clique vertex " << clique_vertex
45 << " is not in this component";
46 throw std::runtime_error(ss.str());
47 }
48 // GCOVR_EXCL_STOP
49
1/2
✓ Branch 1 taken 336746 times.
✗ Branch 2 not taken.
 336746 nodes.emplace_back();
50 336746 nodes.back().vertex = clique_vertex;
51 }
52 // Now, we do a breadth-first traversal of the remaining vertices,
53 // adding all vertices only one step away from the current set.
54 302476 size_t current_nodes_begin = 0;
55
56
1/2
✓ Branch 1 taken 302476 times.
✗ Branch 2 not taken.
 302476 set<size_t> vertices_seen = initial_clique;
57 302476 set<size_t> vertices_to_add;
58
59
1/2
✓ Branch 1 taken 331813 times.
✗ Branch 2 not taken.
1/2
✓ Decision 'true' taken 331813 times.
✗ Decision 'false' not taken.
 331813 for (size_t counter = 0; counter < 2 * vertices_in_component.size();
60 ++counter) {
61 331813 const size_t current_nodes_end = nodes.size();
62
63
2/2
✓ Branch 0 taken 484931 times.
✓ Branch 1 taken 331813 times.
2/2
✓ Decision 'true' taken 484931 times.
✓ Decision 'false' taken 331813 times.
 816744 for (size_t i = current_nodes_begin; i < current_nodes_end; ++i) {
64
1/2
✓ Branch 2 taken 484931 times.
✗ Branch 3 not taken.
 484931 const auto& neighbours = adjacency_data.get_neighbours(nodes[i].vertex);
65
2/2
✓ Branch 5 taken 754004 times.
✓ Branch 6 taken 484931 times.
2/2
✓ Decision 'true' taken 754004 times.
✓ Decision 'false' taken 484931 times.
 1238935 for (size_t neighbour : neighbours) {
66
3/4
✓ Branch 1 taken 754004 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 197503 times.
✓ Branch 4 taken 556501 times.
2/2
✓ Decision 'true' taken 197503 times.
✓ Decision 'false' taken 556501 times.
 754004 if (vertices_seen.count(neighbour) == 0) {
67
1/2
✓ Branch 1 taken 197503 times.
✗ Branch 2 not taken.
 197503 vertices_to_add.insert(neighbour);
68 }
69 }
70 }
71
2/2
✓ Branch 1 taken 302476 times.
✓ Branch 2 taken 29337 times.
2/2
✓ Decision 'true' taken 302476 times.
✓ Decision 'false' taken 29337 times.
 331813 if (vertices_to_add.empty()) {
72 302476 break;
73 }
74
2/2
✓ Branch 4 taken 148185 times.
✓ Branch 5 taken 29337 times.
2/2
✓ Decision 'true' taken 148185 times.
✓ Decision 'false' taken 29337 times.
 177522 for (size_t neighbour : vertices_to_add) {
75
1/2
✓ Branch 1 taken 148185 times.
✗ Branch 2 not taken.
 148185 vertices_seen.insert(neighbour);
76
1/2
✓ Branch 1 taken 148185 times.
✗ Branch 2 not taken.
 148185 nodes.emplace_back();
77 148185 nodes.back().vertex = neighbour;
78 }
79 29337 vertices_to_add.clear();
80 29337 current_nodes_begin = current_nodes_end;
81 }
82 // GCOVR_EXCL_START
83 if (nodes.size() != vertices_in_component.size()) {
84 throw std::runtime_error(
85 "Final size check: number of filled "
86 "nodes does not match number of vertices in this component");
87 }
88 // GCOVR_EXCL_STOP
89
0/2
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 302476 } catch (const std::exception& e) {
90 // GCOVR_EXCL_START
91 TKET_ASSERT(
92 AssertMessage()
93 << "ColouringPriority: fill_initial_node_sequence: initial"
94 << " clique size " << initial_clique.size() << ", "
95 << vertices_in_component.size() << " vertices in"
96 << " this component (full graph has "
97 << adjacency_data.get_number_of_vertices() << " vertices)."
98 << " So far, filled " << nodes.size() << " nodes."
99 << " Error: " << e.what());
100 // GCOVR_EXCL_STOP
101 }
102 302476 }
103
104 // Quadratic, but we're not afraid; the main brute force colouring is
105 // exponential! Assumes that "fill_initial_node_sequence" has just been called.
106 // Fills in "earlier_neighbour_node_indices".
107 302476 static void fill_node_dependencies(
108 ColouringPriority::Nodes& nodes, const AdjacencyData& adjacency_data) {
109
2/2
✓ Branch 1 taken 182455 times.
✓ Branch 2 taken 302476 times.
2/2
✓ Decision 'true' taken 182455 times.
✓ Decision 'false' taken 302476 times.
 484931 for (size_t node_index = 1; node_index < nodes.size(); ++node_index) {
110 182455 auto& this_node = nodes[node_index];
111
112
2/2
✓ Branch 0 taken 2879499 times.
✓ Branch 1 taken 182455 times.
2/2
✓ Decision 'true' taken 2879499 times.
✓ Decision 'false' taken 182455 times.
 3061954 for (size_t other_index = 0; other_index < node_index; ++other_index) {
113
3/4
✓ Branch 1 taken 2879499 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 377002 times.
✓ Branch 4 taken 2502497 times.
2/2
✓ Decision 'true' taken 377002 times.
✓ Decision 'false' taken 2502497 times.
 2879499 if (adjacency_data.edge_exists(
114 2879499 this_node.vertex, nodes[other_index].vertex)) {
115
1/2
✓ Branch 1 taken 377002 times.
✗ Branch 2 not taken.
 377002 this_node.earlier_neighbour_node_indices.emplace_back(other_index);
116 }
117 }
118 }
119 302476 }
120
121 642548 const ColouringPriority::Nodes& ColouringPriority::get_nodes() const {
122 642548 return m_nodes;
123 }
124
125 // GCOVR_EXCL_START
126 // currently used only within a tket assert macro
127 string ColouringPriority::print_raw_data(bool relabel_to_simplify) const {
128 map<size_t, size_t> old_vertex_to_new_vertex;
129 if (relabel_to_simplify) {
130 for (size_t i = 0; i < m_nodes.size(); ++i) {
131 old_vertex_to_new_vertex[m_nodes[i].vertex] = i;
132 }
133 } else {
134 for (const auto& node : m_nodes) {
135 const auto v = node.vertex;
136 old_vertex_to_new_vertex[v] = v;
137 }
138 }
139 map<size_t, set<size_t>> data;
140 for (const auto& node : m_nodes) {
141 const auto this_v = old_vertex_to_new_vertex.at(node.vertex);
142 const auto& earlier_v_indices = node.earlier_neighbour_node_indices;
143 for (size_t i : earlier_v_indices) {
144 const auto other_v = old_vertex_to_new_vertex.at(m_nodes[i].vertex);
145 data[this_v].insert(other_v);
146 data[other_v].insert(this_v);
147 }
148 }
149 // Compress: remove (i,j) edges if i>j.
150 {
151 vector<size_t> v_to_erase;
152 for (auto& entry : data) {
153 v_to_erase.clear();
154 for (auto v : entry.second) {
155 if (v < entry.first) {
156 v_to_erase.push_back(v);
157 }
158 }
159 for (auto v : v_to_erase) {
160 entry.second.erase(v);
161 }
162 }
163 }
164 std::stringstream ss;
165
166 ss << "\nNeighbours:\nconst std::map<std::size_t, std::vector<std::size_t>> "
167 "data { ";
168 for (const auto& entry : data) {
169 if (!entry.second.empty()) {
170 ss << "\n { " << entry.first << ", { ";
171 for (auto v : entry.second) {
172 ss << v << ", ";
173 }
174 ss << "} },";
175 }
176 }
177 ss << "\n};\n\n";
178 return ss.str();
179 }
180 // GCOVR_EXCL_STOP
181
182 302476 ColouringPriority::ColouringPriority(
183 const AdjacencyData& adjacency_data,
184 302476 const set<size_t>& vertices_in_component, const set<size_t>& initial_clique)
185 302476 : m_initial_clique(initial_clique) {
186 302476 fill_initial_node_sequence(
187
1/2
✓ Branch 1 taken 302476 times.
✗ Branch 2 not taken.
 302476 m_nodes, adjacency_data, vertices_in_component, initial_clique);
188
189
1/2
✓ Branch 1 taken 302476 times.
✗ Branch 2 not taken.
 302476 fill_node_dependencies(m_nodes, adjacency_data);
190 302476 }
191
192 15078 const set<size_t>& ColouringPriority::get_initial_clique() const {
193 15078 return m_initial_clique;
194 }
195
196 } // namespace graphs
197 } // namespace tket
198