]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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(p, 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 | : _graph(gp) | |
330 | { while(n-- > 0) add_vertex(*l++, *p++); } | |
331 | ||
332 | labeled_graph& operator=(labeled_graph const& x) { | |
333 | _graph = x._graph; | |
334 | _map = x._map; | |
335 | return *this; | |
336 | } | |
337 | ||
338 | /** @name Graph Accessors */ | |
339 | //@{ | |
340 | graph_type& graph() { return _graph; } | |
341 | graph_type const& graph() const { return _graph; } | |
342 | //@} | |
343 | ||
344 | /** | |
345 | * Create a new label for the given vertex, returning false, if the label | |
346 | * cannot be created. | |
347 | */ | |
348 | bool label_vertex(vertex_descriptor v, Label const& l) | |
349 | { return graph_detail::put_vertex_label(_map, _graph, l, v); } | |
350 | ||
351 | /** @name Add Vertex | |
352 | * Add a vertex to the graph, returning the descriptor. If the vertices | |
353 | * are uniquely labeled and the label already exists within the graph, | |
354 | * then no vertex is added, and the returned descriptor refers to the | |
355 | * existing vertex. A vertex property can be given as a parameter, if | |
356 | * needed. | |
357 | */ | |
358 | //@{ | |
359 | vertex_descriptor add_vertex(Label const& l) { | |
360 | return graph_detail::insert_labeled_vertex( | |
361 | _map, _graph, l, vertex_property_type() | |
362 | ).first; | |
363 | } | |
364 | ||
365 | vertex_descriptor add_vertex(Label const& l, vertex_property_type const& p) | |
366 | { return graph_detail::insert_labeled_vertex(_map, _graph, l, p).first; } | |
367 | //@} | |
368 | ||
369 | /** @name Insert Vertex | |
370 | * Insert a vertex into the graph, returning a pair containing the | |
371 | * descriptor of a vertex and a boolean value that describes whether or not | |
372 | * a new vertex was inserted. If vertices are not uniquely labeled, then | |
373 | * insertion will always succeed. | |
374 | */ | |
375 | //@{ | |
376 | std::pair<vertex_descriptor, bool> insert_vertex(Label const& l) { | |
377 | return graph_detail::insert_labeled_vertex( | |
378 | _map, _graph, l, vertex_property_type() | |
379 | ); | |
380 | } | |
381 | ||
382 | std::pair<vertex_descriptor, bool> | |
383 | insert_vertex(Label const& l, vertex_property_type const& p) | |
384 | { return graph_detail::insert_labeled_vertex(_map, _graph, l, p); } | |
385 | //@} | |
386 | ||
387 | /** Remove the vertex with the given label. */ | |
388 | void remove_vertex(Label const& l) | |
389 | { return boost::remove_vertex(vertex(l), _graph); } | |
390 | ||
391 | /** Return a descriptor for the given label. */ | |
392 | vertex_descriptor vertex(Label const& l) const | |
393 | { return graph_detail::find_labeled_vertex(_map, _graph, l); } | |
394 | ||
395 | #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES | |
396 | /** @name Bundled Properties */ | |
397 | //@{ | |
398 | // Lookup the requested vertex and return the bundle. | |
399 | vertex_bundled& operator[](Label const& l) | |
400 | { return _graph[vertex(l)]; } | |
401 | ||
402 | vertex_bundled const& operator[](Label const& l) const | |
403 | { return _graph[vertex(l)]; } | |
404 | ||
405 | // Delegate edge lookup to the underlying graph. | |
406 | edge_bundled& operator[](edge_descriptor e) | |
407 | { return _graph[e]; } | |
408 | ||
409 | edge_bundled const& operator[](edge_descriptor e) const | |
410 | { return _graph[e]; } | |
411 | //@} | |
412 | #endif | |
413 | ||
414 | /** Return a null descriptor */ | |
415 | static vertex_descriptor null_vertex() | |
416 | { return graph_traits<graph_type>::null_vertex(); } | |
417 | ||
418 | private: | |
419 | graph_type _graph; | |
420 | map_type _map; | |
421 | }; | |
422 | ||
423 | /** | |
424 | * The partial specialization over graph pointers allows the construction | |
425 | * of temporary labeled graph objects. In this case, the labels are destructed | |
426 | * when the wrapper goes out of scope. | |
427 | */ | |
428 | template <typename Graph, typename Label, typename Selector> | |
429 | class labeled_graph<Graph*, Label, Selector> | |
430 | : protected labeled_graph_types<Graph, Label, Selector> | |
431 | { | |
432 | typedef labeled_graph_types<Graph, Label, Selector> Base; | |
433 | public: | |
434 | typedef labeled_graph_class_tag graph_tag; | |
435 | ||
436 | typedef typename Base::graph_type graph_type; | |
437 | typedef typename graph_traits<graph_type>::vertex_descriptor vertex_descriptor; | |
438 | typedef typename graph_traits<graph_type>::edge_descriptor edge_descriptor; | |
439 | typedef typename graph_traits<graph_type>::directed_category directed_category; | |
440 | typedef typename graph_traits<graph_type>::edge_parallel_category edge_parallel_category; | |
441 | typedef typename graph_traits<graph_type>::traversal_category traversal_category; | |
442 | ||
443 | typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator; | |
444 | typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator; | |
445 | typedef typename graph_traits<graph_type>::adjacency_iterator adjacency_iterator; | |
446 | typedef typename graph_traits<graph_type>::degree_size_type degree_size_type; | |
447 | ||
448 | typedef typename graph_traits<graph_type>::vertex_iterator vertex_iterator; | |
449 | typedef typename graph_traits<graph_type>::vertices_size_type vertices_size_type; | |
450 | typedef typename graph_traits<graph_type>::edge_iterator edge_iterator; | |
451 | typedef typename graph_traits<graph_type>::edges_size_type edges_size_type; | |
452 | ||
453 | typedef typename graph_type::vertex_property_type vertex_property_type; | |
454 | typedef typename graph_type::edge_property_type edge_property_type; | |
455 | typedef typename graph_type::graph_property_type graph_property_type; | |
456 | typedef typename graph_type::vertex_bundled vertex_bundled; | |
457 | typedef typename graph_type::edge_bundled edge_bundled; | |
458 | ||
459 | typedef typename Base::label_type label_type; | |
460 | typedef typename Base::map_type map_type; | |
461 | ||
462 | labeled_graph(graph_type* g) | |
463 | : _graph(g) | |
464 | { } | |
465 | ||
466 | /** @name Graph Access */ | |
467 | //@{ | |
468 | graph_type& graph() { return *_graph; } | |
469 | graph_type const& graph() const { return *_graph; } | |
470 | //@} | |
471 | ||
472 | /** | |
473 | * Create a new label for the given vertex, returning false, if the label | |
474 | * cannot be created. | |
475 | */ | |
476 | bool label_vertex(vertex_descriptor v, Label const& l) | |
477 | { return graph_detail::put_vertex_label(_map, *_graph, l, v); } | |
478 | ||
479 | /** @name Add Vertex */ | |
480 | //@{ | |
481 | vertex_descriptor add_vertex(Label const& l) { | |
482 | return graph_detail::insert_labeled_vertex( | |
483 | _map, *_graph, l, vertex_property_type() | |
484 | ).first; | |
485 | } | |
486 | ||
487 | vertex_descriptor add_vertex(Label const& l, vertex_property_type const& p) | |
488 | { return graph_detail::insert_labeled_vertex(_map, *_graph, l, p).first; } | |
489 | ||
490 | std::pair<vertex_descriptor, bool> insert_vertex(Label const& l) { | |
491 | return graph_detail::insert_labeled_vertex( | |
492 | _map, *_graph, l, vertex_property_type() | |
493 | ); | |
494 | } | |
495 | //@} | |
496 | ||
497 | /** Try to insert a vertex with the given label. */ | |
498 | std::pair<vertex_descriptor, bool> | |
499 | insert_vertex(Label const& l, vertex_property_type const& p) | |
500 | { return graph_detail::insert_labeled_vertex(_map, *_graph, l, p); } | |
501 | ||
502 | /** Remove the vertex with the given label. */ | |
503 | void remove_vertex(Label const& l) | |
504 | { return boost::remove_vertex(vertex(l), *_graph); } | |
505 | ||
506 | /** Return a descriptor for the given label. */ | |
507 | vertex_descriptor vertex(Label const& l) const | |
508 | { return graph_detail::find_labeled_vertex(_map, *_graph, l); } | |
509 | ||
510 | #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES | |
511 | /** @name Bundled Properties */ | |
512 | //@{ | |
513 | // Lookup the requested vertex and return the bundle. | |
514 | vertex_bundled& operator[](Label const& l) | |
515 | { return (*_graph)[vertex(l)]; } | |
516 | ||
517 | vertex_bundled const& operator[](Label const& l) const | |
518 | { return (*_graph)[vertex(l)]; } | |
519 | ||
520 | // Delegate edge lookup to the underlying graph. | |
521 | edge_bundled& operator[](edge_descriptor e) | |
522 | { return (*_graph)[e]; } | |
523 | ||
524 | edge_bundled const& operator[](edge_descriptor e) const | |
525 | { return (*_graph)[e]; } | |
526 | //@} | |
527 | #endif | |
528 | ||
529 | static vertex_descriptor null_vertex() | |
530 | { return graph_traits<graph_type>::null_vertex(); } | |
531 | ||
532 | private: | |
533 | graph_type* _graph; | |
534 | map_type _map; | |
535 | }; | |
536 | ||
537 | #define LABELED_GRAPH_PARAMS typename G, typename L, typename S | |
538 | #define LABELED_GRAPH labeled_graph<G,L,S> | |
539 | ||
540 | /** @name Labeled Graph */ | |
541 | //@{ | |
542 | template <LABELED_GRAPH_PARAMS> | |
543 | inline bool label_vertex(typename LABELED_GRAPH::vertex_descriptor v, | |
544 | typename LABELED_GRAPH::label_type const l, | |
545 | LABELED_GRAPH& g) | |
546 | { return g.label_vertex(v, l); } | |
547 | ||
548 | template <LABELED_GRAPH_PARAMS> | |
549 | inline typename LABELED_GRAPH::vertex_descriptor | |
550 | vertex_by_label(typename LABELED_GRAPH::label_type const l, | |
551 | LABELED_GRAPH& g) | |
552 | { return g.vertex(l); } | |
553 | //@} | |
554 | ||
555 | /** @name Graph */ | |
556 | //@{ | |
557 | template <LABELED_GRAPH_PARAMS> | |
558 | inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool> | |
559 | edge(typename LABELED_GRAPH::vertex_descriptor const& u, | |
560 | typename LABELED_GRAPH::vertex_descriptor const& v, | |
561 | LABELED_GRAPH const& g) | |
562 | { return edge(u, v, g.graph()); } | |
563 | ||
564 | // Labeled Extensions | |
565 | template <LABELED_GRAPH_PARAMS> | |
566 | inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool> | |
567 | edge_by_label(typename LABELED_GRAPH::label_type const& u, | |
568 | typename LABELED_GRAPH::label_type const& v, | |
569 | LABELED_GRAPH const& g) | |
570 | { return edge(g.vertex(u), g.vertex(v), g); } | |
571 | //@} | |
572 | ||
573 | /** @name Incidence Graph */ | |
574 | //@{ | |
575 | template <LABELED_GRAPH_PARAMS> | |
576 | inline std::pair< | |
577 | typename LABELED_GRAPH::out_edge_iterator, | |
578 | typename LABELED_GRAPH::out_edge_iterator> | |
579 | out_edges(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g) | |
580 | { return out_edges(v, g.graph()); } | |
581 | ||
582 | template <LABELED_GRAPH_PARAMS> | |
583 | inline typename LABELED_GRAPH::degree_size_type | |
584 | out_degree(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g) | |
585 | { return out_degree(v, g.graph()); } | |
586 | ||
587 | template <LABELED_GRAPH_PARAMS> | |
588 | inline typename LABELED_GRAPH::vertex_descriptor | |
589 | source(typename LABELED_GRAPH::edge_descriptor e, LABELED_GRAPH const& g) | |
590 | { return source(e, g.graph()); } | |
591 | ||
592 | template <LABELED_GRAPH_PARAMS> | |
593 | inline typename LABELED_GRAPH::vertex_descriptor | |
594 | target(typename LABELED_GRAPH::edge_descriptor e, LABELED_GRAPH const& g) | |
595 | { return target(e, g.graph()); } | |
596 | //@} | |
597 | ||
598 | /** @name Bidirectional Graph */ | |
599 | //@{ | |
600 | template <LABELED_GRAPH_PARAMS> | |
601 | inline std::pair< | |
602 | typename LABELED_GRAPH::in_edge_iterator, | |
603 | typename LABELED_GRAPH::in_edge_iterator> | |
604 | in_edges(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g) | |
605 | { return in_edges(v, g.graph()); } | |
606 | ||
607 | template <LABELED_GRAPH_PARAMS> | |
608 | inline typename LABELED_GRAPH::degree_size_type | |
609 | in_degree(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g) | |
610 | { return in_degree(v, g.graph()); } | |
611 | ||
612 | template <LABELED_GRAPH_PARAMS> | |
613 | inline typename LABELED_GRAPH::degree_size_type | |
614 | degree(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g) | |
615 | { return degree(v, g.graph()); } | |
616 | //@} | |
617 | ||
618 | /** @name Adjacency Graph */ | |
619 | //@{ | |
620 | template <LABELED_GRAPH_PARAMS> | |
621 | inline std::pair< | |
622 | typename LABELED_GRAPH::adjacency_iterator, | |
623 | typename LABELED_GRAPH::adjacency_iterator> | |
624 | adjacenct_vertices(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g) | |
625 | { return adjacent_vertices(v, g.graph()); } | |
626 | //@} | |
627 | ||
628 | /** @name VertexListGraph */ | |
629 | //@{ | |
630 | template <LABELED_GRAPH_PARAMS> | |
631 | inline std::pair< | |
632 | typename LABELED_GRAPH::vertex_iterator, | |
633 | typename LABELED_GRAPH::vertex_iterator> | |
634 | vertices(LABELED_GRAPH const& g) | |
635 | { return vertices(g.graph()); } | |
636 | ||
637 | template <LABELED_GRAPH_PARAMS> | |
638 | inline typename LABELED_GRAPH::vertices_size_type | |
639 | num_vertices(LABELED_GRAPH const& g) | |
640 | { return num_vertices(g.graph()); } | |
641 | //@} | |
642 | ||
643 | /** @name EdgeListGraph */ | |
644 | //@{ | |
645 | template <LABELED_GRAPH_PARAMS> | |
646 | inline std::pair< | |
647 | typename LABELED_GRAPH::edge_iterator, | |
648 | typename LABELED_GRAPH::edge_iterator> | |
649 | edges(LABELED_GRAPH const& g) | |
650 | { return edges(g.graph()); } | |
651 | ||
652 | template <LABELED_GRAPH_PARAMS> | |
653 | inline typename LABELED_GRAPH::edges_size_type | |
654 | num_edges(LABELED_GRAPH const& g) | |
655 | { return num_edges(g.graph()); } | |
656 | //@} | |
657 | ||
658 | /** @internal @name Property Lookup */ | |
659 | //@{ | |
660 | namespace graph_detail { | |
661 | struct labeled_graph_vertex_property_selector { | |
662 | template <class LabeledGraph, class Property, class Tag> | |
663 | struct bind_ { | |
664 | typedef typename LabeledGraph::graph_type Graph; | |
665 | typedef property_map<Graph, Tag> PropertyMap; | |
666 | typedef typename PropertyMap::type type; | |
667 | typedef typename PropertyMap::const_type const_type; | |
668 | }; | |
669 | }; | |
670 | ||
671 | struct labeled_graph_edge_property_selector { | |
672 | template <class LabeledGraph, class Property, class Tag> | |
673 | struct bind_ { | |
674 | typedef typename LabeledGraph::graph_type Graph; | |
675 | typedef property_map<Graph, Tag> PropertyMap; | |
676 | typedef typename PropertyMap::type type; | |
677 | typedef typename PropertyMap::const_type const_type; | |
678 | }; | |
679 | }; | |
680 | } | |
681 | ||
682 | template <> | |
683 | struct vertex_property_selector<labeled_graph_class_tag> { | |
684 | typedef graph_detail::labeled_graph_vertex_property_selector type; | |
685 | }; | |
686 | ||
687 | template <> | |
688 | struct edge_property_selector<labeled_graph_class_tag> { | |
689 | typedef graph_detail::labeled_graph_edge_property_selector type; | |
690 | }; | |
691 | //@} | |
692 | ||
693 | /** @name Property Graph */ | |
694 | //@{ | |
695 | template <LABELED_GRAPH_PARAMS, typename Prop> | |
696 | inline typename property_map<LABELED_GRAPH, Prop>::type | |
697 | get(Prop p, LABELED_GRAPH& g) | |
698 | { return get(p, g.graph()); } | |
699 | ||
700 | template <LABELED_GRAPH_PARAMS, typename Prop> | |
701 | inline typename property_map<LABELED_GRAPH, Prop>::const_type | |
702 | get(Prop p, LABELED_GRAPH const& g) | |
703 | { return get(p, g.graph()); } | |
704 | ||
705 | template <LABELED_GRAPH_PARAMS, typename Prop, typename Key> | |
706 | inline typename property_traits< | |
707 | typename property_map<typename LABELED_GRAPH::graph_type, Prop>::const_type | |
708 | >::value_type | |
709 | get(Prop p, LABELED_GRAPH const& g, const Key& k) | |
710 | { return get(p, g.graph(), k); } | |
711 | ||
712 | template <LABELED_GRAPH_PARAMS, typename Prop, typename Key, typename Value> | |
713 | inline void | |
714 | put(Prop p, LABELED_GRAPH& g, Key const& k, Value const& v) | |
715 | { put(p, g.graph(), k, v); } | |
716 | //@} | |
717 | ||
718 | /** @name Mutable Graph */ | |
719 | //@{ | |
720 | template <LABELED_GRAPH_PARAMS> | |
721 | inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool> | |
722 | add_edge(typename LABELED_GRAPH::vertex_descriptor const& u, | |
723 | typename LABELED_GRAPH::vertex_descriptor const& v, | |
724 | LABELED_GRAPH& g) | |
725 | { return add_edge(u, v, g.graph()); } | |
726 | ||
727 | template <LABELED_GRAPH_PARAMS> | |
728 | inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool> | |
729 | add_edge(typename LABELED_GRAPH::vertex_descriptor const& u, | |
730 | typename LABELED_GRAPH::vertex_descriptor const& v, | |
731 | typename LABELED_GRAPH::edge_property_type const& p, | |
732 | LABELED_GRAPH& g) | |
733 | { return add_edge(u, v, p, g.graph()); } | |
734 | ||
735 | template <LABELED_GRAPH_PARAMS> | |
736 | inline void | |
737 | clear_vertex(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH& g) | |
738 | { return clear_vertex(v, g.graph()); } | |
739 | ||
740 | template <LABELED_GRAPH_PARAMS> | |
741 | inline void | |
742 | remove_edge(typename LABELED_GRAPH::edge_descriptor e, LABELED_GRAPH& g) | |
743 | { return remove_edge(e, g.graph()); } | |
744 | ||
745 | template <LABELED_GRAPH_PARAMS> | |
746 | inline void | |
747 | remove_edge(typename LABELED_GRAPH::vertex_descriptor u, | |
748 | typename LABELED_GRAPH::vertex_descriptor v, | |
749 | LABELED_GRAPH& g) | |
750 | { return remove_edge(u, v, g.graph()); } | |
751 | ||
752 | // Labeled extensions | |
753 | template <LABELED_GRAPH_PARAMS> | |
754 | inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool> | |
755 | add_edge_by_label(typename LABELED_GRAPH::label_type const& u, | |
756 | typename LABELED_GRAPH::label_type const& v, | |
757 | LABELED_GRAPH& g) | |
758 | { return add_edge(g.vertex(u), g.vertex(v), g); } | |
759 | ||
760 | template <LABELED_GRAPH_PARAMS> | |
761 | inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool> | |
762 | add_edge_by_label(typename LABELED_GRAPH::label_type const& u, | |
763 | typename LABELED_GRAPH::label_type const& v, | |
764 | typename LABELED_GRAPH::edge_property_type const& p, | |
765 | LABELED_GRAPH& g) | |
766 | { return add_edge(g.vertex(u), g.vertex(v), p, g); } | |
767 | ||
768 | template <LABELED_GRAPH_PARAMS> | |
769 | inline void | |
770 | clear_vertex_by_label(typename LABELED_GRAPH::label_type const& l, LABELED_GRAPH& g) | |
771 | { clear_vertex(g.vertex(l), g.graph()); } | |
772 | ||
773 | template <LABELED_GRAPH_PARAMS> | |
774 | inline void | |
775 | remove_edge_by_label(typename LABELED_GRAPH::label_type const& u, | |
776 | typename LABELED_GRAPH::label_type const& v, | |
777 | LABELED_GRAPH& g) | |
778 | { remove_edge(g.vertex(u), g.vertex(v), g.graph()); } | |
779 | //@} | |
780 | ||
781 | /** @name Labeled Mutable Graph | |
782 | * The labeled mutable graph hides the add_ and remove_ vertex functions from | |
783 | * the mutable graph concept. Note that the remove_vertex is hidden because | |
784 | * removing the vertex without its key could leave a dangling reference in | |
785 | * the map. | |
786 | */ | |
787 | //@{ | |
788 | template <LABELED_GRAPH_PARAMS> | |
789 | inline typename LABELED_GRAPH::vertex_descriptor | |
790 | add_vertex(typename LABELED_GRAPH::label_type const& l, | |
791 | LABELED_GRAPH& g) | |
792 | { return g.add_vertex(l); } | |
793 | ||
794 | // MutableLabeledPropertyGraph::add_vertex(l, vp, g) | |
795 | template <LABELED_GRAPH_PARAMS> | |
796 | inline typename LABELED_GRAPH::vertex_descriptor | |
797 | add_vertex(typename LABELED_GRAPH::label_type const& l, | |
798 | typename LABELED_GRAPH::vertex_property_type const& p, | |
799 | LABELED_GRAPH& g) | |
800 | { return g.add_vertex(l, p); } | |
801 | ||
802 | template <LABELED_GRAPH_PARAMS> | |
803 | inline void | |
804 | remove_vertex(typename LABELED_GRAPH::label_type const& l, LABELED_GRAPH& g) | |
805 | { g.remove_vertex(l); } | |
806 | //@} | |
807 | ||
808 | #undef LABELED_GRAPH_PARAMS | |
809 | #undef LABELED_GRAPH | |
810 | ||
811 | } // namespace boost | |
812 | ||
813 | // Pull the labeled graph traits | |
814 | #include <boost/graph/detail/labeled_graph_traits.hpp> | |
815 | ||
816 | #endif // BOOST_GRAPH_LABELED_GRAPH_HPP |