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 ; |
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 ; |
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(e: 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 ; |
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 |
214 | { |
215 | typedef vertex_name_type ; |
216 | |
217 | (Graph& graph, const extract_name_type& ) |
218 | : graph(graph), extract(extract) { } |
219 | |
220 | const result_type& (Vertex vertex) const |
221 | { |
222 | return extract(graph[vertex]); |
223 | } |
224 | |
225 | Graph& ; |
226 | extract_name_type ; |
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_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& , |
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(property: 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::(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 |
509 | |