GCC Code Coverage Report

Directory: ./
File: Graphs/include/Graphs/Utils.hpp
Date: 2022-10-15 05:10:18
Exec Total Coverage
Lines: 36 40 90.0%
Functions: 11 23 47.8%
Branches: 22 48 45.8%
Decisions: 0 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
17 #include <algorithm>
18 #include <boost/graph/copy.hpp>
19 #include <set>
20 #include <type_traits>
21
22 #include "Graphs/Utils_impl.hpp"
23 #include "Utils/BiMapHeaders.hpp"
24 #include "Utils/GraphHeaders.hpp"
25
26 namespace tket::graphs {
27
28 using dist_vec = std::vector<std::size_t>;
29
30 namespace utils {
31
32 // Type synonyms for many often-used BGL types
33
34 // BGL vertex descriptor
35 template <typename T>
36 using vertex = detail::vertex<T>;
37 // BGL edge descriptor
38 template <typename T>
39 using edge = detail::edge<T>;
40
41 /* Compile-time boolean flag to check if boost graph type is
42 * directed or undirected graph
43 *
44 * Template Argument Graph is the boost type of the graph to be checked
45 */
46 template <typename Graph>
47 constexpr bool is_directed = detail::is_directed_struct<Graph>::value;
48
49 /* These utility functions are meant to offer a more consistent
50 * alternative to boost::remove_vertex, so that the vertex storage container
51 * can be changed without changes in the implementation
52 *
53 * boost::remove_vertex behaves differently depending on the vertex container
54 * type
55 * - for vecS, remove_vertex will shift vertex indices so that they remain in
56 * the continuous interval [0..n-1].
57 * - for other types, remove_vertex will leave the vertex descriptors unchanged
58 *
59 * Instead, these wrappers behave as follows
60 * - support for explicit indices: if vertex descriptors are numbers
61 * (i.e. VertexList == vecS) or if an explicit index map is provided, indices
62 * will be shifted as with the default boost vecS implementation.
63 * - support for external map: additionally, a map from vertex descriptors to
64 * arbitrary types can be provided. The map keys will then automatically be
65 * changed to mirror the vertex descriptors changes.
66 *
67 * As a result, implementations can abstract away the vertex descriptor
68 * implementation, and either rely on explicit indices throughout, or stick to
69 * vertex descriptors and have the necessary translation maps be updated
70 * automatically
71 */
72 template <typename Graph>
73 inline void remove_vertex(vertex<Graph> v, Graph& graph) {
74 detail::graph_utils_impl<Graph> impl(graph);
75 impl.remove_vertex(v);
76 }
77 template <typename Graph, typename PMap>
78 inline void remove_vertex(vertex<Graph> v, Graph& graph, PMap& p) {
79 detail::graph_utils_impl<Graph, PMap> impl(graph, p);
80 impl.remove_vertex(v);
81 }
82 template <typename Graph, typename PMap, typename Map>
83 inline void remove_vertex(vertex<Graph> v, Graph& graph, PMap& pmap, Map& map) {
84 detail::graph_utils_impl_with_map<Graph, Map, PMap> impl(graph, map, pmap);
85 impl.remove_vertex(v);
86 }
87 template <typename Graph, typename Map, typename PMap>
88 inline void remove_vertex_with_map(
89 vertex<Graph> v, Graph& graph, Map& map, PMap& pmap) {
90 detail::graph_utils_impl_with_map<Graph, Map, PMap> impl(graph, map, pmap);
91 impl.remove_vertex(v);
92 }
93 template <typename Graph, typename Map>
94 1068 inline void remove_vertex_with_map(vertex<Graph> v, Graph& graph, Map& map) {
95
1/2
✓ Branch 1 taken 1068 times.
✗ Branch 2 not taken.
 1068 detail::graph_utils_impl_with_map<Graph, Map> impl(graph, map);
96
1/2
✓ Branch 1 taken 1068 times.
✗ Branch 2 not taken.
 1068 impl.remove_vertex(v);
97 1068 }
98
99 // like boost::remove_edge, but optionally removes disconnected vertices
100 // in which case it can also update a map as above in graph_utils::remove_vertex
101 template <typename Graph>
102 51 inline void remove_edge(
103 edge<Graph> e, Graph& graph, bool remove_unused_vertices = false) {
104
1/2
✓ Branch 1 taken 51 times.
✗ Branch 2 not taken.
 51 detail::graph_utils_impl<Graph> impl(graph);
105
1/2
✓ Branch 1 taken 51 times.
✗ Branch 2 not taken.
 51 impl.remove_edge(e, remove_unused_vertices);
106 51 }
107 template <typename Graph, typename PMap>
108 inline void remove_edge(
109 edge<Graph> e, Graph& graph, PMap& pmap,
110 bool remove_unused_vertices = false) {
111 detail::graph_utils_impl<Graph, PMap> impl(graph, pmap);
112 impl.remove_edge(e, remove_unused_vertices);
113 }
114 template <typename Graph, typename PMap, typename Map>
115 inline void remove_edge(
116 edge<Graph> e, Graph& graph, PMap& pmap, Map& map,
117 bool remove_unused_vertices = false) {
118 detail::graph_utils_impl_with_map<Graph, Map, PMap> impl(graph, map, pmap);
119 impl.remove_edge(e, remove_unused_vertices);
120 }
121 template <typename Graph, typename Map>
122 1 inline void remove_edge_with_map(edge<Graph> e, Graph& graph, Map& map) {
123
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 detail::graph_utils_impl_with_map<Graph, Map> impl(graph, map);
124
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 impl.remove_edge(e);
125 1 }
126 template <typename Graph, typename Map, typename PMap>
127 inline void remove_edge_with_map(
128 edge<Graph> e, Graph& graph, Map& map, PMap& pmap) {
129 detail::graph_utils_impl_with_map<Graph, Map, PMap> impl(graph, map, pmap);
130 impl.remove_edge(e);
131 }
132
133 // simple wrapper around boost::copy_graph that serves
134 // to transform a directed into an undirected graph
135 template <typename GraphOut, typename GraphIn>
136 ✗ GraphOut symmetrise(const GraphIn& g) {
137 static_assert(
138 !is_directed<GraphOut>,
139 "The GraphOut template type should be undirected. Use "
140 "boost::copy_graph otherwise");
141 ✗ GraphOut out;
142 ✗ boost::copy_graph(g, out);
143 ✗ return out;
144 }
145
146 template <typename GraphOut, typename GraphIn>
147 GraphOut symmetrise(
148 const GraphIn& g, boost::bimap<vertex<GraphIn>, vertex<GraphOut>>& v_map) {
149 static_assert(
150 !is_directed<GraphOut>,
151 "The GraphOut template type should be undirected. Use "
152 "boost::copy_graph otherwise");
153 GraphOut out;
154 // when vertices are copied, do the default thing but keep track of the map
155 boost::detail::vertex_copier<GraphIn, GraphOut> v_copier =
156 boost::detail::make_vertex_copier(g, out);
157 boost::copy_graph(
158 g, out,
159 boost::vertex_copy(
160 [&v_map, &v_copier](vertex<GraphIn> old_v, vertex<GraphOut> new_v) {
161 v_copier(old_v, new_v);
162 v_map.insert({old_v, new_v});
163 }));
164 return out;
165 }
166
167 template <typename Graph>
168 20 std::size_t max_degree(const Graph& g) {
169 554 auto degree = [&g](vertex<Graph> v) { return boost::degree(v, g); };
170
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 auto [from, to] = boost::vertices(g);
171 vertex<Graph> max_vertex =
172
2/4
✓ Branch 2 taken 20 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 20 times.
✗ Branch 6 not taken.
 20 *std::max_element(from, to, detail::lt_with_key<vertex<Graph>>(degree));
173
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 40 return degree(max_vertex);
174 }
175
176 template <typename Graph>
177 446 std::size_t min_degree(const Graph& g) {
178 67514 auto degree = [&g](vertex<Graph> v) { return boost::degree(v, g); };
179
1/2
✓ Branch 1 taken 446 times.
✗ Branch 2 not taken.
 446 auto [from, to] = boost::vertices(g);
180 vertex<Graph> min_vertex =
181
2/4
✓ Branch 2 taken 446 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 446 times.
✗ Branch 6 not taken.
 446 *std::min_element(from, to, detail::lt_with_key<vertex<Graph>>(degree));
182
1/2
✓ Branch 1 taken 446 times.
✗ Branch 2 not taken.
 892 return degree(min_vertex);
183 }
184
185 template <typename Graph>
186 20 std::set<vertex<Graph>> max_degree_nodes(const Graph& g) {
187
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 const auto max = max_degree(g);
188
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 auto [from, to] = boost::vertices(g);
189 20 std::set<vertex<Graph>> out;
190
2/4
✓ Branch 2 taken 20 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 20 times.
✗ Branch 6 not taken.
 20 std::copy_if(
191 from, to, std::inserter(out, out.begin()),
192 287 [&g, max](vertex<Graph> v) { return boost::degree(v, g) == max; });
193 40 return out;
194 }
195
196 template <typename Graph>
197 446 std::set<vertex<Graph>> min_degree_nodes(const Graph& g) {
198
1/2
✓ Branch 1 taken 446 times.
✗ Branch 2 not taken.
 446 const auto min = min_degree(g);
199
1/2
✓ Branch 1 taken 446 times.
✗ Branch 2 not taken.
 446 auto [from, to] = boost::vertices(g);
200 446 std::set<vertex<Graph>> out;
201
2/4
✓ Branch 2 taken 446 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 446 times.
✗ Branch 6 not taken.
 446 std::copy_if(
202 from, to, std::inserter(out, out.begin()),
203 33980 [&g, min](vertex<Graph> v) { return boost::degree(v, g) == min; });
204 892 return out;
205 }
206
207 } // namespace utils
208 } // namespace tket::graphs
209