GCC Code Coverage Report

Directory: ./
File: Graphs/ArticulationPoints.cpp
Date: 2022-10-15 05:10:18
Warnings: 7 unchecked decisions!
Exec Total Coverage
Lines: 70 72 97.2%
Functions: 11 31 35.5%
Branches: 101 178 56.7%
Decisions: 14 30 46.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 "Graphs/ArticulationPoints.hpp"
16
17 #include <boost/property_map/property_map.hpp>
18 #include <boost/range/adaptor/transformed.hpp>
19 #include <boost/range/iterator_range_core.hpp>
20 #include <memory>
21 #include <set>
22 #include <utility>
23 #include <vector>
24
25 #include "Graphs/Utils.hpp"
26 #include "Utils/GraphHeaders.hpp"
27
28 namespace tket::graphs {
29
30 namespace detail {
31
32 // Types used in `get_ap_to_comp`
33 // Maps BGL edges descriptors to their (unique) biconnected component
34 template <typename T>
35 using EdgeToCompT = std::map<utils::edge<UndirectedConnGraph<T>>, unsigned>;
36
37 template <typename T>
38 8 BicomponentGraph<T>::BicomponentGraph(const UndirectedConnGraph<T>& graph)
39
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 8 : underlying_g(graph) {
40 // get map from APs to their bicomponents (as well as the number of bicomps)
41
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 8 compute_components_map();
42
43 // all that remains is to build the graph
44
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 8 build_graph();
45 }
46
47 /** Computes map from APs (identified by UnitID) to the set of
48 * biconnected components they belong to.
49 * Returns a pair with the map and the number of components
50 */
51 template <typename T>
52 8 void BicomponentGraph<T>::compute_components_map() {
53 // Map from edges to their (unique) biconnected component
54 // (this is filled out by call to boost::biconnected_components)
55 8 EdgeToCompT<T> edge_to_comp;
56
57 8 std::vector<unsigned> underlying_aps;
58 // call to BGL
59
2/4
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 4 times.
✗ Branch 5 not taken.
 8 auto bgl_res = boost::biconnected_components(
60
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 8 underlying_g, boost::make_assoc_property_map(edge_to_comp),
61 std::back_inserter(underlying_aps));
62
2/2
✓ Branch 5 taken 10 times.
✓ Branch 6 taken 4 times.
2/2
✓ Decision 'true' taken 10 times.
✓ Decision 'false' taken 4 times.
 28 for (auto v_ap : underlying_aps) {
63
2/4
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 10 times.
✗ Branch 5 not taken.
 20 aps.push_back(underlying_g[v_ap]);
64 }
65 8 unsigned n_components = bgl_res.first;
66
67 // Now populate map from vertices to the set of biconnected components of v
68
7/12
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 4 times.
✗ Branch 5 not taken.
✓ Branch 9 taken 29 times.
✗ Branch 10 not taken.
✓ Branch 13 taken 29 times.
✗ Branch 14 not taken.
✓ Branch 16 taken 33 times.
✗ Branch 17 not taken.
✓ Branch 18 taken 29 times.
✓ Branch 19 taken 4 times.
0/1
? Decision couldn't be analyzed.
 66 for (auto v : boost::make_iterator_range(boost::vertices(underlying_g))) {
69
1/2
✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
 58 T node = underlying_g[v];
70
2/4
✓ Branch 2 taken 29 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 29 times.
✗ Branch 6 not taken.
 58 vertex_to_comps.insert({node, {}});
71 // we get the components `v` belongs to by looking at the components
72 // of its incident edges
73
3/4
✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 27 times.
✓ Branch 4 taken 2 times.
0/1
? Decision couldn't be analyzed.
 58 if (boost::degree(v, underlying_g) > 0) {
74
5/8
✓ Branch 2 taken 72 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 72 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 99 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 72 times.
✓ Branch 11 taken 27 times.
0/1
? Decision couldn't be analyzed.
 198 for (auto e :
75
2/4
✓ Branch 1 taken 27 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 27 times.
✗ Branch 5 not taken.
 54 boost::make_iterator_range(boost::out_edges(v, underlying_g))) {
76 // it's a set, we do not need to worry about duplicates
77
3/6
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 72 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 72 times.
✗ Branch 8 not taken.
 144 vertex_to_comps[node].insert(edge_to_comp[e]);
78 }
79 } else {
80 // if vertex is disconnected, create new exclusive component
81
2/4
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
 4 vertex_to_comps[node].insert(n_components++);
82 }
83 }
84
1/2
✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
 8 selected_comps = std::vector<bool>(n_components, false);
85 }
86
87 template <typename T>
88 8 void BicomponentGraph<T>::build_graph() {
89 // initialise bicomponent graph with `n_components` vertices
90 8 unsigned n_components = selected_comps.size();
91
2/4
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 4 times.
✗ Branch 5 not taken.
 8 g = Graph(n_components);
92
93 // add edges according to vertex_to_comps
94
2/2
✓ Branch 8 taken 10 times.
✓ Branch 9 taken 4 times.
2/2
✓ Decision 'true' taken 10 times.
✓ Decision 'false' taken 4 times.
 28 for (auto ap : aps) {
95
2/4
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 10 times.
✗ Branch 5 not taken.
 20 auto comps = vertex_to_comps[ap];
96
2/2
✓ Branch 4 taken 20 times.
✓ Branch 5 taken 10 times.
2/2
✓ Decision 'true' taken 20 times.
✓ Decision 'false' taken 10 times.
 60 for (auto it = comps.cbegin(); it != comps.cend(); ++it) {
97 40 unsigned comp1 = *it;
98
2/2
✓ Branch 3 taken 10 times.
✓ Branch 4 taken 20 times.
2/2
✓ Decision 'true' taken 10 times.
✓ Decision 'false' taken 20 times.
 60 for (auto it2 = it; ++it2 != comps.cend();) {
99 20 unsigned comp2 = *it2;
100 // add edge between any 2 components that `ap` links
101
1/2
✓ Branch 2 taken 10 times.
✗ Branch 3 not taken.
 20 boost::add_edge(comp1, comp2, {ap}, g);
102 }
103 }
104 }
105 }
106
107 template <typename T>
108 template <typename Range>
109 16 void BicomponentGraph<T>::select_comps(Range nodes) {
110
8/12
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 15 times.
✓ Branch 8 taken 6 times.
✓ Branch 11 taken 9 times.
✗ Branch 12 not taken.
✓ Branch 14 taken 11 times.
✗ Branch 15 not taken.
✓ Branch 16 taken 9 times.
✓ Branch 17 taken 2 times.
0/1
? Decision couldn't be analyzed.
 50 for (T node : nodes) {
111
3/4
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
✓ Branch 7 taken 22 times.
✓ Branch 8 taken 15 times.
0/1
? Decision couldn't be analyzed.
 74 for (unsigned comp : vertex_to_comps[node]) {
112
1/2
✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
 44 selected_comps[comp] = true;
113 }
114 }
115 }
116
117 /** Propagation of selected components (`propagate_selected_comps`)
118 *
119 * Strategy to minimally expand the selected components to a connected
120 * subgraph: given that the bicomp graph is a tree, we simply need to select
121 * every vertex that is on a path between two selected vertices
122 *
123 * We can easily achieve that using e.g. depth-first-search (DFS):
124 * i) we fix a vertex that is selected as root
125 * ii) at each vertex we discover, we check recursively if one of the
126 * descendants is selected, and if so, we select the vertex
127 */
128
129 /** A BGL custom visitor, in all its glory
130 * It checks if after visiting all the descendants, one of them
131 * was found to be selected.
132 * If so, then vertex must be on a path between two selected vertices
133 * and thus the vertex is selected
134 */
135 template <typename Graph>
136 struct TrackUsedEdgesVisitor : public boost::default_dfs_visitor {
137 using edge =
138 std::pair<graphs::utils::vertex<Graph>, graphs::utils::vertex<Graph>>;
139
140 16 explicit TrackUsedEdgesVisitor(std::vector<bool>& s) : selected(s) {
141
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 16 tree_edges = std::make_shared<std::set<edge>>();
142 }
143 std::vector<bool>& selected;
144 std::shared_ptr<std::set<edge>> tree_edges;
145
146 // called as DFS leaves the edge and returns to parent
147 96 void finish_edge(graphs::utils::edge<Graph> e, const Graph& g) {
148 96 unsigned target = boost::target(e, g);
149 96 unsigned source = boost::source(e, g);
150 // only consider tree edges
151
3/4
✓ Branch 3 taken 48 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 24 times.
✓ Branch 6 taken 24 times.
2/2
✓ Decision 'true' taken 48 times.
✓ Decision 'false' taken 48 times.
 96 if (!tree_edges->count({source, target})) {
152 48 return;
153 }
154
3/4
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 17 times.
✓ Branch 5 taken 7 times.
2/2
✓ Decision 'true' taken 34 times.
✓ Decision 'false' taken 14 times.
 48 if (selected[target]) {
155
1/2
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
 34 selected[source] = true;
156 }
157 }
158 // keep track of tree edges
159 48 void tree_edge(graphs::utils::edge<Graph> e, const Graph& g) {
160 48 unsigned target = boost::target(e, g);
161 48 unsigned source = boost::source(e, g);
162
1/2
✓ Branch 3 taken 24 times.
✗ Branch 4 not taken.
 48 tree_edges->insert({source, target});
163 }
164 };
165
166 template <typename T>
167 16 void BicomponentGraph<T>::propagate_selected_comps() {
168 16 unsigned root = 0;
169 16 unsigned n_components = selected_comps.size();
170
4/8
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 8 times.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 8 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 8 times.
0/1
? Decision couldn't be analyzed.
 16 while (root < n_components && !selected_comps[root]) {
171 ✗ ++root;
172 }
173
174
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 16 times.
 16 if (root == n_components) {
175 ✗ throw NoSelectedComponent(
176 "At least one component must be selected"
177 " to be able to propagate");
178 }
179
180 // using our custom visitor, DFS will propagate selected_comps as necessary
181
3/6
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 8 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 8 times.
✗ Branch 8 not taken.
 32 auto params = boost::visitor(TrackUsedEdgesVisitor<Graph>(selected_comps))
182 .root_vertex(root);
183
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 16 boost::depth_first_search(g, params);
184 }
185
186 template <typename T>
187 4 std::set<T> BicomponentGraph<T>::get_inner_edges() {
188 4 std::set<T> out;
189
7/12
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
✓ Branch 9 taken 3 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 3 times.
✗ Branch 13 not taken.
✓ Branch 15 taken 5 times.
✗ Branch 16 not taken.
✓ Branch 17 taken 3 times.
✓ Branch 18 taken 2 times.
0/1
? Decision couldn't be analyzed.
 10 for (auto e : boost::make_iterator_range(boost::edges(g))) {
190 6 unsigned comp1 = boost::source(e, g);
191 6 unsigned comp2 = boost::target(e, g);
192
5/10
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 3 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 3 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 3 times.
✗ Branch 11 not taken.
✓ Branch 12 taken 3 times.
✗ Branch 13 not taken.
1/2
✓ Decision 'true' taken 6 times.
✗ Decision 'false' not taken.
 6 if (selected_comps[comp1] && selected_comps[comp2]) {
193
2/4
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 3 times.
✗ Branch 5 not taken.
 6 out.insert(g[e].ap);
194 }
195 }
196 4 return out;
197 }
198
199 template class BicomponentGraph<UnitID>;
200 template class BicomponentGraph<Node>;
201 template class BicomponentGraph<Qubit>;
202 template void BicomponentGraph<UnitID>::select_comps(std::vector<UnitID>);
203 template void BicomponentGraph<Node>::select_comps(std::vector<Node>);
204 template void BicomponentGraph<Qubit>::select_comps(std::vector<Qubit>);
205
206 } // namespace detail
207
208 template <typename T>
209 4 std::set<T> get_subgraph_aps(
210 const UndirectedConnGraph<T>& graph,
211 const UndirectedConnGraph<T>& subgraph) {
212
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 4 detail::BicomponentGraph<T> bicomp_graph(graph);
213 using funcT = std::function<T(unsigned)>;
214 13 funcT to_node = [&subgraph](unsigned v) { return subgraph[v]; };
215
5/10
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 2 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 2 times.
✗ Branch 11 not taken.
✓ Branch 13 taken 2 times.
✗ Branch 14 not taken.
 4 auto selected = boost::make_iterator_range(boost::vertices(subgraph)) |
216 boost::adaptors::transformed(to_node);
217
2/4
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
 4 bicomp_graph.select_comps(selected);
218
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 4 bicomp_graph.propagate_selected_comps();
219
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 8 return bicomp_graph.get_inner_edges();
220 }
221
222 template std::set<UnitID> get_subgraph_aps(
223 const UndirectedConnGraph<UnitID>& graph,
224 const UndirectedConnGraph<UnitID>& subgraph);
225 template std::set<Node> get_subgraph_aps(
226 const UndirectedConnGraph<Node>& graph,
227 const UndirectedConnGraph<Node>& subgraph);
228
229 } // namespace tket::graphs
230