]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Copyright (C) 2007 Douglas Gregor |
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 | // Provides support for named vertices in graphs, allowing one to more | |
8 | // easily associate unique external names (URLs, city names, employee | |
9 | // ID numbers, etc.) with the vertices of a graph. | |
10 | #ifndef BOOST_GRAPH_NAMED_GRAPH_HPP | |
11 | #define BOOST_GRAPH_NAMED_GRAPH_HPP | |
12 | ||
13 | #include <boost/config.hpp> | |
14 | #include <boost/static_assert.hpp> | |
15 | #include <boost/functional/hash.hpp> | |
16 | #include <boost/graph/graph_traits.hpp> | |
17 | #include <boost/graph/properties.hpp> | |
18 | #include <boost/multi_index/hashed_index.hpp> | |
19 | #include <boost/multi_index/member.hpp> | |
20 | #include <boost/multi_index_container.hpp> | |
21 | #include <boost/optional.hpp> | |
22 | #include <boost/pending/property.hpp> // for boost::lookup_one_property | |
23 | #include <boost/pending/container_traits.hpp> | |
24 | #include <boost/throw_exception.hpp> | |
25 | #include <boost/tuple/tuple.hpp> // for boost::make_tuple | |
26 | #include <boost/type_traits/is_same.hpp> | |
27 | #include <boost/type_traits/is_base_of.hpp> | |
28 | #include <boost/type_traits/remove_cv.hpp> | |
29 | #include <boost/type_traits/remove_reference.hpp> | |
30 | #include <boost/utility/enable_if.hpp> | |
31 | #include <functional> // for std::equal_to | |
32 | #include <stdexcept> // for std::runtime_error | |
33 | #include <utility> // for std::pair | |
34 | ||
35 | namespace boost { namespace graph { | |
36 | ||
37 | /******************************************************************* | |
38 | * User-customized traits * | |
39 | *******************************************************************/ | |
40 | ||
41 | /** | |
42 | * @brief Trait used to extract the internal vertex name from a vertex | |
43 | * property. | |
44 | * | |
45 | * To enable the use of internal vertex names in a graph type, | |
46 | * specialize the @c internal_vertex_name trait for your graph | |
47 | * property (e.g., @c a City class, which stores information about the | |
48 | * vertices in a road map). | |
49 | */ | |
50 | template<typename VertexProperty> | |
51 | struct internal_vertex_name | |
52 | { | |
53 | /** | |
54 | * The @c type field provides a function object that extracts a key | |
55 | * from the @c VertexProperty. The function object type must have a | |
56 | * nested @c result_type that provides the type of the key. For | |
57 | * more information, see the @c KeyExtractor concept in the | |
58 | * Boost.MultiIndex documentation: @c type must either be @c void | |
59 | * (if @c VertexProperty does not have an internal vertex name) or | |
60 | * a model of @c KeyExtractor. | |
61 | */ | |
62 | typedef void type; | |
63 | }; | |
64 | ||
65 | /** | |
66 | * Extract the internal vertex name from a @c property structure by | |
67 | * looking at its base. | |
68 | */ | |
69 | template<typename Tag, typename T, typename Base> | |
70 | struct internal_vertex_name<property<Tag, T, Base> > | |
71 | : internal_vertex_name<Base> { }; | |
72 | ||
73 | /** | |
74 | * Construct an instance of @c VertexProperty directly from its | |
75 | * name. This function object should be used within the @c | |
76 | * internal_vertex_constructor trait. | |
77 | */ | |
78 | template<typename VertexProperty> | |
79 | struct vertex_from_name | |
80 | { | |
81 | private: | |
82 | typedef typename internal_vertex_name<VertexProperty>::type extract_name_type; | |
83 | ||
84 | typedef typename remove_cv< | |
85 | typename remove_reference< | |
86 | typename extract_name_type::result_type>::type>::type | |
87 | vertex_name_type; | |
88 | ||
89 | public: | |
90 | typedef vertex_name_type argument_type; | |
91 | typedef VertexProperty result_type; | |
92 | ||
93 | VertexProperty operator()(const vertex_name_type& name) | |
94 | { | |
95 | return VertexProperty(name); | |
96 | } | |
97 | }; | |
98 | ||
99 | /** | |
100 | * Throw an exception whenever one tries to construct a @c | |
101 | * VertexProperty instance from its name. | |
102 | */ | |
103 | template<typename VertexProperty> | |
104 | struct cannot_add_vertex | |
105 | { | |
106 | private: | |
107 | typedef typename internal_vertex_name<VertexProperty>::type extract_name_type; | |
108 | ||
109 | typedef typename remove_cv< | |
110 | typename remove_reference< | |
111 | typename extract_name_type::result_type>::type>::type | |
112 | vertex_name_type; | |
113 | ||
114 | public: | |
115 | typedef vertex_name_type argument_type; | |
116 | typedef VertexProperty result_type; | |
117 | ||
118 | VertexProperty operator()(const vertex_name_type&) | |
119 | { | |
120 | boost::throw_exception(std::runtime_error("add_vertex: " | |
121 | "unable to create a vertex from its name")); | |
122 | } | |
123 | }; | |
124 | ||
125 | /** | |
126 | * @brief Trait used to construct an instance of a @c VertexProperty, | |
127 | * which is a class type that stores the properties associated with a | |
128 | * vertex in a graph, from just the name of that vertex property. This | |
129 | * operation is used when an operation is required to map from a | |
130 | * vertex name to a vertex descriptor (e.g., to add an edge outgoing | |
131 | * from that vertex), but no vertex by the name exists. The function | |
132 | * object provided by this trait will be used to add new vertices | |
133 | * based only on their names. Since this cannot be done for arbitrary | |
134 | * types, the default behavior is to throw an exception when this | |
135 | * routine is called, which requires that all named vertices be added | |
136 | * before adding any edges by name. | |
137 | */ | |
138 | template<typename VertexProperty> | |
139 | struct internal_vertex_constructor | |
140 | { | |
141 | /** | |
142 | * The @c type field provides a function object that constructs a | |
143 | * new instance of @c VertexProperty from the name of the vertex (as | |
144 | * determined by @c internal_vertex_name). The function object shall | |
145 | * accept a vertex name and return a @c VertexProperty. Predefined | |
146 | * options include: | |
147 | * | |
148 | * @c vertex_from_name<VertexProperty>: construct an instance of | |
149 | * @c VertexProperty directly from the name. | |
150 | * | |
151 | * @c cannot_add_vertex<VertexProperty>: the default value, which | |
152 | * throws an @c std::runtime_error if one attempts to add a vertex | |
153 | * given just the name. | |
154 | */ | |
155 | typedef cannot_add_vertex<VertexProperty> type; | |
156 | }; | |
157 | ||
158 | /** | |
159 | * Extract the internal vertex constructor from a @c property structure by | |
160 | * looking at its base. | |
161 | */ | |
162 | template<typename Tag, typename T, typename Base> | |
163 | struct internal_vertex_constructor<property<Tag, T, Base> > | |
164 | : internal_vertex_constructor<Base> { }; | |
165 | ||
166 | /******************************************************************* | |
167 | * Named graph mixin * | |
168 | *******************************************************************/ | |
169 | ||
170 | /** | |
171 | * named_graph is a mixin that provides names for the vertices of a | |
172 | * graph, including a mapping from names to vertices. Graph types that | |
173 | * may or may not be have vertex names (depending on the properties | |
174 | * supplied by the user) should use maybe_named_graph. | |
175 | * | |
176 | * Template parameters: | |
177 | * | |
178 | * Graph: the graph type that derives from named_graph | |
179 | * | |
180 | * Vertex: the type of a vertex descriptor in Graph. Note: we cannot | |
181 | * use graph_traits here, because the Graph is not yet defined. | |
182 | * | |
183 | * VertexProperty: the type stored with each vertex in the Graph. | |
184 | */ | |
185 | template<typename Graph, typename Vertex, typename VertexProperty> | |
186 | class named_graph | |
187 | { | |
188 | public: | |
189 | /// The type of the function object that extracts names from vertex | |
190 | /// properties. | |
191 | typedef typename internal_vertex_name<VertexProperty>::type extract_name_type; | |
192 | /// The type of the "bundled" property, from which the name can be | |
193 | /// extracted. | |
194 | typedef typename lookup_one_property<VertexProperty, vertex_bundle_t>::type | |
195 | bundled_vertex_property_type; | |
196 | ||
197 | /// The type of the function object that generates vertex properties | |
198 | /// from names, for the implicit addition of vertices. | |
199 | typedef typename internal_vertex_constructor<VertexProperty>::type | |
200 | vertex_constructor_type; | |
201 | ||
202 | /// The type used to name vertices in the graph | |
203 | typedef typename remove_cv< | |
204 | typename remove_reference< | |
205 | typename extract_name_type::result_type>::type>::type | |
206 | vertex_name_type; | |
207 | ||
208 | /// The type of vertex descriptors in the graph | |
209 | typedef Vertex vertex_descriptor; | |
210 | ||
211 | private: | |
212 | /// Key extractor for use with the multi_index_container | |
213 | struct extract_name_from_vertex | |
214 | { | |
215 | typedef vertex_name_type result_type; | |
216 | ||
217 | extract_name_from_vertex(Graph& graph, const extract_name_type& extract) | |
218 | : graph(graph), extract(extract) { } | |
219 | ||
220 | const result_type& operator()(Vertex vertex) const | |
221 | { | |
222 | return extract(graph[vertex]); | |
223 | } | |
224 | ||
225 | Graph& graph; | |
226 | extract_name_type extract; | |
227 | }; | |
228 | ||
229 | public: | |
230 | /// The type that maps names to vertices | |
231 | typedef multi_index::multi_index_container< | |
232 | Vertex, | |
233 | multi_index::indexed_by< | |
234 | multi_index::hashed_unique<multi_index::tag<vertex_name_t>, | |
235 | extract_name_from_vertex> > | |
236 | > named_vertices_type; | |
237 | ||
238 | /// The set of vertices, indexed by name | |
239 | typedef typename named_vertices_type::template index<vertex_name_t>::type | |
240 | vertices_by_name_type; | |
241 | ||
242 | /// Construct an instance of the named graph mixin, using the given | |
243 | /// function object to extract a name from the bundled property | |
244 | /// associated with a vertex. | |
245 | named_graph(const extract_name_type& extract = extract_name_type(), | |
246 | const vertex_constructor_type& vertex_constructor | |
247 | = vertex_constructor_type()); | |
248 | ||
249 | /// Notify the named_graph that we have added the given vertex. The | |
250 | /// name of the vertex will be added to the mapping. | |
251 | void added_vertex(Vertex vertex); | |
252 | ||
253 | /// Notify the named_graph that we are removing the given | |
254 | /// vertex. The name of the vertex will be removed from the mapping. | |
255 | template <typename VertexIterStability> | |
256 | void removing_vertex(Vertex vertex, VertexIterStability); | |
257 | ||
258 | /// Notify the named_graph that we are clearing the graph. | |
259 | /// This will clear out all of the name->vertex mappings | |
260 | void clearing_graph(); | |
261 | ||
262 | /// Retrieve the derived instance | |
263 | Graph& derived() { return static_cast<Graph&>(*this); } | |
264 | const Graph& derived() const { return static_cast<const Graph&>(*this); } | |
265 | ||
266 | /// Extract the name from a vertex property instance | |
267 | typename extract_name_type::result_type | |
268 | extract_name(const bundled_vertex_property_type& property); | |
269 | ||
270 | /// Search for a vertex that has the given property (based on its | |
271 | /// name) | |
272 | optional<vertex_descriptor> | |
273 | vertex_by_property(const bundled_vertex_property_type& property); | |
274 | ||
275 | /// Mapping from names to vertices | |
276 | named_vertices_type named_vertices; | |
277 | ||
278 | /// Constructs a vertex from the name of that vertex | |
279 | vertex_constructor_type vertex_constructor; | |
280 | }; | |
281 | ||
282 | /// Helper macro containing the template parameters of named_graph | |
283 | #define BGL_NAMED_GRAPH_PARAMS \ | |
284 | typename Graph, typename Vertex, typename VertexProperty | |
285 | /// Helper macro containing the named_graph<...> instantiation | |
286 | #define BGL_NAMED_GRAPH \ | |
287 | named_graph<Graph, Vertex, VertexProperty> | |
288 | ||
289 | template<BGL_NAMED_GRAPH_PARAMS> | |
290 | BGL_NAMED_GRAPH::named_graph(const extract_name_type& extract, | |
291 | const vertex_constructor_type& vertex_constructor) | |
292 | : named_vertices( | |
293 | typename named_vertices_type::ctor_args_list( | |
294 | boost::make_tuple( | |
295 | boost::make_tuple( | |
296 | 0, // initial number of buckets | |
297 | extract_name_from_vertex(derived(), extract), | |
298 | boost::hash<vertex_name_type>(), | |
299 | std::equal_to<vertex_name_type>())))), | |
300 | vertex_constructor(vertex_constructor) | |
301 | { | |
302 | } | |
303 | ||
304 | template<BGL_NAMED_GRAPH_PARAMS> | |
305 | inline void BGL_NAMED_GRAPH::added_vertex(Vertex vertex) | |
306 | { | |
307 | named_vertices.insert(vertex); | |
308 | } | |
309 | ||
310 | template<BGL_NAMED_GRAPH_PARAMS> | |
311 | template<typename VertexIterStability> | |
312 | inline void BGL_NAMED_GRAPH::removing_vertex(Vertex vertex, VertexIterStability) | |
313 | { | |
314 | BOOST_STATIC_ASSERT_MSG ((boost::is_base_of<boost::graph_detail::stable_tag, VertexIterStability>::value), "Named graphs cannot use vecS as vertex container and remove vertices; the lack of vertex descriptor stability (which iterator stability is a proxy for) means that the name -> vertex mapping would need to be completely rebuilt after each deletion. See https://svn.boost.org/trac/boost/ticket/7863 for more information and a test case."); | |
315 | typedef typename BGL_NAMED_GRAPH::vertex_name_type vertex_name_type; | |
316 | const vertex_name_type& vertex_name = extract_name(derived()[vertex]); | |
317 | named_vertices.erase(vertex_name); | |
318 | } | |
319 | ||
320 | template<BGL_NAMED_GRAPH_PARAMS> | |
321 | inline void BGL_NAMED_GRAPH::clearing_graph() | |
322 | { | |
323 | named_vertices.clear(); | |
324 | } | |
325 | ||
326 | template<BGL_NAMED_GRAPH_PARAMS> | |
327 | typename BGL_NAMED_GRAPH::extract_name_type::result_type | |
328 | BGL_NAMED_GRAPH::extract_name(const bundled_vertex_property_type& property) | |
329 | { | |
330 | return named_vertices.key_extractor().extract(property); | |
331 | } | |
332 | ||
333 | template<BGL_NAMED_GRAPH_PARAMS> | |
334 | optional<typename BGL_NAMED_GRAPH::vertex_descriptor> | |
335 | BGL_NAMED_GRAPH:: | |
336 | vertex_by_property(const bundled_vertex_property_type& property) | |
337 | { | |
338 | return find_vertex(extract_name(property), *this); | |
339 | } | |
340 | ||
341 | /// Retrieve the vertex associated with the given name | |
342 | template<BGL_NAMED_GRAPH_PARAMS> | |
343 | optional<Vertex> | |
344 | find_vertex(typename BGL_NAMED_GRAPH::vertex_name_type const& name, | |
345 | const BGL_NAMED_GRAPH& g) | |
346 | { | |
347 | typedef typename BGL_NAMED_GRAPH::vertices_by_name_type | |
348 | vertices_by_name_type; | |
349 | ||
350 | // Retrieve the set of vertices indexed by name | |
351 | vertices_by_name_type const& vertices_by_name | |
352 | = g.named_vertices.template get<vertex_name_t>(); | |
353 | ||
354 | /// Look for a vertex with the given name | |
355 | typename vertices_by_name_type::const_iterator iter | |
356 | = vertices_by_name.find(name); | |
357 | ||
358 | if (iter == vertices_by_name.end()) | |
359 | return optional<Vertex>(); // vertex not found | |
360 | else | |
361 | return *iter; | |
362 | } | |
363 | ||
364 | /// Retrieve the vertex associated with the given name, or add a new | |
365 | /// vertex with that name if no such vertex is available. | |
366 | /// Note: This is enabled only when the vertex property type is different | |
367 | /// from the vertex name to avoid ambiguous overload problems with | |
368 | /// the add_vertex() function that takes a vertex property. | |
369 | template<BGL_NAMED_GRAPH_PARAMS> | |
370 | typename disable_if<is_same< | |
371 | typename BGL_NAMED_GRAPH::vertex_name_type, | |
372 | VertexProperty | |
373 | >, | |
374 | Vertex>::type | |
375 | add_vertex(typename BGL_NAMED_GRAPH::vertex_name_type const& name, | |
376 | BGL_NAMED_GRAPH& g) | |
377 | { | |
378 | if (optional<Vertex> vertex = find_vertex(name, g)) | |
379 | /// We found the vertex, so return it | |
380 | return *vertex; | |
381 | else | |
382 | /// There is no vertex with the given name, so create one | |
383 | return add_vertex(g.vertex_constructor(name), g.derived()); | |
384 | } | |
385 | ||
386 | /// Add an edge using vertex names to refer to the vertices | |
387 | template<BGL_NAMED_GRAPH_PARAMS> | |
388 | std::pair<typename graph_traits<Graph>::edge_descriptor, bool> | |
389 | add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name, | |
390 | typename BGL_NAMED_GRAPH::vertex_name_type const& v_name, | |
391 | BGL_NAMED_GRAPH& g) | |
392 | { | |
393 | return add_edge(add_vertex(u_name, g.derived()), | |
394 | add_vertex(v_name, g.derived()), | |
395 | g.derived()); | |
396 | } | |
397 | ||
398 | /// Add an edge using vertex descriptors or names to refer to the vertices | |
399 | template<BGL_NAMED_GRAPH_PARAMS> | |
400 | std::pair<typename graph_traits<Graph>::edge_descriptor, bool> | |
401 | add_edge(typename BGL_NAMED_GRAPH::vertex_descriptor const& u, | |
402 | typename BGL_NAMED_GRAPH::vertex_name_type const& v_name, | |
403 | BGL_NAMED_GRAPH& g) | |
404 | { | |
405 | return add_edge(u, | |
406 | add_vertex(v_name, g.derived()), | |
407 | g.derived()); | |
408 | } | |
409 | ||
410 | /// Add an edge using vertex descriptors or names to refer to the vertices | |
411 | template<BGL_NAMED_GRAPH_PARAMS> | |
412 | std::pair<typename graph_traits<Graph>::edge_descriptor, bool> | |
413 | add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name, | |
414 | typename BGL_NAMED_GRAPH::vertex_descriptor const& v, | |
415 | BGL_NAMED_GRAPH& g) | |
416 | { | |
417 | return add_edge(add_vertex(u_name, g.derived()), | |
418 | v, | |
419 | g.derived()); | |
420 | } | |
421 | ||
422 | // Overloads to support EdgeMutablePropertyGraph graphs | |
423 | template <BGL_NAMED_GRAPH_PARAMS> | |
424 | std::pair<typename graph_traits<Graph>::edge_descriptor, bool> | |
425 | add_edge(typename BGL_NAMED_GRAPH::vertex_descriptor const& u, | |
426 | typename BGL_NAMED_GRAPH::vertex_name_type const& v_name, | |
427 | typename edge_property_type<Graph>::type const& p, | |
428 | BGL_NAMED_GRAPH& g) { | |
429 | return add_edge(u, add_vertex(v_name, g.derived()), p, g.derived()); | |
430 | } | |
431 | ||
432 | template <BGL_NAMED_GRAPH_PARAMS> | |
433 | std::pair<typename graph_traits<Graph>::edge_descriptor, bool> | |
434 | add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name, | |
435 | typename BGL_NAMED_GRAPH::vertex_descriptor const& v, | |
436 | typename edge_property_type<Graph>::type const& p, | |
437 | BGL_NAMED_GRAPH& g) { | |
438 | return add_edge(add_vertex(u_name, g.derived()), v, p, g.derived()); | |
439 | } | |
440 | ||
441 | template <BGL_NAMED_GRAPH_PARAMS> | |
442 | std::pair<typename graph_traits<Graph>::edge_descriptor, bool> | |
443 | add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name, | |
444 | typename BGL_NAMED_GRAPH::vertex_name_type const& v_name, | |
445 | typename edge_property_type<Graph>::type const& p, | |
446 | BGL_NAMED_GRAPH& g) { | |
447 | return add_edge(add_vertex(u_name, g.derived()), | |
448 | add_vertex(v_name, g.derived()), p, g.derived()); | |
449 | } | |
450 | ||
451 | #undef BGL_NAMED_GRAPH | |
452 | #undef BGL_NAMED_GRAPH_PARAMS | |
453 | ||
454 | /******************************************************************* | |
455 | * Maybe named graph mixin * | |
456 | *******************************************************************/ | |
457 | ||
458 | /** | |
459 | * A graph mixin that can provide a mapping from names to vertices, | |
460 | * and use that mapping to simplify creation and manipulation of | |
461 | * graphs. | |
462 | */ | |
463 | template<typename Graph, typename Vertex, typename VertexProperty, | |
464 | typename ExtractName | |
465 | = typename internal_vertex_name<VertexProperty>::type> | |
466 | struct maybe_named_graph : public named_graph<Graph, Vertex, VertexProperty> | |
467 | { | |
468 | }; | |
469 | ||
470 | /** | |
471 | * A graph mixin that can provide a mapping from names to vertices, | |
472 | * and use that mapping to simplify creation and manipulation of | |
473 | * graphs. This partial specialization turns off this functionality | |
474 | * when the @c VertexProperty does not have an internal vertex name. | |
475 | */ | |
476 | template<typename Graph, typename Vertex, typename VertexProperty> | |
477 | struct maybe_named_graph<Graph, Vertex, VertexProperty, void> | |
478 | { | |
479 | /// The type of the "bundled" property, from which the name can be | |
480 | /// extracted. | |
481 | typedef typename lookup_one_property<VertexProperty, vertex_bundle_t>::type | |
482 | bundled_vertex_property_type; | |
483 | ||
484 | /// Notify the named_graph that we have added the given vertex. This | |
485 | /// is a no-op. | |
486 | void added_vertex(Vertex) { } | |
487 | ||
488 | /// Notify the named_graph that we are removing the given | |
489 | /// vertex. This is a no-op. | |
490 | template <typename VertexIterStability> | |
491 | void removing_vertex(Vertex, VertexIterStability) { } | |
492 | ||
493 | /// Notify the named_graph that we are clearing the graph. This is a | |
494 | /// no-op. | |
495 | void clearing_graph() { } | |
496 | ||
497 | /// Search for a vertex that has the given property (based on its | |
498 | /// name). This always returns an empty optional<> | |
499 | optional<Vertex> | |
500 | vertex_by_property(const bundled_vertex_property_type&) | |
501 | { | |
502 | return optional<Vertex>(); | |
503 | } | |
504 | }; | |
505 | ||
506 | } } // end namespace boost::graph | |
507 | ||
508 | #endif // BOOST_GRAPH_NAMED_GRAPH_HPP |