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 | |
26 | namespace boost { |
27 | |
28 | // A type selector that denotes the use of some default value. |
29 | struct defaultS { }; |
30 | |
31 | /** @internal */ |
32 | namespace 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 | |
228 | struct 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 | */ |
234 | template <typename Graph, typename Label, typename Selector> |
235 | struct 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 | */ |
257 | template <typename Graph, typename Label, typename Selector = defaultS> |
258 | class labeled_graph |
259 | : protected labeled_graph_types<Graph, Label, Selector> |
260 | { |
261 | typedef labeled_graph_types<Graph, Label, Selector> Base; |
262 | public: |
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 | |
294 | public: |
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 | |
417 | private: |
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 | */ |
427 | template <typename Graph, typename Label, typename Selector> |
428 | class labeled_graph<Graph*, Label, Selector> |
429 | : protected labeled_graph_types<Graph, Label, Selector> |
430 | { |
431 | typedef labeled_graph_types<Graph, Label, Selector> Base; |
432 | public: |
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 | |
531 | private: |
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 | //@{ |
541 | template <LABELED_GRAPH_PARAMS> |
542 | inline 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 | |
547 | template <LABELED_GRAPH_PARAMS> |
548 | inline typename LABELED_GRAPH::vertex_descriptor |
549 | vertex_by_label(typename LABELED_GRAPH::label_type const l, |
550 | LABELED_GRAPH& g) |
551 | { return g.vertex(l); } |
552 | //@} |
553 | |
554 | /** @name Graph */ |
555 | //@{ |
556 | template <LABELED_GRAPH_PARAMS> |
557 | inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool> |
558 | edge(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 |
564 | template <LABELED_GRAPH_PARAMS> |
565 | inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool> |
566 | edge_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 | //@{ |
574 | template <LABELED_GRAPH_PARAMS> |
575 | inline std::pair< |
576 | typename LABELED_GRAPH::out_edge_iterator, |
577 | typename LABELED_GRAPH::out_edge_iterator> |
578 | out_edges(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g) |
579 | { return out_edges(v, g.graph()); } |
580 | |
581 | template <LABELED_GRAPH_PARAMS> |
582 | inline typename LABELED_GRAPH::degree_size_type |
583 | out_degree(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g) |
584 | { return out_degree(v, g.graph()); } |
585 | |
586 | template <LABELED_GRAPH_PARAMS> |
587 | inline typename LABELED_GRAPH::vertex_descriptor |
588 | source(typename LABELED_GRAPH::edge_descriptor e, LABELED_GRAPH const& g) |
589 | { return source(e, g.graph()); } |
590 | |
591 | template <LABELED_GRAPH_PARAMS> |
592 | inline typename LABELED_GRAPH::vertex_descriptor |
593 | target(typename LABELED_GRAPH::edge_descriptor e, LABELED_GRAPH const& g) |
594 | { return target(e, g.graph()); } |
595 | //@} |
596 | |
597 | /** @name Bidirectional Graph */ |
598 | //@{ |
599 | template <LABELED_GRAPH_PARAMS> |
600 | inline std::pair< |
601 | typename LABELED_GRAPH::in_edge_iterator, |
602 | typename LABELED_GRAPH::in_edge_iterator> |
603 | in_edges(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g) |
604 | { return in_edges(v, g.graph()); } |
605 | |
606 | template <LABELED_GRAPH_PARAMS> |
607 | inline typename LABELED_GRAPH::degree_size_type |
608 | in_degree(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g) |
609 | { return in_degree(v, g.graph()); } |
610 | |
611 | template <LABELED_GRAPH_PARAMS> |
612 | inline typename LABELED_GRAPH::degree_size_type |
613 | degree(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g) |
614 | { return degree(v, g.graph()); } |
615 | //@} |
616 | |
617 | /** @name Adjacency Graph */ |
618 | //@{ |
619 | template <LABELED_GRAPH_PARAMS> |
620 | inline std::pair< |
621 | typename LABELED_GRAPH::adjacency_iterator, |
622 | typename LABELED_GRAPH::adjacency_iterator> |
623 | adjacenct_vertices(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g) |
624 | { return adjacent_vertices(v, g.graph()); } |
625 | //@} |
626 | |
627 | /** @name VertexListGraph */ |
628 | //@{ |
629 | template <LABELED_GRAPH_PARAMS> |
630 | inline std::pair< |
631 | typename LABELED_GRAPH::vertex_iterator, |
632 | typename LABELED_GRAPH::vertex_iterator> |
633 | vertices(LABELED_GRAPH const& g) |
634 | { return vertices(g.graph()); } |
635 | |
636 | template <LABELED_GRAPH_PARAMS> |
637 | inline typename LABELED_GRAPH::vertices_size_type |
638 | num_vertices(LABELED_GRAPH const& g) |
639 | { return num_vertices(g.graph()); } |
640 | //@} |
641 | |
642 | /** @name EdgeListGraph */ |
643 | //@{ |
644 | template <LABELED_GRAPH_PARAMS> |
645 | inline std::pair< |
646 | typename LABELED_GRAPH::edge_iterator, |
647 | typename LABELED_GRAPH::edge_iterator> |
648 | edges(LABELED_GRAPH const& g) |
649 | { return edges(g.graph()); } |
650 | |
651 | template <LABELED_GRAPH_PARAMS> |
652 | inline typename LABELED_GRAPH::edges_size_type |
653 | num_edges(LABELED_GRAPH const& g) |
654 | { return num_edges(g.graph()); } |
655 | //@} |
656 | |
657 | /** @internal @name Property Lookup */ |
658 | //@{ |
659 | namespace 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 | |
681 | template <> |
682 | struct vertex_property_selector<labeled_graph_class_tag> { |
683 | typedef graph_detail::labeled_graph_vertex_property_selector type; |
684 | }; |
685 | |
686 | template <> |
687 | struct 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 | //@{ |
694 | template <LABELED_GRAPH_PARAMS, typename Prop> |
695 | inline typename property_map<LABELED_GRAPH, Prop>::type |
696 | get(Prop p, LABELED_GRAPH& g) |
697 | { return get(p, g.graph()); } |
698 | |
699 | template <LABELED_GRAPH_PARAMS, typename Prop> |
700 | inline typename property_map<LABELED_GRAPH, Prop>::const_type |
701 | get(Prop p, LABELED_GRAPH const& g) |
702 | { return get(p, g.graph()); } |
703 | |
704 | template <LABELED_GRAPH_PARAMS, typename Prop, typename Key> |
705 | inline typename property_traits< |
706 | typename property_map<typename LABELED_GRAPH::graph_type, Prop>::const_type |
707 | >::value_type |
708 | get(Prop p, LABELED_GRAPH const& g, const Key& k) |
709 | { return get(p, g.graph(), k); } |
710 | |
711 | template <LABELED_GRAPH_PARAMS, typename Prop, typename Key, typename Value> |
712 | inline void |
713 | put(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 | //@{ |
719 | template <LABELED_GRAPH_PARAMS> |
720 | inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool> |
721 | add_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 | |
726 | template <LABELED_GRAPH_PARAMS> |
727 | inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool> |
728 | add_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 | |
734 | template <LABELED_GRAPH_PARAMS> |
735 | inline void |
736 | clear_vertex(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH& g) |
737 | { return clear_vertex(v, g.graph()); } |
738 | |
739 | template <LABELED_GRAPH_PARAMS> |
740 | inline void |
741 | remove_edge(typename LABELED_GRAPH::edge_descriptor e, LABELED_GRAPH& g) |
742 | { return remove_edge(e, g.graph()); } |
743 | |
744 | template <LABELED_GRAPH_PARAMS> |
745 | inline void |
746 | remove_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 |
752 | template <LABELED_GRAPH_PARAMS> |
753 | inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool> |
754 | add_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 | |
759 | template <LABELED_GRAPH_PARAMS> |
760 | inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool> |
761 | add_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 | |
767 | template <LABELED_GRAPH_PARAMS> |
768 | inline void |
769 | clear_vertex_by_label(typename LABELED_GRAPH::label_type const& l, LABELED_GRAPH& g) |
770 | { clear_vertex(g.vertex(l), g.graph()); } |
771 | |
772 | template <LABELED_GRAPH_PARAMS> |
773 | inline void |
774 | remove_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 | //@{ |
787 | template <LABELED_GRAPH_PARAMS> |
788 | inline typename LABELED_GRAPH::vertex_descriptor |
789 | add_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) |
794 | template <LABELED_GRAPH_PARAMS> |
795 | inline typename LABELED_GRAPH::vertex_descriptor |
796 | add_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 | |
801 | template <LABELED_GRAPH_PARAMS> |
802 | inline void |
803 | remove_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 | |