1/*
2 * Copyright (c) 2016-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#ifndef UE2_GRAPH_H
30#define UE2_GRAPH_H
31
32#include "ue2common.h"
33#include "util/graph_range.h"
34#include "util/noncopyable.h"
35#include "util/operators.h"
36
37#include <boost/graph/properties.hpp> /* vertex_index_t, ... */
38#include <boost/pending/property.hpp> /* no_property */
39#include <boost/property_map/property_map.hpp>
40#include <boost/intrusive/list.hpp>
41#include <boost/iterator/iterator_adaptor.hpp>
42#include <boost/iterator/iterator_facade.hpp>
43
44#include <functional> /* hash */
45#include <tuple> /* tie */
46#include <type_traits> /* is_same, etc */
47#include <utility> /* pair, declval */
48
49/*
50 * Basic design of ue2_graph:
51 *
52 * Fairly standard adjacency list type graph structure. The main internal
53 * structures are vertex_node and edge_node.
54 *
55 * Each vertex_node maintains lists of incoming and outgoing edge_nodes, a
56 * serial number and the vertex properties.
57 *
58 * Each edge_node contains pointers to the source and target vertex as well as
59 * the serial number and edge properties.
60 *
61 * Every time an edge_node or vertex_node is created in the graph, it is given a
62 * unique serial number by increasing a private counter in the graph.
63 *
64 * The main thing to note is that the in and out edge lists are intrusive lists
65 * with the edge_node containing the necessary hooks. This means that we can
66 * easily convert the edge_node to iterators of the in_edge_list and
67 * out_edge_list and remove them from the lists.
68 *
69 * vertex_descriptor and edge_descriptor structures both just wrap pointers to
70 * the relevant node structure along with the serial number. operator<() for the
71 * descriptors is overridden to look at the serial member of the node.
72 * We do not use:
73 * - the address of the node structure as this would lead to an unstable
74 * ordering of vertices between runs.
75 * - the index field as this would mean that the generation of new index
76 * values (during say renumbering of vertex nodes after removing some
77 * vertices) would potentially reorder vertices and corrupt containers
78 * such as std::set<>.
79 * The serial number is copied into the descriptors so that we can still have
80 * descriptors in a container (such as set or unordered_set) after removing the
81 * underlying node.
82 *
83 * Hashing of descriptors is based on the serial field for similar reasons.
84 *
85 *
86 *
87 * Main differences from boost::adjacency_list<> with listS:
88 *
89 * (1) Deterministic ordering for vertices and edges
90 * boost::adjacency_list<> uses pointer ordering for vertex_descriptors. As
91 * a result, ordering of vertices and edges between runs is
92 * non-deterministic unless containers, etc use custom comparators.
93 *
94 * (2) Proper types for descriptors, etc.
95 * No more void * for vertex_descriptors and trying to use it for the wrong
96 * graph type.
97 *
98 * (3) Constant time num_edges(), num_vertices(), degree(), in_degree() and
99 * out_degree()
100 * std::list is meant to have constant time in C++11 ::size(), but this is
101 * not always implemented as people want to keep ABI compatibility with
102 * existing C++98 standard libraries (gcc 4.8). As ue2_graph_h uses
103 * intrusive lists rather than std::list this is not an issue for us.
104 *
105 * (4) Constant time remove_edge(e, g)
106 * ue2_graph uses boost::intrusive_lists internally so we can easily unlink
107 * an edge from the in and out edgelist of its source and target.
108 *
109 * (5) More efficient edge(u, v, g) and remove_edge(u, v, g)
110 * ue2_graph will check which of u and v has the smallest relevant degree
111 * and use that to search for the edge(s).
112 *
113 * (6) Automatically populate the index field of vertex and edge bundles.
114 * Saves us from doing it manually. Naturally there is nothing to prevent
115 * the user from stuffing up the index properties later.
116 *
117 * (7) Different edge iteration order
118 * ue2_graph does not maintain an explicit global edge list, so the
119 * edge_iterator is constructed out of vertex_iterator and
120 * out_edge_iterators by iterating the out_edges of each vertices. This
121 * means that edge iteration order is not insertion order like for
122 * adjacency_list.
123 *
124 * (8) null_edge()
125 * Because why not?
126 *
127 * (9) vertex and edge properties must have an index field.
128 * We generally need them so the effort has not been put into specialising
129 * for when they are not present.
130 *
131 *
132 *
133 * Possible Future Work:
134 *
135 * (1) Improve edge(u, v, g) performance
136 * This function sees a fair amount of use and is O(n) in the smallest of
137 * the source out_degree or target in_degree. This could be improved by
138 * changes on of the edge containers to be something similar to a multiset.
139 *
140 * (2) 'Lie' about the number of edges / vertices
141 *
142 * One of the main uses of num_edges() and num_vertices() is to allocate a
143 * vector, etc so that it can be indexed by edge or vertex index. If
144 * num_edges() and num_vertices() returned the appropriate size for such a
145 * vector (at least one more than the largest index), we would be able to
146 * avoid some renumbering operations. Functions would have to be provided to
147 * get the real number of vertices and edges. Having num_vertices() and
148 * num_edges() return an over-estimate is not without precedence in the BGL
149 * - the filtered_graph adaptor does the same thing and is compatible with
150 * various (all?) BGL algorithms. It is not clear that this was done
151 * deliberately for the same reason or because it is difficult for
152 * filtered_graph to get the true counts.
153 *
154 * (3) Investigate slab/pooled allocation schemes for nodes.
155 */
156
157namespace ue2 {
158
159namespace graph_detail {
160
161class graph_base : noncopyable {
162};
163
164struct default_edge_property {
165 size_t index;
166};
167
168struct default_vertex_property {
169 size_t index;
170};
171
172template<typename Graph>
173class vertex_descriptor : totally_ordered<vertex_descriptor<Graph>> {
174 using vertex_node = typename Graph::vertex_node;
175public:
176 vertex_descriptor() : p(nullptr), serial(0) {}
177 explicit vertex_descriptor(vertex_node *pp) : p(pp), serial(pp->serial) {}
178
179 operator bool() const { return p; }
180 bool operator<(const vertex_descriptor b) const {
181 if (p && b.p) {
182 /* no vertices in the same graph can have the same serial */
183 assert(p == b.p || serial != b.serial);
184 return serial < b.serial;
185 } else {
186 return p < b.p;
187 }
188 }
189 bool operator==(const vertex_descriptor b) const { return p == b.p; }
190
191 size_t hash() const {
192 return std::hash<u64a>()(serial);
193 }
194
195private:
196 vertex_node *raw(void) { return p; }
197 vertex_node *p;
198 u64a serial;
199 friend Graph;
200};
201
202template<typename Graph>
203class edge_descriptor : totally_ordered<edge_descriptor<Graph>> {
204 using edge_node = typename Graph::edge_node;
205public:
206 edge_descriptor() : p(nullptr), serial(0) {}
207 explicit edge_descriptor(edge_node *pp) : p(pp), serial(pp->serial) {}
208
209 /* Convenience ctor to allow us to directly get an edge_descriptor from
210 * edge() and add_edge(). As we have null_edges and we always allow
211 * parallel edges, the bool component of the return from these functions is
212 * not required. */
213 edge_descriptor(const std::pair<edge_descriptor, bool> &tup)
214 : p(tup.first.p), serial(tup.first.serial) {
215 assert(tup.second == (bool)tup.first);
216 }
217
218 operator bool() const { return p; }
219 bool operator<(const edge_descriptor b) const {
220 if (p && b.p) {
221 /* no edges in the same graph can have the same serial */
222 assert(p == b.p || serial != b.serial);
223 return serial < b.serial;
224 } else {
225 return p < b.p;
226 }
227 }
228 bool operator==(const edge_descriptor b) const { return p == b.p; }
229
230 size_t hash() const {
231 return std::hash<u64a>()(serial);
232 }
233
234private:
235 edge_node *raw(void) { return p; }
236 edge_node *p;
237 u64a serial;
238 friend Graph;
239};
240
241} // namespace graph_detail
242
243template<typename Graph,
244 typename VertexPropertyType = graph_detail::default_vertex_property,
245 typename EdgePropertyType = graph_detail::default_edge_property>
246class ue2_graph : graph_detail::graph_base {
247private:
248 struct in_edge_tag { };
249 struct out_edge_tag { };
250
251 struct vertex_node;
252
253 using out_edge_hook
254 = boost::intrusive::list_base_hook<boost::intrusive::tag<out_edge_tag> >;
255
256 /* in_edge_hook does not use safe mode as during graph destruction we do not
257 * maintain the in edge lists */
258 using in_edge_hook
259 = boost::intrusive::list_base_hook<boost::intrusive::tag<in_edge_tag>,
260 boost::intrusive::link_mode<boost::intrusive::normal_link> >;
261
262 struct edge_node : public out_edge_hook, public in_edge_hook {
263 explicit edge_node(u64a serial_in) : serial(serial_in) { }
264
265 vertex_node *source = nullptr;
266 vertex_node *target = nullptr;
267 const u64a serial; /*< used to order edges. We do not use props.index so
268 * that there is no danger of invalidating sets or
269 * other containers by changing the index due to
270 * renumbering */
271 EdgePropertyType props;
272 };
273
274 template<typename hook_type> using vertex_edge_list
275 = boost::intrusive::list<edge_node,
276 boost::intrusive::base_hook<hook_type> >;
277
278 struct vertex_node : public boost::intrusive::list_base_hook<> {
279 explicit vertex_node(u64a serial_in) : serial(serial_in) { }
280
281 VertexPropertyType props;
282 const u64a serial; /*< used to order vertices. We do not use props.index
283 * so that there is no danger of invalidating sets or
284 * other containers by changing the index due to
285 * renumbering */
286
287 /* The incoming edges are not considered owned by the vertex */
288 vertex_edge_list<in_edge_hook> in_edge_list;
289
290 /* The out going edges are considered owned by the vertex and
291 * need to be freed when the graph is being destroyed */
292 vertex_edge_list<out_edge_hook> out_edge_list;
293
294 /* The destructor only frees memory owned by the vertex and will leave
295 * the neighbour's edges in a bad state. If a vertex is being removed
296 * (rather than the graph being destroyed), then the more gentle clean
297 * up of clear_vertex() is required to be called first */
298 ~vertex_node() {
299 out_edge_list.clear_and_dispose(delete_disposer());
300 }
301 };
302
303 struct delete_disposer {
304 template<typename T> void operator()(const T *d) const { delete d; }
305 };
306
307 struct in_edge_disposer {
308 void operator()(edge_node *e) const {
309 /* remove from source's out edge list before deleting */
310 vertex_node *u = e->source;
311 u->out_edge_list.erase(u->out_edge_list.iterator_to(*e));
312 delete e;
313 }
314 };
315
316 struct out_edge_disposer {
317 void operator()(edge_node *e) const {
318 /* remove from target's in edge list before deleting */
319 vertex_node *v = e->target;
320 v->in_edge_list.erase(v->in_edge_list.iterator_to(*e));
321 delete e;
322 }
323 };
324
325 using vertices_list_type
326 = boost::intrusive::list<vertex_node,
327 boost::intrusive::base_hook<boost::intrusive::list_base_hook<> > >;
328
329 vertices_list_type vertices_list;
330
331protected: /* to allow renumbering */
332 static const size_t N_SPECIAL_VERTICES = 0; /* override in derived class */
333 size_t next_vertex_index = 0;
334 size_t next_edge_index = 0;
335
336private:
337 size_t graph_edge_count = 0; /* maintained explicitly as we have no global
338 edge list */
339
340 u64a next_serial = 0;
341 u64a new_serial() {
342 u64a serial = next_serial++;
343 if (!next_serial) {
344 /* if we have created enough graph edges/vertices to overflow a u64a
345 * we must have spent close to an eternity adding to this graph so
346 * something must have gone very wrong and we will not be producing
347 * a final bytecode in a reasonable amount of time. Or, more likely,
348 * the next_serial value has become corrupt. */
349 throw std::overflow_error("too many graph edges/vertices created");
350 }
351 return serial;
352 }
353public:
354 using vertex_descriptor = graph_detail::vertex_descriptor<ue2_graph>;
355 using edge_descriptor = graph_detail::edge_descriptor<ue2_graph>;
356 friend vertex_descriptor;
357 friend edge_descriptor;
358
359 using vertices_size_type = typename vertices_list_type::size_type;
360 using degree_size_type
361 = typename vertex_edge_list<out_edge_hook>::size_type;
362 using edges_size_type = size_t;
363
364 using vertex_property_type = VertexPropertyType;
365 using edge_property_type = EdgePropertyType;
366
367 using graph_bundled = boost::no_property;
368 using vertex_bundled = VertexPropertyType;
369 using edge_bundled = EdgePropertyType;
370
371private:
372 /* Note: apparently, nested class templates cannot be fully specialised but
373 * they can be partially specialised. Sigh, ... */
374 template<typename BundleType, typename dummy = void>
375 struct bundle_key_type {
376 };
377
378 template<typename dummy>
379 struct bundle_key_type<VertexPropertyType, dummy> {
380 using type = vertex_descriptor;
381 };
382
383 template<typename dummy>
384 struct bundle_key_type<EdgePropertyType, dummy> {
385 using type = edge_descriptor;
386 };
387
388public:
389 class out_edge_iterator : public boost::iterator_adaptor<
390 out_edge_iterator,
391 typename vertex_edge_list<out_edge_hook>::const_iterator,
392 edge_descriptor,
393 boost::bidirectional_traversal_tag,
394 edge_descriptor> {
395 using super = typename out_edge_iterator::iterator_adaptor_;
396 public:
397 out_edge_iterator() : super() { }
398 explicit out_edge_iterator(
399 typename vertex_edge_list<out_edge_hook>::const_iterator it)
400 : super(it) { }
401 edge_descriptor dereference() const {
402 /* :( const_cast makes me sad but constness is defined by the graph
403 * parameter of bgl api calls */
404 return edge_descriptor(const_cast<edge_node *>(&*super::base()));
405 }
406 };
407
408 class in_edge_iterator : public boost::iterator_adaptor<
409 in_edge_iterator,
410 typename vertex_edge_list<in_edge_hook>::const_iterator,
411 edge_descriptor,
412 boost::bidirectional_traversal_tag,
413 edge_descriptor> {
414 using super = typename in_edge_iterator::iterator_adaptor_;
415 public:
416 in_edge_iterator() : super() { }
417 explicit in_edge_iterator(
418 typename vertex_edge_list<in_edge_hook>::const_iterator it)
419 : super(it) { }
420 edge_descriptor dereference() const {
421 /* :( const_cast makes me sad but constness is defined by the graph
422 * parameter of bgl api calls */
423 return edge_descriptor(const_cast<edge_node *>(&*super::base()));
424 }
425 };
426
427 class adjacency_iterator : public boost::iterator_adaptor<
428 adjacency_iterator,
429 out_edge_iterator,
430 vertex_descriptor,
431 boost::bidirectional_traversal_tag,
432 vertex_descriptor> {
433 using super = typename adjacency_iterator::iterator_adaptor_;
434 public:
435 adjacency_iterator(out_edge_iterator a) : super(std::move(a)) { }
436 adjacency_iterator() { }
437
438 vertex_descriptor dereference() const {
439 return vertex_descriptor(super::base()->p->target);
440 }
441 };
442
443 class inv_adjacency_iterator : public boost::iterator_adaptor<
444 inv_adjacency_iterator,
445 in_edge_iterator,
446 vertex_descriptor,
447 boost::bidirectional_traversal_tag,
448 vertex_descriptor> {
449 using super = typename inv_adjacency_iterator::iterator_adaptor_;
450 public:
451 inv_adjacency_iterator(in_edge_iterator a) : super(std::move(a)) { }
452 inv_adjacency_iterator() { }
453
454 vertex_descriptor dereference() const {
455 return vertex_descriptor(super::base()->p->source);
456 }
457 };
458
459 class vertex_iterator : public boost::iterator_adaptor<
460 vertex_iterator,
461 typename vertices_list_type::const_iterator,
462 vertex_descriptor,
463 boost::bidirectional_traversal_tag,
464 vertex_descriptor> {
465 using super = typename vertex_iterator::iterator_adaptor_;
466 public:
467 vertex_iterator() : super() { }
468 explicit vertex_iterator(typename vertices_list_type::const_iterator it)
469 : super(it) { }
470 vertex_descriptor dereference() const {
471 /* :( const_cast makes me sad but constness is defined by the graph
472 * parameter of bgl api calls */
473 return vertex_descriptor(
474 const_cast<vertex_node *>(&*super::base()));
475 }
476 };
477
478 class edge_iterator : public boost::iterator_facade<
479 edge_iterator,
480 edge_descriptor,
481 boost::forward_traversal_tag, /* TODO: make bidi */
482 edge_descriptor> {
483 public:
484 using main_base_iter_type = vertex_iterator;
485 using aux_base_iter_type = out_edge_iterator;
486
487 edge_iterator(main_base_iter_type b, main_base_iter_type e)
488 : main(std::move(b)), main_end(std::move(e)) {
489 if (main == main_end) {
490 return;
491 }
492 std::tie(aux, aux_end) = out_edges_impl(*main);
493 while (aux == aux_end) {
494 ++main;
495 if (main == main_end) {
496 break;
497 }
498 std::tie(aux, aux_end) = out_edges_impl(*main);
499 }
500 }
501 edge_iterator() { }
502
503 friend class boost::iterator_core_access;
504 void increment() {
505 ++aux;
506 while (aux == aux_end) {
507 ++main;
508 if (main == main_end) {
509 break;
510 }
511 std::tie(aux, aux_end) = out_edges_impl(*main);
512 }
513 }
514 bool equal(const edge_iterator &other) const {
515 return main == other.main && (main == main_end || aux == other.aux);
516 }
517 edge_descriptor dereference() const {
518 return *aux;
519 }
520
521 main_base_iter_type main;
522 main_base_iter_type main_end;
523 aux_base_iter_type aux;
524 aux_base_iter_type aux_end;
525 };
526
527public:
528 static
529 vertex_descriptor null_vertex() { return vertex_descriptor(); }
530
531 vertex_descriptor add_vertex_impl() {
532 vertex_node *v = new vertex_node(new_serial());
533 v->props.index = next_vertex_index++;
534 vertices_list.push_back(*v);
535 return vertex_descriptor(v);
536 }
537
538 void remove_vertex_impl(vertex_descriptor v) {
539 vertex_node *vv = v.raw();
540 assert(vv->in_edge_list.empty());
541 assert(vv->out_edge_list.empty());
542 vertices_list.erase_and_dispose(vertices_list.iterator_to(*vv),
543 delete_disposer());
544 }
545
546 void clear_in_edges_impl(vertex_descriptor v) {
547 graph_edge_count -= v.raw()->in_edge_list.size();
548 v.raw()->in_edge_list.clear_and_dispose(in_edge_disposer());
549 }
550
551 void clear_out_edges_impl(vertex_descriptor v) {
552 graph_edge_count -= v.raw()->out_edge_list.size();
553 v.raw()->out_edge_list.clear_and_dispose(out_edge_disposer());
554 }
555
556 /* IncidenceGraph concept functions */
557
558 static
559 vertex_descriptor source_impl(edge_descriptor e) {
560 return vertex_descriptor(e.raw()->source);
561 }
562
563 static
564 vertex_descriptor target_impl(edge_descriptor e) {
565 return vertex_descriptor(e.raw()->target);
566 }
567
568 static
569 degree_size_type out_degree_impl(vertex_descriptor v) {
570 return v.raw()->out_edge_list.size();
571 }
572
573 static
574 std::pair<out_edge_iterator, out_edge_iterator>
575 out_edges_impl(vertex_descriptor v) {
576 return {out_edge_iterator(v.raw()->out_edge_list.begin()),
577 out_edge_iterator(v.raw()->out_edge_list.end())};
578 }
579
580 /* BidirectionalGraph concept functions */
581
582 static
583 degree_size_type in_degree_impl(vertex_descriptor v) {
584 return v.raw()->in_edge_list.size();
585 }
586
587 static
588 std::pair<in_edge_iterator, in_edge_iterator>
589 in_edges_impl(vertex_descriptor v) {
590 return {in_edge_iterator(v.raw()->in_edge_list.begin()),
591 in_edge_iterator(v.raw()->in_edge_list.end())};
592 }
593
594 /* Note: this is defined so that self loops are counted twice - which may or
595 * may not be what you want. Actually, you probably don't want this at
596 * all. */
597 static
598 degree_size_type degree_impl(vertex_descriptor v) {
599 return in_degree_impl(v) + out_degree_impl(v);
600 }
601
602 /* AdjacencyList concept functions */
603
604 static
605 std::pair<adjacency_iterator, adjacency_iterator>
606 adjacent_vertices_impl(vertex_descriptor v) {
607 auto out_edge_its = out_edges_impl(v);
608 return {adjacency_iterator(out_edge_its.first),
609 adjacency_iterator(out_edge_its.second)};
610 }
611
612 /* AdjacencyMatrix concept functions
613 * (Note: complexity guarantee is not met) */
614
615 std::pair<edge_descriptor, bool> edge_impl(vertex_descriptor u,
616 vertex_descriptor v) const {
617 if (in_degree_impl(v) < out_degree_impl(u)) {
618 for (const edge_descriptor &e : in_edges_range(v, *this)) {
619 if (source_impl(e) == u) {
620 return {e, true};
621 }
622 }
623 } else {
624 for (const edge_descriptor &e : out_edges_range(u, *this)) {
625 if (target_impl(e) == v) {
626 return {e, true};
627 }
628 }
629 }
630
631 return {edge_descriptor(), false};
632 }
633
634 /* Misc functions that don't actually seem to belong to a formal BGL
635 concept. */
636 static
637 edge_descriptor null_edge() { return edge_descriptor(); }
638
639 static
640 std::pair<inv_adjacency_iterator, inv_adjacency_iterator>
641 inv_adjacent_vertices_impl(vertex_descriptor v) {
642 auto in_edge_its = in_edges_impl(v);
643 return {inv_adjacency_iterator(in_edge_its.first),
644 inv_adjacency_iterator(in_edge_its.second)};
645 }
646
647 /* MutableGraph concept functions */
648
649 std::pair<edge_descriptor, bool>
650 add_edge_impl(vertex_descriptor u, vertex_descriptor v) {
651 bool added = true; /* we always allow parallel edges */
652 edge_node *e = new edge_node(new_serial());
653 e->source = u.raw();
654 e->target = v.raw();
655 e->props.index = next_edge_index++;
656
657 u.raw()->out_edge_list.push_back(*e);
658 v.raw()->in_edge_list.push_back(*e);
659
660 graph_edge_count++;
661 return {edge_descriptor(e), added};
662 }
663
664 void remove_edge_impl(edge_descriptor e) {
665 graph_edge_count--;
666
667 vertex_node *u = e.raw()->source;
668 vertex_node *v = e.raw()->target;
669
670 v->in_edge_list.erase(v->in_edge_list.iterator_to(*e.raw()));
671 u->out_edge_list.erase(u->out_edge_list.iterator_to(*e.raw()));
672
673 delete e.raw();
674 }
675
676 template<class Predicate>
677 void remove_out_edge_if_impl(vertex_descriptor v, Predicate pred) {
678 out_edge_iterator it, ite;
679 std::tie(it, ite) = out_edges_impl(v);
680 while (it != ite) {
681 auto jt = it;
682 ++it;
683 if (pred(*jt)) {
684 this->remove_edge_impl(*jt);
685 }
686 }
687 }
688
689 template<class Predicate>
690 void remove_in_edge_if_impl(vertex_descriptor v, Predicate pred) {
691 in_edge_iterator it, ite;
692 std::tie(it, ite) = in_edges_impl(v);
693 while (it != ite) {
694 auto jt = it;
695 ++it;
696 if (pred(*jt)) {
697 remove_edge_impl(*jt);
698 }
699 }
700 }
701
702 template<class Predicate>
703 void remove_edge_if_impl(Predicate pred) {
704 edge_iterator it, ite;
705 std::tie(it, ite) = edges_impl();
706 while (it != ite) {
707 auto jt = it;
708 ++it;
709 if (pred(*jt)) {
710 remove_edge_impl(*jt);
711 }
712 }
713 }
714
715private:
716 /* GCC 4.8 has bugs with lambdas in templated friend functions, so: */
717 struct source_match {
718 explicit source_match(const vertex_descriptor &uu) : u(uu) { }
719 bool operator()(edge_descriptor e) const { return source_impl(e) == u; }
720 const vertex_descriptor &u;
721 };
722
723 struct target_match {
724 explicit target_match(const vertex_descriptor &vv) : v(vv) { }
725 bool operator()(edge_descriptor e) const { return target_impl(e) == v; }
726 const vertex_descriptor &v;
727 };
728public:
729 /* Note: (u,v) variant needs to remove all (parallel) edges between (u,v).
730 *
731 * The edge_descriptor version should be strongly preferred if the
732 * edge_descriptor is available.
733 */
734 void remove_edge_impl(const vertex_descriptor &u,
735 const vertex_descriptor &v) {
736 if (in_degree_impl(v) < out_degree_impl(u)) {
737 remove_in_edge_if_impl(v, source_match(u));
738 } else {
739 remove_out_edge_if_impl(u, target_match(v));
740 }
741 }
742
743 /* VertexListGraph concept functions */
744 vertices_size_type num_vertices_impl() const {
745 return vertices_list.size();
746 }
747
748 std::pair<vertex_iterator, vertex_iterator> vertices_impl() const {
749 return {vertex_iterator(vertices_list.begin()),
750 vertex_iterator(vertices_list.end())};
751 }
752
753 /* EdgeListGraph concept functions (aside from those in IncidenceGraph) */
754
755 edges_size_type num_edges_impl() const {
756 return graph_edge_count;
757 }
758
759 std::pair<edge_iterator, edge_iterator> edges_impl() const {
760 vertex_iterator vi, ve;
761 std::tie(vi, ve) = vertices_impl();
762
763 return {edge_iterator(vi, ve), edge_iterator(ve, ve)};
764 }
765
766 /* bundled properties functions */
767
768 vertex_property_type &operator[](vertex_descriptor v) {
769 return v.raw()->props;
770 }
771
772 const vertex_property_type &operator[](vertex_descriptor v) const {
773 return v.raw()->props;
774 }
775
776 edge_property_type &operator[](edge_descriptor e) {
777 return e.raw()->props;
778 }
779
780 const edge_property_type &operator[](edge_descriptor e) const {
781 return e.raw()->props;
782 }
783
784 /* PropertyGraph concept functions & helpers */
785
786 template<typename R, typename P_of>
787 struct prop_map : public boost::put_get_helper<R, prop_map<R, P_of> > {
788 using value_type = typename std::decay<R>::type;
789 using reference = R;
790 using key_type = typename bundle_key_type<P_of>::type;
791
792 typedef typename boost::lvalue_property_map_tag category;
793
794 prop_map(value_type P_of::*m_in) : member(m_in) { }
795
796 reference operator[](key_type k) const {
797 return k.raw()->props.*member;
798 }
799 reference operator()(key_type k) const { return (*this)[k]; }
800
801 private:
802 value_type P_of::*member;
803 };
804
805 template<typename R>
806 struct prop_map_all : public boost::put_get_helper<R, prop_map_all<R> > {
807 using value_type = typename std::decay<R>::type;
808 using reference = R;
809 using key_type = typename bundle_key_type<value_type>::type;
810
811 typedef typename boost::lvalue_property_map_tag category;
812
813 reference operator[](key_type k) const {
814 return k.raw()->props;
815 }
816 reference operator()(key_type k) const { return (*this)[k]; }
817 };
818
819 template<typename P_type, typename P_of>
820 friend
821 prop_map<P_type &, P_of> get(P_type P_of::*t, Graph &) {
822 return prop_map<P_type &, P_of>(t);
823 }
824
825 template<typename P_type, typename P_of>
826 friend
827 prop_map<const P_type &, P_of> get(P_type P_of::*t, const Graph &) {
828 return prop_map<const P_type &, P_of>(t);
829 }
830
831 /* We can't seem to use auto/decltype returns here as it seems that the
832 * templated member functions are not yet visible when the compile is
833 * evaluating the decltype for the return value. We could probably work
834 * around it by making this a dummy templated function. */
835 friend
836 prop_map<size_t &, VertexPropertyType>
837 get(boost::vertex_index_t, Graph &g) {
838 return get(&VertexPropertyType::index, g);
839 }
840
841 friend
842 prop_map<const size_t &, VertexPropertyType>
843 get(boost::vertex_index_t, const Graph &g) {
844 return get(&VertexPropertyType::index, g);
845 }
846
847 friend
848 prop_map<size_t &, EdgePropertyType>
849 get(boost::edge_index_t, Graph &g) {
850 return get(&EdgePropertyType::index, g);
851 }
852
853 friend
854 prop_map<const size_t &, EdgePropertyType>
855 get(boost::edge_index_t, const Graph &g) {
856 return get(&EdgePropertyType::index, g);
857 }
858
859 friend
860 prop_map_all<VertexPropertyType &> get(boost::vertex_all_t, Graph &) {
861 return {};
862 }
863
864 friend
865 prop_map_all<const VertexPropertyType &> get(boost::vertex_all_t,
866 const Graph &) {
867 return {};
868 }
869
870 friend
871 prop_map_all<EdgePropertyType &> get(boost::edge_all_t, Graph &) {
872 return {};
873 }
874
875 friend
876 prop_map_all<const EdgePropertyType &> get(boost::edge_all_t,
877 const Graph &) {
878 return {};
879 }
880
881 friend
882 prop_map_all<VertexPropertyType &> get(boost::vertex_bundle_t, Graph &) {
883 return {};
884 }
885
886 friend
887 prop_map_all<const VertexPropertyType &> get(boost::vertex_bundle_t,
888 const Graph &) {
889 return {};
890 }
891
892 friend
893 prop_map_all<EdgePropertyType &> get(boost::edge_bundle_t, Graph &) {
894 return {};
895 }
896
897 friend
898 prop_map_all<const EdgePropertyType &> get(boost::edge_bundle_t,
899 const Graph &) {
900 return {};
901 }
902
903 template<typename Prop, typename K>
904 friend
905 auto get(Prop p, Graph &g, K key) -> decltype(get(p, g)[key]) {
906 return get(p, g)[key];
907 }
908
909 template<typename Prop, typename K>
910 friend
911 auto get(Prop p, const Graph &g, K key) -> decltype(get(p, g)[key]) {
912 return get(p, g)[key];
913 }
914
915 template<typename Prop, typename K, typename V>
916 friend
917 void put(Prop p, Graph &g, K key, const V &value) {
918 get(p, g)[key] = value;
919 }
920
921 /* MutablePropertyGraph concept functions */
922
923 /* Note: add_vertex(g, vp) allocates a next index value for the vertex
924 * rather than using the index in vp. i.e., except for in rare coincidences:
925 * g[add_vertex(g, vp)].index != vp.index
926 */
927 vertex_descriptor add_vertex_impl(const VertexPropertyType &vp) {
928 vertex_descriptor v = add_vertex_impl();
929 auto i = (*this)[v].index;
930 (*this)[v] = vp;
931 (*this)[v].index = i;
932
933 return v;
934 }
935
936 /* Note: add_edge(u, v, g, vp) allocates a next index value for the edge
937 * rather than using the index in ep. i.e., except for in rare coincidences:
938 * g[add_edge(u, v, g, ep)].index != ep.index
939 */
940 std::pair<edge_descriptor, bool>
941 add_edge_impl(vertex_descriptor u, vertex_descriptor v,
942 const EdgePropertyType &ep) {
943 auto e = add_edge_impl(u, v);
944 auto i = (*this)[e.first].index;
945 (*this)[e.first] = ep;
946 (*this)[e.first].index = i;
947
948 return e;
949 }
950
951 /* End MutablePropertyGraph */
952
953 /** Pack the edge index into a contiguous range [ 0, num_edges(g) ). */
954 void renumber_edges_impl() {
955 next_edge_index = 0;
956 edge_iterator it;
957 edge_iterator ite;
958 for (std::tie(it, ite) = edges_impl(); it != ite; ++it) {
959 (*this)[*it].index = next_edge_index++;
960 }
961 }
962
963 /** Pack the vertex index into a contiguous range [ 0, num_vertices(g) ).
964 * Vertices with indices less than N_SPECIAL_VERTICES are not renumbered.
965 */
966 void renumber_vertices_impl() {
967 DEBUG_PRINTF("renumbering above %zu\n", Graph::N_SPECIAL_VERTICES);
968 next_vertex_index = Graph::N_SPECIAL_VERTICES;
969 vertex_iterator it;
970 vertex_iterator ite;
971 for (std::tie(it, ite) = vertices_impl(); it != ite; ++it) {
972 if ((*this)[*it].index < Graph::N_SPECIAL_VERTICES) {
973 continue;
974 }
975
976 (*this)[*it].index = next_vertex_index++;
977 }
978 }
979
980 /** Returns what the next allocated vertex index will be. This is an upper
981 * on the values of index for vertices (vertex removal means that there may
982 * be gaps). */
983 vertices_size_type vertex_index_upper_bound_impl() const {
984 return next_vertex_index;
985 }
986
987 /** Returns what the next allocated edge index will be. This is an upper on
988 * the values of index for edges (edge removal means that there may be
989 * gaps). */
990 vertices_size_type edge_index_upper_bound_impl() const {
991 return next_edge_index;
992 }
993
994 using directed_category = boost::directed_tag;
995 using edge_parallel_category = boost::allow_parallel_edge_tag;
996 struct traversal_category :
997 public virtual boost::bidirectional_graph_tag,
998 public virtual boost::adjacency_graph_tag,
999 public virtual boost::vertex_list_graph_tag,
1000 public virtual boost::edge_list_graph_tag { };
1001
1002 ue2_graph() = default;
1003
1004 ue2_graph(ue2_graph &&old)
1005 : next_vertex_index(old.next_vertex_index),
1006 next_edge_index(old.next_edge_index),
1007 graph_edge_count(old.graph_edge_count),
1008 next_serial(old.next_serial) {
1009 using std::swap;
1010 swap(vertices_list, old.vertices_list);
1011 }
1012
1013 ue2_graph &operator=(ue2_graph &&old) {
1014 next_vertex_index = old.next_vertex_index;
1015 next_edge_index = old.next_edge_index;
1016 graph_edge_count = old.graph_edge_count;
1017 next_serial = old.next_serial;
1018 using std::swap;
1019 swap(vertices_list, old.vertices_list);
1020 return *this;
1021 }
1022
1023 ~ue2_graph() {
1024 vertices_list.clear_and_dispose(delete_disposer());
1025 }
1026};
1027
1028/** \brief Type trait to enable on whether the Graph is an ue2_graph. */
1029template<typename Graph>
1030struct is_ue2_graph
1031 : public ::std::integral_constant<
1032 bool, std::is_base_of<graph_detail::graph_base, Graph>::value> {};
1033
1034template<typename Graph>
1035typename std::enable_if<is_ue2_graph<Graph>::value,
1036 typename Graph::vertex_descriptor>::type
1037add_vertex(Graph &g) {
1038 return g.add_vertex_impl();
1039}
1040
1041template<typename Graph>
1042typename std::enable_if<is_ue2_graph<Graph>::value>::type
1043remove_vertex(typename Graph::vertex_descriptor v, Graph &g) {
1044 g.remove_vertex_impl(v);
1045}
1046
1047template<typename Graph>
1048typename std::enable_if<is_ue2_graph<Graph>::value>::type
1049clear_in_edges(typename Graph::vertex_descriptor v, Graph &g) {
1050 g.clear_in_edges_impl(v);
1051}
1052
1053template<typename Graph>
1054typename std::enable_if<is_ue2_graph<Graph>::value>::type
1055clear_out_edges(typename Graph::vertex_descriptor v, Graph &g) {
1056 g.clear_out_edges_impl(v);
1057}
1058
1059template<typename Graph>
1060typename std::enable_if<is_ue2_graph<Graph>::value>::type
1061clear_vertex(typename Graph::vertex_descriptor v, Graph &g) {
1062 g.clear_in_edges_impl(v);
1063 g.clear_out_edges_impl(v);
1064}
1065
1066template<typename Graph>
1067typename std::enable_if<is_ue2_graph<Graph>::value,
1068 typename Graph::vertex_descriptor>::type
1069source(typename Graph::edge_descriptor e, const Graph &) {
1070 return Graph::source_impl(e);
1071}
1072
1073template<typename Graph>
1074typename std::enable_if<is_ue2_graph<Graph>::value,
1075 typename Graph::vertex_descriptor>::type
1076target(typename Graph::edge_descriptor e, const Graph &) {
1077 return Graph::target_impl(e);
1078}
1079
1080template<typename Graph>
1081typename std::enable_if<is_ue2_graph<Graph>::value,
1082 typename Graph::degree_size_type>::type
1083out_degree(typename Graph::vertex_descriptor v, const Graph &) {
1084 return Graph::out_degree_impl(v);
1085}
1086
1087template<typename Graph>
1088typename std::enable_if<is_ue2_graph<Graph>::value,
1089 std::pair<typename Graph::out_edge_iterator,
1090 typename Graph::out_edge_iterator>>::type
1091out_edges(typename Graph::vertex_descriptor v, const Graph &) {
1092 return Graph::out_edges_impl(v);
1093}
1094
1095template<typename Graph>
1096typename std::enable_if<is_ue2_graph<Graph>::value,
1097 typename Graph::degree_size_type>::type
1098in_degree(typename Graph::vertex_descriptor v, const Graph &) {
1099 return Graph::in_degree_impl(v);
1100}
1101
1102template<typename Graph>
1103typename std::enable_if<is_ue2_graph<Graph>::value,
1104 std::pair<typename Graph::in_edge_iterator,
1105 typename Graph::in_edge_iterator>>::type
1106in_edges(typename Graph::vertex_descriptor v, const Graph &) {
1107 return Graph::in_edges_impl(v);
1108}
1109
1110template<typename Graph>
1111typename std::enable_if<is_ue2_graph<Graph>::value,
1112 typename Graph::degree_size_type>::type
1113degree(typename Graph::vertex_descriptor v, const Graph &) {
1114 return Graph::degree_impl(v);
1115}
1116
1117template<typename Graph>
1118typename std::enable_if<is_ue2_graph<Graph>::value,
1119 std::pair<typename Graph::adjacency_iterator,
1120 typename Graph::adjacency_iterator>>::type
1121adjacent_vertices(typename Graph::vertex_descriptor v, const Graph &) {
1122 return Graph::adjacent_vertices_impl(v);
1123}
1124
1125template<typename Graph>
1126typename std::enable_if<is_ue2_graph<Graph>::value,
1127 std::pair<typename Graph::edge_descriptor, bool>>::type
1128edge(typename Graph::vertex_descriptor u, typename Graph::vertex_descriptor v,
1129 const Graph &g) {
1130 return g.edge_impl(u, v);
1131}
1132
1133template<typename Graph>
1134typename std::enable_if<is_ue2_graph<Graph>::value,
1135 std::pair<typename Graph::inv_adjacency_iterator,
1136 typename Graph::inv_adjacency_iterator>>::type
1137inv_adjacent_vertices(typename Graph::vertex_descriptor v, const Graph &) {
1138 return Graph::inv_adjacent_vertices_impl(v);
1139}
1140
1141template<typename Graph>
1142typename std::enable_if<is_ue2_graph<Graph>::value,
1143 std::pair<typename Graph::edge_descriptor, bool>>::type
1144add_edge(typename Graph::vertex_descriptor u,
1145 typename Graph::vertex_descriptor v, Graph &g) {
1146 return g.add_edge_impl(u, v);
1147}
1148
1149template<typename Graph>
1150typename std::enable_if<is_ue2_graph<Graph>::value>::type
1151remove_edge(typename Graph::edge_descriptor e, Graph &g) {
1152 g.remove_edge_impl(e);
1153}
1154
1155template<typename Graph, typename Iter>
1156typename std::enable_if<
1157 !std::is_convertible<Iter, typename Graph::edge_descriptor>::value &&
1158 is_ue2_graph<Graph>::value>::type
1159remove_edge(Iter it, Graph &g) {
1160 g.remove_edge_impl(*it);
1161}
1162
1163template<typename Graph, typename Predicate>
1164typename std::enable_if<is_ue2_graph<Graph>::value>::type
1165remove_out_edge_if(typename Graph::vertex_descriptor v, Predicate pred,
1166 Graph &g) {
1167 g.remove_out_edge_if_impl(v, pred);
1168}
1169
1170template<typename Graph, typename Predicate>
1171typename std::enable_if<is_ue2_graph<Graph>::value>::type
1172remove_in_edge_if(typename Graph::vertex_descriptor v, Predicate pred,
1173 Graph &g) {
1174 g.remove_in_edge_if_impl(v, pred);
1175}
1176
1177template<typename Graph, typename Predicate>
1178typename std::enable_if<is_ue2_graph<Graph>::value>::type
1179remove_edge_if(Predicate pred, Graph &g) {
1180 g.remove_edge_if_impl(pred);
1181}
1182
1183template<typename Graph>
1184typename std::enable_if<is_ue2_graph<Graph>::value>::type
1185remove_edge(const typename Graph::vertex_descriptor &u,
1186 const typename Graph::vertex_descriptor &v, Graph &g) {
1187 g.remove_edge_impl(u, v);
1188}
1189
1190template<typename Graph>
1191typename std::enable_if<is_ue2_graph<Graph>::value,
1192 typename Graph::vertices_size_type>::type
1193num_vertices(const Graph &g) {
1194 return g.num_vertices_impl();
1195}
1196
1197template<typename Graph>
1198typename std::enable_if<is_ue2_graph<Graph>::value,
1199 std::pair<typename Graph::vertex_iterator,
1200 typename Graph::vertex_iterator>>::type
1201vertices(const Graph &g) {
1202 return g.vertices_impl();
1203}
1204
1205template<typename Graph>
1206typename std::enable_if<is_ue2_graph<Graph>::value,
1207 typename Graph::edges_size_type>::type
1208num_edges(const Graph &g) {
1209 return g.num_edges_impl();
1210}
1211
1212template<typename Graph>
1213typename std::enable_if<is_ue2_graph<Graph>::value,
1214 std::pair<typename Graph::edge_iterator,
1215 typename Graph::edge_iterator>>::type
1216edges(const Graph &g) {
1217 return g.edges_impl();
1218}
1219
1220template<typename Graph>
1221typename std::enable_if<is_ue2_graph<Graph>::value,
1222 typename Graph::vertex_descriptor>::type
1223add_vertex(const typename Graph::vertex_property_type &vp, Graph &g) {
1224 return g.add_vertex_impl(vp);
1225}
1226
1227template<typename Graph>
1228typename std::enable_if<is_ue2_graph<Graph>::value,
1229 std::pair<typename Graph::edge_descriptor, bool>>::type
1230add_edge(typename Graph::vertex_descriptor u,
1231 typename Graph::vertex_descriptor v,
1232 const typename Graph::edge_property_type &ep, Graph &g) {
1233 return g.add_edge_impl(u, v, ep);
1234}
1235
1236template<typename Graph>
1237typename std::enable_if<is_ue2_graph<Graph>::value>::type
1238renumber_edges(Graph &g) {
1239 g.renumber_edges_impl();
1240}
1241
1242template<typename Graph>
1243typename std::enable_if<is_ue2_graph<Graph>::value>::type
1244renumber_vertices(Graph &g) {
1245 g.renumber_vertices_impl();
1246}
1247
1248template<typename Graph>
1249typename std::enable_if<is_ue2_graph<Graph>::value,
1250 typename Graph::vertices_size_type>::type
1251vertex_index_upper_bound(const Graph &g) {
1252 return g.vertex_index_upper_bound_impl();
1253}
1254
1255template<typename Graph>
1256typename std::enable_if<is_ue2_graph<Graph>::value,
1257 typename Graph::edges_size_type>::type
1258edge_index_upper_bound(const Graph &g) {
1259 return g.edge_index_upper_bound_impl();
1260}
1261
1262template<typename T> struct pointer_to_member_traits {};
1263
1264template<typename Return, typename Class>
1265struct pointer_to_member_traits<Return(Class::*)> {
1266 using member_type = Return;
1267 using class_type = Class;
1268};
1269
1270template<typename Graph, typename Property, typename Enable = void>
1271struct is_ue2_vertex_or_edge_property {
1272 static constexpr bool value = false;
1273};
1274
1275template<typename Graph, typename Property>
1276struct is_ue2_vertex_or_edge_property<
1277 Graph, Property, typename std::enable_if<is_ue2_graph<Graph>::value &&
1278 std::is_member_object_pointer<
1279 Property>::value>::type> {
1280private:
1281 using class_type = typename pointer_to_member_traits<Property>::class_type;
1282 using vertex_type = typename Graph::vertex_property_type;
1283 using edge_type = typename Graph::edge_property_type;
1284public:
1285 static constexpr bool value =
1286 std::is_same<class_type, vertex_type>::value ||
1287 std::is_same<class_type, edge_type>::value;
1288};
1289
1290using boost::vertex_index;
1291using boost::edge_index;
1292
1293} // namespace ue2
1294
1295namespace boost {
1296
1297/* Install partial specialisation of property_map - this is required for
1298 * adaptors (like filtered_graph) to know the type of the property maps */
1299template<typename Graph, typename Prop>
1300struct property_map<Graph, Prop,
1301 typename std::enable_if<ue2::is_ue2_graph<Graph>::value &&
1302 ue2::is_ue2_vertex_or_edge_property<
1303 Graph, Prop>::value>::type> {
1304private:
1305 using prop_traits = ue2::pointer_to_member_traits<Prop>;
1306 using member_type = typename prop_traits::member_type;
1307 using class_type = typename prop_traits::class_type;
1308public:
1309 using type = typename Graph::template prop_map<member_type &, class_type>;
1310 using const_type = typename Graph::template prop_map<const member_type &,
1311 class_type>;
1312};
1313
1314template<typename Graph>
1315struct property_map<Graph, vertex_index_t,
1316 typename std::enable_if<ue2::is_ue2_graph<Graph>::value>::type> {
1317 using v_prop_type = typename Graph::vertex_property_type;
1318 using type = typename Graph::template prop_map<size_t &, v_prop_type>;
1319 using const_type =
1320 typename Graph::template prop_map<const size_t &, v_prop_type>;
1321};
1322
1323template<typename Graph>
1324struct property_map<Graph, edge_index_t,
1325 typename std::enable_if<ue2::is_ue2_graph<Graph>::value>::type> {
1326 using e_prop_type = typename Graph::edge_property_type;
1327 using type = typename Graph::template prop_map<size_t &, e_prop_type>;
1328 using const_type =
1329 typename Graph::template prop_map<const size_t &, e_prop_type>;
1330};
1331
1332template<typename Graph>
1333struct property_map<Graph, vertex_all_t,
1334 typename std::enable_if<ue2::is_ue2_graph<Graph>::value>::type> {
1335 using v_prop_type = typename Graph::vertex_property_type;
1336 using type = typename Graph::template prop_map_all<v_prop_type &>;
1337 using const_type =
1338 typename Graph::template prop_map_all<const v_prop_type &>;
1339};
1340
1341template<typename Graph>
1342struct property_map<Graph, edge_all_t,
1343 typename std::enable_if<ue2::is_ue2_graph<Graph>::value>::type> {
1344 using e_prop_type = typename Graph::edge_property_type;
1345 using type = typename Graph::template prop_map_all<e_prop_type &>;
1346 using const_type =
1347 typename Graph::template prop_map_all<const e_prop_type &>;
1348};
1349
1350} // namespace boost
1351
1352namespace std {
1353
1354/* Specialization of std::hash so that vertex_descriptor can be used in
1355 * unordered containers. */
1356template<typename Graph>
1357struct hash<ue2::graph_detail::vertex_descriptor<Graph>> {
1358 using vertex_descriptor = ue2::graph_detail::vertex_descriptor<Graph>;
1359 std::size_t operator()(const vertex_descriptor &v) const {
1360 return v.hash();
1361 }
1362};
1363
1364/* Specialization of std::hash so that edge_descriptor can be used in
1365 * unordered containers. */
1366template<typename Graph>
1367struct hash<ue2::graph_detail::edge_descriptor<Graph>> {
1368 using edge_descriptor = ue2::graph_detail::edge_descriptor<Graph>;
1369 std::size_t operator()(const edge_descriptor &e) const {
1370 return e.hash();
1371 }
1372};
1373
1374} // namespace std
1375#endif
1376