ceph/src/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/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
  36 {
  37 namespace 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                 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(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