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 { 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 */
50template<typename VertexProperty>
51struct 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 */
69template<typename Tag, typename T, typename Base>
70struct 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 */
78template<typename VertexProperty>
79struct vertex_from_name
80{
81private:
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
89public:
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 */
103template<typename VertexProperty>
104struct cannot_add_vertex
105{
106private:
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
114public:
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 */
138template<typename VertexProperty>
139struct 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 */
162template<typename Tag, typename T, typename Base>
163struct 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 */
185template<typename Graph, typename Vertex, typename VertexProperty>
186class named_graph
187{
188public:
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
211private:
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
229public:
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
289template<BGL_NAMED_GRAPH_PARAMS>
290BGL_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
304template<BGL_NAMED_GRAPH_PARAMS>
305inline void BGL_NAMED_GRAPH::added_vertex(Vertex vertex)
306{
307 named_vertices.insert(vertex);
308}
309
310template<BGL_NAMED_GRAPH_PARAMS>
311template<typename VertexIterStability>
312inline 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
320template<BGL_NAMED_GRAPH_PARAMS>
321inline void BGL_NAMED_GRAPH::clearing_graph()
322{
323 named_vertices.clear();
324}
325
326template<BGL_NAMED_GRAPH_PARAMS>
327typename BGL_NAMED_GRAPH::extract_name_type::result_type
328BGL_NAMED_GRAPH::extract_name(const bundled_vertex_property_type& property)
329{
330 return named_vertices.key_extractor().extract(property);
331}
332
333template<BGL_NAMED_GRAPH_PARAMS>
334optional<typename BGL_NAMED_GRAPH::vertex_descriptor>
335BGL_NAMED_GRAPH::
336vertex_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
342template<BGL_NAMED_GRAPH_PARAMS>
343optional<Vertex>
344find_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.
369template<BGL_NAMED_GRAPH_PARAMS>
370 typename disable_if<is_same<
371 typename BGL_NAMED_GRAPH::vertex_name_type,
372 VertexProperty
373 >,
374Vertex>::type
375add_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
387template<BGL_NAMED_GRAPH_PARAMS>
388std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
389add_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
399template<BGL_NAMED_GRAPH_PARAMS>
400std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
401add_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
411template<BGL_NAMED_GRAPH_PARAMS>
412std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
413add_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
423template <BGL_NAMED_GRAPH_PARAMS>
424std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
425add_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
432template <BGL_NAMED_GRAPH_PARAMS>
433std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
434add_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
441template <BGL_NAMED_GRAPH_PARAMS>
442std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
443add_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 */
463template<typename Graph, typename Vertex, typename VertexProperty,
464 typename ExtractName
465 = typename internal_vertex_name<VertexProperty>::type>
466struct 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 */
476template<typename Graph, typename Vertex, typename VertexProperty>
477struct 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

source code of boost/boost/graph/named_graph.hpp