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 | |
157 | namespace ue2 { |
158 | |
159 | namespace graph_detail { |
160 | |
161 | class graph_base : noncopyable { |
162 | }; |
163 | |
164 | struct default_edge_property { |
165 | size_t index; |
166 | }; |
167 | |
168 | struct default_vertex_property { |
169 | size_t index; |
170 | }; |
171 | |
172 | template<typename Graph> |
173 | class vertex_descriptor : totally_ordered<vertex_descriptor<Graph>> { |
174 | using vertex_node = typename Graph::vertex_node; |
175 | public: |
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 | |
195 | private: |
196 | vertex_node *raw(void) { return p; } |
197 | vertex_node *p; |
198 | u64a serial; |
199 | friend Graph; |
200 | }; |
201 | |
202 | template<typename Graph> |
203 | class edge_descriptor : totally_ordered<edge_descriptor<Graph>> { |
204 | using edge_node = typename Graph::edge_node; |
205 | public: |
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 | |
234 | private: |
235 | edge_node *raw(void) { return p; } |
236 | edge_node *p; |
237 | u64a serial; |
238 | friend Graph; |
239 | }; |
240 | |
241 | } // namespace graph_detail |
242 | |
243 | template<typename Graph, |
244 | typename VertexPropertyType = graph_detail::default_vertex_property, |
245 | typename EdgePropertyType = graph_detail::default_edge_property> |
246 | class ue2_graph : graph_detail::graph_base { |
247 | private: |
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 | |
331 | protected: /* 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 | |
336 | private: |
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 | } |
353 | public: |
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 | |
371 | private: |
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 | |
388 | public: |
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 | |
527 | public: |
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 | |
715 | private: |
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 | }; |
728 | public: |
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. */ |
1029 | template<typename Graph> |
1030 | struct is_ue2_graph |
1031 | : public ::std::integral_constant< |
1032 | bool, std::is_base_of<graph_detail::graph_base, Graph>::value> {}; |
1033 | |
1034 | template<typename Graph> |
1035 | typename std::enable_if<is_ue2_graph<Graph>::value, |
1036 | typename Graph::vertex_descriptor>::type |
1037 | add_vertex(Graph &g) { |
1038 | return g.add_vertex_impl(); |
1039 | } |
1040 | |
1041 | template<typename Graph> |
1042 | typename std::enable_if<is_ue2_graph<Graph>::value>::type |
1043 | remove_vertex(typename Graph::vertex_descriptor v, Graph &g) { |
1044 | g.remove_vertex_impl(v); |
1045 | } |
1046 | |
1047 | template<typename Graph> |
1048 | typename std::enable_if<is_ue2_graph<Graph>::value>::type |
1049 | clear_in_edges(typename Graph::vertex_descriptor v, Graph &g) { |
1050 | g.clear_in_edges_impl(v); |
1051 | } |
1052 | |
1053 | template<typename Graph> |
1054 | typename std::enable_if<is_ue2_graph<Graph>::value>::type |
1055 | clear_out_edges(typename Graph::vertex_descriptor v, Graph &g) { |
1056 | g.clear_out_edges_impl(v); |
1057 | } |
1058 | |
1059 | template<typename Graph> |
1060 | typename std::enable_if<is_ue2_graph<Graph>::value>::type |
1061 | clear_vertex(typename Graph::vertex_descriptor v, Graph &g) { |
1062 | g.clear_in_edges_impl(v); |
1063 | g.clear_out_edges_impl(v); |
1064 | } |
1065 | |
1066 | template<typename Graph> |
1067 | typename std::enable_if<is_ue2_graph<Graph>::value, |
1068 | typename Graph::vertex_descriptor>::type |
1069 | source(typename Graph::edge_descriptor e, const Graph &) { |
1070 | return Graph::source_impl(e); |
1071 | } |
1072 | |
1073 | template<typename Graph> |
1074 | typename std::enable_if<is_ue2_graph<Graph>::value, |
1075 | typename Graph::vertex_descriptor>::type |
1076 | target(typename Graph::edge_descriptor e, const Graph &) { |
1077 | return Graph::target_impl(e); |
1078 | } |
1079 | |
1080 | template<typename Graph> |
1081 | typename std::enable_if<is_ue2_graph<Graph>::value, |
1082 | typename Graph::degree_size_type>::type |
1083 | out_degree(typename Graph::vertex_descriptor v, const Graph &) { |
1084 | return Graph::out_degree_impl(v); |
1085 | } |
1086 | |
1087 | template<typename Graph> |
1088 | typename std::enable_if<is_ue2_graph<Graph>::value, |
1089 | std::pair<typename Graph::out_edge_iterator, |
1090 | typename Graph::out_edge_iterator>>::type |
1091 | out_edges(typename Graph::vertex_descriptor v, const Graph &) { |
1092 | return Graph::out_edges_impl(v); |
1093 | } |
1094 | |
1095 | template<typename Graph> |
1096 | typename std::enable_if<is_ue2_graph<Graph>::value, |
1097 | typename Graph::degree_size_type>::type |
1098 | in_degree(typename Graph::vertex_descriptor v, const Graph &) { |
1099 | return Graph::in_degree_impl(v); |
1100 | } |
1101 | |
1102 | template<typename Graph> |
1103 | typename std::enable_if<is_ue2_graph<Graph>::value, |
1104 | std::pair<typename Graph::in_edge_iterator, |
1105 | typename Graph::in_edge_iterator>>::type |
1106 | in_edges(typename Graph::vertex_descriptor v, const Graph &) { |
1107 | return Graph::in_edges_impl(v); |
1108 | } |
1109 | |
1110 | template<typename Graph> |
1111 | typename std::enable_if<is_ue2_graph<Graph>::value, |
1112 | typename Graph::degree_size_type>::type |
1113 | degree(typename Graph::vertex_descriptor v, const Graph &) { |
1114 | return Graph::degree_impl(v); |
1115 | } |
1116 | |
1117 | template<typename Graph> |
1118 | typename std::enable_if<is_ue2_graph<Graph>::value, |
1119 | std::pair<typename Graph::adjacency_iterator, |
1120 | typename Graph::adjacency_iterator>>::type |
1121 | adjacent_vertices(typename Graph::vertex_descriptor v, const Graph &) { |
1122 | return Graph::adjacent_vertices_impl(v); |
1123 | } |
1124 | |
1125 | template<typename Graph> |
1126 | typename std::enable_if<is_ue2_graph<Graph>::value, |
1127 | std::pair<typename Graph::edge_descriptor, bool>>::type |
1128 | edge(typename Graph::vertex_descriptor u, typename Graph::vertex_descriptor v, |
1129 | const Graph &g) { |
1130 | return g.edge_impl(u, v); |
1131 | } |
1132 | |
1133 | template<typename Graph> |
1134 | typename std::enable_if<is_ue2_graph<Graph>::value, |
1135 | std::pair<typename Graph::inv_adjacency_iterator, |
1136 | typename Graph::inv_adjacency_iterator>>::type |
1137 | inv_adjacent_vertices(typename Graph::vertex_descriptor v, const Graph &) { |
1138 | return Graph::inv_adjacent_vertices_impl(v); |
1139 | } |
1140 | |
1141 | template<typename Graph> |
1142 | typename std::enable_if<is_ue2_graph<Graph>::value, |
1143 | std::pair<typename Graph::edge_descriptor, bool>>::type |
1144 | add_edge(typename Graph::vertex_descriptor u, |
1145 | typename Graph::vertex_descriptor v, Graph &g) { |
1146 | return g.add_edge_impl(u, v); |
1147 | } |
1148 | |
1149 | template<typename Graph> |
1150 | typename std::enable_if<is_ue2_graph<Graph>::value>::type |
1151 | remove_edge(typename Graph::edge_descriptor e, Graph &g) { |
1152 | g.remove_edge_impl(e); |
1153 | } |
1154 | |
1155 | template<typename Graph, typename Iter> |
1156 | typename std::enable_if< |
1157 | !std::is_convertible<Iter, typename Graph::edge_descriptor>::value && |
1158 | is_ue2_graph<Graph>::value>::type |
1159 | remove_edge(Iter it, Graph &g) { |
1160 | g.remove_edge_impl(*it); |
1161 | } |
1162 | |
1163 | template<typename Graph, typename Predicate> |
1164 | typename std::enable_if<is_ue2_graph<Graph>::value>::type |
1165 | remove_out_edge_if(typename Graph::vertex_descriptor v, Predicate pred, |
1166 | Graph &g) { |
1167 | g.remove_out_edge_if_impl(v, pred); |
1168 | } |
1169 | |
1170 | template<typename Graph, typename Predicate> |
1171 | typename std::enable_if<is_ue2_graph<Graph>::value>::type |
1172 | remove_in_edge_if(typename Graph::vertex_descriptor v, Predicate pred, |
1173 | Graph &g) { |
1174 | g.remove_in_edge_if_impl(v, pred); |
1175 | } |
1176 | |
1177 | template<typename Graph, typename Predicate> |
1178 | typename std::enable_if<is_ue2_graph<Graph>::value>::type |
1179 | remove_edge_if(Predicate pred, Graph &g) { |
1180 | g.remove_edge_if_impl(pred); |
1181 | } |
1182 | |
1183 | template<typename Graph> |
1184 | typename std::enable_if<is_ue2_graph<Graph>::value>::type |
1185 | remove_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 | |
1190 | template<typename Graph> |
1191 | typename std::enable_if<is_ue2_graph<Graph>::value, |
1192 | typename Graph::vertices_size_type>::type |
1193 | num_vertices(const Graph &g) { |
1194 | return g.num_vertices_impl(); |
1195 | } |
1196 | |
1197 | template<typename Graph> |
1198 | typename std::enable_if<is_ue2_graph<Graph>::value, |
1199 | std::pair<typename Graph::vertex_iterator, |
1200 | typename Graph::vertex_iterator>>::type |
1201 | vertices(const Graph &g) { |
1202 | return g.vertices_impl(); |
1203 | } |
1204 | |
1205 | template<typename Graph> |
1206 | typename std::enable_if<is_ue2_graph<Graph>::value, |
1207 | typename Graph::edges_size_type>::type |
1208 | num_edges(const Graph &g) { |
1209 | return g.num_edges_impl(); |
1210 | } |
1211 | |
1212 | template<typename Graph> |
1213 | typename std::enable_if<is_ue2_graph<Graph>::value, |
1214 | std::pair<typename Graph::edge_iterator, |
1215 | typename Graph::edge_iterator>>::type |
1216 | edges(const Graph &g) { |
1217 | return g.edges_impl(); |
1218 | } |
1219 | |
1220 | template<typename Graph> |
1221 | typename std::enable_if<is_ue2_graph<Graph>::value, |
1222 | typename Graph::vertex_descriptor>::type |
1223 | add_vertex(const typename Graph::vertex_property_type &vp, Graph &g) { |
1224 | return g.add_vertex_impl(vp); |
1225 | } |
1226 | |
1227 | template<typename Graph> |
1228 | typename std::enable_if<is_ue2_graph<Graph>::value, |
1229 | std::pair<typename Graph::edge_descriptor, bool>>::type |
1230 | add_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 | |
1236 | template<typename Graph> |
1237 | typename std::enable_if<is_ue2_graph<Graph>::value>::type |
1238 | renumber_edges(Graph &g) { |
1239 | g.renumber_edges_impl(); |
1240 | } |
1241 | |
1242 | template<typename Graph> |
1243 | typename std::enable_if<is_ue2_graph<Graph>::value>::type |
1244 | renumber_vertices(Graph &g) { |
1245 | g.renumber_vertices_impl(); |
1246 | } |
1247 | |
1248 | template<typename Graph> |
1249 | typename std::enable_if<is_ue2_graph<Graph>::value, |
1250 | typename Graph::vertices_size_type>::type |
1251 | vertex_index_upper_bound(const Graph &g) { |
1252 | return g.vertex_index_upper_bound_impl(); |
1253 | } |
1254 | |
1255 | template<typename Graph> |
1256 | typename std::enable_if<is_ue2_graph<Graph>::value, |
1257 | typename Graph::edges_size_type>::type |
1258 | edge_index_upper_bound(const Graph &g) { |
1259 | return g.edge_index_upper_bound_impl(); |
1260 | } |
1261 | |
1262 | template<typename T> struct pointer_to_member_traits {}; |
1263 | |
1264 | template<typename Return, typename Class> |
1265 | struct pointer_to_member_traits<Return(Class::*)> { |
1266 | using member_type = Return; |
1267 | using class_type = Class; |
1268 | }; |
1269 | |
1270 | template<typename Graph, typename Property, typename Enable = void> |
1271 | struct is_ue2_vertex_or_edge_property { |
1272 | static constexpr bool value = false; |
1273 | }; |
1274 | |
1275 | template<typename Graph, typename Property> |
1276 | struct 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> { |
1280 | private: |
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; |
1284 | public: |
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 | |
1290 | using boost::vertex_index; |
1291 | using boost::edge_index; |
1292 | |
1293 | } // namespace ue2 |
1294 | |
1295 | namespace 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 */ |
1299 | template<typename Graph, typename Prop> |
1300 | struct 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> { |
1304 | private: |
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; |
1308 | public: |
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 | |
1314 | template<typename Graph> |
1315 | struct 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 | |
1323 | template<typename Graph> |
1324 | struct 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 | |
1332 | template<typename Graph> |
1333 | struct 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 | |
1341 | template<typename Graph> |
1342 | struct 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 | |
1352 | namespace std { |
1353 | |
1354 | /* Specialization of std::hash so that vertex_descriptor can be used in |
1355 | * unordered containers. */ |
1356 | template<typename Graph> |
1357 | struct 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. */ |
1366 | template<typename Graph> |
1367 | struct 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 | |