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