GCC Code Coverage Report

Directory: ./
File: Graphs/include/Graphs/Utils_impl.hpp
Date: 2022-10-15 05:10:18
Warnings: 1 unchecked decisions!
Exec Total Coverage
Lines: 60 65 92.3%
Functions: 30 55 54.5%
Branches: 33 52 63.5%
Decisions: 13 16 81.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 #pragma once
16
17 #include <algorithm>
18 #include <boost/iterator/transform_iterator.hpp>
19 #include <boost/range/iterator_range_core.hpp>
20 #include <map>
21 #include <set>
22 #include <type_traits>
23 #include <utility>
24
25 #include "Utils/BiMapHeaders.hpp"
26 #include "Utils/GraphHeaders.hpp"
27
28 // Implemetation details of `Graphs/Utils.hpp`
29 namespace tket::graphs::utils {
30
31 // ::detail includes all internal implementation-specific details
32 namespace detail {
33
34 // Type synonyms for many often-used BGL types
35 template <typename T>
36 using vertex =
37 typename boost::graph_traits<std::remove_reference_t<T>>::vertex_descriptor;
38 template <typename T>
39 using edge =
40 typename boost::graph_traits<std::remove_reference_t<T>>::edge_descriptor;
41 template <typename T>
42 using vertex_index_pmap = typename boost::property_map<
43 std::remove_reference_t<T>, boost::vertex_index_t>::type;
44 template <typename T>
45 using vertex_index =
46 typename boost::property_traits<vertex_index_pmap<T>>::value_type;
47
48 /* Compile-time boolean flag to check if boost graph type is
49 * directed or undirected graph
50 *
51 * Template Argument Graph is the boost type of the graph to be checked
52 * the second (directedness tag) should be left to default to be inferred
53 * by the compiler ("SFINAE")
54 *
55 * This is available in the public interface as is_directed<Graph> (see
56 * `Utils.hpp`)
57 */
58 template <
59 typename Graph, typename directed_category = typename boost::graph_traits<
60 std::remove_reference_t<Graph>>::directed_category>
61 struct is_directed_struct {
62 static const bool value = true;
63 };
64 template <typename Graph>
65 struct is_directed_struct<Graph, boost::undirected_tag> {
66 static const bool value = false;
67 };
68
69 /* Compile-time boolean used in template specialisations
70 * and graph_utils_helper_with_map to infer whether the Graph type supports
71 * integer indexing
72 *
73 * has_integral_index<Graph, PMap> is true iff
74 * either the vertex_descriptor of Graph are integers (i.e. VertexList = vecS)
75 * or an explicit property map PMap is provided with integral values
76 *
77 * Template argument Graph is the boost type of the graph to be checked
78 * PMap is the optional property map to provide integral index values
79 * The third argument should always be left to default, used for type inference
80 * ("SFINAE")
81 */
82 template <typename Graph, typename PMap = void, typename = void>
83 struct has_integral_index_struct {
84 static const bool value = false;
85 };
86 template <typename Graph>
87 struct has_integral_index_struct<
88 Graph, void, std::enable_if_t<std::is_integral_v<vertex<Graph>>>> {
89 static const bool value = true;
90 };
91 template <typename Graph, typename PMap>
92 struct has_integral_index_struct<
93 Graph, PMap,
94 std::enable_if_t<std::is_integral_v<typename PMap::mapped_type>>> {
95 static const bool value = true;
96 };
97 template <typename Graph, typename PMap = void>
98 constexpr bool has_integral_index =
99 has_integral_index_struct<Graph, PMap>::value;
100
101 // less than comparison using key as compared values
102 template <typename V, typename Func>
103 932 auto lt_with_key(const Func& key) {
104 34733 return [&key](const V& v1, const V& v2) { return key(v1) < key(v2); };
105 }
106
107 /* This class, along with their inherited classes and template specialisations
108 * below implement the graphs::utils helper functions, defined further below.
109 *
110 * CLASS HIERARCHY
111 * ---------------
112 * +---------------------+ +---------------------------+
113 * Base classes: | graph_utils_base | | graph_utils_base_with_ind |
114 * +---------------------+ +---------------------------+
115 * | | | |
116 * v v v v
117 * Container-specific +---------+ +---------+ +---------+ +---------+
118 * classes | _helper | | _helper | | _helper | | _helper |
119 * (pmap / indexable) | YES/NO | | NO/NO | | YES/YES | | NO/YES |
120 * +---------+ +---------+ +---------+ +---------+
121 * | | | | | | | |
122 * | | | | +-------+ | | | |
123 * Child class to be used | | | +->| _impl |<--+ | | |
124 * in utils | +------------>| |<--------------+ |
125 * | | +-------+ | |
126 * v v v v
127 * Container-specific +---------+ +---------+ +---------+ +---------+
128 * classes with added | _helper | | _helper | | _helper | | _helper |
129 * support for maps |_with_map| |_with_map| |_with_map| |_with_map|
130 * (pmap / indexable) | YES/NO | | NO/NO | | YES/YES | | NO/YES |
131 * +---------+ +---------+ +---------+ +---------+
132 * | | | |
133 * | | +---------+ | |
134 * Child class to be used | +->| _impl |<----+ |
135 * in utils with map support +------------>|_with_map|<---------------+
136 * +---------+
137 *
138 * graph_utils_base and graph_utils_base_with_ind implement the functionality
139 * that is shared among all vertex container types (i.e. most of the code logic)
140 *
141 * Impl must be a subclass of this and must implement
142 * - on_remove_vertex: event handler when vertex is removed
143 */
144 template <typename Graph, typename Impl>
145 class graph_utils_base {
146 public:
147 1120 explicit graph_utils_base(Graph& g) : graph(g) {}
148
149 1084 void remove_vertex(vertex<Graph> v) {
150 1084 remove_vertex_handler(v);
151 1084 boost::remove_vertex(v, graph);
152 1084 }
153
154 52 void remove_edge(edge<Graph> e, bool remove_unused_vertices = false) {
155
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 auto [u, v] = get_vertex_pair(e);
156
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 boost::remove_edge(e, graph);
157
158
2/2
✓ Branch 0 taken 51 times.
✓ Branch 1 taken 1 times.
2/2
✓ Decision 'true' taken 51 times.
✓ Decision 'false' taken 1 times.
 52 if (remove_unused_vertices) {
159
3/4
✓ Branch 1 taken 51 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 14 times.
✓ Branch 4 taken 37 times.
2/2
✓ Decision 'true' taken 14 times.
✓ Decision 'false' taken 37 times.
 51 if (boost::degree(u, graph) == 0) {
160
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 remove_vertex(u);
161 }
162
3/4
✓ Branch 1 taken 51 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 2 times.
✓ Branch 4 taken 49 times.
2/2
✓ Decision 'true' taken 2 times.
✓ Decision 'false' taken 49 times.
 51 if (boost::degree(v, graph) == 0) {
163
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 remove_vertex(v);
164 }
165 }
166 52 }
167
168 protected:
169 ✗ virtual void remove_vertex_handler(vertex<Graph> v) {
170 ✗ Impl* impl = static_cast<Impl*>(this);
171 ✗ impl->on_remove_vertex(v);
172 }
173
174 /* returns source and target in an order in which they can be
175 * safely deleted if necessary
176 */
177 52 std::pair<vertex<Graph>, vertex<Graph>> get_vertex_pair(edge<Graph> e) {
178 52 vertex<Graph> u = boost::source(e, graph);
179 52 vertex<Graph> v = boost::target(e, graph);
180
181 52 return in_delete_order(u, v);
182 }
183
184 ✗ virtual std::pair<vertex<Graph>, vertex<Graph>> in_delete_order(
185 vertex<Graph> u, vertex<Graph> v) {
186 ✗ return {u, v};
187 }
188
189 Graph& graph;
190 };
191
192 /* small adjustments to graph_utils_helper for integral vertex indices.
193 * Unlike the general case, here indices get shifted when vertices are deleted
194 * so that the vertex indices remain contiguous
195 *
196 * Impl must be a subclass of this and must implement
197 * - to_index: return index of vertex v
198 * - typename index_type: type of index returned by to_index
199 * - on_index_change: event handler when indices are shifted
200 * - on_remove_vertex: event handler when vertex is removed, after all
201 * indices were updated
202 */
203 template <typename Graph, typename Impl>
204 class graph_utils_base_with_ind : public graph_utils_base<Graph, Impl> {
205 private:
206 using Base = graph_utils_base<Graph, Impl>;
207
208 public:
209 1120 explicit graph_utils_base_with_ind(Graph& g) : Base(g) {}
210
211 protected:
212 using Base::graph;
213 1084 void remove_vertex_handler(vertex<Graph> v) override {
214 1084 Impl* impl = static_cast<Impl*>(this);
215 using index_type = typename Impl::index_type;
216
217
7/12
✓ Branch 1 taken 1084 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1084 times.
✗ Branch 5 not taken.
✓ Branch 9 taken 80117 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 80117 times.
✗ Branch 13 not taken.
✓ Branch 15 taken 81201 times.
✗ Branch 16 not taken.
✓ Branch 17 taken 80117 times.
✓ Branch 18 taken 1084 times.
0/1
? Decision couldn't be analyzed.
 81201 for (vertex<Graph> u : boost::make_iterator_range(boost::vertices(graph))) {
218
2/2
✓ Branch 2 taken 74502 times.
✓ Branch 3 taken 5615 times.
2/2
✓ Decision 'true' taken 74502 times.
✓ Decision 'false' taken 5615 times.
 80117 if (impl->to_index(u) > impl->to_index(v)) {
219 74502 index_type new_ind = impl->to_index(u) - 1;
220
1/2
✓ Branch 1 taken 74494 times.
✗ Branch 2 not taken.
 74502 impl->on_index_change(u, new_ind);
221 }
222 }
223 1084 impl->on_remove_vertex(v);
224 1084 }
225
226 52 std::pair<vertex<Graph>, vertex<Graph>> in_delete_order(
227 vertex<Graph> u, vertex<Graph> v) override {
228 52 Impl* impl = static_cast<Impl*>(this);
229
230 // return larger index first
231
2/2
✓ Branch 2 taken 39 times.
✓ Branch 3 taken 13 times.
2/2
✓ Decision 'true' taken 39 times.
✓ Decision 'false' taken 13 times.
 52 if (impl->to_index(u) < impl->to_index(v)) {
232 39 return {v, u};
233 } else {
234 13 return {u, v};
235 }
236 }
237 };
238
239 /* The classes graph_utils_helper and graph_utils_helper_with_map provide
240 * the container-specific implementation bits.
241 * The Derived template type is the child class that inherits from this class
242 * -> see Curiously Recurring Template Pattern (CRTP)
243 * The Indexable boolean template is true iff Graph support integer vertex
244 * indexing (see has_integral_index). It should be left to default and infered
245 * by compiler
246 *
247 * We distinguish four cases for template specialisations, given by the four
248 * combinations of two variables:
249 *
250 * a) whether an explicit property map is provided or not
251 * b) whether the graph is indexable, i.e. either it has an intrinsic
252 * vertex_index property (case VertexList == vecS) or the property map has
253 * integral values
254 *
255 * Case 1: explicit property map, not indexable
256 */
257 template <
258 typename Derived, typename Graph, typename PMap = void,
259 bool Indexable = has_integral_index<Graph, PMap>>
260 class graph_utils_helper : public graph_utils_base<Graph, Derived> {
261 private:
262 using Base = graph_utils_base<Graph, Derived>;
263
264 public:
265 graph_utils_helper(Graph& g, PMap& p) : Base(g), pmap(p) {}
266
267 void on_remove_vertex(vertex<Graph> v) { pmap.erase(v); }
268
269 private:
270 PMap& pmap;
271 };
272
273 // Case 2: no explicit property, not indexable
274 template <typename Derived, typename Graph>
275 class graph_utils_helper<Derived, Graph, void, false>
276 : public graph_utils_base<Graph, Derived> {
277 private:
278 using Base = graph_utils_base<Graph, Derived>;
279
280 public:
281 explicit graph_utils_helper(Graph& g) : Base(g) {}
282 void on_remove_vertex(vertex<Graph>) {}
283 };
284
285 // Case 3: explicit property, indexable
286 // in this case we must ensure that we update the property map
287 // when vertices are removed and indices get shifted
288 template <typename Derived, typename Graph, typename PMap>
289 class graph_utils_helper<Derived, Graph, PMap, true>
290 : public graph_utils_base_with_ind<Graph, Derived> {
291 private:
292 using Base = graph_utils_base_with_ind<Graph, Derived>;
293
294 public:
295 using index_type = typename PMap::mapped_type;
296 graph_utils_helper(Graph& g, PMap& p) : Base(g), pmap(p), new_pmap(p) {
297 static_assert(
298 !std::is_integral_v<vertex<Graph>>,
299 "Ambiguous vertex index: you cannot provide an explicit "
300 "index property map if vertex descriptors are integrals.");
301 }
302
303 index_type to_index(vertex<Graph> v) { return pmap[v]; }
304
305 void on_index_change(vertex<Graph> v, index_type new_ind) {
306 new_pmap[v] = new_ind;
307 }
308 void on_remove_vertex(vertex<Graph> v) {
309 new_pmap.erase(v);
310 pmap = new_pmap;
311 }
312
313 private:
314 PMap& pmap;
315 PMap new_pmap;
316 };
317
318 // Case 4: no explicit property, indexable
319 // boost automatically shifts indices, so there is not much to do
320 template <typename Derived, typename Graph>
321 class graph_utils_helper<Derived, Graph, void, true>
322 : public graph_utils_base_with_ind<Graph, Derived> {
323 private:
324 using Base = graph_utils_base_with_ind<Graph, Derived>;
325
326 public:
327 using index_type = vertex_index<Graph>;
328 1120 explicit graph_utils_helper(Graph& g) : Base(g) {}
329
330 309334 index_type to_index(vertex<Graph> v) { return v; }
331 74502 void on_index_change(vertex<Graph>, index_type) {}
332 1084 void on_remove_vertex(vertex<Graph>) {}
333 };
334
335 /* Now come the same 4 cases with the additional support of an external map
336 * with vertrex indices as keys
337 */
338 // Case 1-2: not indexable
339 template <
340 typename Derived, typename Graph, typename Map, typename PMap = void,
341 bool Indexable = has_integral_index<Graph, PMap>>
342 class graph_utils_helper_with_map
343 : public graph_utils_helper<Derived, Graph, PMap> {
344 private:
345 using Base = graph_utils_helper<Derived, Graph, PMap>;
346
347 public:
348 graph_utils_helper_with_map(Graph& g, Map& m) : Base(g), map(m) {}
349
350 void on_remove_vertex(vertex<Graph> v) {
351 map.erase(v);
352 Base::on_remove_vertex(v);
353 }
354
355 private:
356 Map& map;
357 };
358
359 // Case 3: explicit property, indexable
360 template <typename Derived, typename Graph, typename Map, typename PMap>
361 class graph_utils_helper_with_map<Derived, Graph, Map, PMap, true>
362 : public graph_utils_helper<Derived, Graph, PMap> {
363 private:
364 using Base = graph_utils_helper<Derived, Graph, PMap>;
365
366 public:
367 using index_type = typename Base::index_type;
368 graph_utils_helper_with_map(Graph& g, Map& m, PMap& p)
369 : Base(g, p), map(m), new_map(m) {}
370
371 void on_index_change(vertex<Graph> v, index_type new_ind) {
372 if (new_map.count(new_ind)) {
373 new_map.erase(new_ind);
374 }
375 new_map.insert({new_ind, new_map[Base::to_index(v)]});
376 Base::on_index_change(v, new_ind);
377 }
378 void on_remove_vertex(vertex<Graph> v) {
379 auto max_ind = std::max_element(std::begin(new_map), std::end(new_map));
380 new_map.erase(max_ind);
381 map.clear();
382 for (auto& p : new_map) {
383 map.insert(p);
384 }
385
386 Base::on_remove_vertex(v);
387 }
388
389 private:
390 Map& map;
391 Map new_map;
392 };
393
394 // Case 4: no explicit property, indexable
395 template <typename Derived, typename Graph, typename Map>
396 class graph_utils_helper_with_map<Derived, Graph, Map, void, true>
397 : public graph_utils_helper<Derived, Graph, void> {
398 private:
399 using Base = graph_utils_helper<Derived, Graph, void>;
400 using StdMap = std::map<typename Map::key_type, typename Map::mapped_type>;
401
402 80048 static typename StdMap::value_type transformer_it(
403 typename Map::value_type& elem) {
404 80048 return std::make_pair(elem.first, elem.second);
405 }
406 1069 auto map_begin_it(Map& m) {
407 1069 return boost::make_transform_iterator(m.begin(), &transformer_it);
408 }
409 1069 auto map_end_it(Map& m) {
410 1069 return boost::make_transform_iterator(m.end(), &transformer_it);
411 }
412
413 public:
414 using index_type = typename Base::index_type;
415 1069 graph_utils_helper_with_map(Graph& g, Map& m)
416 1069 : Base(g), map(m), new_map(map_begin_it(m), map_end_it(m)) {}
417 74494 void on_index_change(vertex<Graph> v, index_type new_ind) {
418
1/2
✓ Branch 1 taken 74494 times.
✗ Branch 2 not taken.
1/2
✓ Decision 'true' taken 74494 times.
✗ Decision 'false' not taken.
 74494 if (new_map.count(new_ind)) {
419 74494 new_map.erase(new_ind);
420 }
421
2/4
✓ Branch 2 taken 74494 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 74494 times.
✗ Branch 7 not taken.
 74494 new_map.insert({new_ind, new_map[Base::to_index(v)]});
422 74494 Base::on_index_change(v, new_ind);
423 74494 }
424 1068 void on_remove_vertex(vertex<Graph> v) {
425
1/2
✓ Branch 3 taken 1068 times.
✗ Branch 4 not taken.
 1068 auto max_ind = std::max_element(std::begin(new_map), std::end(new_map));
426
1/2
✓ Branch 1 taken 1068 times.
✗ Branch 2 not taken.
 1068 new_map.erase(max_ind);
427 1068 map.clear();
428
2/2
✓ Branch 4 taken 78976 times.
✓ Branch 5 taken 1068 times.
2/2
✓ Decision 'true' taken 78976 times.
✓ Decision 'false' taken 1068 times.
 80044 for (auto& p : new_map) {
429
2/4
✓ Branch 1 taken 78976 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 78976 times.
✗ Branch 5 not taken.
 78976 map.insert(p);
430 }
431
432 1068 Base::on_remove_vertex(v);
433 1068 }
434
435 protected:
436 Map& map;
437 StdMap new_map;
438 };
439
440 // The above implementions are accessed through the following helper classes,
441 // making template args nicer
442 template <typename Graph, typename PMap = void>
443 class graph_utils_impl
444 : public graph_utils_helper<graph_utils_impl<Graph, PMap>, Graph, PMap> {
445 private:
446 using Base = graph_utils_helper<graph_utils_impl<Graph, PMap>, Graph, PMap>;
447
448 public:
449 using Base::Base;
450 };
451 template <typename Graph, typename Map, typename PMap = void>
452 class graph_utils_impl_with_map
453 : public graph_utils_helper_with_map<
454 graph_utils_impl_with_map<Graph, Map, PMap>, Graph, Map, PMap> {
455 private:
456 using Base = graph_utils_helper_with_map<
457 graph_utils_impl_with_map<Graph, Map, PMap>, Graph, Map, PMap>;
458
459 public:
460 using Base::Base;
461 };
462
463 } // namespace detail
464 } // namespace tket::graphs::utils
465