GCC Code Coverage Report

Directory: ./
File: Graphs/include/Graphs/TreeSearch_impl.hpp
Date: 2022-10-15 05:10:18
Warnings: 2 unchecked decisions!
Exec Total Coverage
Lines: 61 65 93.8%
Functions: 24 36 66.7%
Branches: 46 94 48.9%
Decisions: 8 14 57.1%
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 <boost/graph/breadth_first_search.hpp>
18 #include <boost/graph/depth_first_search.hpp>
19 #include <boost/graph/properties.hpp>
20 #include <boost/graph/visitors.hpp>
21 #include <boost/property_map/property_map.hpp>
22 #include <boost/range/iterator_range_core.hpp>
23 #include <numeric>
24 #include <type_traits>
25 #include <utility>
26 #include <vector>
27
28 #include "Graphs/Utils.hpp"
29
30 // implementation details of `TreeSearch.hpp`
31
32 namespace tket::graphs {
33
34 // ::detail includes all internal implementation-specific details
35 namespace detail {
36
37 /* Helpers `run_bfs` and `run_dfs` return instances of TreeSearchBase
38 * subclasses. These provide a host of useful member functions to obtain the
39 * relevant results from the tree search.
40 *
41 * Note that run() must have been called before
42 * using the member functions to retrieve results.
43 * This is done automatically by the utility functions in `TreeSearch.hpp`
44 *
45 * First template argument is Graph type, second is the boost property map type
46 * that should be used as a vertex index.
47 */
48 template <typename Graph, typename BoostPMap>
49 class TreeSearchBase {
50 protected:
51 using vertex = utils::vertex<Graph>;
52 using size_t = std::size_t;
53 using parent_vec = std::vector<vertex>;
54 using color_vec = std::vector<boost::default_color_type>;
55 using index_pmap_t = BoostPMap;
56 using dist_pmap_t =
57 boost::iterator_property_map<typename dist_vec::iterator, index_pmap_t>;
58 using parent_pmap_t =
59 boost::iterator_property_map<typename parent_vec::iterator, index_pmap_t>;
60 using color_pmap_t =
61 boost::iterator_property_map<typename color_vec::iterator, index_pmap_t>;
62 using visitor_t = std::pair<
63 boost::distance_recorder<dist_pmap_t, boost::on_tree_edge>,
64 boost::predecessor_recorder<parent_pmap_t, boost::on_tree_edge>>;
65
66 public:
67 /* Constructor: search through Graph g with root v, using index map pmap */
68 333 TreeSearchBase(vertex v, Graph&& g, BoostPMap pmap)
69 333 : root(v),
70 to_index(pmap),
71 333 graph(g),
72
2/6
✓ Branch 1 taken 333 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 333 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 333 dists(boost::num_vertices(g)),
73
2/4
✓ Branch 2 taken 333 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 333 times.
✗ Branch 6 not taken.
 333 parents(boost::num_vertices(g)),
74
2/4
✓ Branch 2 taken 333 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 333 times.
✗ Branch 6 not taken.
 333 color_map(boost::num_vertices(g)),
75 333 visitor{
76
2/5
✓ Branch 2 taken 333 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 333 times.
✗ Branch 6 not taken.
 333 boost::record_distances(
77 boost::make_iterator_property_map(dists.begin(), to_index),
78 boost::on_tree_edge()),
79
2/5
✓ Branch 2 taken 333 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 333 times.
✗ Branch 6 not taken.
 333 boost::record_predecessors(
80 boost::make_iterator_property_map(parents.begin(), to_index),
81 333 boost::on_tree_edge())} {
82 // for every vertex, assign self as parent
83
6/10
✓ Branch 1 taken 333 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 333 times.
✗ Branch 5 not taken.
✓ Branch 9 taken 7864 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 8197 times.
✗ Branch 13 not taken.
✓ Branch 14 taken 7864 times.
✓ Branch 15 taken 333 times.
0/1
? Decision couldn't be analyzed.
 8197 for (auto v : boost::make_iterator_range(boost::vertices(graph))) {
84
1/2
✓ Branch 3 taken 7864 times.
✗ Branch 4 not taken.
 7864 parents[to_index[v]] = v;
85 }
86 333 }
87
88 /* Get results from tree search */
89 /* vector of vertex predecessor in search */
90 const parent_vec& get_parents() const& { return parents; }
91 const parent_vec&& get_parents() const&& { return std::move(parents); }
92 /* vector of distances from the root */
93 const dist_vec& get_dists() const& { return dists; }
94 ✗ const dist_vec&& get_dists() const&& { return std::move(dists); }
95 67 size_t get_dist(const vertex& v) const { return dists[to_index[v]]; }
96
97 /* Rebase tree search from some new root */
98 64 void change_root(vertex v) {
99 // naive implementation
100 // This might be made more efficient in the subclasses
101 64 vertex old_root = root;
102 64 root = v;
103
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 24 times.
2/2
✓ Decision 'true' taken 40 times.
✓ Decision 'false' taken 24 times.
 64 if (root != old_root) {
104
1/2
✓ Branch 3 taken 40 times.
✗ Branch 4 not taken.
 40 std::fill(dists.begin(), dists.end(), 0);
105 40 std::iota(parents.begin(), parents.end(), 0);
106 40 run();
107 }
108 64 }
109
110 /* Vector from target to root (following reverse edges) */
111 335 parent_vec path_to_root(vertex target) const {
112 335 std::vector<vertex> path;
113
114 335 vertex current = target;
115
1/2
✓ Branch 1 taken 335 times.
✗ Branch 2 not taken.
 335 path.push_back(target);
116
2/2
✓ Branch 0 taken 664 times.
✓ Branch 1 taken 335 times.
2/2
✓ Decision 'true' taken 664 times.
✓ Decision 'false' taken 335 times.
 999 while (current != root) {
117 664 vertex parent = parents[to_index[current]];
118
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 664 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 664 times.
 664 if (parent == current) {
119 // graph is disconnected and there is no path to root
120 ✗ return {};
121 }
122 664 current = parent;
123
1/2
✓ Branch 1 taken 664 times.
✗ Branch 2 not taken.
 664 path.push_back(current);
124 }
125 335 return path;
126 335 }
127
128 /* Vector from root to target along graph edges */
129 26 parent_vec path_from_root(vertex target) const {
130 26 parent_vec out = path_to_root(target);
131
1/2
✓ Branch 3 taken 26 times.
✗ Branch 4 not taken.
 26 std::reverse(out.begin(), out.end());
132 26 return out;
133 }
134
135 /* Depth of tree search */
136 90 size_t max_depth() const {
137
1/2
✓ Branch 3 taken 90 times.
✗ Branch 4 not taken.
 90 auto it = std::max_element(dists.cbegin(), dists.cend());
138
1/2
✗ Branch 2 not taken.
✓ Branch 3 taken 90 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 90 times.
 90 if (it == dists.cend()) {
139 ✗ throw std::invalid_argument(
140 "TreeSearch::max_depth: There is no entry in distance "
141 "vector");
142 }
143 90 return *it;
144 }
145
146 /* Vertex of max depth
147 * if more than one exist, returns first found */
148 26 vertex max_depth_vertex() const {
149 26 const size_t target_depth = max_depth();
150
6/12
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 26 times.
✗ Branch 5 not taken.
✓ Branch 9 taken 67 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 41 times.
✗ Branch 13 not taken.
✓ Branch 15 taken 67 times.
✗ Branch 16 not taken.
✓ Branch 17 taken 67 times.
✗ Branch 18 not taken.
0/1
? Decision couldn't be analyzed.
 67 for (vertex v : boost::make_iterator_range(boost::vertices(this->graph))) {
151
3/4
✓ Branch 1 taken 67 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 26 times.
✓ Branch 4 taken 41 times.
2/2
✓ Decision 'true' taken 26 times.
✓ Decision 'false' taken 41 times.
 67 if (get_dist(v) == target_depth) {
152 26 return v;
153 }
154 }
155 ✗ throw std::runtime_error("max_depth_vertex: No vertex has maximal depth");
156 }
157
158 /* Path from root to deepest vertex */
159 26 parent_vec longest_path() const { return path_from_root(max_depth_vertex()); }
160
161 /* Run tree search */
162 virtual void run() = 0;
163
164 protected:
165 template <typename Visitor>
166 682 auto get_default_named_params(Visitor& vis) {
167
1/2
✓ Branch 2 taken 373 times.
✗ Branch 3 not taken.
 1364 return boost::visitor(vis).color_map(
168
1/2
✓ Branch 2 taken 373 times.
✗ Branch 3 not taken.
 1364 boost::make_iterator_property_map(color_map.begin(), to_index));
169 }
170
171 vertex root; // root of tree search
172 index_pmap_t to_index; // vertex index pmap
173 Graph graph; // graph to be searched
174 dist_vec dists; // distance from root
175 parent_vec parents; // parent towards root
176 color_vec color_map; // color used by tree search algorithm
177 visitor_t visitor; // visitor passed to boost tree search alg
178 };
179
180 /* A vertex index map, mapping boost vertex descriptors to unsigned
181 * is required for tree searches (to index the parents and dists vectors).
182 *
183 * The TreeSearch class accepts a std::map-like PMap argument to define such a
184 * mapping. This is converted to a boost property map using
185 * boost::associative_property_map. If none is provided, the default
186 * boost::vertex_index is used (by default, this is available on boost graphs
187 * using the vecS underlying EdgeOutList type
188 */
189
190 /* Note on the implementation:
191 * The third template argument (a bool) should always be left to its
192 * default value. It is used to flag whether the Graph type considered
193 * has an implicit integer vertex index.
194 * This flag is used in the template specialisation below to change
195 * the template definition when `HasImplicitIndex == True`,
196 * i.e. the first definition of `TreeSearch` is for the case `HasImplicitIndex
197 * == False` while the template partial specialisation below is for the case
198 * `HasImplicitIndex == True`.
199 */
200 template <
201 typename Graph, typename PMap = void,
202 bool HasImplicitIndex = utils::detail::has_integral_index<Graph>>
203 class TreeSearch
204 : public TreeSearchBase<Graph, boost::associative_property_map<PMap>> {
205 private:
206 using Base = TreeSearchBase<Graph, boost::associative_property_map<PMap>>;
207 using vertex = typename Base::vertex;
208
209 public:
210 TreeSearch(vertex v, Graph&& g, PMap& pmap)
211 : Base(v, std::forward<Graph>(g), boost::make_assoc_property_map(pmap)) {}
212 };
213
214 template <typename Graph>
215 class TreeSearch<Graph, void, true>
216 : public TreeSearchBase<
217 Graph,
218 decltype(boost::get(boost::vertex_index, std::declval<Graph>()))> {
219 private:
220 using PMap = decltype(boost::get(boost::vertex_index, std::declval<Graph>()));
221 using Base = TreeSearchBase<Graph, PMap>;
222 using vertex = typename Base::vertex;
223
224 public:
225 333 TreeSearch(vertex v, Graph&& g)
226 333 : Base(v, std::forward<Graph>(g), boost::get(boost::vertex_index, g)) {}
227 };
228
229 } // namespace detail
230
231 /* Return type of `run_bfs`.
232 *
233 * For each vertex, computes the BFS distance to the root
234 * as well as the next node on the path towards root (parent).
235 * These are stored in the base class TreeSearchBase and can
236 * be retrieved through one of the member functions defined therein
237 */
238 template <typename... Args>
239 class BFS : public detail::TreeSearch<Args...> {
240 private:
241 using Base = detail::TreeSearch<Args...>;
242
243 public:
244 // inherit constructors
245 using Base::Base;
246
247 using parent_vec = typename Base::parent_vec;
248
249 /* Run bfs */
250 618 void run() override {
251
1/2
✓ Branch 1 taken 309 times.
✗ Branch 2 not taken.
 618 auto vis = boost::make_bfs_visitor(this->visitor);
252
1/2
✓ Branch 1 taken 309 times.
✗ Branch 2 not taken.
 618 boost::breadth_first_search(
253
1/4
✓ Branch 1 taken 309 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 618 this->graph, this->root, this->get_default_named_params(vis));
254 }
255 };
256
257 /* Return type of `run_dfs`.
258 *
259 * For each vertex, computes the DFS distance to the root
260 * as well as the next node on the path towards root (parent).
261 * These are stored in the base class TreeSearchBase and can
262 * be retrieved through one of the member functions defined therein
263 */
264 template <typename... Args>
265 class DFS : public detail::TreeSearch<Args...> {
266 private:
267 using Base = detail::TreeSearch<Args...>;
268
269 public:
270 // inherit constructors
271 using Base::Base;
272
273 using parent_vec = typename Base::parent_vec;
274
275 /* Run dfs */
276 64 void run() override {
277
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 auto vis = boost::make_dfs_visitor(this->visitor);
278
1/2
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
 64 boost::depth_first_search(
279 this->graph,
280
2/4
✓ Branch 1 taken 64 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 64 times.
✗ Branch 5 not taken.
 64 this->get_default_named_params(vis).root_vertex(this->root));
281 64 }
282 };
283
284 } // namespace tket::graphs
285