1/*
2 * Copyright (c) 2018, Intel Corporation
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are met:
6 *
7 * * Redistributions of source code must retain the above copyright notice,
8 * this list of conditions and the following disclaimer.
9 * * Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 * * Neither the name of Intel Corporation nor the names of its contributors
13 * may be used to endorse or promote products derived from this software
14 * without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28
29/**
30 * \file
31 * \brief Adaptor that presents an undirected view of a bidirectional BGL graph.
32 *
33 * Analogous to the reverse_graph adapter. You can construct one of these for
34 * bidirectional graph g with:
35 *
36 * auto ug = make_undirected_graph(g);
37 *
38 * The vertex descriptor type is the same as that of the underlying graph, but
39 * the edge descriptor is different.
40 */
41
42#ifndef GRAPH_UNDIRECTED_H
43#define GRAPH_UNDIRECTED_H
44
45#include "util/operators.h"
46
47#include <boost/graph/adjacency_iterator.hpp>
48#include <boost/graph/graph_traits.hpp>
49#include <boost/graph/properties.hpp>
50#include <boost/iterator/iterator_facade.hpp>
51
52#include <type_traits>
53#include <utility>
54
55namespace ue2 {
56
57struct undirected_graph_tag {};
58
59template <class BidirectionalGraph, class GraphRef>
60class undirected_graph;
61
62namespace undirected_detail {
63
64template <typename BidirectionalGraph>
65class undirected_graph_edge_descriptor
66 : totally_ordered<undirected_graph_edge_descriptor<BidirectionalGraph>> {
67 using base_graph_type = BidirectionalGraph;
68 using base_graph_traits = typename boost::graph_traits<base_graph_type>;
69 using base_edge_type = typename base_graph_traits::edge_descriptor;
70 using base_vertex_type = typename base_graph_traits::vertex_descriptor;
71
72 base_edge_type underlying_edge;
73 const base_graph_type *g;
74 bool reverse; // if true, reverse vertices in source() and target()
75
76 inline std::pair<base_vertex_type, base_vertex_type>
77 canonical_edge() const {
78 auto u = std::min(source(underlying_edge, *g),
79 target(underlying_edge, *g));
80 auto v = std::max(source(underlying_edge, *g),
81 target(underlying_edge, *g));
82 return std::make_pair(u, v);
83 }
84
85 template <class BidiGraph, class GraphRef>
86 friend class ::ue2::undirected_graph;
87
88public:
89 undirected_graph_edge_descriptor() = default;
90
91 undirected_graph_edge_descriptor(base_edge_type edge,
92 const base_graph_type &g_in,
93 bool reverse_in)
94 : underlying_edge(std::move(edge)), g(&g_in), reverse(reverse_in) {}
95
96 bool operator==(const undirected_graph_edge_descriptor &other) const {
97 return canonical_edge() == other.canonical_edge();
98 }
99
100 bool operator<(const undirected_graph_edge_descriptor &other) const {
101 return canonical_edge() < other.canonical_edge();
102 }
103
104 base_vertex_type get_source() const {
105 return reverse ? target(underlying_edge, *g)
106 : source(underlying_edge, *g);
107 }
108
109 base_vertex_type get_target() const {
110 return reverse ? source(underlying_edge, *g)
111 : target(underlying_edge, *g);
112 }
113};
114
115} // namespace undirected_detail
116
117template <class BidirectionalGraph, class GraphRef = const BidirectionalGraph &>
118class undirected_graph {
119private:
120 using Self = undirected_graph<BidirectionalGraph, GraphRef>;
121 using Traits = boost::graph_traits<BidirectionalGraph>;
122
123public:
124 using base_type = BidirectionalGraph;
125 using base_ref_type = GraphRef;
126
127 explicit undirected_graph(GraphRef g_in) : g(g_in) {}
128
129 // Graph requirements
130 using vertex_descriptor = typename Traits::vertex_descriptor;
131 using edge_descriptor =
132 undirected_detail::undirected_graph_edge_descriptor<base_type>;
133 using directed_category = boost::undirected_tag;
134 using edge_parallel_category = boost::disallow_parallel_edge_tag;
135 using traversal_category = typename Traits::traversal_category;
136
137 // IncidenceGraph requirements
138
139 /**
140 * \brief Templated iterator used for out_edge_iterator and
141 * in_edge_iterator, depending on the value of Reverse.
142 */
143 template <bool Reverse>
144 class adj_edge_iterator
145 : public boost::iterator_facade<
146 adj_edge_iterator<Reverse>, edge_descriptor,
147 boost::forward_traversal_tag, edge_descriptor> {
148 vertex_descriptor u;
149 const base_type *g;
150 typename Traits::in_edge_iterator in_it;
151 typename Traits::out_edge_iterator out_it;
152 bool done_in = false;
153 public:
154 adj_edge_iterator() = default;
155
156 adj_edge_iterator(vertex_descriptor u_in, const base_type &g_in,
157 bool end_iter)
158 : u(std::move(u_in)), g(&g_in) {
159 auto pi = in_edges(u, *g);
160 auto po = out_edges(u, *g);
161 if (end_iter) {
162 in_it = pi.second;
163 out_it = po.second;
164 done_in = true;
165 } else {
166 in_it = pi.first;
167 out_it = po.first;
168 if (in_it == pi.second) {
169 done_in = true;
170 find_first_valid_out();
171 }
172 }
173 }
174
175 private:
176 friend class boost::iterator_core_access;
177
178 void find_first_valid_out() {
179 auto out_end = out_edges(u, *g).second;
180 for (; out_it != out_end; ++out_it) {
181 auto v = target(*out_it, *g);
182 if (!edge(v, u, *g).second) {
183 break;
184 }
185 }
186 }
187
188 void increment() {
189 if (!done_in) {
190 auto in_end = in_edges(u, *g).second;
191 assert(in_it != in_end);
192 ++in_it;
193 if (in_it == in_end) {
194 done_in = true;
195 find_first_valid_out();
196 }
197 } else {
198 ++out_it;
199 find_first_valid_out();
200 }
201 }
202 bool equal(const adj_edge_iterator &other) const {
203 return in_it == other.in_it && out_it == other.out_it;
204 }
205 edge_descriptor dereference() const {
206 if (done_in) {
207 return edge_descriptor(*out_it, *g, Reverse);
208 } else {
209 return edge_descriptor(*in_it, *g, !Reverse);
210 }
211 }
212 };
213
214 using out_edge_iterator = adj_edge_iterator<false>;
215 using in_edge_iterator = adj_edge_iterator<true>;
216
217 using degree_size_type = typename Traits::degree_size_type;
218
219 // AdjacencyGraph requirements
220 using adjacency_iterator =
221 typename boost::adjacency_iterator_generator<Self, vertex_descriptor,
222 out_edge_iterator>::type;
223 using inv_adjacency_iterator =
224 typename boost::inv_adjacency_iterator_generator<
225 Self, vertex_descriptor, in_edge_iterator>::type;
226
227 // VertexListGraph requirements
228 using vertex_iterator = typename Traits::vertex_iterator;
229
230 // EdgeListGraph requirements
231 enum {
232 is_edge_list = std::is_convertible<traversal_category,
233 boost::edge_list_graph_tag>::value
234 };
235
236 /** \brief Iterator used for edges(). */
237 class edge_iterator
238 : public boost::iterator_facade<edge_iterator, edge_descriptor,
239 boost::forward_traversal_tag,
240 edge_descriptor> {
241 const base_type *g;
242 typename Traits::edge_iterator it;
243 public:
244 edge_iterator() = default;
245
246 edge_iterator(typename Traits::edge_iterator it_in,
247 const base_type &g_in)
248 : g(&g_in), it(std::move(it_in)) {
249 find_first_valid_edge();
250 }
251
252 private:
253 friend class boost::iterator_core_access;
254
255 void find_first_valid_edge() {
256 const auto end = edges(*g).second;
257 for (; it != end; ++it) {
258 const auto &u = source(*it, *g);
259 const auto &v = target(*it, *g);
260 if (!edge(v, u, *g).second) {
261 break; // No reverse edge, we must visit this one
262 }
263 if (u <= v) {
264 // We have a reverse edge, but we'll return this one (and
265 // skip the other). Note that (u, u) shouldn't be skipped.
266 break;
267 }
268 }
269 }
270
271 void increment() {
272 assert(it != edges(*g).second);
273 ++it;
274 find_first_valid_edge();
275 }
276 bool equal(const edge_iterator &other) const {
277 return it == other.it;
278 }
279 edge_descriptor dereference() const {
280 return edge_descriptor(*it, *g, false);
281 }
282 };
283
284 using vertices_size_type = typename Traits::vertices_size_type;
285 using edges_size_type = typename Traits::edges_size_type;
286
287 using graph_tag = undirected_graph_tag;
288
289 using vertex_bundle_type =
290 typename boost::vertex_bundle_type<base_type>::type;
291 using edge_bundle_type = typename boost::edge_bundle_type<base_type>::type;
292
293 vertex_bundle_type &operator[](const vertex_descriptor &d) {
294 return const_cast<base_type &>(g)[d];
295 }
296 const vertex_bundle_type &operator[](const vertex_descriptor &d) const {
297 return g[d];
298 }
299
300 edge_bundle_type &operator[](const edge_descriptor &d) {
301 return const_cast<base_type &>(g)[d.underlying_edge];
302 }
303 const edge_bundle_type &operator[](const edge_descriptor &d) const {
304 return g[d.underlying_edge];
305 }
306
307 static vertex_descriptor null_vertex() { return Traits::null_vertex(); }
308
309 // Accessor free functions follow
310
311 friend std::pair<vertex_iterator, vertex_iterator>
312 vertices(const undirected_graph &ug) {
313 return vertices(ug.g);
314 }
315
316 friend std::pair<edge_iterator, edge_iterator>
317 edges(const undirected_graph &ug) {
318 auto e = edges(ug.g);
319 return std::make_pair(edge_iterator(e.first, ug.g),
320 edge_iterator(e.second, ug.g));
321 }
322
323 friend std::pair<out_edge_iterator, out_edge_iterator>
324 out_edges(const vertex_descriptor &u, const undirected_graph &ug) {
325 return std::make_pair(out_edge_iterator(u, ug.g, false),
326 out_edge_iterator(u, ug.g, true));
327 }
328
329 friend vertices_size_type num_vertices(const undirected_graph &ug) {
330 return num_vertices(ug.g);
331 }
332
333 friend edges_size_type num_edges(const undirected_graph &ug) {
334 auto p = edges(ug);
335 return std::distance(p.first, p.second);
336 }
337
338 friend degree_size_type out_degree(const vertex_descriptor &u,
339 const undirected_graph &ug) {
340 return degree(u, ug);
341 }
342
343 friend vertex_descriptor vertex(vertices_size_type n,
344 const undirected_graph &ug) {
345 return vertex(n, ug.g);
346 }
347
348 friend std::pair<edge_descriptor, bool> edge(const vertex_descriptor &u,
349 const vertex_descriptor &v,
350 const undirected_graph &ug) {
351 auto e = edge(u, v, ug.g);
352 if (e.second) {
353 return std::make_pair(edge_descriptor(e.first, ug.g, false), true);
354 }
355 auto e_rev = edge(v, u, ug.g);
356 if (e_rev.second) {
357 return std::make_pair(edge_descriptor(e_rev.first, ug.g, true),
358 true);
359 }
360 return std::make_pair(edge_descriptor(), false);
361 }
362
363 friend std::pair<in_edge_iterator, in_edge_iterator>
364 in_edges(const vertex_descriptor &v, const undirected_graph &ug) {
365 return std::make_pair(in_edge_iterator(v, ug.g, false),
366 in_edge_iterator(v, ug.g, true));
367 }
368
369 friend std::pair<adjacency_iterator, adjacency_iterator>
370 adjacent_vertices(const vertex_descriptor &u, const undirected_graph &ug) {
371 out_edge_iterator oi, oe;
372 std::tie(oi, oe) = out_edges(u, ug);
373 return std::make_pair(adjacency_iterator(oi, &ug),
374 adjacency_iterator(oe, &ug));
375 }
376
377 friend std::pair<inv_adjacency_iterator, inv_adjacency_iterator>
378 inv_adjacent_vertices(const vertex_descriptor &v,
379 const undirected_graph &ug) {
380 in_edge_iterator ei, ee;
381 std::tie(ei, ee) = in_edges(v, ug);
382 return std::make_pair(inv_adjacency_iterator(ei, &ug),
383 inv_adjacency_iterator(ee, &ug));
384 }
385
386 friend degree_size_type in_degree(const vertex_descriptor &v,
387 const undirected_graph &ug) {
388 return degree(v, ug);
389 }
390
391 friend vertex_descriptor source(const edge_descriptor &e,
392 const undirected_graph &) {
393 return e.get_source();
394 }
395
396 friend vertex_descriptor target(const edge_descriptor &e,
397 const undirected_graph &) {
398 return e.get_target();
399 }
400
401 friend degree_size_type degree(const vertex_descriptor &u,
402 const undirected_graph &ug) {
403 auto p = out_edges(u, ug);
404 return std::distance(p.first, p.second);
405 }
406
407 // Property accessors.
408
409 template <typename Property>
410 using prop_map = typename boost::property_map<undirected_graph, Property>;
411
412 template <typename Property>
413 friend typename prop_map<Property>::type
414 get(Property p, undirected_graph &ug) {
415 return get(p, ug.g);
416 }
417
418 template <typename Property>
419 friend typename prop_map<Property>::const_type
420 get(Property p, const undirected_graph &ug) {
421 return get(p, ug.g);
422 }
423
424 template <typename Property, typename Key>
425 friend typename boost::property_traits<
426 typename prop_map<Property>::const_type>::value_type
427 get(Property p, const undirected_graph &ug, const Key &k) {
428 return get(p, ug.g, get_underlying_descriptor(k));
429 }
430
431 template <typename Property, typename Value, typename Key>
432 friend void put(Property p, const undirected_graph &ug,
433 const Key &k, const Value &val) {
434 put(p, const_cast<BidirectionalGraph &>(ug.g),
435 get_underlying_descriptor(k), val);
436 }
437
438private:
439 // Accessors are here because our free friend functions (above) cannot see
440 // edge_descriptor's private members.
441 static typename base_type::vertex_descriptor
442 get_underlying_descriptor(const vertex_descriptor &v) {
443 return v;
444 }
445 static typename base_type::edge_descriptor
446 get_underlying_descriptor(const edge_descriptor &e) {
447 return e.underlying_edge;
448 }
449
450 // Reference to underlying bidirectional graph
451 GraphRef g;
452};
453
454template <class BidirectionalGraph>
455undirected_graph<BidirectionalGraph>
456make_undirected_graph(const BidirectionalGraph &g) {
457 return undirected_graph<BidirectionalGraph>(g);
458}
459
460} // namespace ue2
461
462namespace boost {
463
464/* Derive all the property map specializations from the underlying
465 * bidirectional graph. */
466
467template <typename BidirectionalGraph, typename GraphRef, typename Property>
468struct property_map<ue2::undirected_graph<BidirectionalGraph, GraphRef>,
469 Property> {
470 using base_map_type = property_map<BidirectionalGraph, Property>;
471 using type = typename base_map_type::type;
472 using const_type = typename base_map_type::const_type;
473};
474
475template <class BidirectionalGraph, class GraphRef>
476struct vertex_property_type<ue2::undirected_graph<BidirectionalGraph, GraphRef>>
477 : vertex_property_type<BidirectionalGraph> {};
478
479template <class BidirectionalGraph, class GraphRef>
480struct edge_property_type<ue2::undirected_graph<BidirectionalGraph, GraphRef>>
481 : edge_property_type<BidirectionalGraph> {};
482
483template <class BidirectionalGraph, class GraphRef>
484struct graph_property_type<ue2::undirected_graph<BidirectionalGraph, GraphRef>>
485 : graph_property_type<BidirectionalGraph> {};
486
487template <typename BidirectionalGraph, typename GraphRef>
488struct vertex_bundle_type<ue2::undirected_graph<BidirectionalGraph, GraphRef>>
489 : vertex_bundle_type<BidirectionalGraph> {};
490
491template <typename BidirectionalGraph, typename GraphRef>
492struct edge_bundle_type<ue2::undirected_graph<BidirectionalGraph, GraphRef>>
493 : edge_bundle_type<BidirectionalGraph> {};
494
495template <typename BidirectionalGraph, typename GraphRef>
496struct graph_bundle_type<ue2::undirected_graph<BidirectionalGraph, GraphRef>>
497 : graph_bundle_type<BidirectionalGraph> {};
498
499} // namespace boost
500
501#endif // GRAPH_UNDIRECTED_H
502