GCC Code Coverage Report

Directory: ./
File: Graphs/GraphColouring.cpp
Date: 2022-10-15 05:10:18
Exec Total Coverage
Lines: 54 54 100.0%
Functions: 7 7 100.0%
Branches: 36 64 56.2%
Decisions: 11 12 91.7%
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 "GraphColouring.hpp"
16
17 #include <algorithm>
18 #include <limits>
19 #include <set>
20 #include <sstream>
21 #include <stdexcept>
22 #include <tkassert/Assert.hpp>
23
24 #include "AdjacencyData.hpp"
25 #include "BruteForceColouring.hpp"
26 #include "ColouringPriority.hpp"
27 #include "GraphRoutines.hpp"
28 #include "LargeCliquesResult.hpp"
29
30 using std::exception;
31 using std::map;
32 using std::runtime_error;
33 using std::set;
34 using std::string;
35 using std::stringstream;
36 using std::vector;
37
38 namespace tket {
39 namespace graphs {
40
41 30544 string GraphColouringResult::to_string() const {
42
1/2
✓ Branch 1 taken 30544 times.
✗ Branch 2 not taken.
 30544 stringstream ss;
43
4/8
✓ Branch 1 taken 30544 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 30544 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 30544 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 30544 times.
✗ Branch 12 not taken.
 30544 ss << "\nColouring: " << colours.size() << " vertices, " << number_of_colours
44
1/2
✓ Branch 1 taken 30544 times.
✗ Branch 2 not taken.
 30544 << " colours : [ ";
45
46
2/2
✓ Branch 5 taken 1337830 times.
✓ Branch 6 taken 30544 times.
2/2
✓ Decision 'true' taken 1337830 times.
✓ Decision 'false' taken 30544 times.
 1368374 for (auto col : colours) {
47
2/4
✓ Branch 1 taken 1337830 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1337830 times.
✗ Branch 5 not taken.
 1337830 ss << col << ", ";
48 }
49
1/2
✓ Branch 1 taken 30544 times.
✗ Branch 2 not taken.
 30544 ss << "]";
50
1/2
✓ Branch 1 taken 30544 times.
✗ Branch 2 not taken.
 61088 return ss.str();
51 30544 }
52
53 16990 GraphColouringResult::GraphColouringResult() {}
54
55 174 GraphColouringResult::GraphColouringResult(const vector<std::size_t>& _colours)
56 174 : colours(_colours) {
57
1/2
✓ Branch 1 taken 174 times.
✗ Branch 2 not taken.
1/2
✓ Decision 'true' taken 174 times.
✗ Decision 'false' not taken.
 174 if (!colours.empty()) {
58
1/2
✓ Branch 3 taken 174 times.
✗ Branch 4 not taken.
 174 number_of_colours = 1 + *std::max_element(colours.cbegin(), colours.cend());
59 }
60 174 }
61
62 // Also updates the number of colours used in "result".
63 302476 static void colour_single_component(
64 const AdjacencyData& adjacency_data,
65 const vector<set<std::size_t>>& connected_components,
66 const vector<set<std::size_t>>& cliques, std::size_t component_index,
67 GraphColouringResult& result) {
68 302476 result.number_of_colours =
69 302476 std::max(result.number_of_colours, cliques[component_index].size());
70
71 const ColouringPriority colouring_priority(
72 302476 adjacency_data, connected_components[component_index],
73
1/2
✓ Branch 3 taken 302476 times.
✗ Branch 4 not taken.
 302476 cliques[component_index]);
74
75 const BruteForceColouring brute_force_colouring(
76
1/2
✓ Branch 1 taken 302476 times.
✗ Branch 2 not taken.
 302476 colouring_priority, result.number_of_colours);
77
78
1/2
✓ Branch 1 taken 302476 times.
✗ Branch 2 not taken.
 302476 const auto& partial_colour_map = brute_force_colouring.get_colours();
79
80
2/2
✓ Branch 5 taken 484931 times.
✓ Branch 6 taken 302476 times.
2/2
✓ Decision 'true' taken 484931 times.
✓ Decision 'false' taken 302476 times.
 787407 for (const auto& entry : partial_colour_map) {
81 484931 const auto& vertex = entry.first;
82 484931 const auto& colour = entry.second;
83 484931 result.number_of_colours = std::max(result.number_of_colours, colour + 1);
84
85 // GCOVR_EXCL_START
86 try {
87 if (vertex >= result.colours.size()) {
88 throw runtime_error("illegal vertex index");
89 }
90 auto& colour_to_assign = result.colours[vertex];
91 if (colour_to_assign < result.colours.size()) {
92 stringstream ss;
93 ss << "colour already assigned! Existing colour " << colour_to_assign;
94 throw runtime_error(ss.str());
95 }
96 colour_to_assign = colour;
97 } catch (const exception& e) {
98 TKET_ASSERT(
99 AssertMessage() << "colouring single component " << component_index
100 << " returned vertex " << vertex << " with colour "
101 << colour << " : " << e.what());
102 }
103 // GCOVR_EXCL_STOP
104 }
105 302476 }
106
107 // Check that everything was coloured,
108 // and we do have the correct number of colours
109 // (we might not have used all the colours we were allowed).
110 // (Don't bother trying to remove colour gaps, there shouldn't be any).
111 16983 static void check_final_colouring(GraphColouringResult& result) {
112 16983 result.number_of_colours = 0;
113
2/2
✓ Branch 1 taken 484931 times.
✓ Branch 2 taken 16983 times.
2/2
✓ Decision 'true' taken 484931 times.
✓ Decision 'false' taken 16983 times.
 501914 for (std::size_t i = 0; i < result.colours.size(); ++i) {
114 484931 const auto colour = result.colours[i];
115 // GCOVR_EXCL_START
116 if (colour >= result.colours.size()) {
117 stringstream ss;
118 ss << "vertex " << i << " has unassigned or illegal colour " << colour;
119 throw runtime_error(ss.str());
120 }
121 // GCOVR_EXCL_STOP
122 484931 result.number_of_colours = std::max(result.number_of_colours, colour + 1);
123 }
124 16983 }
125
126 16983 GraphColouringResult GraphColouringRoutines::get_colouring(
127 const AdjacencyData& adjacency_data) {
128 const auto connected_components =
129
1/2
✓ Branch 1 taken 16983 times.
✗ Branch 2 not taken.
 16983 GraphRoutines::get_connected_components(adjacency_data);
130
1/2
✓ Branch 3 taken 16983 times.
✗ Branch 4 not taken.
 16983 vector<set<std::size_t>> cliques(connected_components.size());
131
1/2
✓ Branch 3 taken 16983 times.
✗ Branch 4 not taken.
 16983 vector<std::size_t> component_indices(connected_components.size());
132
133 try {
134
2/2
✓ Branch 1 taken 302476 times.
✓ Branch 2 taken 16983 times.
2/2
✓ Decision 'true' taken 302476 times.
✓ Decision 'false' taken 16983 times.
 319459 for (std::size_t i = 0; i < connected_components.size(); ++i) {
135 const LargeCliquesResult cliques_in_this_component(
136
1/2
✓ Branch 2 taken 302476 times.
✗ Branch 3 not taken.
 302476 adjacency_data, connected_components[i]);
137
138 // GCOVR_EXCL_START
139 if (cliques_in_this_component.cliques.empty()) {
140 stringstream ss;
141 ss << "component " << i << " has " << connected_components[i].size()
142 << " vertices, but couldn't find a clique!";
143 throw runtime_error(ss.str());
144 }
145 // GCOVR_EXCL_STOP
146
1/2
✓ Branch 3 taken 302476 times.
✗ Branch 4 not taken.
 302476 cliques[i] = cliques_in_this_component.cliques[0];
147 302476 component_indices[i] = i;
148 302476 }
149
150 // Now, we might as well start with the component containing the LARGEST
151 // clique first (since, colouring becomes easier with more colours, and once
152 // we've coloured one component, no point in trying to colour the others
153 // with fewer colours).
154
1/2
✓ Branch 3 taken 16983 times.
✗ Branch 4 not taken.
 16983 std::sort(
155 component_indices.begin(), component_indices.end(),
156 2078306 [&cliques](std::size_t lhs, std::size_t rhs) {
157 1039153 return cliques[lhs].size() > cliques[rhs].size();
158 });
159
160
1/2
✓ Branch 1 taken 16983 times.
✗ Branch 2 not taken.
 16983 GraphColouringResult result;
161
1/2
✓ Branch 1 taken 16983 times.
✗ Branch 2 not taken.
 16983 result.colours.assign(
162 adjacency_data.get_number_of_vertices(),
163
1/2
✓ Branch 2 taken 16983 times.
✗ Branch 3 not taken.
 16983 std::numeric_limits<std::size_t>::max());
164
165
2/2
✓ Branch 5 taken 302476 times.
✓ Branch 6 taken 16983 times.
2/2
✓ Decision 'true' taken 302476 times.
✓ Decision 'false' taken 16983 times.
 319459 for (auto component_index : component_indices) {
166
1/2
✓ Branch 1 taken 302476 times.
✗ Branch 2 not taken.
 302476 colour_single_component(
167 adjacency_data, connected_components, cliques, component_index,
168 result);
169 }
170
1/2
✓ Branch 1 taken 16983 times.
✗ Branch 2 not taken.
 16983 check_final_colouring(result);
171 16983 return result;
172
0/2
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 16983 } catch (const exception& e) {
173 // GCOVR_EXCL_START
174 TKET_ASSERT(
175 AssertMessage() << "We had " << connected_components.size()
176 << " connected components, "
177 << adjacency_data.get_number_of_vertices()
178 << " vertices in total: " << e.what());
179 // Some compilers error with "non-void function does not
180 // return a value in all control paths..."
181 return GraphColouringResult();
182 // GCOVR_EXCL_STOP
183 }
184 16983 }
185
186 } // namespace graphs
187 } // namespace tket
188