ceph/src/boost/libs/graph/include/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/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   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