File: named_graph.hpp

package info (click to toggle)
boost1.62 1.62.0+dfsg-4
  • links: PTS, VCS
  • area: main
  • in suites: stretch
  • size: 686,420 kB
  • sloc: cpp: 2,609,004; xml: 972,558; ansic: 53,674; python: 32,437; sh: 8,829; asm: 3,071; cs: 2,121; makefile: 964; perl: 859; yacc: 472; php: 132; ruby: 94; f90: 55; sql: 13; csh: 6
file content (508 lines) | stat: -rw-r--r-- 18,652 bytes parent folder | download | duplicates (13)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
// Copyright (C) 2007 Douglas Gregor

// Use, modification and distribution is subject to the Boost Software
// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

// Provides support for named vertices in graphs, allowing one to more
// easily associate unique external names (URLs, city names, employee
// ID numbers, etc.) with the vertices of a graph.
#ifndef BOOST_GRAPH_NAMED_GRAPH_HPP
#define BOOST_GRAPH_NAMED_GRAPH_HPP

#include <boost/config.hpp>
#include <boost/static_assert.hpp>
#include <boost/functional/hash.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index_container.hpp>
#include <boost/optional.hpp>
#include <boost/pending/property.hpp> // for boost::lookup_one_property
#include <boost/pending/container_traits.hpp>
#include <boost/throw_exception.hpp>
#include <boost/tuple/tuple.hpp> // for boost::make_tuple
#include <boost/type_traits/is_same.hpp>
#include <boost/type_traits/is_base_of.hpp>
#include <boost/type_traits/remove_cv.hpp>
#include <boost/type_traits/remove_reference.hpp>
#include <boost/utility/enable_if.hpp>
#include <functional> // for std::equal_to
#include <stdexcept> // for std::runtime_error
#include <utility> // for std::pair

namespace boost { namespace graph {

/*******************************************************************
 * User-customized traits                                          *
 *******************************************************************/

/**
 * @brief Trait used to extract the internal vertex name from a vertex
 * property.
 *
 * To enable the use of internal vertex names in a graph type,
 * specialize the @c internal_vertex_name trait for your graph
 * property (e.g., @c a City class, which stores information about the
 * vertices in a road map).
 */
template<typename VertexProperty>
struct internal_vertex_name
{
  /**
   *  The @c type field provides a function object that extracts a key
   *  from the @c VertexProperty. The function object type must have a
   *  nested @c result_type that provides the type of the key. For
   *  more information, see the @c KeyExtractor concept in the
   *  Boost.MultiIndex documentation: @c type must either be @c void
   *  (if @c VertexProperty does not have an internal vertex name) or
   *  a model of @c KeyExtractor.
   */
  typedef void type;
};

/**
 * Extract the internal vertex name from a @c property structure by
 * looking at its base.
 */
template<typename Tag, typename T, typename Base>
struct internal_vertex_name<property<Tag, T, Base> >
  : internal_vertex_name<Base> { };

/**
 * Construct an instance of @c VertexProperty directly from its
 * name. This function object should be used within the @c
 * internal_vertex_constructor trait.
 */
template<typename VertexProperty>
struct vertex_from_name
{
private:
  typedef typename internal_vertex_name<VertexProperty>::type extract_name_type;

  typedef typename remove_cv<
            typename remove_reference<
              typename extract_name_type::result_type>::type>::type
    vertex_name_type;

public:
  typedef vertex_name_type argument_type;
  typedef VertexProperty result_type;

  VertexProperty operator()(const vertex_name_type& name)
  {
    return VertexProperty(name);
  }
};

/**
 * Throw an exception whenever one tries to construct a @c
 * VertexProperty instance from its name.
 */
template<typename VertexProperty>
struct cannot_add_vertex
{
private:
  typedef typename internal_vertex_name<VertexProperty>::type extract_name_type;

  typedef typename remove_cv<
            typename remove_reference<
              typename extract_name_type::result_type>::type>::type
    vertex_name_type;

public:
  typedef vertex_name_type argument_type;
  typedef VertexProperty result_type;

  VertexProperty operator()(const vertex_name_type&)
  {
      boost::throw_exception(std::runtime_error("add_vertex: "
                                                "unable to create a vertex from its name"));
  }
};

/**
 * @brief Trait used to construct an instance of a @c VertexProperty,
 * which is a class type that stores the properties associated with a
 * vertex in a graph, from just the name of that vertex property. This
 * operation is used when an operation is required to map from a
 * vertex name to a vertex descriptor (e.g., to add an edge outgoing
 * from that vertex), but no vertex by the name exists. The function
 * object provided by this trait will be used to add new vertices
 * based only on their names. Since this cannot be done for arbitrary
 * types, the default behavior is to throw an exception when this
 * routine is called, which requires that all named vertices be added
 * before adding any edges by name.
 */
template<typename VertexProperty>
struct internal_vertex_constructor
{
  /**
   * The @c type field provides a function object that constructs a
   * new instance of @c VertexProperty from the name of the vertex (as
   * determined by @c internal_vertex_name). The function object shall
   * accept a vertex name and return a @c VertexProperty. Predefined
   * options include:
   *
   *   @c vertex_from_name<VertexProperty>: construct an instance of
   *   @c VertexProperty directly from the name.
   *
   *   @c cannot_add_vertex<VertexProperty>: the default value, which
   *   throws an @c std::runtime_error if one attempts to add a vertex
   *   given just the name.
   */
  typedef cannot_add_vertex<VertexProperty> type;
};

/**
 * Extract the internal vertex constructor from a @c property structure by
 * looking at its base.
 */
template<typename Tag, typename T, typename Base>
struct internal_vertex_constructor<property<Tag, T, Base> >
  : internal_vertex_constructor<Base> { };

/*******************************************************************
 * Named graph mixin                                               *
 *******************************************************************/

/**
 * named_graph is a mixin that provides names for the vertices of a
 * graph, including a mapping from names to vertices. Graph types that
 * may or may not be have vertex names (depending on the properties
 * supplied by the user) should use maybe_named_graph.
 *
 * Template parameters:
 *
 *   Graph: the graph type that derives from named_graph
 *
 *   Vertex: the type of a vertex descriptor in Graph. Note: we cannot
 *   use graph_traits here, because the Graph is not yet defined.
 *
 *   VertexProperty: the type stored with each vertex in the Graph.
 */
template<typename Graph, typename Vertex, typename VertexProperty>
class named_graph
{
public:
  /// The type of the function object that extracts names from vertex
  /// properties.
  typedef typename internal_vertex_name<VertexProperty>::type extract_name_type;
  /// The type of the "bundled" property, from which the name can be
  /// extracted.
  typedef typename lookup_one_property<VertexProperty, vertex_bundle_t>::type
    bundled_vertex_property_type;

  /// The type of the function object that generates vertex properties
  /// from names, for the implicit addition of vertices.
  typedef typename internal_vertex_constructor<VertexProperty>::type
    vertex_constructor_type;

  /// The type used to name vertices in the graph
  typedef typename remove_cv<
            typename remove_reference<
              typename extract_name_type::result_type>::type>::type
    vertex_name_type;

  /// The type of vertex descriptors in the graph
  typedef Vertex vertex_descriptor;

private:
  /// Key extractor for use with the multi_index_container
  struct extract_name_from_vertex
  {
    typedef vertex_name_type result_type;

    extract_name_from_vertex(Graph& graph, const extract_name_type& extract)
      : graph(graph), extract(extract) { }

    const result_type& operator()(Vertex vertex) const
    {
      return extract(graph[vertex]);
    }

    Graph& graph;
    extract_name_type extract;
  };

public:
  /// The type that maps names to vertices
  typedef multi_index::multi_index_container<
            Vertex,
            multi_index::indexed_by<
              multi_index::hashed_unique<multi_index::tag<vertex_name_t>,
                                         extract_name_from_vertex> >
          > named_vertices_type;

  /// The set of vertices, indexed by name
  typedef typename named_vertices_type::template index<vertex_name_t>::type
    vertices_by_name_type;

  /// Construct an instance of the named graph mixin, using the given
  /// function object to extract a name from the bundled property
  /// associated with a vertex.
  named_graph(const extract_name_type& extract = extract_name_type(),
              const vertex_constructor_type& vertex_constructor
                = vertex_constructor_type());

  /// Notify the named_graph that we have added the given vertex. The
  /// name of the vertex will be added to the mapping.
  void added_vertex(Vertex vertex);

  /// Notify the named_graph that we are removing the given
  /// vertex. The name of the vertex will be removed from the mapping.
  template <typename VertexIterStability>
  void removing_vertex(Vertex vertex, VertexIterStability);

  /// Notify the named_graph that we are clearing the graph.
  /// This will clear out all of the name->vertex mappings
  void clearing_graph();

  /// Retrieve the derived instance
  Graph&       derived()       { return static_cast<Graph&>(*this); }
  const Graph& derived() const { return static_cast<const Graph&>(*this); }

  /// Extract the name from a vertex property instance
  typename extract_name_type::result_type
  extract_name(const bundled_vertex_property_type& property);

  /// Search for a vertex that has the given property (based on its
  /// name)
  optional<vertex_descriptor>
  vertex_by_property(const bundled_vertex_property_type& property);

  /// Mapping from names to vertices
  named_vertices_type named_vertices;

  /// Constructs a vertex from the name of that vertex
  vertex_constructor_type vertex_constructor;
};

/// Helper macro containing the template parameters of named_graph
#define BGL_NAMED_GRAPH_PARAMS \
  typename Graph, typename Vertex, typename VertexProperty
/// Helper macro containing the named_graph<...> instantiation
#define BGL_NAMED_GRAPH \
  named_graph<Graph, Vertex, VertexProperty>

template<BGL_NAMED_GRAPH_PARAMS>
BGL_NAMED_GRAPH::named_graph(const extract_name_type& extract,
                             const vertex_constructor_type& vertex_constructor)
  : named_vertices(
      typename named_vertices_type::ctor_args_list(
        boost::make_tuple(
          boost::make_tuple(
            0, // initial number of buckets
            extract_name_from_vertex(derived(), extract),
            boost::hash<vertex_name_type>(),
            std::equal_to<vertex_name_type>())))),
    vertex_constructor(vertex_constructor)
{
}

template<BGL_NAMED_GRAPH_PARAMS>
inline void BGL_NAMED_GRAPH::added_vertex(Vertex vertex)
{
  named_vertices.insert(vertex);
}

template<BGL_NAMED_GRAPH_PARAMS>
template<typename VertexIterStability>
inline void BGL_NAMED_GRAPH::removing_vertex(Vertex vertex, VertexIterStability)
{
  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.");
  typedef typename BGL_NAMED_GRAPH::vertex_name_type vertex_name_type;
  const vertex_name_type& vertex_name = extract_name(derived()[vertex]);
  named_vertices.erase(vertex_name);
}

template<BGL_NAMED_GRAPH_PARAMS>
inline void BGL_NAMED_GRAPH::clearing_graph()
{
  named_vertices.clear();
}

template<BGL_NAMED_GRAPH_PARAMS>
typename BGL_NAMED_GRAPH::extract_name_type::result_type
BGL_NAMED_GRAPH::extract_name(const bundled_vertex_property_type& property)
{
  return named_vertices.key_extractor().extract(property);
}

template<BGL_NAMED_GRAPH_PARAMS>
optional<typename BGL_NAMED_GRAPH::vertex_descriptor>
BGL_NAMED_GRAPH::
vertex_by_property(const bundled_vertex_property_type& property)
{
  return find_vertex(extract_name(property), *this);
}

/// Retrieve the vertex associated with the given name
template<BGL_NAMED_GRAPH_PARAMS>
optional<Vertex>
find_vertex(typename BGL_NAMED_GRAPH::vertex_name_type const& name,
            const BGL_NAMED_GRAPH& g)
{
  typedef typename BGL_NAMED_GRAPH::vertices_by_name_type
    vertices_by_name_type;

  // Retrieve the set of vertices indexed by name
  vertices_by_name_type const& vertices_by_name
    = g.named_vertices.template get<vertex_name_t>();

  /// Look for a vertex with the given name
  typename vertices_by_name_type::const_iterator iter
    = vertices_by_name.find(name);

  if (iter == vertices_by_name.end())
    return optional<Vertex>(); // vertex not found
  else
    return *iter;
}

/// Retrieve the vertex associated with the given name, or add a new
/// vertex with that name if no such vertex is available.
/// Note: This is enabled only when the vertex property type is different
///       from the vertex name to avoid ambiguous overload problems with
///       the add_vertex() function that takes a vertex property.
template<BGL_NAMED_GRAPH_PARAMS>
    typename disable_if<is_same<
        typename BGL_NAMED_GRAPH::vertex_name_type,
        VertexProperty
    >,
Vertex>::type
add_vertex(typename BGL_NAMED_GRAPH::vertex_name_type const& name,
           BGL_NAMED_GRAPH& g)
{
  if (optional<Vertex> vertex = find_vertex(name, g))
    /// We found the vertex, so return it
    return *vertex;
  else
    /// There is no vertex with the given name, so create one
    return add_vertex(g.vertex_constructor(name), g.derived());
}

/// Add an edge using vertex names to refer to the vertices
template<BGL_NAMED_GRAPH_PARAMS>
std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
         typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
         BGL_NAMED_GRAPH& g)
{
  return add_edge(add_vertex(u_name, g.derived()),
                  add_vertex(v_name, g.derived()),
                  g.derived());
}

/// Add an edge using vertex descriptors or names to refer to the vertices
template<BGL_NAMED_GRAPH_PARAMS>
std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
add_edge(typename BGL_NAMED_GRAPH::vertex_descriptor const& u,
         typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
         BGL_NAMED_GRAPH& g)
{
  return add_edge(u,
                  add_vertex(v_name, g.derived()),
                  g.derived());
}

/// Add an edge using vertex descriptors or names to refer to the vertices
template<BGL_NAMED_GRAPH_PARAMS>
std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
         typename BGL_NAMED_GRAPH::vertex_descriptor const& v,
         BGL_NAMED_GRAPH& g)
{
  return add_edge(add_vertex(u_name, g.derived()),
                  v,
                  g.derived());
}

// Overloads to support EdgeMutablePropertyGraph graphs
template <BGL_NAMED_GRAPH_PARAMS>
std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
add_edge(typename BGL_NAMED_GRAPH::vertex_descriptor const& u,
         typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
         typename edge_property_type<Graph>::type const& p,
         BGL_NAMED_GRAPH& g) {
    return add_edge(u, add_vertex(v_name, g.derived()), p, g.derived());
}

template <BGL_NAMED_GRAPH_PARAMS>
std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
         typename BGL_NAMED_GRAPH::vertex_descriptor const& v,
         typename edge_property_type<Graph>::type const& p,
         BGL_NAMED_GRAPH& g) {
    return add_edge(add_vertex(u_name, g.derived()), v, p, g.derived());
}

template <BGL_NAMED_GRAPH_PARAMS>
std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
         typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
         typename edge_property_type<Graph>::type const& p,
         BGL_NAMED_GRAPH& g) {
    return add_edge(add_vertex(u_name, g.derived()),
                    add_vertex(v_name, g.derived()), p, g.derived());
}

#undef BGL_NAMED_GRAPH
#undef BGL_NAMED_GRAPH_PARAMS

/*******************************************************************
 * Maybe named graph mixin                                         *
 *******************************************************************/

/**
 * A graph mixin that can provide a mapping from names to vertices,
 * and use that mapping to simplify creation and manipulation of
 * graphs.
 */
template<typename Graph, typename Vertex, typename VertexProperty,
         typename ExtractName
           = typename internal_vertex_name<VertexProperty>::type>
struct maybe_named_graph : public named_graph<Graph, Vertex, VertexProperty>
{
};

/**
 * A graph mixin that can provide a mapping from names to vertices,
 * and use that mapping to simplify creation and manipulation of
 * graphs. This partial specialization turns off this functionality
 * when the @c VertexProperty does not have an internal vertex name.
 */
template<typename Graph, typename Vertex, typename VertexProperty>
struct maybe_named_graph<Graph, Vertex, VertexProperty, void>
{
  /// The type of the "bundled" property, from which the name can be
  /// extracted.
  typedef typename lookup_one_property<VertexProperty, vertex_bundle_t>::type
    bundled_vertex_property_type;

  /// Notify the named_graph that we have added the given vertex. This
  /// is a no-op.
  void added_vertex(Vertex) { }

  /// Notify the named_graph that we are removing the given
  /// vertex. This is a no-op.
  template <typename VertexIterStability>
  void removing_vertex(Vertex, VertexIterStability) { }

  /// Notify the named_graph that we are clearing the graph. This is a
  /// no-op.
  void clearing_graph() { }

  /// Search for a vertex that has the given property (based on its
  /// name). This always returns an empty optional<>
  optional<Vertex>
  vertex_by_property(const bundled_vertex_property_type&)
  {
    return optional<Vertex>();
  }
};

} } // end namespace boost::graph

#endif // BOOST_GRAPH_NAMED_GRAPH_HPP