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
17namespace boost
18{
19struct 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 */
34template < typename VertexProp = no_property, typename EdgeProp = no_property,
35 typename GraphProp = no_property >
36class directed_graph
37{
38public:
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
49public:
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
56public:
57 typedef adjacency_list< listS, listS, bidirectionalS,
58 internal_vertex_property, internal_edge_property, GraphProp, listS >
59 graph_type;
60
61private:
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
68public:
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
159private:
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
169public:
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
195private:
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
209public:
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
340private:
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
378template < DIRECTED_GRAPH_PARAMS >
379inline 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
385template < DIRECTED_GRAPH_PARAMS >
386inline 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
392template < DIRECTED_GRAPH_PARAMS >
393inline 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
399template < DIRECTED_GRAPH_PARAMS >
400inline std::pair< typename DIRECTED_GRAPH::out_edge_iterator,
401 typename DIRECTED_GRAPH::out_edge_iterator >
402out_edges(typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g)
403{
404 return out_edges(v, g.impl());
405}
406
407// BidirectionalGraph concepts
408template < DIRECTED_GRAPH_PARAMS >
409inline 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
415template < DIRECTED_GRAPH_PARAMS >
416inline std::pair< typename DIRECTED_GRAPH::in_edge_iterator,
417 typename DIRECTED_GRAPH::in_edge_iterator >
418in_edges(typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g)
419{
420 return in_edges(v, g.impl());
421}
422
423template < DIRECTED_GRAPH_PARAMS >
424inline 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
431template < DIRECTED_GRAPH_PARAMS >
432inline std::pair< typename DIRECTED_GRAPH::adjacency_iterator,
433 typename DIRECTED_GRAPH::adjacency_iterator >
434adjacent_vertices(
435 typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g)
436{
437 return adjacent_vertices(v, g.impl());
438}
439
440template < DIRECTED_GRAPH_PARAMS >
441typename 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
447template < DIRECTED_GRAPH_PARAMS >
448std::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
456template < DIRECTED_GRAPH_PARAMS >
457inline typename DIRECTED_GRAPH::vertices_size_type num_vertices(
458 DIRECTED_GRAPH const& g)
459{
460 return g.num_vertices();
461}
462
463template < DIRECTED_GRAPH_PARAMS >
464inline std::pair< typename DIRECTED_GRAPH::vertex_iterator,
465 typename DIRECTED_GRAPH::vertex_iterator >
466vertices(DIRECTED_GRAPH const& g)
467{
468 return vertices(g.impl());
469}
470
471// EdgeListGraph concepts
472template < DIRECTED_GRAPH_PARAMS >
473inline typename DIRECTED_GRAPH::edges_size_type num_edges(
474 DIRECTED_GRAPH const& g)
475{
476 return g.num_edges();
477}
478
479template < DIRECTED_GRAPH_PARAMS >
480inline std::pair< typename DIRECTED_GRAPH::edge_iterator,
481 typename DIRECTED_GRAPH::edge_iterator >
482edges(DIRECTED_GRAPH const& g)
483{
484 return edges(g.impl());
485}
486
487// MutableGraph concepts
488template < DIRECTED_GRAPH_PARAMS >
489inline typename DIRECTED_GRAPH::vertex_descriptor add_vertex(DIRECTED_GRAPH& g)
490{
491 return g.add_vertex();
492}
493
494template < DIRECTED_GRAPH_PARAMS >
495inline 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
501template < DIRECTED_GRAPH_PARAMS >
502inline void clear_vertex(
503 typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH& g)
504{
505 return g.clear_vertex(v);
506}
507
508template < DIRECTED_GRAPH_PARAMS >
509inline void remove_vertex(
510 typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH& g)
511{
512 return g.remove_vertex(v);
513}
514
515template < DIRECTED_GRAPH_PARAMS >
516inline 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
523template < DIRECTED_GRAPH_PARAMS >
524inline 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
532template < DIRECTED_GRAPH_PARAMS >
533inline 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
539template < DIRECTED_GRAPH_PARAMS >
540inline void remove_edge(
541 typename DIRECTED_GRAPH::edge_descriptor e, DIRECTED_GRAPH& g)
542{
543 return g.remove_edge(e);
544}
545
546template < DIRECTED_GRAPH_PARAMS >
547inline void remove_edge(
548 typename DIRECTED_GRAPH::edge_iterator i, DIRECTED_GRAPH& g)
549{
550 return g.remove_edge(i);
551}
552
553template < DIRECTED_GRAPH_PARAMS, class Predicate >
554inline void remove_edge_if(Predicate pred, DIRECTED_GRAPH& g)
555{
556 return remove_edge_if(pred, g.impl());
557}
558
559template < DIRECTED_GRAPH_PARAMS, class Predicate >
560inline 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
566template < DIRECTED_GRAPH_PARAMS, class Predicate >
567inline 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
573template < DIRECTED_GRAPH_PARAMS, typename Property >
574struct property_map< DIRECTED_GRAPH, Property >
575: property_map< typename DIRECTED_GRAPH::graph_type, Property >
576{
577};
578
579template < DIRECTED_GRAPH_PARAMS >
580struct 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
592template < DIRECTED_GRAPH_PARAMS >
593struct 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
606template < DIRECTED_GRAPH_PARAMS, typename Property >
607inline typename property_map< DIRECTED_GRAPH, Property >::type get(
608 Property p, DIRECTED_GRAPH& g)
609{
610 return get(p, g.impl());
611}
612
613template < DIRECTED_GRAPH_PARAMS, typename Property >
614inline 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
620template < DIRECTED_GRAPH_PARAMS >
621inline 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
628template < DIRECTED_GRAPH_PARAMS >
629inline 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
636template < DIRECTED_GRAPH_PARAMS >
637inline 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
644template < DIRECTED_GRAPH_PARAMS >
645inline 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
652template < DIRECTED_GRAPH_PARAMS, typename Property, typename Key >
653inline typename property_traits< typename property_map<
654 typename DIRECTED_GRAPH::graph_type, Property >::const_type >::value_type
655get(Property p, DIRECTED_GRAPH const& g, Key const& k)
656{
657 return get(p, g.impl(), k);
658}
659
660template < DIRECTED_GRAPH_PARAMS, typename Key >
661inline typename property_traits<
662 typename property_map< typename DIRECTED_GRAPH::graph_type,
663 vertex_all_t >::const_type >::value_type
664get(vertex_all_t, DIRECTED_GRAPH const& g, Key const& k)
665{
666 return get(vertex_all, g.impl(), k).m_base;
667}
668
669template < DIRECTED_GRAPH_PARAMS, typename Key >
670inline typename property_traits< typename property_map<
671 typename DIRECTED_GRAPH::graph_type, edge_all_t >::const_type >::value_type
672get(edge_all_t, DIRECTED_GRAPH const& g, Key const& k)
673{
674 return get(edge_all, g.impl(), k).m_base;
675}
676
677template < DIRECTED_GRAPH_PARAMS, typename Property, typename Key,
678 typename Value >
679inline void put(Property p, DIRECTED_GRAPH& g, Key const& k, Value const& v)
680{
681 put(p, g.impl(), k, v);
682}
683
684template < DIRECTED_GRAPH_PARAMS, typename Key, typename Value >
685inline 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
692template < DIRECTED_GRAPH_PARAMS, typename Key, typename Value >
693inline 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
700template < DIRECTED_GRAPH_PARAMS, class Property >
701typename graph_property< DIRECTED_GRAPH, Property >::type& get_property(
702 DIRECTED_GRAPH& g, Property p)
703{
704 return get_property(g.impl(), p);
705}
706
707template < DIRECTED_GRAPH_PARAMS, class Property >
708typename 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
714template < DIRECTED_GRAPH_PARAMS, class Property, class Value >
715void 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
722template < DIRECTED_GRAPH_PARAMS >
723inline 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
729template < DIRECTED_GRAPH_PARAMS >
730typename DIRECTED_GRAPH::vertex_index_type max_vertex_index(
731 DIRECTED_GRAPH const& g)
732{
733 return g.max_vertex_index();
734}
735
736template < DIRECTED_GRAPH_PARAMS >
737inline void renumber_vertex_indices(DIRECTED_GRAPH& g)
738{
739 g.renumber_vertex_indices();
740}
741
742template < DIRECTED_GRAPH_PARAMS >
743inline 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
750template < DIRECTED_GRAPH_PARAMS >
751inline 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
757template < DIRECTED_GRAPH_PARAMS >
758typename DIRECTED_GRAPH::edge_index_type max_edge_index(DIRECTED_GRAPH const& g)
759{
760 return g.max_edge_index();
761}
762
763template < DIRECTED_GRAPH_PARAMS >
764inline void renumber_edge_indices(DIRECTED_GRAPH& g)
765{
766 g.renumber_edge_indices();
767}
768
769template < DIRECTED_GRAPH_PARAMS >
770inline 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
777template < DIRECTED_GRAPH_PARAMS >
778inline void renumber_indices(DIRECTED_GRAPH& g)
779{
780 g.renumber_indices();
781}
782
783// Mutability Traits
784template < DIRECTED_GRAPH_PARAMS >
785struct 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

source code of boost/libs/graph/include/boost/graph/directed_graph.hpp