1 | // (C) Copyright 2007-2009 Andrew Sutton |
2 | // |
3 | // Use, modification and distribution are subject to the |
4 | // Boost Software License, Version 1.0 (See accompanying file |
5 | // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt) |
6 | |
7 | #ifndef BOOST_GRAPH_UNDIRECTED_GRAPH_HPP |
8 | #define BOOST_GRAPH_UNDIRECTED_GRAPH_HPP |
9 | |
10 | #include <boost/graph/adjacency_list.hpp> |
11 | #include <boost/graph/properties.hpp> |
12 | #include <boost/pending/property.hpp> |
13 | #include <boost/property_map/transform_value_property_map.hpp> |
14 | #include <boost/type_traits.hpp> |
15 | #include <boost/mpl/if.hpp> |
16 | |
17 | namespace boost |
18 | { |
19 | struct undirected_graph_tag |
20 | { |
21 | }; |
22 | |
23 | /** |
24 | * The undirected_graph class template is a simplified version of the BGL |
25 | * adjacency list. This class is provided for ease of use, but may not |
26 | * perform as well as custom-defined adjacency list classes. Instances of |
27 | * this template model the VertexIndexGraph, and EdgeIndexGraph concepts. The |
28 | * graph is also fully mutable, supporting both insertions and removals of |
29 | * vertices and edges. |
30 | * |
31 | * @note Special care must be taken when removing vertices or edges since |
32 | * those operations can invalidate the numbering of vertices. |
33 | */ |
34 | template < typename VertexProp = no_property, typename EdgeProp = no_property, |
35 | typename GraphProp = no_property > |
36 | class undirected_graph |
37 | { |
38 | public: |
39 | typedef GraphProp graph_property_type; |
40 | typedef VertexProp vertex_property_type; |
41 | typedef EdgeProp edge_property_type; |
42 | typedef typename lookup_one_property< GraphProp, graph_bundle_t >::type |
43 | graph_bundled; |
44 | typedef typename lookup_one_property< VertexProp, vertex_bundle_t >::type |
45 | vertex_bundled; |
46 | typedef typename lookup_one_property< EdgeProp, edge_bundle_t >::type |
47 | edge_bundled; |
48 | |
49 | public: |
50 | // Embed indices into the vertex type. |
51 | typedef property< vertex_index_t, unsigned, vertex_property_type > |
52 | internal_vertex_property; |
53 | typedef property< edge_index_t, unsigned, edge_property_type > |
54 | internal_edge_property; |
55 | |
56 | public: |
57 | typedef adjacency_list< listS, listS, undirectedS, internal_vertex_property, |
58 | internal_edge_property, GraphProp, listS > |
59 | graph_type; |
60 | |
61 | private: |
62 | // storage selectors |
63 | typedef typename graph_type::vertex_list_selector vertex_list_selector; |
64 | typedef typename graph_type::edge_list_selector edge_list_selector; |
65 | typedef typename graph_type::out_edge_list_selector out_edge_list_selector; |
66 | typedef typename graph_type::directed_selector directed_selector; |
67 | |
68 | public: |
69 | // more commonly used graph types |
70 | typedef typename graph_type::stored_vertex stored_vertex; |
71 | typedef typename graph_type::vertices_size_type vertices_size_type; |
72 | typedef typename graph_type::edges_size_type edges_size_type; |
73 | typedef typename graph_type::degree_size_type degree_size_type; |
74 | typedef typename graph_type::vertex_descriptor vertex_descriptor; |
75 | typedef typename graph_type::edge_descriptor edge_descriptor; |
76 | |
77 | // iterator types |
78 | typedef typename graph_type::vertex_iterator vertex_iterator; |
79 | typedef typename graph_type::edge_iterator edge_iterator; |
80 | typedef typename graph_type::out_edge_iterator out_edge_iterator; |
81 | typedef typename graph_type::in_edge_iterator in_edge_iterator; |
82 | typedef typename graph_type::adjacency_iterator adjacency_iterator; |
83 | |
84 | // miscellaneous types |
85 | typedef undirected_graph_tag graph_tag; |
86 | typedef typename graph_type::directed_category directed_category; |
87 | typedef typename graph_type::edge_parallel_category edge_parallel_category; |
88 | typedef typename graph_type::traversal_category traversal_category; |
89 | |
90 | typedef std::size_t vertex_index_type; |
91 | typedef std::size_t edge_index_type; |
92 | |
93 | inline undirected_graph(GraphProp const& p = GraphProp()) |
94 | : m_graph(p) |
95 | , m_num_vertices(0) |
96 | , m_num_edges(0) |
97 | , m_max_vertex_index(0) |
98 | , m_max_edge_index(0) |
99 | { |
100 | } |
101 | |
102 | inline undirected_graph(undirected_graph const& x) |
103 | : m_graph(x.m_graph) |
104 | , m_num_vertices(x.m_num_vertices) |
105 | , m_num_edges(x.m_num_edges) |
106 | , m_max_vertex_index(x.m_max_vertex_index) |
107 | , m_max_edge_index(x.m_max_edge_index) |
108 | { |
109 | } |
110 | |
111 | inline undirected_graph( |
112 | vertices_size_type n, GraphProp const& p = GraphProp()) |
113 | : m_graph(n, p) |
114 | , m_num_vertices(n) |
115 | , m_num_edges(0) |
116 | , m_max_vertex_index(n) |
117 | , m_max_edge_index(0) |
118 | { |
119 | renumber_vertex_indices(); |
120 | } |
121 | |
122 | template < typename EdgeIterator > |
123 | inline undirected_graph(EdgeIterator f, EdgeIterator l, |
124 | vertices_size_type n, edges_size_type m = 0, |
125 | GraphProp const& p = GraphProp()) |
126 | : m_graph(f, l, n, m, p) |
127 | , m_num_vertices(n) |
128 | , m_num_edges(0) |
129 | , m_max_vertex_index(n) |
130 | , m_max_edge_index(0) |
131 | { |
132 | // Unfortunately, we have to renumber to ensure correct indexing. |
133 | renumber_indices(); |
134 | |
135 | // Can't always guarantee that the number of edges is actually |
136 | // m if distance(f, l) != m (or is undefined). |
137 | m_num_edges = m_max_edge_index = boost::num_edges(m_graph); |
138 | } |
139 | |
140 | undirected_graph& operator=(undirected_graph const& g) |
141 | { |
142 | if (&g != this) |
143 | { |
144 | m_graph = g.m_graph; |
145 | m_num_vertices = g.m_num_vertices; |
146 | m_num_edges = g.m_num_edges; |
147 | m_max_vertex_index = g.m_max_vertex_index; |
148 | } |
149 | return *this; |
150 | } |
151 | |
152 | // The impl_() methods are not part of the public interface. |
153 | graph_type& impl() { return m_graph; } |
154 | |
155 | graph_type const& impl() const { return m_graph; } |
156 | |
157 | // The following methods are not part of the public interface |
158 | vertices_size_type num_vertices() const { return m_num_vertices; } |
159 | |
160 | private: |
161 | // This helper function manages the attribution of vertex indices. |
162 | vertex_descriptor make_index(vertex_descriptor v) |
163 | { |
164 | boost::put(vertex_index, m_graph, v, m_max_vertex_index); |
165 | m_num_vertices++; |
166 | m_max_vertex_index++; |
167 | return v; |
168 | } |
169 | |
170 | public: |
171 | vertex_descriptor add_vertex() |
172 | { |
173 | return make_index(boost::add_vertex(m_graph)); |
174 | } |
175 | |
176 | vertex_descriptor add_vertex(vertex_property_type const& p) |
177 | { |
178 | return make_index( |
179 | boost::add_vertex(internal_vertex_property(0u, p), m_graph)); |
180 | } |
181 | |
182 | void clear_vertex(vertex_descriptor v) |
183 | { |
184 | std::pair< out_edge_iterator, out_edge_iterator > p |
185 | = boost::out_edges(v, m_graph); |
186 | m_num_edges -= std::distance(p.first, p.second); |
187 | boost::clear_vertex(v, m_graph); |
188 | } |
189 | |
190 | void remove_vertex(vertex_descriptor v) |
191 | { |
192 | boost::remove_vertex(v, m_graph); |
193 | --m_num_vertices; |
194 | } |
195 | |
196 | edges_size_type num_edges() const { return m_num_edges; } |
197 | |
198 | private: |
199 | // A helper fucntion for managing edge index attributes. |
200 | std::pair< edge_descriptor, bool > const& make_index( |
201 | std::pair< edge_descriptor, bool > const& x) |
202 | { |
203 | if (x.second) |
204 | { |
205 | boost::put(edge_index, m_graph, x.first, m_max_edge_index); |
206 | ++m_num_edges; |
207 | ++m_max_edge_index; |
208 | } |
209 | return x; |
210 | } |
211 | |
212 | public: |
213 | std::pair< edge_descriptor, bool > add_edge( |
214 | vertex_descriptor u, vertex_descriptor v) |
215 | { |
216 | return make_index(boost::add_edge(u, v, m_graph)); |
217 | } |
218 | |
219 | std::pair< edge_descriptor, bool > add_edge( |
220 | vertex_descriptor u, vertex_descriptor v, edge_property_type const& p) |
221 | { |
222 | return make_index( |
223 | boost::add_edge(u, v, internal_edge_property(0u, p), m_graph)); |
224 | } |
225 | |
226 | void remove_edge(vertex_descriptor u, vertex_descriptor v) |
227 | { |
228 | // find all edges, (u, v) |
229 | std::vector< edge_descriptor > edges; |
230 | out_edge_iterator i, i_end; |
231 | for (boost::tie(i, i_end) = boost::out_edges(u, m_graph); i != i_end; |
232 | ++i) |
233 | { |
234 | if (boost::target(*i, m_graph) == v) |
235 | { |
236 | edges.push_back(*i); |
237 | } |
238 | } |
239 | // remove all edges, (u, v) |
240 | typename std::vector< edge_descriptor >::iterator j = edges.begin(), |
241 | j_end = edges.end(); |
242 | for (; j != j_end; ++j) |
243 | { |
244 | remove_edge(*j); |
245 | } |
246 | } |
247 | |
248 | void remove_edge(edge_iterator i) { remove_edge(*i); } |
249 | |
250 | void remove_edge(edge_descriptor e) |
251 | { |
252 | boost::remove_edge(e, m_graph); |
253 | --m_num_edges; |
254 | } |
255 | |
256 | vertex_index_type max_vertex_index() const { return m_max_vertex_index; } |
257 | |
258 | void renumber_vertex_indices() |
259 | { |
260 | vertex_iterator i, i_end; |
261 | boost::tie(i, i_end) = vertices(m_graph); |
262 | m_max_vertex_index = renumber_vertex_indices(i, i_end, 0); |
263 | } |
264 | |
265 | void remove_vertex_and_renumber_indices(vertex_iterator i) |
266 | { |
267 | vertex_iterator j = next(i), end = vertices(m_graph).second; |
268 | vertex_index_type n = get(vertex_index, m_graph, *i); |
269 | |
270 | // remove the offending vertex and renumber everything after |
271 | remove_vertex(v: *i); |
272 | m_max_vertex_index = renumber_vertex_indices(j, end, n); |
273 | } |
274 | |
275 | edge_index_type max_edge_index() const { return m_max_edge_index; } |
276 | |
277 | void renumber_edge_indices() |
278 | { |
279 | edge_iterator i, end; |
280 | boost::tie(i, end) = edges(m_graph); |
281 | m_max_edge_index = renumber_edge_indices(i, end, 0); |
282 | } |
283 | |
284 | void remove_edge_and_renumber_indices(edge_iterator i) |
285 | { |
286 | edge_iterator j = next(i), end = edges(m_graph.second); |
287 | edge_index_type n = get(edge_index, m_graph, *i); |
288 | |
289 | // remove the edge and renumber everything after it |
290 | remove_edge(*i); |
291 | m_max_edge_index = renumber_edge_indices(j, end, n); |
292 | } |
293 | |
294 | void renumber_indices() |
295 | { |
296 | renumber_vertex_indices(); |
297 | renumber_edge_indices(); |
298 | } |
299 | |
300 | // bundled property support |
301 | #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES |
302 | vertex_bundled& operator[](vertex_descriptor v) { return m_graph[v]; } |
303 | |
304 | vertex_bundled const& operator[](vertex_descriptor v) const |
305 | { |
306 | return m_graph[v]; |
307 | } |
308 | |
309 | edge_bundled& operator[](edge_descriptor e) { return m_graph[e]; } |
310 | |
311 | edge_bundled const& operator[](edge_descriptor e) const |
312 | { |
313 | return m_graph[e]; |
314 | } |
315 | |
316 | graph_bundled& operator[](graph_bundle_t) { return get_property(*this); } |
317 | |
318 | graph_bundled const& operator[](graph_bundle_t) const |
319 | { |
320 | return get_property(*this); |
321 | } |
322 | #endif |
323 | |
324 | // Graph concepts |
325 | static vertex_descriptor null_vertex() { return graph_type::null_vertex(); } |
326 | |
327 | void clear() |
328 | { |
329 | m_graph.clear(); |
330 | m_num_vertices = m_max_vertex_index = 0; |
331 | m_num_edges = m_max_edge_index = 0; |
332 | } |
333 | |
334 | void swap(undirected_graph& g) |
335 | { |
336 | m_graph.swap(g.m_graph); |
337 | std::swap(m_num_vertices, g.m_num_vertices); |
338 | std::swap(m_max_vertex_index, g.m_max_vertex_index); |
339 | std::swap(m_num_edges, g.m_num_edges); |
340 | std::swap(m_max_edge_index, g.m_max_edge_index); |
341 | } |
342 | |
343 | private: |
344 | vertices_size_type renumber_vertex_indices( |
345 | vertex_iterator i, vertex_iterator end, vertices_size_type n) |
346 | { |
347 | typedef |
348 | typename property_map< graph_type, vertex_index_t >::type IndexMap; |
349 | IndexMap indices = get(vertex_index, m_graph); |
350 | for (; i != end; ++i) |
351 | { |
352 | indices[*i] = n++; |
353 | } |
354 | return n; |
355 | } |
356 | |
357 | edges_size_type renumber_edge_indices( |
358 | edge_iterator i, edge_iterator end, edges_size_type n) |
359 | { |
360 | typedef |
361 | typename property_map< graph_type, edge_index_t >::type IndexMap; |
362 | IndexMap indices = get(edge_index, m_graph); |
363 | for (; i != end; ++i) |
364 | { |
365 | indices[*i] = n++; |
366 | } |
367 | return n; |
368 | } |
369 | |
370 | graph_type m_graph; |
371 | vertices_size_type m_num_vertices; |
372 | edges_size_type m_num_edges; |
373 | vertex_index_type m_max_vertex_index; |
374 | edge_index_type m_max_edge_index; |
375 | }; |
376 | |
377 | #define UNDIRECTED_GRAPH_PARAMS typename VP, typename EP, typename GP |
378 | #define UNDIRECTED_GRAPH undirected_graph< VP, EP, GP > |
379 | |
380 | // IncidenceGraph concepts |
381 | template < UNDIRECTED_GRAPH_PARAMS > |
382 | inline typename UNDIRECTED_GRAPH::vertex_descriptor source( |
383 | typename UNDIRECTED_GRAPH::edge_descriptor e, UNDIRECTED_GRAPH const& g) |
384 | { |
385 | return source(e, g.impl()); |
386 | } |
387 | |
388 | template < UNDIRECTED_GRAPH_PARAMS > |
389 | inline typename UNDIRECTED_GRAPH::vertex_descriptor target( |
390 | typename UNDIRECTED_GRAPH::edge_descriptor e, UNDIRECTED_GRAPH const& g) |
391 | { |
392 | return target(e, g.impl()); |
393 | } |
394 | |
395 | template < UNDIRECTED_GRAPH_PARAMS > |
396 | inline typename UNDIRECTED_GRAPH::degree_size_type out_degree( |
397 | typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g) |
398 | { |
399 | return out_degree(v, g.impl()); |
400 | } |
401 | |
402 | template < UNDIRECTED_GRAPH_PARAMS > |
403 | inline std::pair< typename UNDIRECTED_GRAPH::out_edge_iterator, |
404 | typename UNDIRECTED_GRAPH::out_edge_iterator > |
405 | out_edges( |
406 | typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g) |
407 | { |
408 | return out_edges(v, g.impl()); |
409 | } |
410 | |
411 | // BidirectionalGraph concepts |
412 | template < UNDIRECTED_GRAPH_PARAMS > |
413 | inline typename UNDIRECTED_GRAPH::degree_size_type in_degree( |
414 | typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g) |
415 | { |
416 | return in_degree(v, g.impl()); |
417 | } |
418 | |
419 | template < UNDIRECTED_GRAPH_PARAMS > |
420 | inline std::pair< typename UNDIRECTED_GRAPH::in_edge_iterator, |
421 | typename UNDIRECTED_GRAPH::in_edge_iterator > |
422 | in_edges( |
423 | typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g) |
424 | { |
425 | return in_edges(v, g.impl()); |
426 | } |
427 | |
428 | template < UNDIRECTED_GRAPH_PARAMS > |
429 | inline std::pair< typename UNDIRECTED_GRAPH::out_edge_iterator, |
430 | typename UNDIRECTED_GRAPH::out_edge_iterator > |
431 | incident_edges( |
432 | typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g) |
433 | { |
434 | return out_edges(v, g.impl()); |
435 | } |
436 | |
437 | template < UNDIRECTED_GRAPH_PARAMS > |
438 | inline typename UNDIRECTED_GRAPH::degree_size_type degree( |
439 | typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g) |
440 | { |
441 | return degree(v, g.impl()); |
442 | } |
443 | |
444 | // AdjacencyGraph concepts |
445 | template < UNDIRECTED_GRAPH_PARAMS > |
446 | inline std::pair< typename UNDIRECTED_GRAPH::adjacency_iterator, |
447 | typename UNDIRECTED_GRAPH::adjacency_iterator > |
448 | adjacent_vertices( |
449 | typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g) |
450 | { |
451 | return adjacent_vertices(v, g.impl()); |
452 | } |
453 | |
454 | template < UNDIRECTED_GRAPH_PARAMS > |
455 | typename UNDIRECTED_GRAPH::vertex_descriptor vertex( |
456 | typename UNDIRECTED_GRAPH::vertices_size_type n, UNDIRECTED_GRAPH const& g) |
457 | { |
458 | return vertex(n, g.impl()); |
459 | } |
460 | |
461 | template < UNDIRECTED_GRAPH_PARAMS > |
462 | std::pair< typename UNDIRECTED_GRAPH::edge_descriptor, bool > edge( |
463 | typename UNDIRECTED_GRAPH::vertex_descriptor u, |
464 | typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g) |
465 | { |
466 | return edge(u, v, g.impl()); |
467 | } |
468 | |
469 | // VertexListGraph concepts |
470 | template < UNDIRECTED_GRAPH_PARAMS > |
471 | inline typename UNDIRECTED_GRAPH::vertices_size_type num_vertices( |
472 | UNDIRECTED_GRAPH const& g) |
473 | { |
474 | return g.num_vertices(); |
475 | } |
476 | |
477 | template < UNDIRECTED_GRAPH_PARAMS > |
478 | inline std::pair< typename UNDIRECTED_GRAPH::vertex_iterator, |
479 | typename UNDIRECTED_GRAPH::vertex_iterator > |
480 | vertices(UNDIRECTED_GRAPH const& g) |
481 | { |
482 | return vertices(g.impl()); |
483 | } |
484 | |
485 | // EdgeListGraph concepts |
486 | template < UNDIRECTED_GRAPH_PARAMS > |
487 | inline typename UNDIRECTED_GRAPH::edges_size_type num_edges( |
488 | UNDIRECTED_GRAPH const& g) |
489 | { |
490 | return g.num_edges(); |
491 | } |
492 | |
493 | template < UNDIRECTED_GRAPH_PARAMS > |
494 | inline std::pair< typename UNDIRECTED_GRAPH::edge_iterator, |
495 | typename UNDIRECTED_GRAPH::edge_iterator > |
496 | edges(UNDIRECTED_GRAPH const& g) |
497 | { |
498 | return edges(g.impl()); |
499 | } |
500 | |
501 | // MutableGraph concepts |
502 | template < UNDIRECTED_GRAPH_PARAMS > |
503 | inline typename UNDIRECTED_GRAPH::vertex_descriptor add_vertex( |
504 | UNDIRECTED_GRAPH& g) |
505 | { |
506 | return g.add_vertex(); |
507 | } |
508 | |
509 | template < UNDIRECTED_GRAPH_PARAMS > |
510 | inline typename UNDIRECTED_GRAPH::vertex_descriptor add_vertex( |
511 | typename UNDIRECTED_GRAPH::vertex_property_type const& p, |
512 | UNDIRECTED_GRAPH& g) |
513 | { |
514 | return g.add_vertex(p); |
515 | } |
516 | |
517 | template < UNDIRECTED_GRAPH_PARAMS > |
518 | inline void clear_vertex( |
519 | typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH& g) |
520 | { |
521 | return g.clear_vertex(v); |
522 | } |
523 | |
524 | template < UNDIRECTED_GRAPH_PARAMS > |
525 | inline void remove_vertex( |
526 | typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH& g) |
527 | { |
528 | return g.remove_vertex(v); |
529 | } |
530 | |
531 | template < UNDIRECTED_GRAPH_PARAMS > |
532 | inline std::pair< typename UNDIRECTED_GRAPH::edge_descriptor, bool > add_edge( |
533 | typename UNDIRECTED_GRAPH::vertex_descriptor u, |
534 | typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH& g) |
535 | { |
536 | return g.add_edge(u, v); |
537 | } |
538 | |
539 | template < UNDIRECTED_GRAPH_PARAMS > |
540 | inline std::pair< typename UNDIRECTED_GRAPH::edge_descriptor, bool > add_edge( |
541 | typename UNDIRECTED_GRAPH::vertex_descriptor u, |
542 | typename UNDIRECTED_GRAPH::vertex_descriptor v, |
543 | typename UNDIRECTED_GRAPH::edge_property_type const& p, UNDIRECTED_GRAPH& g) |
544 | { |
545 | return g.add_edge(u, v, p); |
546 | } |
547 | |
548 | template < UNDIRECTED_GRAPH_PARAMS > |
549 | inline void remove_edge(typename UNDIRECTED_GRAPH::vertex_descriptor u, |
550 | typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH& g) |
551 | { |
552 | return g.remove_edge(u, v); |
553 | } |
554 | |
555 | template < UNDIRECTED_GRAPH_PARAMS > |
556 | inline void remove_edge( |
557 | typename UNDIRECTED_GRAPH::edge_descriptor e, UNDIRECTED_GRAPH& g) |
558 | { |
559 | return g.remove_edge(e); |
560 | } |
561 | |
562 | template < UNDIRECTED_GRAPH_PARAMS > |
563 | inline void remove_edge( |
564 | typename UNDIRECTED_GRAPH::edge_iterator i, UNDIRECTED_GRAPH& g) |
565 | { |
566 | return g.remove_edge(i); |
567 | } |
568 | |
569 | template < UNDIRECTED_GRAPH_PARAMS, class Predicate > |
570 | inline void remove_edge_if(Predicate pred, UNDIRECTED_GRAPH& g) |
571 | { |
572 | return remove_edge_if(pred, g.impl()); |
573 | } |
574 | |
575 | template < UNDIRECTED_GRAPH_PARAMS, class Predicate > |
576 | inline void remove_incident_edge_if( |
577 | typename UNDIRECTED_GRAPH::vertex_descriptor v, Predicate pred, |
578 | UNDIRECTED_GRAPH& g) |
579 | { |
580 | return remove_out_edge_if(v, pred, g.impl()); |
581 | } |
582 | |
583 | template < UNDIRECTED_GRAPH_PARAMS, class Predicate > |
584 | inline void remove_out_edge_if(typename UNDIRECTED_GRAPH::vertex_descriptor v, |
585 | Predicate pred, UNDIRECTED_GRAPH& g) |
586 | { |
587 | return remove_out_edge_if(v, pred, g.impl()); |
588 | } |
589 | |
590 | template < UNDIRECTED_GRAPH_PARAMS, class Predicate > |
591 | inline void remove_in_edge_if(typename UNDIRECTED_GRAPH::vertex_descriptor v, |
592 | Predicate pred, UNDIRECTED_GRAPH& g) |
593 | { |
594 | return remove_in_edge_if(v, pred, g.impl()); |
595 | } |
596 | |
597 | template < UNDIRECTED_GRAPH_PARAMS, typename Property > |
598 | struct property_map< UNDIRECTED_GRAPH, Property > |
599 | : property_map< typename UNDIRECTED_GRAPH::graph_type, Property > |
600 | { |
601 | }; |
602 | |
603 | template < UNDIRECTED_GRAPH_PARAMS > |
604 | struct property_map< UNDIRECTED_GRAPH, vertex_all_t > |
605 | { |
606 | typedef transform_value_property_map< detail::remove_first_property, |
607 | typename property_map< typename UNDIRECTED_GRAPH::graph_type, |
608 | vertex_all_t >::const_type > |
609 | const_type; |
610 | typedef transform_value_property_map< detail::remove_first_property, |
611 | typename property_map< typename UNDIRECTED_GRAPH::graph_type, |
612 | vertex_all_t >::type > |
613 | type; |
614 | }; |
615 | |
616 | template < UNDIRECTED_GRAPH_PARAMS > |
617 | struct property_map< UNDIRECTED_GRAPH, edge_all_t > |
618 | { |
619 | typedef transform_value_property_map< detail::remove_first_property, |
620 | typename property_map< typename UNDIRECTED_GRAPH::graph_type, |
621 | edge_all_t >::const_type > |
622 | const_type; |
623 | typedef transform_value_property_map< detail::remove_first_property, |
624 | typename property_map< typename UNDIRECTED_GRAPH::graph_type, |
625 | edge_all_t >::type > |
626 | type; |
627 | }; |
628 | |
629 | // PropertyGraph concepts |
630 | template < UNDIRECTED_GRAPH_PARAMS, typename Property > |
631 | inline typename property_map< UNDIRECTED_GRAPH, Property >::type get( |
632 | Property p, UNDIRECTED_GRAPH& g) |
633 | { |
634 | return get(p, g.impl()); |
635 | } |
636 | |
637 | template < UNDIRECTED_GRAPH_PARAMS, typename Property > |
638 | inline typename property_map< UNDIRECTED_GRAPH, Property >::const_type get( |
639 | Property p, UNDIRECTED_GRAPH const& g) |
640 | { |
641 | return get(p, g.impl()); |
642 | } |
643 | |
644 | template < UNDIRECTED_GRAPH_PARAMS > |
645 | inline typename property_map< UNDIRECTED_GRAPH, vertex_all_t >::type get( |
646 | vertex_all_t, UNDIRECTED_GRAPH& g) |
647 | { |
648 | return typename property_map< UNDIRECTED_GRAPH, vertex_all_t >::type( |
649 | detail::remove_first_property(), get(vertex_all, g.impl())); |
650 | } |
651 | |
652 | template < UNDIRECTED_GRAPH_PARAMS > |
653 | inline typename property_map< UNDIRECTED_GRAPH, vertex_all_t >::const_type get( |
654 | vertex_all_t, UNDIRECTED_GRAPH const& g) |
655 | { |
656 | return typename property_map< UNDIRECTED_GRAPH, vertex_all_t >::const_type( |
657 | detail::remove_first_property(), get(vertex_all, g.impl())); |
658 | } |
659 | |
660 | template < UNDIRECTED_GRAPH_PARAMS > |
661 | inline typename property_map< UNDIRECTED_GRAPH, edge_all_t >::type get( |
662 | edge_all_t, UNDIRECTED_GRAPH& g) |
663 | { |
664 | return typename property_map< UNDIRECTED_GRAPH, edge_all_t >::type( |
665 | detail::remove_first_property(), get(edge_all, g.impl())); |
666 | } |
667 | |
668 | template < UNDIRECTED_GRAPH_PARAMS > |
669 | inline typename property_map< UNDIRECTED_GRAPH, edge_all_t >::const_type get( |
670 | edge_all_t, UNDIRECTED_GRAPH const& g) |
671 | { |
672 | return typename property_map< UNDIRECTED_GRAPH, edge_all_t >::const_type( |
673 | detail::remove_first_property(), get(edge_all, g.impl())); |
674 | } |
675 | |
676 | template < UNDIRECTED_GRAPH_PARAMS, typename Property, typename Key > |
677 | inline typename property_traits< typename property_map< |
678 | typename UNDIRECTED_GRAPH::graph_type, Property >::const_type >::value_type |
679 | get(Property p, UNDIRECTED_GRAPH const& g, Key const& k) |
680 | { |
681 | return get(p, g.impl(), k); |
682 | } |
683 | |
684 | template < UNDIRECTED_GRAPH_PARAMS, typename Key > |
685 | inline typename property_traits< |
686 | typename property_map< typename UNDIRECTED_GRAPH::graph_type, |
687 | vertex_all_t >::const_type >::value_type |
688 | get(vertex_all_t, UNDIRECTED_GRAPH const& g, Key const& k) |
689 | { |
690 | return get(vertex_all, g.impl(), k).m_base; |
691 | } |
692 | |
693 | template < UNDIRECTED_GRAPH_PARAMS, typename Key > |
694 | inline typename property_traits< |
695 | typename property_map< typename UNDIRECTED_GRAPH::graph_type, |
696 | edge_all_t >::const_type >::value_type |
697 | get(edge_all_t, UNDIRECTED_GRAPH const& g, Key const& k) |
698 | { |
699 | return get(edge_all, g.impl(), k).m_base; |
700 | } |
701 | |
702 | template < UNDIRECTED_GRAPH_PARAMS, typename Property, typename Key, |
703 | typename Value > |
704 | inline void put(Property p, UNDIRECTED_GRAPH& g, Key const& k, Value const& v) |
705 | { |
706 | put(p, g.impl(), k, v); |
707 | } |
708 | |
709 | template < UNDIRECTED_GRAPH_PARAMS, typename Key, typename Value > |
710 | inline void put(vertex_all_t, UNDIRECTED_GRAPH& g, Key const& k, Value const& v) |
711 | { |
712 | put(vertex_all, g.impl(), k, |
713 | typename UNDIRECTED_GRAPH::internal_vertex_property( |
714 | get(vertex_index, g.impl(), k), v)); |
715 | } |
716 | |
717 | template < UNDIRECTED_GRAPH_PARAMS, typename Key, typename Value > |
718 | inline void put(edge_all_t, UNDIRECTED_GRAPH& g, Key const& k, Value const& v) |
719 | { |
720 | put(edge_all, g.impl(), k, |
721 | typename UNDIRECTED_GRAPH::internal_vertex_property( |
722 | get(edge_index, g.impl(), k), v)); |
723 | } |
724 | |
725 | template < UNDIRECTED_GRAPH_PARAMS, class Property > |
726 | inline typename graph_property< UNDIRECTED_GRAPH, Property >::type& |
727 | get_property(UNDIRECTED_GRAPH& g, Property p) |
728 | { |
729 | return get_property(g.impl(), p); |
730 | } |
731 | |
732 | template < UNDIRECTED_GRAPH_PARAMS, class Property > |
733 | inline typename graph_property< UNDIRECTED_GRAPH, Property >::type const& |
734 | get_property(UNDIRECTED_GRAPH const& g, Property p) |
735 | { |
736 | return get_property(g.impl(), p); |
737 | } |
738 | |
739 | template < UNDIRECTED_GRAPH_PARAMS, class Property, class Value > |
740 | inline void set_property(UNDIRECTED_GRAPH& g, Property p, Value v) |
741 | { |
742 | return set_property(g.impl(), p, v); |
743 | } |
744 | |
745 | // Indexed Vertex graph |
746 | |
747 | template < UNDIRECTED_GRAPH_PARAMS > |
748 | inline typename UNDIRECTED_GRAPH::vertex_index_type get_vertex_index( |
749 | typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g) |
750 | { |
751 | return get(vertex_index, g, v); |
752 | } |
753 | |
754 | template < UNDIRECTED_GRAPH_PARAMS > |
755 | typename UNDIRECTED_GRAPH::vertex_index_type max_vertex_index( |
756 | UNDIRECTED_GRAPH const& g) |
757 | { |
758 | return g.max_vertex_index(); |
759 | } |
760 | |
761 | template < UNDIRECTED_GRAPH_PARAMS > |
762 | inline void renumber_vertex_indices(UNDIRECTED_GRAPH& g) |
763 | { |
764 | g.renumber_vertex_indices(); |
765 | } |
766 | |
767 | template < UNDIRECTED_GRAPH_PARAMS > |
768 | inline void remove_vertex_and_renumber_indices( |
769 | typename UNDIRECTED_GRAPH::vertex_iterator i, UNDIRECTED_GRAPH& g) |
770 | { |
771 | g.remove_vertex_and_renumber_indices(i); |
772 | } |
773 | |
774 | // Edge index management |
775 | |
776 | template < UNDIRECTED_GRAPH_PARAMS > |
777 | inline typename UNDIRECTED_GRAPH::edge_index_type get_edge_index( |
778 | typename UNDIRECTED_GRAPH::edge_descriptor v, UNDIRECTED_GRAPH const& g) |
779 | { |
780 | return get(edge_index, g, v); |
781 | } |
782 | |
783 | template < UNDIRECTED_GRAPH_PARAMS > |
784 | typename UNDIRECTED_GRAPH::edge_index_type max_edge_index( |
785 | UNDIRECTED_GRAPH const& g) |
786 | { |
787 | return g.max_edge_index(); |
788 | } |
789 | |
790 | template < UNDIRECTED_GRAPH_PARAMS > |
791 | inline void renumber_edge_indices(UNDIRECTED_GRAPH& g) |
792 | { |
793 | g.renumber_edge_indices(); |
794 | } |
795 | |
796 | template < UNDIRECTED_GRAPH_PARAMS > |
797 | inline void remove_edge_and_renumber_indices( |
798 | typename UNDIRECTED_GRAPH::edge_iterator i, UNDIRECTED_GRAPH& g) |
799 | { |
800 | g.remove_edge_and_renumber_indices(i); |
801 | } |
802 | |
803 | // Index management |
804 | template < UNDIRECTED_GRAPH_PARAMS > |
805 | inline void renumber_indices(UNDIRECTED_GRAPH& g) |
806 | { |
807 | g.renumber_indices(); |
808 | } |
809 | |
810 | // Mutability Traits |
811 | template < UNDIRECTED_GRAPH_PARAMS > |
812 | struct graph_mutability_traits< UNDIRECTED_GRAPH > |
813 | { |
814 | typedef mutable_property_graph_tag category; |
815 | }; |
816 | |
817 | #undef UNDIRECTED_GRAPH_PARAMS |
818 | #undef UNDIRECTED_GRAPH |
819 | |
820 | } /* namespace boost */ |
821 | |
822 | #endif |
823 | |