1// Copyright (C) 2009 Andrew Sutton
2
3// Use, modification and distribution is subject to the Boost Software
4// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
5// http://www.boost.org/LICENSE_1_0.txt)
6
7#ifndef BOOST_GRAPH_LABELED_GRAPH_HPP
8#define BOOST_GRAPH_LABELED_GRAPH_HPP
9
10#include <boost/config.hpp>
11#include <vector>
12#include <map>
13
14#include <boost/static_assert.hpp>
15#include <boost/mpl/if.hpp>
16#include <boost/mpl/bool.hpp>
17#include <boost/unordered_map.hpp>
18#include <boost/type_traits/is_same.hpp>
19#include <boost/type_traits/is_unsigned.hpp>
20#include <boost/pending/container_traits.hpp>
21#include <boost/graph/graph_traits.hpp>
22
23// This file implements a utility for creating mappings from arbitrary
24// identifiers to the vertices of a graph.
25
26namespace boost {
27
28// A type selector that denotes the use of some default value.
29struct defaultS { };
30
31/** @internal */
32namespace graph_detail {
33 /** Returns true if the selector is the default selector. */
34 template <typename Selector>
35 struct is_default
36 : mpl::bool_<is_same<Selector, defaultS>::value>
37 { };
38
39 /**
40 * Choose the default map instance. If Label is an unsigned integral type
41 * the we can use a vector to store the information.
42 */
43 template <typename Label, typename Vertex>
44 struct choose_default_map {
45 typedef typename mpl::if_<
46 is_unsigned<Label>,
47 std::vector<Vertex>,
48 std::map<Label, Vertex> // TODO: Should use unordered_map?
49 >::type type;
50 };
51
52 /**
53 * @name Generate Label Map
54 * These type generators are responsible for instantiating an associative
55 * container for the the labeled graph. Note that the Selector must be
56 * select a pair associative container or a vecS, which is only valid if
57 * Label is an integral type.
58 */
59 //@{
60 template <typename Selector, typename Label, typename Vertex>
61 struct generate_label_map { };
62
63 template <typename Label, typename Vertex>
64 struct generate_label_map<vecS, Label, Vertex>
65 { typedef std::vector<Vertex> type; };
66
67 template <typename Label, typename Vertex>
68 struct generate_label_map<mapS, Label, Vertex>
69 { typedef std::map<Label, Vertex> type; };
70
71 template <typename Label, typename Vertex>
72 struct generate_label_map<multimapS, Label, Vertex>
73 { typedef std::multimap<Label, Vertex> type; };
74
75 template <typename Label, typename Vertex>
76 struct generate_label_map<hash_mapS, Label, Vertex>
77 { typedef boost::unordered_map<Label, Vertex> type; };
78
79 template <typename Label, typename Vertex>
80 struct generate_label_map<hash_multimapS, Label, Vertex>
81 { typedef boost::unordered_multimap<Label, Vertex> type; };
82
83 template <typename Selector, typename Label, typename Vertex>
84 struct choose_custom_map {
85 typedef typename generate_label_map<Selector, Label, Vertex>::type type;
86 };
87 //@}
88
89 /**
90 * Choose and instantiate an "associative" container. Note that this can
91 * also choose vector.
92 */
93 template <typename Selector, typename Label, typename Vertex>
94 struct choose_map {
95 typedef typename mpl::eval_if<
96 is_default<Selector>,
97 choose_default_map<Label, Vertex>,
98 choose_custom_map<Selector, Label, Vertex>
99 >::type type;
100 };
101
102 /** @name Insert Labeled Vertex */
103 //@{
104 // Tag dispatch on random access containers (i.e., vectors). This function
105 // basically requires a) that Container is vector<Label> and that Label
106 // is an unsigned integral value. Note that this will resize the vector
107 // to accommodate indices.
108 template <typename Container, typename Graph, typename Label, typename Prop>
109 std::pair<typename graph_traits<Graph>::vertex_descriptor, bool>
110 insert_labeled_vertex(Container& c, Graph& g, Label const& l, Prop const& p,
111 random_access_container_tag)
112 {
113 typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
114
115 // If the label is out of bounds, resize the vector to accommodate.
116 // Resize by 2x the index so we don't cause quadratic insertions over
117 // time.
118 if(l >= c.size()) {
119 c.resize((l + 1) * 2);
120 }
121 Vertex v = add_vertex(p, g);
122 c[l] = v;
123 return std::make_pair(c[l], true);
124 }
125
126 // Tag dispatch on multi associative containers (i.e. multimaps).
127 template <typename Container, typename Graph, typename Label, typename Prop>
128 std::pair<typename graph_traits<Graph>::vertex_descriptor, bool>
129 insert_labeled_vertex(Container& c, Graph& g, Label const& l, Prop const& p,
130 multiple_associative_container_tag const&)
131 {
132 // Note that insertion always succeeds so we can add the vertex first
133 // and then the mapping to the label.
134 typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
135 Vertex v = add_vertex(g);
136 c.insert(std::make_pair(l, v));
137 return std::make_pair(v, true);
138 }
139
140 // Tag dispatch on unique associative containers (i.e. maps).
141 template <typename Container, typename Graph, typename Label, typename Prop>
142 std::pair<typename graph_traits<Graph>::vertex_descriptor, bool>
143 insert_labeled_vertex(Container& c, Graph& g, Label const& l, Prop const& p,
144 unique_associative_container_tag)
145 {
146 // Here, we actually have to try the insertion first, and only add
147 // the vertex if we get a new element.
148 typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
149 typedef typename Container::iterator Iterator;
150 std::pair<Iterator, bool> x = c.insert(std::make_pair(l, Vertex()));
151 if(x.second) {
152 x.first->second = add_vertex(g);
153 put(boost::vertex_all, g, x.first->second, p);
154 }
155 return std::make_pair(x.first->second, x.second);
156 }
157
158 // Dispatcher
159 template <typename Container, typename Graph, typename Label, typename Prop>
160 std::pair<typename graph_traits<Graph>::vertex_descriptor, bool>
161 insert_labeled_vertex(Container& c, Graph& g, Label const& l, Prop const& p)
162 { return insert_labeled_vertex(c, g, l, p, container_category(c)); }
163 //@}
164
165 /** @name Find Labeled Vertex */
166 //@{
167 // Tag dispatch for sequential maps (i.e., vectors).
168 template <typename Container, typename Graph, typename Label>
169 typename graph_traits<Graph>::vertex_descriptor
170 find_labeled_vertex(Container const& c, Graph const&, Label const& l,
171 random_access_container_tag)
172 { return l < c.size() ? c[l] : graph_traits<Graph>::null_vertex(); }
173
174 // Tag dispatch for pair associative maps (more or less).
175 template <typename Container, typename Graph, typename Label>
176 typename graph_traits<Graph>::vertex_descriptor
177 find_labeled_vertex(Container const& c, Graph const&, Label const& l,
178 associative_container_tag)
179 {
180 typename Container::const_iterator i = c.find(l);
181 return i != c.end() ? i->second : graph_traits<Graph>::null_vertex();
182 }
183
184 // Dispatcher
185 template <typename Container, typename Graph, typename Label>
186 typename graph_traits<Graph>::vertex_descriptor
187 find_labeled_vertex(Container const& c, Graph const& g, Label const& l)
188 { return find_labeled_vertex(c, g, l, container_category(c)); }
189 //@}
190
191 /** @name Put Vertex Label */
192 //@{
193 // Tag dispatch on vectors.
194 template <typename Container, typename Label, typename Graph, typename Vertex>
195 bool put_vertex_label(Container& c, Graph const&, Label const& l, Vertex v,
196 random_access_container_tag)
197 {
198 // If the element is already occupied, then we probably don't want to
199 // overwrite it.
200 if(c[l] == graph_traits<Graph>::null_vertex()) return false;
201 c[l] = v;
202 return true;
203 }
204
205 // Attempt the insertion and return its result.
206 template <typename Container, typename Label, typename Graph, typename Vertex>
207 bool put_vertex_label(Container& c, Graph const&, Label const& l, Vertex v,
208 unique_associative_container_tag)
209 { return c.insert(std::make_pair(l, v)).second; }
210
211 // Insert the pair and return true.
212 template <typename Container, typename Label, typename Graph, typename Vertex>
213 bool put_vertex_label(Container& c, Graph const&, Label const& l, Vertex v,
214 multiple_associative_container_tag)
215 {
216 c.insert(std::make_pair(l, v));
217 return true;
218 }
219
220 // Dispatcher
221 template <typename Container, typename Label, typename Graph, typename Vertex>
222 bool put_vertex_label(Container& c, Graph const& g, Label const& l, Vertex v)
223 { return put_vertex_label(c, g, l, v, container_category(c)); }
224 //@}
225
226} // namespace detail
227
228struct labeled_graph_class_tag { };
229
230/** @internal
231 * This class is responsible for the deduction and declaration of type names
232 * for the labeled_graph class template.
233 */
234template <typename Graph, typename Label, typename Selector>
235struct labeled_graph_types {
236 typedef Graph graph_type;
237
238 // Label and maps
239 typedef Label label_type;
240 typedef typename graph_detail::choose_map<
241 Selector, Label, typename graph_traits<Graph>::vertex_descriptor
242 >::type map_type;
243};
244
245/**
246 * The labeled_graph class is a graph adaptor that maintains a mapping between
247 * vertex labels and vertex descriptors.
248 *
249 * @todo This class is somewhat redundant for adjacency_list<*, vecS> if
250 * the intended label is an unsigned int (and perhaps some other cases), but
251 * it does avoid some weird ambiguities (i.e. adding a vertex with a label that
252 * does not match its target index).
253 *
254 * @todo This needs to be reconciled with the named_graph, but since there is
255 * no documentation or examples, its not going to happen.
256 */
257template <typename Graph, typename Label, typename Selector = defaultS>
258class labeled_graph
259 : protected labeled_graph_types<Graph, Label, Selector>
260{
261 typedef labeled_graph_types<Graph, Label, Selector> Base;
262public:
263 typedef labeled_graph_class_tag graph_tag;
264
265 typedef typename Base::graph_type graph_type;
266 typedef typename graph_traits<graph_type>::vertex_descriptor vertex_descriptor;
267 typedef typename graph_traits<graph_type>::edge_descriptor edge_descriptor;
268 typedef typename graph_traits<graph_type>::directed_category directed_category;
269 typedef typename graph_traits<graph_type>::edge_parallel_category edge_parallel_category;
270 typedef typename graph_traits<graph_type>::traversal_category traversal_category;
271
272 typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
273 typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
274 typedef typename graph_traits<graph_type>::adjacency_iterator adjacency_iterator;
275 typedef typename graph_traits<graph_type>::degree_size_type degree_size_type;
276
277 typedef typename graph_traits<graph_type>::vertex_iterator vertex_iterator;
278 typedef typename graph_traits<graph_type>::vertices_size_type vertices_size_type;
279 typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
280 typedef typename graph_traits<graph_type>::edges_size_type edges_size_type;
281
282 typedef typename graph_type::graph_property_type graph_property_type;
283 typedef typename graph_type::graph_bundled graph_bundled;
284
285 typedef typename graph_type::vertex_property_type vertex_property_type;
286 typedef typename graph_type::vertex_bundled vertex_bundled;
287
288 typedef typename graph_type::edge_property_type edge_property_type;
289 typedef typename graph_type::edge_bundled edge_bundled;
290
291 typedef typename Base::label_type label_type;
292 typedef typename Base::map_type map_type;
293
294public:
295 labeled_graph(graph_property_type const& gp = graph_property_type())
296 : _graph(gp), _map()
297 { }
298
299 labeled_graph(labeled_graph const& x)
300 : _graph(x._graph), _map(x._map)
301 { }
302
303 // This constructor can only be used if map_type supports positional
304 // range insertion (i.e. its a vector). This is the only case where we can
305 // try to guess the intended labels for graph.
306 labeled_graph(vertices_size_type n,
307 graph_property_type const& gp = graph_property_type())
308 : _graph(n, gp), _map()
309 {
310 std::pair<vertex_iterator, vertex_iterator> rng = vertices(_graph);
311 _map.insert(_map.end(), rng.first, rng.second);
312 }
313
314 // Construct a graph over n vertices, each of which receives a label from
315 // the range [l, l + n). Note that the graph is not directly constructed
316 // over the n vertices, but added sequentially. This constructor is
317 // necessarily slower than the underlying counterpart.
318 template <typename LabelIter>
319 labeled_graph(vertices_size_type n, LabelIter l,
320 graph_property_type const& gp = graph_property_type())
321 : _graph(gp)
322 { while(n-- >= 0) add_vertex(*l++); }
323
324 // Construct the graph over n vertices each of which has a label in the
325 // range [l, l + n) and a property in the range [p, p + n).
326 template <typename LabelIter, typename PropIter>
327 labeled_graph(vertices_size_type n, LabelIter l, PropIter p,
328 graph_property_type const& gp = graph_property_type())
329 { while(n-- >= 0) add_vertex(*l++, *p++); }
330
331 labeled_graph& operator=(labeled_graph const& x) {
332 _graph = x._graph;
333 _map = x._map;
334 return *this;
335 }
336
337 /** @name Graph Accessors */
338 //@{
339 graph_type& graph() { return _graph; }
340 graph_type const& graph() const { return _graph; }
341 //@}
342
343 /**
344 * Create a new label for the given vertex, returning false, if the label
345 * cannot be created.
346 */
347 bool label_vertex(vertex_descriptor v, Label const& l)
348 { return graph_detail::put_vertex_label(_map, _graph, l, v); }
349
350 /** @name Add Vertex
351 * Add a vertex to the graph, returning the descriptor. If the vertices
352 * are uniquely labeled and the label already exists within the graph,
353 * then no vertex is added, and the returned descriptor refers to the
354 * existing vertex. A vertex property can be given as a parameter, if
355 * needed.
356 */
357 //@{
358 vertex_descriptor add_vertex(Label const& l) {
359 return graph_detail::insert_labeled_vertex(
360 _map, _graph, l, vertex_property_type()
361 ).first;
362 }
363
364 vertex_descriptor add_vertex(Label const& l, vertex_property_type const& p)
365 { return graph_detail::insert_labeled_vertex(_map, _graph, l, p).first; }
366 //@}
367
368 /** @name Insert Vertex
369 * Insert a vertex into the graph, returning a pair containing the
370 * descriptor of a vertex and a boolean value that describes whether or not
371 * a new vertex was inserted. If vertices are not uniquely labeled, then
372 * insertion will always succeed.
373 */
374 //@{
375 std::pair<vertex_descriptor, bool> insert_vertex(Label const& l) {
376 return graph_detail::insert_labeled_vertex(
377 _map, _graph, l, vertex_property_type()
378 );
379 }
380
381 std::pair<vertex_descriptor, bool>
382 insert_vertex(Label const& l, vertex_property_type const& p)
383 { return graph_detail::insert_labeled_vertex(_map, _graph, l, p); }
384 //@}
385
386 /** Remove the vertex with the given label. */
387 void remove_vertex(Label const& l)
388 { return boost::remove_vertex(vertex(l), _graph); }
389
390 /** Return a descriptor for the given label. */
391 vertex_descriptor vertex(Label const& l) const
392 { return graph_detail::find_labeled_vertex(_map, _graph, l); }
393
394#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
395 /** @name Bundled Properties */
396 //@{
397 // Lookup the requested vertex and return the bundle.
398 vertex_bundled& operator[](Label const& l)
399 { return _graph[vertex(l)]; }
400
401 vertex_bundled const& operator[](Label const& l) const
402 { return _graph[vertex(l)]; }
403
404 // Delegate edge lookup to the underlying graph.
405 edge_bundled& operator[](edge_descriptor e)
406 { return _graph[e]; }
407
408 edge_bundled const& operator[](edge_descriptor e) const
409 { return _graph[e]; }
410 //@}
411#endif
412
413 /** Return a null descriptor */
414 static vertex_descriptor null_vertex()
415 { return graph_traits<graph_type>::null_vertex(); }
416
417private:
418 graph_type _graph;
419 map_type _map;
420};
421
422/**
423 * The partial specialization over graph pointers allows the construction
424 * of temporary labeled graph objects. In this case, the labels are destructed
425 * when the wrapper goes out of scope.
426 */
427template <typename Graph, typename Label, typename Selector>
428class labeled_graph<Graph*, Label, Selector>
429 : protected labeled_graph_types<Graph, Label, Selector>
430{
431 typedef labeled_graph_types<Graph, Label, Selector> Base;
432public:
433 typedef labeled_graph_class_tag graph_tag;
434
435 typedef typename Base::graph_type graph_type;
436 typedef typename graph_traits<graph_type>::vertex_descriptor vertex_descriptor;
437 typedef typename graph_traits<graph_type>::edge_descriptor edge_descriptor;
438 typedef typename graph_traits<graph_type>::directed_category directed_category;
439 typedef typename graph_traits<graph_type>::edge_parallel_category edge_parallel_category;
440 typedef typename graph_traits<graph_type>::traversal_category traversal_category;
441
442 typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
443 typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
444 typedef typename graph_traits<graph_type>::adjacency_iterator adjacency_iterator;
445 typedef typename graph_traits<graph_type>::degree_size_type degree_size_type;
446
447 typedef typename graph_traits<graph_type>::vertex_iterator vertex_iterator;
448 typedef typename graph_traits<graph_type>::vertices_size_type vertices_size_type;
449 typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
450 typedef typename graph_traits<graph_type>::edges_size_type edges_size_type;
451
452 typedef typename graph_type::vertex_property_type vertex_property_type;
453 typedef typename graph_type::edge_property_type edge_property_type;
454 typedef typename graph_type::graph_property_type graph_property_type;
455 typedef typename graph_type::vertex_bundled vertex_bundled;
456 typedef typename graph_type::edge_bundled edge_bundled;
457
458 typedef typename Base::label_type label_type;
459 typedef typename Base::map_type map_type;
460
461 labeled_graph(graph_type* g)
462 : _graph(g)
463 { }
464
465 /** @name Graph Access */
466 //@{
467 graph_type& graph() { return *_graph; }
468 graph_type const& graph() const { return *_graph; }
469 //@}
470
471 /**
472 * Create a new label for the given vertex, returning false, if the label
473 * cannot be created.
474 */
475 bool label_vertex(vertex_descriptor v, Label const& l)
476 { return graph_detail::put_vertex_label(_map, *_graph, l, v); }
477
478 /** @name Add Vertex */
479 //@{
480 vertex_descriptor add_vertex(Label const& l) {
481 return graph_detail::insert_labeled_vertex(
482 _map, *_graph, l, vertex_property_type()
483 ).first;
484 }
485
486 vertex_descriptor add_vertex(Label const& l, vertex_property_type const& p)
487 { return graph_detail::insert_labeled_vertex(_map, *_graph, l, p).first; }
488
489 std::pair<vertex_descriptor, bool> insert_vertex(Label const& l) {
490 return graph_detail::insert_labeled_vertex(
491 _map, *_graph, l, vertex_property_type()
492 );
493 }
494 //@}
495
496 /** Try to insert a vertex with the given label. */
497 std::pair<vertex_descriptor, bool>
498 insert_vertex(Label const& l, vertex_property_type const& p)
499 { return graph_detail::insert_labeled_vertex(_map, *_graph, l, p); }
500
501 /** Remove the vertex with the given label. */
502 void remove_vertex(Label const& l)
503 { return boost::remove_vertex(vertex(l), *_graph); }
504
505 /** Return a descriptor for the given label. */
506 vertex_descriptor vertex(Label const& l) const
507 { return graph_detail::find_labeled_vertex(_map, *_graph, l); }
508
509#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
510 /** @name Bundled Properties */
511 //@{
512 // Lookup the requested vertex and return the bundle.
513 vertex_bundled& operator[](Label const& l)
514 { return (*_graph)[vertex(l)]; }
515
516 vertex_bundled const& operator[](Label const& l) const
517 { return (*_graph)[vertex(l)]; }
518
519 // Delegate edge lookup to the underlying graph.
520 edge_bundled& operator[](edge_descriptor e)
521 { return (*_graph)[e]; }
522
523 edge_bundled const& operator[](edge_descriptor e) const
524 { return (*_graph)[e]; }
525 //@}
526#endif
527
528 static vertex_descriptor null_vertex()
529 { return graph_traits<graph_type>::null_vertex(); }
530
531private:
532 graph_type* _graph;
533 map_type _map;
534};
535
536#define LABELED_GRAPH_PARAMS typename G, typename L, typename S
537#define LABELED_GRAPH labeled_graph<G,L,S>
538
539/** @name Labeled Graph */
540//@{
541template <LABELED_GRAPH_PARAMS>
542inline bool label_vertex(typename LABELED_GRAPH::vertex_descriptor v,
543 typename LABELED_GRAPH::label_type const l,
544 LABELED_GRAPH& g)
545{ return g.label_vertex(v, l); }
546
547template <LABELED_GRAPH_PARAMS>
548inline typename LABELED_GRAPH::vertex_descriptor
549vertex_by_label(typename LABELED_GRAPH::label_type const l,
550 LABELED_GRAPH& g)
551{ return g.vertex(l); }
552//@}
553
554/** @name Graph */
555//@{
556template <LABELED_GRAPH_PARAMS>
557inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool>
558edge(typename LABELED_GRAPH::vertex_descriptor const& u,
559 typename LABELED_GRAPH::vertex_descriptor const& v,
560 LABELED_GRAPH const& g)
561{ return edge(u, v, g.graph()); }
562
563// Labeled Extensions
564template <LABELED_GRAPH_PARAMS>
565inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool>
566edge_by_label(typename LABELED_GRAPH::label_type const& u,
567 typename LABELED_GRAPH::label_type const& v,
568 LABELED_GRAPH const& g)
569{ return edge(g.vertex(u), g.vertex(v), g); }
570//@}
571
572/** @name Incidence Graph */
573//@{
574template <LABELED_GRAPH_PARAMS>
575inline std::pair<
576 typename LABELED_GRAPH::out_edge_iterator,
577 typename LABELED_GRAPH::out_edge_iterator>
578out_edges(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g)
579{ return out_edges(v, g.graph()); }
580
581template <LABELED_GRAPH_PARAMS>
582inline typename LABELED_GRAPH::degree_size_type
583out_degree(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g)
584{ return out_degree(v, g.graph()); }
585
586template <LABELED_GRAPH_PARAMS>
587inline typename LABELED_GRAPH::vertex_descriptor
588source(typename LABELED_GRAPH::edge_descriptor e, LABELED_GRAPH const& g)
589{ return source(e, g.graph()); }
590
591template <LABELED_GRAPH_PARAMS>
592inline typename LABELED_GRAPH::vertex_descriptor
593target(typename LABELED_GRAPH::edge_descriptor e, LABELED_GRAPH const& g)
594{ return target(e, g.graph()); }
595//@}
596
597/** @name Bidirectional Graph */
598//@{
599template <LABELED_GRAPH_PARAMS>
600inline std::pair<
601 typename LABELED_GRAPH::in_edge_iterator,
602 typename LABELED_GRAPH::in_edge_iterator>
603in_edges(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g)
604{ return in_edges(v, g.graph()); }
605
606template <LABELED_GRAPH_PARAMS>
607inline typename LABELED_GRAPH::degree_size_type
608in_degree(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g)
609{ return in_degree(v, g.graph()); }
610
611template <LABELED_GRAPH_PARAMS>
612inline typename LABELED_GRAPH::degree_size_type
613degree(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g)
614{ return degree(v, g.graph()); }
615//@}
616
617/** @name Adjacency Graph */
618//@{
619template <LABELED_GRAPH_PARAMS>
620inline std::pair<
621 typename LABELED_GRAPH::adjacency_iterator,
622 typename LABELED_GRAPH::adjacency_iterator>
623adjacenct_vertices(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g)
624{ return adjacent_vertices(v, g.graph()); }
625//@}
626
627/** @name VertexListGraph */
628//@{
629template <LABELED_GRAPH_PARAMS>
630inline std::pair<
631 typename LABELED_GRAPH::vertex_iterator,
632 typename LABELED_GRAPH::vertex_iterator>
633vertices(LABELED_GRAPH const& g)
634{ return vertices(g.graph()); }
635
636template <LABELED_GRAPH_PARAMS>
637inline typename LABELED_GRAPH::vertices_size_type
638num_vertices(LABELED_GRAPH const& g)
639{ return num_vertices(g.graph()); }
640//@}
641
642/** @name EdgeListGraph */
643//@{
644template <LABELED_GRAPH_PARAMS>
645inline std::pair<
646 typename LABELED_GRAPH::edge_iterator,
647 typename LABELED_GRAPH::edge_iterator>
648edges(LABELED_GRAPH const& g)
649{ return edges(g.graph()); }
650
651template <LABELED_GRAPH_PARAMS>
652inline typename LABELED_GRAPH::edges_size_type
653num_edges(LABELED_GRAPH const& g)
654{ return num_edges(g.graph()); }
655//@}
656
657/** @internal @name Property Lookup */
658//@{
659namespace graph_detail {
660 struct labeled_graph_vertex_property_selector {
661 template <class LabeledGraph, class Property, class Tag>
662 struct bind_ {
663 typedef typename LabeledGraph::graph_type Graph;
664 typedef property_map<Graph, Tag> PropertyMap;
665 typedef typename PropertyMap::type type;
666 typedef typename PropertyMap::const_type const_type;
667 };
668 };
669
670 struct labeled_graph_edge_property_selector {
671 template <class LabeledGraph, class Property, class Tag>
672 struct bind_ {
673 typedef typename LabeledGraph::graph_type Graph;
674 typedef property_map<Graph, Tag> PropertyMap;
675 typedef typename PropertyMap::type type;
676 typedef typename PropertyMap::const_type const_type;
677 };
678 };
679}
680
681template <>
682struct vertex_property_selector<labeled_graph_class_tag> {
683 typedef graph_detail::labeled_graph_vertex_property_selector type;
684};
685
686template <>
687struct edge_property_selector<labeled_graph_class_tag> {
688 typedef graph_detail::labeled_graph_edge_property_selector type;
689};
690//@}
691
692/** @name Property Graph */
693//@{
694template <LABELED_GRAPH_PARAMS, typename Prop>
695inline typename property_map<LABELED_GRAPH, Prop>::type
696get(Prop p, LABELED_GRAPH& g)
697{ return get(p, g.graph()); }
698
699template <LABELED_GRAPH_PARAMS, typename Prop>
700inline typename property_map<LABELED_GRAPH, Prop>::const_type
701get(Prop p, LABELED_GRAPH const& g)
702{ return get(p, g.graph()); }
703
704template <LABELED_GRAPH_PARAMS, typename Prop, typename Key>
705inline typename property_traits<
706 typename property_map<typename LABELED_GRAPH::graph_type, Prop>::const_type
707>::value_type
708get(Prop p, LABELED_GRAPH const& g, const Key& k)
709{ return get(p, g.graph(), k); }
710
711template <LABELED_GRAPH_PARAMS, typename Prop, typename Key, typename Value>
712inline void
713put(Prop p, LABELED_GRAPH& g, Key const& k, Value const& v)
714{ put(p, g.graph(), k, v); }
715//@}
716
717/** @name Mutable Graph */
718//@{
719template <LABELED_GRAPH_PARAMS>
720inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool>
721add_edge(typename LABELED_GRAPH::vertex_descriptor const& u,
722 typename LABELED_GRAPH::vertex_descriptor const& v,
723 LABELED_GRAPH& g)
724{ return add_edge(u, v, g.graph()); }
725
726template <LABELED_GRAPH_PARAMS>
727inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool>
728add_edge(typename LABELED_GRAPH::vertex_descriptor const& u,
729 typename LABELED_GRAPH::vertex_descriptor const& v,
730 typename LABELED_GRAPH::edge_property_type const& p,
731 LABELED_GRAPH& g)
732{ return add_edge(u, v, p, g.graph()); }
733
734template <LABELED_GRAPH_PARAMS>
735inline void
736clear_vertex(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH& g)
737{ return clear_vertex(v, g.graph()); }
738
739template <LABELED_GRAPH_PARAMS>
740inline void
741remove_edge(typename LABELED_GRAPH::edge_descriptor e, LABELED_GRAPH& g)
742{ return remove_edge(e, g.graph()); }
743
744template <LABELED_GRAPH_PARAMS>
745inline void
746remove_edge(typename LABELED_GRAPH::vertex_descriptor u,
747 typename LABELED_GRAPH::vertex_descriptor v,
748 LABELED_GRAPH& g)
749{ return remove_edge(u, v, g.graph()); }
750
751// Labeled extensions
752template <LABELED_GRAPH_PARAMS>
753inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool>
754add_edge_by_label(typename LABELED_GRAPH::label_type const& u,
755 typename LABELED_GRAPH::label_type const& v,
756 LABELED_GRAPH& g)
757{ return add_edge(g.vertex(u), g.vertex(v), g); }
758
759template <LABELED_GRAPH_PARAMS>
760inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool>
761add_edge_by_label(typename LABELED_GRAPH::label_type const& u,
762 typename LABELED_GRAPH::label_type const& v,
763 typename LABELED_GRAPH::edge_property_type const& p,
764 LABELED_GRAPH& g)
765{ return add_edge(g.vertex(u), g.vertex(v), p, g); }
766
767template <LABELED_GRAPH_PARAMS>
768inline void
769clear_vertex_by_label(typename LABELED_GRAPH::label_type const& l, LABELED_GRAPH& g)
770{ clear_vertex(g.vertex(l), g.graph()); }
771
772template <LABELED_GRAPH_PARAMS>
773inline void
774remove_edge_by_label(typename LABELED_GRAPH::label_type const& u,
775 typename LABELED_GRAPH::label_type const& v,
776 LABELED_GRAPH& g)
777{ remove_edge(g.vertex(u), g.vertex(v), g.graph()); }
778//@}
779
780/** @name Labeled Mutable Graph
781 * The labeled mutable graph hides the add_ and remove_ vertex functions from
782 * the mutable graph concept. Note that the remove_vertex is hidden because
783 * removing the vertex without its key could leave a dangling reference in
784 * the map.
785 */
786//@{
787template <LABELED_GRAPH_PARAMS>
788inline typename LABELED_GRAPH::vertex_descriptor
789add_vertex(typename LABELED_GRAPH::label_type const& l,
790 LABELED_GRAPH& g)
791{ return g.add_vertex(l); }
792
793// MutableLabeledPropertyGraph::add_vertex(l, vp, g)
794template <LABELED_GRAPH_PARAMS>
795inline typename LABELED_GRAPH::vertex_descriptor
796add_vertex(typename LABELED_GRAPH::label_type const& l,
797 typename LABELED_GRAPH::vertex_property_type const& p,
798 LABELED_GRAPH& g)
799{ return g.add_vertex(l, p); }
800
801template <LABELED_GRAPH_PARAMS>
802inline void
803remove_vertex(typename LABELED_GRAPH::label_type const& l, LABELED_GRAPH& g)
804{ g.remove_vertex(l); }
805//@}
806
807#undef LABELED_GRAPH_PARAMS
808#undef LABELED_GRAPH
809
810} // namespace boost
811
812// Pull the labeled graph traits
813#include <boost/graph/detail/labeled_graph_traits.hpp>
814
815#endif // BOOST_GRAPH_LABELED_GRAPH_HPP
816

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