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

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