GCC Code Coverage Report

Directory: ./
File: Graphs/BruteForceColouring.cpp
Date: 2022-10-15 05:10:18
Warnings: 1 unchecked decisions!
Exec Total Coverage
Lines: 82 88 93.2%
Functions: 8 8 100.0%
Branches: 57 86 66.3%
Decisions: 30 34 88.2%
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 "BruteForceColouring.hpp"
16
17 #include <set>
18 #include <sstream>
19 #include <stdexcept>
20 #include <tkassert/Assert.hpp>
21
22 #include "ColouringPriority.hpp"
23
24 using std::map;
25 using std::set;
26 using std::size_t;
27 using std::vector;
28
29 namespace tket {
30 namespace graphs {
31
32 struct BruteForceColouring::Impl {
33 struct NodeColouringData {
34 vector<size_t> allowed_colours;
35
36 // The index in "allowed_colours", not the actual colour
37 size_t current_colour_index = 0;
38
39 1220269 bool is_valid_colour() const {
40 1220269 return current_colour_index < allowed_colours.size();
41 }
42
43 2893890 size_t get_colour() const { return allowed_colours[current_colour_index]; }
44 };
45
46 // This exactly mirrors the nodes in the ColouringPriority object;
47 // it is just extra data specifically related to colouring.
48 vector<NodeColouringData> colouring_data;
49
50 // KEY: is the vertex, VALUE: the colour
51 map<size_t, size_t> colours;
52
53 // Fills in the colour possibilities,
54 // possibly increasing suggested_number_of_colours.
55 // Returns false if it failed.
56 14647 bool initial_colouring_setup(
57 const ColouringPriority& priority, size_t& suggested_number_of_colours) {
58
1/2
✓ Branch 1 taken 14647 times.
✗ Branch 2 not taken.
 14647 const auto& initial_clique = priority.get_initial_clique();
59
60 14647 suggested_number_of_colours =
61 14647 std::max(suggested_number_of_colours, initial_clique.size());
62
63
1/2
✓ Branch 1 taken 14647 times.
✗ Branch 2 not taken.
 14647 const auto& nodes = priority.get_nodes();
64
65
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 14647 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 14647 times.
 14647 if (suggested_number_of_colours > nodes.size()) {
66 ✗ return false;
67 }
68
1/2
✓ Branch 2 taken 14647 times.
✗ Branch 3 not taken.
 14647 colouring_data.resize(nodes.size());
69
70
2/2
✓ Branch 1 taken 41088 times.
✓ Branch 2 taken 14647 times.
2/2
✓ Decision 'true' taken 41088 times.
✓ Decision 'false' taken 14647 times.
 55735 for (size_t i = 0; i < initial_clique.size(); ++i) {
71
1/2
✓ Branch 2 taken 41088 times.
✗ Branch 3 not taken.
 41088 colouring_data[i].allowed_colours.assign(1, i);
72
1/2
✓ Branch 2 taken 41088 times.
✗ Branch 3 not taken.
 41088 colours[nodes[i].vertex] = i;
73 }
74
75 // Now, recursively keep increasing the number of colours until we at least
76 // have nonempty colour possibility lists. (It may still be impossible, of
77 // course, due to the detailed graph structure).
78
79 14647 set<size_t> forbidden_colours;
80
81
2/2
✓ Branch 2 taken 148143 times.
✓ Branch 3 taken 14647 times.
2/2
✓ Decision 'true' taken 148143 times.
✓ Decision 'false' taken 14647 times.
 162790 for (size_t i = initial_clique.size(); i < nodes.size(); ++i) {
82 148143 forbidden_colours.clear();
83
84
2/2
✓ Branch 6 taken 322820 times.
✓ Branch 7 taken 148143 times.
2/2
✓ Decision 'true' taken 322820 times.
✓ Decision 'false' taken 148143 times.
 470963 for (size_t node_index : nodes[i].earlier_neighbour_node_indices) {
85 const auto& earlier_colours =
86 322820 colouring_data[node_index].allowed_colours;
87
88 // It is only the initial CLIQUE vertices which have fixed colours;
89 // as the number of possible colours increases, EVERY other vertex
90 // has more colour possibilities; so we must NOT think that,
91 // just because CURRENTLY a vertex has only one colour,
92 // that it will ALWAYS be that way!
93
3/4
✓ Branch 2 taken 322820 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 136833 times.
✓ Branch 5 taken 185987 times.
2/2
✓ Decision 'true' taken 136833 times.
✓ Decision 'false' taken 185987 times.
 322820 if (initial_clique.count(nodes[node_index].vertex) != 0) {
94 TKET_ASSERT(earlier_colours.size() == 1);
95
1/2
✓ Branch 2 taken 136833 times.
✗ Branch 3 not taken.
 136833 forbidden_colours.insert(earlier_colours[0]);
96 }
97 }
98 148143 auto& possible_colours = colouring_data[i].allowed_colours;
99 148143 possible_colours.clear();
100
2/2
✓ Branch 0 taken 469845 times.
✓ Branch 1 taken 148143 times.
2/2
✓ Decision 'true' taken 469845 times.
✓ Decision 'false' taken 148143 times.
 617988 for (size_t col = 0; col < suggested_number_of_colours; ++col) {
101
3/4
✓ Branch 1 taken 469845 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 333012 times.
✓ Branch 4 taken 136833 times.
2/2
✓ Decision 'true' taken 333012 times.
✓ Decision 'false' taken 136833 times.
 469845 if (forbidden_colours.count(col) == 0) {
102
1/2
✓ Branch 1 taken 333012 times.
✗ Branch 2 not taken.
 333012 possible_colours.push_back(col);
103 }
104 }
105
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 148143 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 148143 times.
 148143 if (possible_colours.empty()) {
106 ✗ ++suggested_number_of_colours;
107 ✗ return initial_colouring_setup(priority, suggested_number_of_colours);
108 }
109 }
110 14647 return true;
111 14647 }
112
113 14647 void fill_colour_map(const ColouringPriority& priority) {
114 14647 const auto& nodes = priority.get_nodes();
115
2/2
✓ Branch 1 taken 189231 times.
✓ Branch 2 taken 14647 times.
2/2
✓ Decision 'true' taken 189231 times.
✓ Decision 'false' taken 14647 times.
 203878 for (size_t i = 0; i < nodes.size(); ++i) {
116 189231 colours[nodes[i].vertex] = colouring_data[i].get_colour();
117 }
118 14647 }
119
120 15078 bool attempt_brute_force_colouring(const ColouringPriority& priority) {
121
2/2
✓ Branch 4 taken 194173 times.
✓ Branch 5 taken 15078 times.
2/2
✓ Decision 'true' taken 194173 times.
✓ Decision 'false' taken 15078 times.
 209251 for (auto& data : colouring_data) {
122 194173 data.current_colour_index = 0;
123 }
124 15078 const auto& nodes = priority.get_nodes();
125 15078 const size_t number_of_nodes = nodes.size();
126
127 15078 for (size_t current_node_index = 0;;) {
128 1220269 const auto& current_node = nodes[current_node_index];
129 1220269 auto& current_colouring_node = colouring_data[current_node_index];
130
131
2/2
✓ Branch 1 taken 949390 times.
✓ Branch 2 taken 270879 times.
2/2
✓ Decision 'true' taken 949390 times.
✓ Decision 'false' taken 270879 times.
 1220269 if (current_colouring_node.is_valid_colour()) {
132 // We have a candidate colour, now test it for consistency.
133 949390 const auto current_col = current_colouring_node.get_colour();
134 949390 bool colour_is_impossible = false;
135
136 // TODO: would a set of colours be faster here?
137 949390 for (size_t earlier_node_index :
138
2/2
✓ Branch 5 taken 1755269 times.
✓ Branch 6 taken 459679 times.
 3164338 current_node.earlier_neighbour_node_indices) {
139
2/2
✓ Branch 2 taken 489711 times.
✓ Branch 3 taken 1265558 times.
2/2
✓ Decision 'true' taken 489711 times.
✓ Decision 'false' taken 1265558 times.
 1755269 if (colouring_data[earlier_node_index].get_colour() == current_col) {
140 489711 colour_is_impossible = true;
141 489711 break;
142 }
143 }
144
2/2
✓ Branch 0 taken 459679 times.
✓ Branch 1 taken 489711 times.
2/2
✓ Decision 'true' taken 459679 times.
✓ Decision 'false' taken 489711 times.
 949390 if (!colour_is_impossible) {
145 // Advance to the next node to colour.
146 459679 ++current_node_index;
147
2/2
✓ Branch 0 taken 445032 times.
✓ Branch 1 taken 14647 times.
2/2
✓ Decision 'true' taken 445032 times.
✓ Decision 'false' taken 14647 times.
 459679 if (current_node_index < number_of_nodes) {
148 445032 colouring_data[current_node_index].current_colour_index = 0;
149 445032 continue;
150 }
151 // We've hit the end! We are finished.
152 14647 return true;
153 }
154 489711 ++current_colouring_node.current_colour_index;
155 489711 continue;
156 489711 }
157
158 // We must backtrack.
159
2/2
✓ Branch 0 taken 431 times.
✓ Branch 1 taken 270448 times.
2/2
✓ Decision 'true' taken 431 times.
✓ Decision 'false' taken 270448 times.
 270879 if (current_node_index == 0) {
160 431 return false;
161 }
162 270448 --current_node_index;
163
164 // Advance the colour.
165 270448 ++colouring_data[current_node_index].current_colour_index;
166 1205191 }
167 // We cannot actually reach here, the outer loop only returns, never breaks.
168 }
169 };
170
171 302476 BruteForceColouring::~BruteForceColouring() {}
172
173 302476 BruteForceColouring::BruteForceColouring(
174 302476 const ColouringPriority& priority, size_t suggested_number_of_colours)
175 302476 : m_pimpl(std::make_unique<BruteForceColouring::Impl>()) {
176
1/2
✓ Branch 1 taken 302476 times.
✗ Branch 2 not taken.
 302476 const auto number_of_nodes = priority.get_nodes().size();
177
2/2
✓ Branch 0 taken 287829 times.
✓ Branch 1 taken 14647 times.
0/1
? Decision couldn't be analyzed.
 302476 if (suggested_number_of_colours >= number_of_nodes) {
178 // We've been given permission to use many colours;
179 // so just use them all!
180
2/2
✓ Branch 0 taken 295700 times.
✓ Branch 1 taken 287829 times.
2/2
✓ Decision 'true' taken 295700 times.
✓ Decision 'false' taken 287829 times.
 583529 for (size_t i = 0; i < number_of_nodes; ++i) {
181
2/4
✓ Branch 2 taken 295700 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 295700 times.
✗ Branch 7 not taken.
 295700 m_pimpl->colours[priority.get_nodes()[i].vertex] = i;
182 }
183 302476 return;
184 }
185
186 14647 const auto initial_suggested_number_of_colours = suggested_number_of_colours;
187
188 try {
189
2/4
✓ Branch 2 taken 14647 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 14647 times.
 14647 if (!m_pimpl->initial_colouring_setup(
190 priority, suggested_number_of_colours)) {
191 ✗ throw std::runtime_error("initial_colouring_setup failed");
192 }
193
194 // From now on, every time we fail to colour with the specified number,
195 // we simply have to add the extra colour onto
196 // each list of possible colours;
197 // no need to redo "initial_colouring_setup".
198
199
1/2
✓ Branch 0 taken 15078 times.
✗ Branch 1 not taken.
 15078 for (; suggested_number_of_colours <= number_of_nodes;
200 ++suggested_number_of_colours) {
201
3/4
✓ Branch 2 taken 15078 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 14647 times.
✓ Branch 5 taken 431 times.
 15078 if (m_pimpl->attempt_brute_force_colouring(priority)) {
202 // We've succeeded!
203
1/2
✓ Branch 2 taken 14647 times.
✗ Branch 3 not taken.
 14647 m_pimpl->fill_colour_map(priority);
204 14647 return;
205 }
206 // It's impossible with this number of colours,
207 // so try again with one more.
208 // If we were really fancy we might consider
209 // a binary search on the number of colours.
210
3/4
✓ Branch 1 taken 431 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 3678 times.
✓ Branch 5 taken 431 times.
 4109 for (size_t i = priority.get_initial_clique().size(); i < number_of_nodes;
211 ++i) {
212
1/2
✓ Branch 3 taken 3678 times.
✗ Branch 4 not taken.
 3678 m_pimpl->colouring_data[i].allowed_colours.push_back(
213 suggested_number_of_colours);
214 }
215 }
216 ✗ throw std::runtime_error("suggested_number_of_colours hit number_of_nodes");
217 ✗ } catch (const std::exception& e) {
218 // GCOVR_EXCL_START
219 TKET_ASSERT(
220 AssertMessage() << "initial_suggested_number_of_colours = "
221 << initial_suggested_number_of_colours
222 << ", reached suggested_number_of_colours = "
223 << suggested_number_of_colours << ", had "
224 << number_of_nodes << " nodes. Error: " << e.what()
225 << priority.print_raw_data());
226 // GCOVR_EXCL_STOP
227 }
228 }
229
230 302476 const map<size_t, size_t>& BruteForceColouring::get_colours() const {
231 302476 return m_pimpl->colours;
232 }
233
234 } // namespace graphs
235 } // namespace tket
236