GCC Code Coverage Report

Directory: ./
File: Graphs/include/Graphs/DirectedGraph.hpp
Date: 2022-10-15 05:10:18
Warnings: 4 unchecked decisions!
Exec Total Coverage
Lines: 112 239 46.9%
Functions: 23 107 21.5%
Branches: 106 378 28.0%
Decisions: 33 94 35.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 <algorithm>
18 #include <boost/range/adaptor/transformed.hpp>
19 #include <boost/range/iterator_range_core.hpp>
20 #include <functional>
21 #include <iostream>
22 #include <map>
23 #include <memory>
24 #include <optional>
25 #include <stdexcept>
26 #include <type_traits>
27
28 #include "Graphs/AbstractGraph.hpp"
29 #include "Graphs/TreeSearch.hpp"
30 #include "Graphs/Utils.hpp"
31 #include "Utils/GraphHeaders.hpp"
32
33 namespace tket::graphs {
34
35 /**
36 * Exception thrown because two nodes are disconnected from one another.
37 *
38 * @tparam T node type
39 */
40 template <typename T>
41 class NodesNotConnected : public std::logic_error {
42 public:
43 ✗ NodesNotConnected(const T& node1, const T& node2)
44 : std::logic_error(
45 ✗ node1.repr() + " and " + node2.repr() + " are not connected") {}
46 };
47
48 /** Weighted edge */
49 struct WeightedEdge {
50 ✗ explicit WeightedEdge(unsigned w = 1) : weight(w) {}
51 unsigned weight;
52 };
53
54 template <typename T>
55 class DirectedGraphBase : public AbstractGraph<T> {
56 protected:
57 using ConnGraph = boost::adjacency_list<
58 boost::vecS, boost::vecS, boost::bidirectionalS, T, WeightedEdge>;
59 using UndirectedConnGraph = boost::adjacency_list<
60 boost::setS, boost::vecS, boost::undirectedS, T, WeightedEdge>;
61 using Vertex = utils::vertex<ConnGraph>;
62 using UndirectedVertex = utils::vertex<UndirectedConnGraph>;
63 using Connection = typename AbstractGraph<T>::Edge;
64 using AbstractGraph<T>::nodes_;
65
66 public:
67 using AbstractGraph<T>::node_exists;
68 using AbstractGraph<T>::edge_exists;
69 using AbstractGraph<T>::get_all_nodes_vec;
70 using AbstractGraph<T>::get_all_edges_vec;
71 using AbstractGraph<T>::n_nodes;
72
73 /** Construct an empty graph. */
74
2/4
✓ Branch 2 taken 19 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 19 times.
✗ Branch 7 not taken.
 19 DirectedGraphBase() : AbstractGraph<T>(), graph(), node_to_vertex() {}
75
76 /** Construct a graph with no edges. */
77 79 explicit DirectedGraphBase(const std::vector<T>& nodes)
78
2/4
✓ Branch 2 taken 79 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 79 times.
✗ Branch 7 not taken.
 79 : AbstractGraph<T>(nodes), graph() {
79
2/2
✓ Branch 5 taken 1444 times.
✓ Branch 6 taken 79 times.
2/2
✓ Decision 'true' taken 1444 times.
✓ Decision 'false' taken 79 times.
 1523 for (const T& node : nodes) {
80
1/2
✓ Branch 1 taken 1444 times.
✗ Branch 2 not taken.
 1444 add_node(node);
81 }
82 79 }
83
84 /** Construct a graph from its edges. */
85 ✗ explicit DirectedGraphBase(const std::vector<Connection>& edges) : graph() {
86
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ for (auto [node1, node2] : edges) {
87
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (!node_exists(node1)) {
88 ✗ add_node(node1);
89 }
90
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (!node_exists(node2)) {
91 ✗ add_node(node2);
92 }
93
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (node1 == node2) {
94 ✗ throw std::invalid_argument(
95 "An edge can not be added from a node to itself.");
96 }
97 ✗ add_connection(node1, node2);
98 }
99 }
100
101 /** Test whether two nodes are connected. */
102 ✗ bool edge_exists(const T& node1, const T& node2) const override {
103
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (!node_exists(node1) || !node_exists(node2)) {
104 ✗ throw NodeDoesNotExistError(
105 "The nodes passed to DirectedGraph::edge_exists must exist");
106 }
107 ✗ auto [_, exists] =
108 ✗ boost::edge(to_vertices(node1), to_vertices(node2), graph);
109 ✗ return exists;
110 }
111
112 /** Add a new node to the graph. */
113 ✗ void add_node(const T& node) {
114 ✗ nodes_.insert(node);
115 ✗ Vertex v = boost::add_vertex(node, graph);
116 ✗ node_to_vertex.left.insert({node, v});
117 }
118
119 /** Remove a node from the graph. */
120 1068 void remove_node(const T& node) {
121
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1068 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 1068 times.
 1068 if (!node_exists(node)) {
122 ✗ throw NodeDoesNotExistError(
123 "The node passed to DirectedGraph::remove_node must exist!");
124 }
125 1068 nodes_.erase(node);
126 1068 Vertex v = to_vertices(node);
127 1068 boost::clear_vertex(v, graph);
128 1068 utils::remove_vertex_with_map(v, graph, node_to_vertex.right);
129 1068 }
130
131 /** Add a weighted edge to the graph. */
132 ✗ void add_connection(const T& node1, const T& node2, unsigned weight = 1) {
133
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (!node_exists(node1) || !node_exists(node2)) {
134 ✗ throw NodeDoesNotExistError(
135 "The nodes passed to DirectedGraph::add_connection must exist");
136 }
137
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (node1 == node2) {
138 ✗ throw std::invalid_argument(
139 "A connection can not be added between a node to itself.");
140 }
141 ✗ boost::add_edge(
142 ✗ to_vertices(node1), to_vertices(node2), WeightedEdge(weight), graph);
143 }
144
145 /** Remove an edge from the graph. */
146 1 void remove_connection(const Connection& edge) {
147
5/10
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 1 times.
✗ Branch 10 not taken.
✓ Branch 11 taken 1 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 1 times.
 1 if (!node_exists(edge.first) || !node_exists(edge.second)) {
148 ✗ throw NodeDoesNotExistError(
149 "Trying to remove an edge with non-existent vertices");
150 }
151 1 auto [e, exists] =
152
3/6
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 times.
✗ Branch 8 not taken.
 1 boost::edge(to_vertices(edge.first), to_vertices(edge.second), graph);
153
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 1 times.
 1 if (!exists) {
154 ✗ throw EdgeDoesNotExistError(
155 "The edge (" + edge.first.repr() + ", " + edge.second.repr() +
156 ") cannot be removed as it does not exist");
157 }
158
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 utils::remove_edge_with_map(e, graph, node_to_vertex.right);
159 1 }
160
161 /** Remove an edge between two nodes. */
162 ✗ void remove_connection(const T& node1, const T& node2) {
163 ✗ remove_connection({node1, node2});
164 }
165
166 /**
167 * Get the weight of an edge between two nodes.
168 *
169 * Returns 0 if the edge does not exist.
170 */
171 10734 unsigned get_connection_weight(const T& node1, const T& node2) const {
172
5/10
✓ Branch 1 taken 10734 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 10734 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 10734 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 10734 times.
✗ Branch 10 not taken.
✓ Branch 11 taken 10734 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 10734 times.
 10734 if (!node_exists(node1) || !node_exists(node2)) {
173 ✗ throw NodeDoesNotExistError(
174 "Trying to retrieve edge weight from non-existent vertices");
175 }
176 10734 auto [e, exists] =
177
3/6
✓ Branch 1 taken 10734 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 10734 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 10734 times.
✗ Branch 8 not taken.
 10734 boost::edge(to_vertices(node1), to_vertices(node2), graph);
178
2/2
✓ Branch 0 taken 4262 times.
✓ Branch 1 taken 6472 times.
2/2
✓ Decision 'true' taken 4262 times.
✓ Decision 'false' taken 6472 times.
 10734 if (!exists) {
179 4262 return 0;
180 }
181
182
1/2
✓ Branch 1 taken 6472 times.
✗ Branch 2 not taken.
 6472 return graph[e].weight;
183 }
184
185 /** Get the degree of a node. */
186 1371 unsigned get_degree(const T& node) const {
187
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1371 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 1371 times.
 1371 if (!node_exists(node)) {
188 ✗ throw NodeDoesNotExistError(
189 "Trying to retrieve vertex degree from non-existent vertex");
190 }
191 1371 return boost::degree(to_vertices(node), graph);
192 }
193
194 /** Get the out-degree of a node. */
195 ✗ unsigned get_out_degree(const T& node) const {
196
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (!node_exists(node)) {
197 ✗ throw NodeDoesNotExistError(
198 "Trying to get outdegree from non-existent vertex");
199 }
200 ✗ return boost::out_degree(to_vertices(node), graph);
201 }
202
203 /** Number of edges. */
204 ✗ inline unsigned n_connections() const { return boost::num_edges(graph); }
205
206 /** Number of nodes with degree > 0. */
207 ✗ inline unsigned n_connected() const {
208 ✗ auto [beg, end] = boost::vertices(graph);
209 ✗ auto nonzero_deg = [this](Vertex v) { return boost::degree(v, graph) > 0; };
210 ✗ return std::count_if(beg, end, nonzero_deg);
211 }
212
213 /** All edges in the graph. */
214 ✗ std::set<Connection> edges() const {
215 ✗ std::vector<Connection> vec = get_all_edges_vec();
216 ✗ return std::set(vec.begin(), vec.end());
217 }
218
219 /** All edges as a vector. */
220 ✗ std::vector<Connection> get_all_edges_vec() const override {
221 ✗ std::vector<Connection> out;
222
0/1
? Decision couldn't be analyzed.
 ✗ for (auto e : get_edges_it()) {
223 ✗ T source = graph[boost::source(e, graph)];
224 ✗ T target = graph[boost::target(e, graph)];
225 ✗ out.push_back({source, target});
226 }
227 ✗ return out;
228 }
229
230 /** Return an unweighted undirected graph with the same connectivity. */
231 ✗ UndirectedConnGraph get_undirected_connectivity() const {
232 ✗ return graphs::utils::symmetrise<UndirectedConnGraph>(graph);
233 }
234
235 /** Get all distances between pairs of nodes. */
236 ✗ std::vector<std::size_t> get_distances(const T& root) const {
237
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (!node_exists(root)) {
238 ✗ throw NodeDoesNotExistError(
239 "Trying to get distances from non-existent root vertex");
240 }
241 return run_bfs(to_vertices(root), get_undirected_connectivity())
242 ✗ .get_dists();
243 }
244
245 /** Get the distance between two nodes. */
246 ✗ unsigned get_distance(const T& node1, const T& node2) const override {
247
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (node1 == node2) {
248 ✗ return 0;
249 }
250 ✗ size_t d = get_distances(node1)[to_vertices(node2)];
251
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (d == 0) {
252 ✗ throw NodesNotConnected(node1, node2);
253 }
254 ✗ return d;
255 }
256
257 /** Remove nodes with degree 0 */
258 61 inline void remove_stray_nodes() {
259 61 std::set<T> strays;
260
2/2
✓ Branch 5 taken 1323 times.
✓ Branch 6 taken 61 times.
2/2
✓ Decision 'true' taken 1323 times.
✓ Decision 'false' taken 61 times.
 1384 for (const T& node : nodes_) {
261
3/4
✓ Branch 1 taken 1323 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1068 times.
✓ Branch 4 taken 255 times.
2/2
✓ Decision 'true' taken 1068 times.
✓ Decision 'false' taken 255 times.
 1323 if (get_degree(node) == 0) {
262
1/2
✓ Branch 1 taken 1068 times.
✗ Branch 2 not taken.
 1068 strays.insert(node);
263 }
264 }
265
2/2
✓ Branch 5 taken 1068 times.
✓ Branch 6 taken 61 times.
2/2
✓ Decision 'true' taken 1068 times.
✓ Decision 'false' taken 61 times.
 1129 for (const T& node : strays) {
266
1/2
✓ Branch 1 taken 1068 times.
✗ Branch 2 not taken.
 1068 remove_node(node);
267 }
268 61 }
269
270 /* Return nodes with maximum degree. */
271 20 std::set<T> max_degree_nodes() const {
272 20 std::set<T> out;
273
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 auto max_vertices = graphs::utils::max_degree_nodes(graph);
274
2/4
✓ Branch 2 taken 20 times.
✗ Branch 3 not taken.
✓ Branch 7 taken 20 times.
✗ Branch 8 not taken.
 20 std::transform(
275 max_vertices.begin(), max_vertices.end(),
276 std::inserter(out, out.begin()),
277 131 [this](Vertex v) { return get_node(v); });
278 40 return out;
279 20 }
280
281 /** Return nodes with minimum degree. */
282 446 std::set<T> min_degree_nodes() const {
283 446 std::set<T> out;
284
1/2
✓ Branch 1 taken 446 times.
✗ Branch 2 not taken.
 446 auto min_vertices = graphs::utils::min_degree_nodes(graph);
285
2/4
✓ Branch 2 taken 446 times.
✗ Branch 3 not taken.
✓ Branch 7 taken 446 times.
✗ Branch 8 not taken.
 446 std::transform(
286 min_vertices.begin(), min_vertices.end(),
287 std::inserter(out, out.begin()),
288 893 [this](Vertex v) { return get_node(v); });
289 892 return out;
290 446 }
291
292 /** Returns path between two nodes. */
293 309 std::vector<T> get_path(const T& root, const T& target) const {
294
5/10
✓ Branch 1 taken 309 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 309 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 309 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 309 times.
✗ Branch 10 not taken.
✓ Branch 11 taken 309 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 309 times.
 309 if (!node_exists(root) || !node_exists(target)) {
295 ✗ throw NodeDoesNotExistError(
296 "Trying to get path between non-existent vertices");
297 }
298 using parent_vec = typename BFS<UndirectedConnGraph>::parent_vec;
299
300
1/2
✓ Branch 1 taken 309 times.
✗ Branch 2 not taken.
 309 const UndirectedConnGraph& g = get_undirected_connectivity();
301
2/4
✓ Branch 1 taken 309 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 309 times.
✗ Branch 5 not taken.
 309 auto bfs = run_bfs(to_vertices(root), g);
302
303 930 auto to_node = [&g](UndirectedVertex v) { return g[v]; };
304
2/4
✓ Branch 1 taken 309 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 309 times.
✗ Branch 5 not taken.
 309 parent_vec path = bfs.path_to_root(to_vertices(target));
305
1/2
✓ Branch 3 taken 309 times.
✗ Branch 4 not taken.
 309 std::vector<T> converted_path(path.size());
306
1/2
✓ Branch 4 taken 309 times.
✗ Branch 5 not taken.
 309 std::transform(path.begin(), path.end(), converted_path.begin(), to_node);
307 618 return converted_path;
308 309 }
309
310 /** Get all neighbours of a node. */
311 56706 std::set<T> get_neighbour_nodes(const T& node) const {
312
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 56706 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 56706 times.
 56706 if (!node_exists(node)) {
313 ✗ throw NodeDoesNotExistError(
314 "Trying to get neighbours from non-existent vertex");
315 }
316 56706 std::set<T> neighbours;
317
5/8
✓ Branch 1 taken 56706 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 56706 times.
✗ Branch 5 not taken.
✓ Branch 9 taken 133987 times.
✗ Branch 10 not taken.
✓ Branch 11 taken 77281 times.
✓ Branch 12 taken 56706 times.
0/1
? Decision couldn't be analyzed.
 133987 for (auto [it, end] = boost::out_edges(to_vertices(node), graph); it != end;
318 77281 ++it) {
319
4/8
✓ Branch 1 taken 77281 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 77281 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 77281 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 77281 times.
✗ Branch 12 not taken.
 77281 neighbours.insert(get_node(boost::target(*it, graph)));
320 }
321
5/8
✓ Branch 1 taken 56706 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 56706 times.
✗ Branch 5 not taken.
✓ Branch 9 taken 133780 times.
✗ Branch 10 not taken.
✓ Branch 11 taken 77074 times.
✓ Branch 12 taken 56706 times.
0/1
? Decision couldn't be analyzed.
 133780 for (auto [it, end] = boost::in_edges(to_vertices(node), graph); it != end;
322 77074 ++it) {
323
4/8
✓ Branch 1 taken 77074 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 77074 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 77074 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 77074 times.
✗ Branch 12 not taken.
 77074 neighbours.insert(get_node(boost::source(*it, graph)));
324 }
325 56706 return neighbours;
326 }
327
328 4 bool operator==(const DirectedGraphBase<T>& other) const {
329
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 4 times.
0/1
? Decision couldn't be analyzed.
 4 if (nodes_ != other.nodes_) return false;
330
2/2
✓ Branch 5 taken 15 times.
✓ Branch 6 taken 4 times.
2/2
✓ Decision 'true' taken 15 times.
✓ Decision 'false' taken 4 times.
 19 for (const T& u : nodes_) {
331
2/2
✓ Branch 5 taken 63 times.
✓ Branch 6 taken 15 times.
2/2
✓ Decision 'true' taken 63 times.
✓ Decision 'false' taken 15 times.
 78 for (const T& v : nodes_) {
332
3/4
✓ Branch 1 taken 63 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 15 times.
✓ Branch 4 taken 48 times.
2/2
✓ Decision 'true' taken 15 times.
✓ Decision 'false' taken 48 times.
 63 if (this->edge_exists(u, v)) {
333
2/4
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 15 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 15 times.
 15 if (!other.edge_exists(u, v))
334 ✗ return false;
335 15 else if (
336
1/2
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
 15 this->get_connection_weight(u, v) !=
337
2/4
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 15 times.
 15 other.get_connection_weight(u, v))
338 ✗ return false;
339
2/4
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 48 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 48 times.
 48 } else if (other.edge_exists(u, v))
340 ✗ return false;
341 }
342 }
343 4 return true;
344 }
345
346 protected:
347 /** get edge iterator */
348 ✗ auto get_edges_it() const {
349 ✗ return boost::make_iterator_range(boost::edges(graph));
350 }
351
352 /** get vertex iterator */
353 ✗ auto get_vertices_it() const {
354 ✗ return boost::make_iterator_range(boost::vertices(graph));
355 }
356
357 using vertex_bimap = boost::bimap<T, Vertex>;
358 using left_map = typename vertex_bimap::left_map;
359 using right_map = typename vertex_bimap::right_map;
360 /* get node from vertex */
361 201101 const T& get_node(Vertex v) const { return graph[v]; }
362
363 ✗ left_map& to_vertices() { return node_to_vertex.left; }
364 ✗ const left_map& to_vertices() const { return node_to_vertex.left; }
365 ✗ Vertex to_vertices(const T& node) const { return to_vertices().at(node); }
366
367 ✗ right_map& from_vertices() { return node_to_vertex.right; }
368 ✗ const right_map& from_vertices() const { return node_to_vertex.right; }
369 ✗ T from_vertices(Vertex v) const { return from_vertices().at(v); }
370
371 ConnGraph graph;
372 vertex_bimap node_to_vertex;
373 };
374
375 /**
376 * DirectedGraph instances are loop-free directed graphs. It is a wrapper around
377 * a BGL graph that provides a clean class API, taking care of mapping all BGL
378 * vertices and edge pointers to nodes, respectively pairs of nodes.
379 *
380 * The vertices and edges can be given weights of type double if desired, and
381 * the underlying undirected graph can be computed.
382 *
383 * All functionality for this class is implemented in the base class
384 * DirectedGraphBase. This class only adds caching of some function calls for
385 * efficiency, invalidating cache in case of changes on the underlying graph.
386 */
387 template <typename T>
388 class DirectedGraph : public DirectedGraphBase<T> {
389 private:
390 using Base = DirectedGraphBase<T>;
391
392 public:
393 using Base::Base;
394 using Base::get_all_nodes_vec;
395 using Base::n_nodes;
396 using Base::node_exists;
397 /* useful type synonyms */
398 using UndirectedConnGraph = typename Base::UndirectedConnGraph;
399 using ConnGraph = typename Base::ConnGraph;
400 using Connection = typename Base::Connection;
401 using Vertex = typename Base::Vertex;
402
403 /**
404 * Get all distances between nodes.
405 */
406 21992 const std::vector<std::size_t>& get_distances(const T& root) const& {
407 // We cache distances. A value of zero in the cache implies that the nodes
408 // are disconnected (unless they are equal).
409
3/4
✓ Branch 2 taken 21992 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 1606 times.
✓ Branch 6 taken 20386 times.
2/2
✓ Decision 'true' taken 1606 times.
✓ Decision 'false' taken 20386 times.
 21992 if (distance_cache.find(root) == distance_cache.end()) {
410
1/2
✓ Branch 2 taken 1606 times.
✗ Branch 3 not taken.
 1606 distance_cache[root] = Base::get_distances(root);
411 }
412 21992 return distance_cache[root];
413 }
414
415 /**
416 * Get all distances between nodes.
417 */
418 ✗ std::vector<std::size_t>&& get_distances(const T& root) const&& {
419
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (distance_cache.find(root) == distance_cache.end()) {
420 ✗ distance_cache[root] = Base::get_distances(root);
421 }
422 ✗ return std::move(distance_cache[root]);
423 }
424
425 ✗ unsigned get_distance(const T& node1, const T& node2) const override {
426
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (node1 == node2) {
427 ✗ return 0;
428 }
429 size_t d;
430
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (distance_cache.find(node1) != distance_cache.end()) {
431 ✗ d = distance_cache[node1][this->to_vertices(node2)];
432
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ } else if (distance_cache.find(node2) != distance_cache.end()) {
433 ✗ d = distance_cache[node2][this->to_vertices(node1)];
434 } else {
435 ✗ distance_cache[node1] = Base::get_distances(node1);
436 ✗ d = distance_cache[node1][this->to_vertices(node2)];
437 }
438
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (d == 0) {
439 ✗ throw NodesNotConnected(node1, node2);
440 }
441 ✗ return d;
442 }
443
444 ✗ unsigned get_diameter() override {
445 ✗ unsigned N = n_nodes();
446
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (N == 0) {
447 ✗ throw std::logic_error("Graph is empty.");
448 }
449
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (!this->diameter_) {
450 ✗ this->diameter_ = 0;
451 ✗ const std::vector<T> nodes = get_all_nodes_vec();
452
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ for (unsigned i = 0; i < N; i++) {
453
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ for (unsigned j = i + 1; j < N; j++) {
454 ✗ unsigned d = get_distance(nodes[i], nodes[j]);
455
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (d > *this->diameter_) this->diameter_ = d;
456 }
457 }
458 }
459 ✗ return *this->diameter_;
460 }
461
462 /** Returns all nodes at a given distance from a given 'source' node */
463 19368 std::vector<T> nodes_at_distance(const T& root, std::size_t distance) const {
464
2/4
✓ Branch 1 taken 19368 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 19368 times.
✗ Branch 5 not taken.
 19368 auto dists = get_distances(root);
465 19368 std::vector<T> out;
466
2/2
✓ Branch 1 taken 492719 times.
✓ Branch 2 taken 19368 times.
2/2
✓ Decision 'true' taken 492719 times.
✓ Decision 'false' taken 19368 times.
 512087 for (unsigned i = 0; i < dists.size(); ++i) {
467
2/2
✓ Branch 1 taken 45722 times.
✓ Branch 2 taken 446997 times.
2/2
✓ Decision 'true' taken 45722 times.
✓ Decision 'false' taken 446997 times.
 492719 if (dists[i] == distance) {
468
2/4
✓ Branch 1 taken 45722 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 45722 times.
✗ Branch 5 not taken.
 45722 out.push_back(this->get_node(i));
469 }
470 }
471 38736 return out;
472 19368 }
473
474 /** Return an unweighted undirected graph with the same connectivity. */
475 85 const UndirectedConnGraph& get_undirected_connectivity() const& {
476 // we cache the undirected graph
477
2/2
✓ Branch 1 taken 83 times.
✓ Branch 2 taken 2 times.
2/2
✓ Decision 'true' taken 83 times.
✓ Decision 'false' taken 2 times.
 85 if (!undir_graph) {
478
1/2
✓ Branch 2 taken 83 times.
✗ Branch 3 not taken.
 83 undir_graph = Base::get_undirected_connectivity();
479 }
480 85 return undir_graph.value();
481 }
482
483 /** Return an unweighted undirected graph with the same connectivity. */
484 ✗ UndirectedConnGraph&& get_undirected_connectivity() const&& {
485
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (!undir_graph) {
486 ✗ undir_graph = Base::get_undirected_connectivity();
487 }
488 ✗ return std::move(undir_graph.value());
489 }
490
491 // The following functions invalidate caching.
492
493 /** Remove a node from the graph. */
494 448 void remove_node(const T& node) {
495 448 invalidate_cache();
496 448 Base::remove_node(node);
497 448 }
498
499 /** Add a node to the graph. */
500 ✗ void add_node(const T& node) {
501 ✗ invalidate_cache();
502 ✗ Base::add_node(node);
503 }
504
505 /** Remove nodes with degree 0. */
506 61 void remove_stray_nodes() {
507 61 invalidate_cache();
508 61 Base::remove_stray_nodes();
509 61 }
510
511 /** Add a (weighted) edge between two nodes. */
512 ✗ void add_connection(const T& node1, const T& node2, unsigned weight = 1) {
513 ✗ invalidate_cache();
514 ✗ Base::add_connection(node1, node2, weight);
515 }
516
517 /** Remove an edge. */
518 3 void remove_connection(const Connection& edge) {
519 3 invalidate_cache();
520 3 Base::remove_connection(edge);
521 3 }
522
523 /** Remove a connection between two nodes. */
524 ✗ void remove_connection(const T& node1, const T& node2) {
525 ✗ invalidate_cache();
526 ✗ Base::remove_connection(node1, node2);
527 }
528
529 private:
530 ✗ inline void invalidate_cache() {
531 ✗ distance_cache.clear();
532 ✗ undir_graph = std::nullopt;
533 }
534 mutable std::map<T, std::vector<std::size_t>> distance_cache;
535 mutable std::optional<UndirectedConnGraph> undir_graph;
536 };
537
538 } // namespace tket::graphs
539