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_DIRECTED_GRAPH_HPP |
8 | #define BOOST_GRAPH_DIRECTED_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 directed_graph_tag |
20 | { |
21 | }; |
22 | |
23 | /** |
24 | * The directed_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 BidirectionalGraph, VertexIndexGraph, and |
28 | * EdgeIndexGraph concepts. The graph is also fully mutable, supporting |
29 | * both insertions and removals of 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 directed_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, bidirectionalS, |
58 | internal_vertex_property, 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 directed_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 | directed_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 | directed_graph(directed_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 | directed_graph(vertices_size_type n, GraphProp const& p = GraphProp()) |
112 | : m_graph(n, p) |
113 | , m_num_vertices(n) |
114 | , m_num_edges(0) |
115 | , m_max_vertex_index(n) |
116 | , m_max_edge_index(0) |
117 | { |
118 | renumber_vertex_indices(); |
119 | } |
120 | |
121 | template < typename EdgeIterator > |
122 | directed_graph(EdgeIterator f, EdgeIterator l, vertices_size_type n, |
123 | edges_size_type m = 0, GraphProp const& p = GraphProp()) |
124 | : m_graph(f, l, n, m, p) |
125 | , m_num_vertices(n) |
126 | , m_num_edges(0) |
127 | , m_max_vertex_index(n) |
128 | , m_max_edge_index(0) |
129 | { |
130 | // Unfortunately, we have to renumber the entire graph. |
131 | renumber_indices(); |
132 | |
133 | // Can't always guarantee that the number of edges is actually |
134 | // m if distance(f, l) != m (or is undefined). |
135 | m_num_edges = m_max_edge_index = boost::num_edges(m_graph); |
136 | } |
137 | |
138 | directed_graph& operator=(directed_graph const& g) |
139 | { |
140 | if (&g != this) |
141 | { |
142 | m_graph = g.m_graph; |
143 | m_num_vertices = g.m_num_vertices; |
144 | m_num_edges = g.m_num_edges; |
145 | m_max_vertex_index = g.m_max_vertex_index; |
146 | m_max_edge_index = g.m_max_edge_index; |
147 | } |
148 | return *this; |
149 | } |
150 | |
151 | // The impl_() methods are not part of the public interface. |
152 | graph_type& impl() { return m_graph; } |
153 | |
154 | graph_type const& impl() const { return m_graph; } |
155 | |
156 | // The following methods are not part of the public interface |
157 | vertices_size_type num_vertices() const { return m_num_vertices; } |
158 | |
159 | private: |
160 | // This helper function manages the attribution of vertex indices. |
161 | vertex_descriptor make_index(vertex_descriptor v) |
162 | { |
163 | boost::put(vertex_index, m_graph, v, m_max_vertex_index); |
164 | m_num_vertices++; |
165 | m_max_vertex_index++; |
166 | return v; |
167 | } |
168 | |
169 | public: |
170 | vertex_descriptor add_vertex() |
171 | { |
172 | return make_index(boost::add_vertex(m_graph)); |
173 | } |
174 | |
175 | vertex_descriptor add_vertex(vertex_property_type const& p) |
176 | { |
177 | return make_index( |
178 | boost::add_vertex(internal_vertex_property(0u, p), m_graph)); |
179 | } |
180 | |
181 | void clear_vertex(vertex_descriptor v) |
182 | { |
183 | m_num_edges -= boost::degree(v, m_graph); |
184 | boost::clear_vertex(v, m_graph); |
185 | } |
186 | |
187 | void remove_vertex(vertex_descriptor v) |
188 | { |
189 | boost::remove_vertex(v, m_graph); |
190 | --m_num_vertices; |
191 | } |
192 | |
193 | edges_size_type num_edges() const { return m_num_edges; } |
194 | |
195 | private: |
196 | // A helper function for managing edge index attributes. |
197 | std::pair< edge_descriptor, bool > const& make_index( |
198 | std::pair< edge_descriptor, bool > const& x) |
199 | { |
200 | if (x.second) |
201 | { |
202 | boost::put(edge_index, m_graph, x.first, m_max_edge_index); |
203 | ++m_num_edges; |
204 | ++m_max_edge_index; |
205 | } |
206 | return x; |
207 | } |
208 | |
209 | public: |
210 | std::pair< edge_descriptor, bool > add_edge( |
211 | vertex_descriptor u, vertex_descriptor v) |
212 | { |
213 | return make_index(boost::add_edge(u, v, m_graph)); |
214 | } |
215 | |
216 | std::pair< edge_descriptor, bool > add_edge( |
217 | vertex_descriptor u, vertex_descriptor v, edge_property_type const& p) |
218 | { |
219 | return make_index( |
220 | boost::add_edge(u, v, internal_edge_property(0u, p), m_graph)); |
221 | } |
222 | |
223 | void remove_edge(vertex_descriptor u, vertex_descriptor v) |
224 | { |
225 | // find all edges, (u, v) |
226 | std::vector< edge_descriptor > edges; |
227 | out_edge_iterator i, i_end; |
228 | for (boost::tie(i, i_end) = boost::out_edges(u, m_graph); i != i_end; |
229 | ++i) |
230 | { |
231 | if (boost::target(*i, m_graph) == v) |
232 | { |
233 | edges.push_back(*i); |
234 | } |
235 | } |
236 | // remove all edges, (u, v) |
237 | typename std::vector< edge_descriptor >::iterator j = edges.begin(), |
238 | j_end = edges.end(); |
239 | for (; j != j_end; ++j) |
240 | { |
241 | remove_edge(*j); |
242 | } |
243 | } |
244 | |
245 | void remove_edge(edge_iterator i) { remove_edge(*i); } |
246 | |
247 | void remove_edge(edge_descriptor e) |
248 | { |
249 | boost::remove_edge(e, m_graph); |
250 | --m_num_edges; |
251 | } |
252 | |
253 | vertex_index_type max_vertex_index() const { return m_max_vertex_index; } |
254 | |
255 | void renumber_vertex_indices() |
256 | { |
257 | vertex_iterator i, end; |
258 | boost::tie(i, end) = vertices(m_graph); |
259 | m_max_vertex_index = renumber_vertex_indices(i, end, 0); |
260 | } |
261 | |
262 | void remove_vertex_and_renumber_indices(vertex_iterator i) |
263 | { |
264 | vertex_iterator j = next(i), end = vertices(m_graph).second; |
265 | vertex_index_type n = get(vertex_index, m_graph, *i); |
266 | |
267 | // remove the offending vertex and renumber everything after |
268 | remove_vertex(v: *i); |
269 | m_max_vertex_index = renumber_vertex_indices(j, end, n); |
270 | } |
271 | |
272 | edge_index_type max_edge_index() const { return m_max_edge_index; } |
273 | |
274 | void renumber_edge_indices() |
275 | { |
276 | edge_iterator i, end; |
277 | boost::tie(i, end) = edges(m_graph); |
278 | m_max_edge_index = renumber_edge_indices(i, end, 0); |
279 | } |
280 | |
281 | void remove_edge_and_renumber_indices(edge_iterator i) |
282 | { |
283 | edge_iterator j = next(i), end = edges(m_graph).second; |
284 | edge_index_type n = get(edge_index, m_graph, *i); |
285 | |
286 | // remove the offending edge and renumber everything after |
287 | remove_edge(*i); |
288 | m_max_edge_index = renumber_edge_indices(j, end, n); |
289 | } |
290 | |
291 | void renumber_indices() |
292 | { |
293 | renumber_vertex_indices(); |
294 | renumber_edge_indices(); |
295 | } |
296 | |
297 | // bundled property support |
298 | #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES |
299 | vertex_bundled& operator[](vertex_descriptor v) { return m_graph[v]; } |
300 | |
301 | vertex_bundled const& operator[](vertex_descriptor v) const |
302 | { |
303 | return m_graph[v]; |
304 | } |
305 | |
306 | edge_bundled& operator[](edge_descriptor e) { return m_graph[e]; } |
307 | |
308 | edge_bundled const& operator[](edge_descriptor e) const |
309 | { |
310 | return m_graph[e]; |
311 | } |
312 | |
313 | graph_bundled& operator[](graph_bundle_t) { return get_property(*this); } |
314 | |
315 | graph_bundled const& operator[](graph_bundle_t) const |
316 | { |
317 | return get_property(*this); |
318 | } |
319 | #endif |
320 | |
321 | // Graph concepts |
322 | static vertex_descriptor null_vertex() { return graph_type::null_vertex(); } |
323 | |
324 | void clear() |
325 | { |
326 | m_graph.clear(); |
327 | m_num_vertices = m_max_vertex_index = 0; |
328 | m_num_edges = m_max_edge_index = 0; |
329 | } |
330 | |
331 | void swap(directed_graph& g) |
332 | { |
333 | m_graph.swap(g.m_graph); |
334 | std::swap(m_num_vertices, g.m_num_vertices); |
335 | std::swap(m_max_vertex_index, g.m_max_vertex_index); |
336 | std::swap(m_num_edges, g.m_num_edges); |
337 | std::swap(m_max_edge_index, g.m_max_edge_index); |
338 | } |
339 | |
340 | private: |
341 | vertices_size_type renumber_vertex_indices( |
342 | vertex_iterator i, vertex_iterator end, vertices_size_type n) |
343 | { |
344 | typedef |
345 | typename property_map< graph_type, vertex_index_t >::type IndexMap; |
346 | IndexMap indices = get(vertex_index, m_graph); |
347 | for (; i != end; ++i) |
348 | { |
349 | indices[*i] = n++; |
350 | } |
351 | return n; |
352 | } |
353 | |
354 | vertices_size_type renumber_edge_indices( |
355 | edge_iterator i, edge_iterator end, vertices_size_type n) |
356 | { |
357 | typedef |
358 | typename property_map< graph_type, edge_index_t >::type IndexMap; |
359 | IndexMap indices = get(edge_index, m_graph); |
360 | for (; i != end; ++i) |
361 | { |
362 | indices[*i] = n++; |
363 | } |
364 | return n; |
365 | } |
366 | |
367 | graph_type m_graph; |
368 | vertices_size_type m_num_vertices; |
369 | edges_size_type m_num_edges; |
370 | vertex_index_type m_max_vertex_index; |
371 | edge_index_type m_max_edge_index; |
372 | }; |
373 | |
374 | #define DIRECTED_GRAPH_PARAMS typename VP, typename EP, typename GP |
375 | #define DIRECTED_GRAPH directed_graph< VP, EP, GP > |
376 | |
377 | // IncidenceGraph concepts |
378 | template < DIRECTED_GRAPH_PARAMS > |
379 | inline typename DIRECTED_GRAPH::vertex_descriptor source( |
380 | typename DIRECTED_GRAPH::edge_descriptor e, DIRECTED_GRAPH const& g) |
381 | { |
382 | return source(e, g.impl()); |
383 | } |
384 | |
385 | template < DIRECTED_GRAPH_PARAMS > |
386 | inline typename DIRECTED_GRAPH::vertex_descriptor target( |
387 | typename DIRECTED_GRAPH::edge_descriptor e, DIRECTED_GRAPH const& g) |
388 | { |
389 | return target(e, g.impl()); |
390 | } |
391 | |
392 | template < DIRECTED_GRAPH_PARAMS > |
393 | inline typename DIRECTED_GRAPH::degree_size_type out_degree( |
394 | typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g) |
395 | { |
396 | return out_degree(v, g.impl()); |
397 | } |
398 | |
399 | template < DIRECTED_GRAPH_PARAMS > |
400 | inline std::pair< typename DIRECTED_GRAPH::out_edge_iterator, |
401 | typename DIRECTED_GRAPH::out_edge_iterator > |
402 | out_edges(typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g) |
403 | { |
404 | return out_edges(v, g.impl()); |
405 | } |
406 | |
407 | // BidirectionalGraph concepts |
408 | template < DIRECTED_GRAPH_PARAMS > |
409 | inline typename DIRECTED_GRAPH::degree_size_type in_degree( |
410 | typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g) |
411 | { |
412 | return in_degree(v, g.impl()); |
413 | } |
414 | |
415 | template < DIRECTED_GRAPH_PARAMS > |
416 | inline std::pair< typename DIRECTED_GRAPH::in_edge_iterator, |
417 | typename DIRECTED_GRAPH::in_edge_iterator > |
418 | in_edges(typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g) |
419 | { |
420 | return in_edges(v, g.impl()); |
421 | } |
422 | |
423 | template < DIRECTED_GRAPH_PARAMS > |
424 | inline typename DIRECTED_GRAPH::degree_size_type degree( |
425 | typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g) |
426 | { |
427 | return degree(v, g.impl()); |
428 | } |
429 | |
430 | // AdjacencyGraph concepts |
431 | template < DIRECTED_GRAPH_PARAMS > |
432 | inline std::pair< typename DIRECTED_GRAPH::adjacency_iterator, |
433 | typename DIRECTED_GRAPH::adjacency_iterator > |
434 | adjacent_vertices( |
435 | typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g) |
436 | { |
437 | return adjacent_vertices(v, g.impl()); |
438 | } |
439 | |
440 | template < DIRECTED_GRAPH_PARAMS > |
441 | typename DIRECTED_GRAPH::vertex_descriptor vertex( |
442 | typename DIRECTED_GRAPH::vertices_size_type n, DIRECTED_GRAPH const& g) |
443 | { |
444 | return vertex(n, g.impl()); |
445 | } |
446 | |
447 | template < DIRECTED_GRAPH_PARAMS > |
448 | std::pair< typename DIRECTED_GRAPH::edge_descriptor, bool > edge( |
449 | typename DIRECTED_GRAPH::vertex_descriptor u, |
450 | typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g) |
451 | { |
452 | return edge(u, v, g.impl()); |
453 | } |
454 | |
455 | // VertexListGraph concepts |
456 | template < DIRECTED_GRAPH_PARAMS > |
457 | inline typename DIRECTED_GRAPH::vertices_size_type num_vertices( |
458 | DIRECTED_GRAPH const& g) |
459 | { |
460 | return g.num_vertices(); |
461 | } |
462 | |
463 | template < DIRECTED_GRAPH_PARAMS > |
464 | inline std::pair< typename DIRECTED_GRAPH::vertex_iterator, |
465 | typename DIRECTED_GRAPH::vertex_iterator > |
466 | vertices(DIRECTED_GRAPH const& g) |
467 | { |
468 | return vertices(g.impl()); |
469 | } |
470 | |
471 | // EdgeListGraph concepts |
472 | template < DIRECTED_GRAPH_PARAMS > |
473 | inline typename DIRECTED_GRAPH::edges_size_type num_edges( |
474 | DIRECTED_GRAPH const& g) |
475 | { |
476 | return g.num_edges(); |
477 | } |
478 | |
479 | template < DIRECTED_GRAPH_PARAMS > |
480 | inline std::pair< typename DIRECTED_GRAPH::edge_iterator, |
481 | typename DIRECTED_GRAPH::edge_iterator > |
482 | edges(DIRECTED_GRAPH const& g) |
483 | { |
484 | return edges(g.impl()); |
485 | } |
486 | |
487 | // MutableGraph concepts |
488 | template < DIRECTED_GRAPH_PARAMS > |
489 | inline typename DIRECTED_GRAPH::vertex_descriptor add_vertex(DIRECTED_GRAPH& g) |
490 | { |
491 | return g.add_vertex(); |
492 | } |
493 | |
494 | template < DIRECTED_GRAPH_PARAMS > |
495 | inline typename DIRECTED_GRAPH::vertex_descriptor add_vertex( |
496 | typename DIRECTED_GRAPH::vertex_property_type const& p, DIRECTED_GRAPH& g) |
497 | { |
498 | return g.add_vertex(p); |
499 | } |
500 | |
501 | template < DIRECTED_GRAPH_PARAMS > |
502 | inline void clear_vertex( |
503 | typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH& g) |
504 | { |
505 | return g.clear_vertex(v); |
506 | } |
507 | |
508 | template < DIRECTED_GRAPH_PARAMS > |
509 | inline void remove_vertex( |
510 | typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH& g) |
511 | { |
512 | return g.remove_vertex(v); |
513 | } |
514 | |
515 | template < DIRECTED_GRAPH_PARAMS > |
516 | inline std::pair< typename DIRECTED_GRAPH::edge_descriptor, bool > add_edge( |
517 | typename DIRECTED_GRAPH::vertex_descriptor u, |
518 | typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH& g) |
519 | { |
520 | return g.add_edge(u, v); |
521 | } |
522 | |
523 | template < DIRECTED_GRAPH_PARAMS > |
524 | inline std::pair< typename DIRECTED_GRAPH::edge_descriptor, bool > add_edge( |
525 | typename DIRECTED_GRAPH::vertex_descriptor u, |
526 | typename DIRECTED_GRAPH::vertex_descriptor v, |
527 | typename DIRECTED_GRAPH::edge_property_type const& p, DIRECTED_GRAPH& g) |
528 | { |
529 | return g.add_edge(u, v, p); |
530 | } |
531 | |
532 | template < DIRECTED_GRAPH_PARAMS > |
533 | inline void remove_edge(typename DIRECTED_GRAPH::vertex_descriptor u, |
534 | typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH& g) |
535 | { |
536 | return g.remove_edge(u, v); |
537 | } |
538 | |
539 | template < DIRECTED_GRAPH_PARAMS > |
540 | inline void remove_edge( |
541 | typename DIRECTED_GRAPH::edge_descriptor e, DIRECTED_GRAPH& g) |
542 | { |
543 | return g.remove_edge(e); |
544 | } |
545 | |
546 | template < DIRECTED_GRAPH_PARAMS > |
547 | inline void remove_edge( |
548 | typename DIRECTED_GRAPH::edge_iterator i, DIRECTED_GRAPH& g) |
549 | { |
550 | return g.remove_edge(i); |
551 | } |
552 | |
553 | template < DIRECTED_GRAPH_PARAMS, class Predicate > |
554 | inline void remove_edge_if(Predicate pred, DIRECTED_GRAPH& g) |
555 | { |
556 | return remove_edge_if(pred, g.impl()); |
557 | } |
558 | |
559 | template < DIRECTED_GRAPH_PARAMS, class Predicate > |
560 | inline void remove_out_edge_if(typename DIRECTED_GRAPH::vertex_descriptor v, |
561 | Predicate pred, DIRECTED_GRAPH& g) |
562 | { |
563 | return remove_out_edge_if(v, pred, g.impl()); |
564 | } |
565 | |
566 | template < DIRECTED_GRAPH_PARAMS, class Predicate > |
567 | inline void remove_in_edge_if(typename DIRECTED_GRAPH::vertex_descriptor v, |
568 | Predicate pred, DIRECTED_GRAPH& g) |
569 | { |
570 | return remove_in_edge_if(v, pred, g.impl()); |
571 | } |
572 | |
573 | template < DIRECTED_GRAPH_PARAMS, typename Property > |
574 | struct property_map< DIRECTED_GRAPH, Property > |
575 | : property_map< typename DIRECTED_GRAPH::graph_type, Property > |
576 | { |
577 | }; |
578 | |
579 | template < DIRECTED_GRAPH_PARAMS > |
580 | struct property_map< DIRECTED_GRAPH, vertex_all_t > |
581 | { |
582 | typedef transform_value_property_map< detail::remove_first_property, |
583 | typename property_map< typename DIRECTED_GRAPH::graph_type, |
584 | vertex_all_t >::const_type > |
585 | const_type; |
586 | typedef transform_value_property_map< detail::remove_first_property, |
587 | typename property_map< typename DIRECTED_GRAPH::graph_type, |
588 | vertex_all_t >::type > |
589 | type; |
590 | }; |
591 | |
592 | template < DIRECTED_GRAPH_PARAMS > |
593 | struct property_map< DIRECTED_GRAPH, edge_all_t > |
594 | { |
595 | typedef transform_value_property_map< detail::remove_first_property, |
596 | typename property_map< typename DIRECTED_GRAPH::graph_type, |
597 | edge_all_t >::const_type > |
598 | const_type; |
599 | typedef transform_value_property_map< detail::remove_first_property, |
600 | typename property_map< typename DIRECTED_GRAPH::graph_type, |
601 | edge_all_t >::type > |
602 | type; |
603 | }; |
604 | |
605 | // PropertyGraph concepts |
606 | template < DIRECTED_GRAPH_PARAMS, typename Property > |
607 | inline typename property_map< DIRECTED_GRAPH, Property >::type get( |
608 | Property p, DIRECTED_GRAPH& g) |
609 | { |
610 | return get(p, g.impl()); |
611 | } |
612 | |
613 | template < DIRECTED_GRAPH_PARAMS, typename Property > |
614 | inline typename property_map< DIRECTED_GRAPH, Property >::const_type get( |
615 | Property p, DIRECTED_GRAPH const& g) |
616 | { |
617 | return get(p, g.impl()); |
618 | } |
619 | |
620 | template < DIRECTED_GRAPH_PARAMS > |
621 | inline typename property_map< DIRECTED_GRAPH, vertex_all_t >::type get( |
622 | vertex_all_t, DIRECTED_GRAPH& g) |
623 | { |
624 | return typename property_map< DIRECTED_GRAPH, vertex_all_t >::type( |
625 | detail::remove_first_property(), get(vertex_all, g.impl())); |
626 | } |
627 | |
628 | template < DIRECTED_GRAPH_PARAMS > |
629 | inline typename property_map< DIRECTED_GRAPH, vertex_all_t >::const_type get( |
630 | vertex_all_t, DIRECTED_GRAPH const& g) |
631 | { |
632 | return typename property_map< DIRECTED_GRAPH, vertex_all_t >::const_type( |
633 | detail::remove_first_property(), get(vertex_all, g.impl())); |
634 | } |
635 | |
636 | template < DIRECTED_GRAPH_PARAMS > |
637 | inline typename property_map< DIRECTED_GRAPH, edge_all_t >::type get( |
638 | edge_all_t, DIRECTED_GRAPH& g) |
639 | { |
640 | return typename property_map< DIRECTED_GRAPH, edge_all_t >::type( |
641 | detail::remove_first_property(), get(edge_all, g.impl())); |
642 | } |
643 | |
644 | template < DIRECTED_GRAPH_PARAMS > |
645 | inline typename property_map< DIRECTED_GRAPH, edge_all_t >::const_type get( |
646 | edge_all_t, DIRECTED_GRAPH const& g) |
647 | { |
648 | return typename property_map< DIRECTED_GRAPH, edge_all_t >::const_type( |
649 | detail::remove_first_property(), get(edge_all, g.impl())); |
650 | } |
651 | |
652 | template < DIRECTED_GRAPH_PARAMS, typename Property, typename Key > |
653 | inline typename property_traits< typename property_map< |
654 | typename DIRECTED_GRAPH::graph_type, Property >::const_type >::value_type |
655 | get(Property p, DIRECTED_GRAPH const& g, Key const& k) |
656 | { |
657 | return get(p, g.impl(), k); |
658 | } |
659 | |
660 | template < DIRECTED_GRAPH_PARAMS, typename Key > |
661 | inline typename property_traits< |
662 | typename property_map< typename DIRECTED_GRAPH::graph_type, |
663 | vertex_all_t >::const_type >::value_type |
664 | get(vertex_all_t, DIRECTED_GRAPH const& g, Key const& k) |
665 | { |
666 | return get(vertex_all, g.impl(), k).m_base; |
667 | } |
668 | |
669 | template < DIRECTED_GRAPH_PARAMS, typename Key > |
670 | inline typename property_traits< typename property_map< |
671 | typename DIRECTED_GRAPH::graph_type, edge_all_t >::const_type >::value_type |
672 | get(edge_all_t, DIRECTED_GRAPH const& g, Key const& k) |
673 | { |
674 | return get(edge_all, g.impl(), k).m_base; |
675 | } |
676 | |
677 | template < DIRECTED_GRAPH_PARAMS, typename Property, typename Key, |
678 | typename Value > |
679 | inline void put(Property p, DIRECTED_GRAPH& g, Key const& k, Value const& v) |
680 | { |
681 | put(p, g.impl(), k, v); |
682 | } |
683 | |
684 | template < DIRECTED_GRAPH_PARAMS, typename Key, typename Value > |
685 | inline void put(vertex_all_t, DIRECTED_GRAPH& g, Key const& k, Value const& v) |
686 | { |
687 | put(vertex_all, g.impl(), k, |
688 | typename DIRECTED_GRAPH::internal_vertex_property( |
689 | get(vertex_index, g.impl(), k), v)); |
690 | } |
691 | |
692 | template < DIRECTED_GRAPH_PARAMS, typename Key, typename Value > |
693 | inline void put(edge_all_t, DIRECTED_GRAPH& g, Key const& k, Value const& v) |
694 | { |
695 | put(edge_all, g.impl(), k, |
696 | typename DIRECTED_GRAPH::internal_vertex_property( |
697 | get(edge_index, g.impl(), k), v)); |
698 | } |
699 | |
700 | template < DIRECTED_GRAPH_PARAMS, class Property > |
701 | typename graph_property< DIRECTED_GRAPH, Property >::type& get_property( |
702 | DIRECTED_GRAPH& g, Property p) |
703 | { |
704 | return get_property(g.impl(), p); |
705 | } |
706 | |
707 | template < DIRECTED_GRAPH_PARAMS, class Property > |
708 | typename graph_property< DIRECTED_GRAPH, Property >::type const& get_property( |
709 | DIRECTED_GRAPH const& g, Property p) |
710 | { |
711 | return get_property(g.impl(), p); |
712 | } |
713 | |
714 | template < DIRECTED_GRAPH_PARAMS, class Property, class Value > |
715 | void set_property(DIRECTED_GRAPH& g, Property p, Value v) |
716 | { |
717 | return set_property(g.impl(), p, v); |
718 | } |
719 | |
720 | // Vertex index management |
721 | |
722 | template < DIRECTED_GRAPH_PARAMS > |
723 | inline typename DIRECTED_GRAPH::vertex_index_type get_vertex_index( |
724 | typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g) |
725 | { |
726 | return get(vertex_index, g, v); |
727 | } |
728 | |
729 | template < DIRECTED_GRAPH_PARAMS > |
730 | typename DIRECTED_GRAPH::vertex_index_type max_vertex_index( |
731 | DIRECTED_GRAPH const& g) |
732 | { |
733 | return g.max_vertex_index(); |
734 | } |
735 | |
736 | template < DIRECTED_GRAPH_PARAMS > |
737 | inline void renumber_vertex_indices(DIRECTED_GRAPH& g) |
738 | { |
739 | g.renumber_vertex_indices(); |
740 | } |
741 | |
742 | template < DIRECTED_GRAPH_PARAMS > |
743 | inline void remove_vertex_and_renumber_indices( |
744 | typename DIRECTED_GRAPH::vertex_iterator i, DIRECTED_GRAPH& g) |
745 | { |
746 | g.remove_vertex_and_renumber_indices(i); |
747 | } |
748 | |
749 | // Edge index management |
750 | template < DIRECTED_GRAPH_PARAMS > |
751 | inline typename DIRECTED_GRAPH::edge_index_type get_edge_index( |
752 | typename DIRECTED_GRAPH::edge_descriptor v, DIRECTED_GRAPH const& g) |
753 | { |
754 | return get(edge_index, g, v); |
755 | } |
756 | |
757 | template < DIRECTED_GRAPH_PARAMS > |
758 | typename DIRECTED_GRAPH::edge_index_type max_edge_index(DIRECTED_GRAPH const& g) |
759 | { |
760 | return g.max_edge_index(); |
761 | } |
762 | |
763 | template < DIRECTED_GRAPH_PARAMS > |
764 | inline void renumber_edge_indices(DIRECTED_GRAPH& g) |
765 | { |
766 | g.renumber_edge_indices(); |
767 | } |
768 | |
769 | template < DIRECTED_GRAPH_PARAMS > |
770 | inline void remove_edge_and_renumber_indices( |
771 | typename DIRECTED_GRAPH::edge_iterator i, DIRECTED_GRAPH& g) |
772 | { |
773 | g.remove_edge_and_renumber_indices(i); |
774 | } |
775 | |
776 | // Index management |
777 | template < DIRECTED_GRAPH_PARAMS > |
778 | inline void renumber_indices(DIRECTED_GRAPH& g) |
779 | { |
780 | g.renumber_indices(); |
781 | } |
782 | |
783 | // Mutability Traits |
784 | template < DIRECTED_GRAPH_PARAMS > |
785 | struct graph_mutability_traits< DIRECTED_GRAPH > |
786 | { |
787 | typedef mutable_property_graph_tag category; |
788 | }; |
789 | |
790 | #undef DIRECTED_GRAPH_PARAMS |
791 | #undef DIRECTED_GRAPH |
792 | |
793 | } /* namespace boost */ |
794 | |
795 | #endif |
796 | |