git.sesse.net Git - casparcg/blob - dependencies/boost/boost/graph/named_graph.hpp

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