Line data Source code
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 0 : 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 0 : 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
|
