boost/graph/named_graph.hpp

0001 // Copyright (C) 2007 Douglas Gregor
0002
0003 // Use, modification and distribution is subject to the Boost Software
0004 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0005 // http://www.boost.org/LICENSE_1_0.txt)
0006
0007 // Provides support for named vertices in graphs, allowing one to more
0008 // easily associate unique external names (URLs, city names, employee
0009 // ID numbers, etc.) with the vertices of a graph.
0010 #ifndef BOOST_GRAPH_NAMED_GRAPH_HPP
0011 #define BOOST_GRAPH_NAMED_GRAPH_HPP
0012
0013 #include <boost/config.hpp>
0014 #include <boost/static_assert.hpp>
0015 #include <boost/functional/hash.hpp>
0016 #include <boost/graph/graph_traits.hpp>
0017 #include <boost/graph/properties.hpp>
0018 #include <boost/multi_index/hashed_index.hpp>
0019 #include <boost/multi_index/member.hpp>
0020 #include <boost/multi_index_container.hpp>
0021 #include <boost/optional.hpp>
0022 #include <boost/pending/property.hpp> // for boost::lookup_one_property
0023 #include <boost/pending/container_traits.hpp>
0024 #include <boost/throw_exception.hpp>
0025 #include <boost/tuple/tuple.hpp> // for boost::make_tuple
0026 #include <boost/type_traits/is_same.hpp>
0027 #include <boost/type_traits/is_base_of.hpp>
0028 #include <boost/type_traits/remove_cv.hpp>
0029 #include <boost/type_traits/remove_reference.hpp>
0030 #include <boost/utility/enable_if.hpp>
0031 #include <functional> // for std::equal_to
0032 #include <stdexcept> // for std::runtime_error
0033 #include <utility> // for std::pair
0034
0035 namespace boost
0036 {
0037 namespace graph
0038 {
0039
0040     /*******************************************************************
0041      * User-customized traits                                          *
0042      *******************************************************************/
0043
0044     /**
0045      * @brief Trait used to extract the internal vertex name from a vertex
0046      * property.
0047      *
0048      * To enable the use of internal vertex names in a graph type,
0049      * specialize the @c internal_vertex_name trait for your graph
0050      * property (e.g., @c a City class, which stores information about the
0051      * vertices in a road map).
0052      */
0053     template < typename VertexProperty > struct internal_vertex_name
0054     {
0055         /**
0056          *  The @c type field provides a function object that extracts a key
0057          *  from the @c VertexProperty. The function object type must have a
0058          *  nested @c result_type that provides the type of the key. For
0059          *  more information, see the @c KeyExtractor concept in the
0060          *  Boost.MultiIndex documentation: @c type must either be @c void
0061          *  (if @c VertexProperty does not have an internal vertex name) or
0062          *  a model of @c KeyExtractor.
0063          */
0064         typedef void type;
0065     };
0066
0067     /**
0068      * Extract the internal vertex name from a @c property structure by
0069      * looking at its base.
0070      */
0071     template < typename Tag, typename T, typename Base >
0072     struct internal_vertex_name< property< Tag, T, Base > >
0073     : internal_vertex_name< Base >
0074     {
0075     };
0076
0077     /**
0078      * Construct an instance of @c VertexProperty directly from its
0079      * name. This function object should be used within the @c
0080      * internal_vertex_constructor trait.
0081      */
0082     template < typename VertexProperty > struct vertex_from_name
0083     {
0084     private:
0085         typedef typename internal_vertex_name< VertexProperty >::type
0086             extract_name_type;
0087
0088         typedef typename remove_cv< typename remove_reference<
0089             typename extract_name_type::result_type >::type >::type
0090             vertex_name_type;
0091
0092     public:
0093         typedef vertex_name_type argument_type;
0094         typedef VertexProperty result_type;
0095
0096         VertexProperty operator()(const vertex_name_type& name)
0097         {
0098             return VertexProperty(name);
0099         }
0100     };
0101
0102     /**
0103      * Throw an exception whenever one tries to construct a @c
0104      * VertexProperty instance from its name.
0105      */
0106     template < typename VertexProperty > struct cannot_add_vertex
0107     {
0108     private:
0109         typedef typename internal_vertex_name< VertexProperty >::type
0110             extract_name_type;
0111
0112         typedef typename remove_cv< typename remove_reference<
0113             typename extract_name_type::result_type >::type >::type
0114             vertex_name_type;
0115
0116     public:
0117         typedef vertex_name_type argument_type;
0118         typedef VertexProperty result_type;
0119
0120         VertexProperty operator()(const vertex_name_type&)
0121         {
0122             boost::throw_exception(
0123                 std::runtime_error("add_vertex: "
0124                                    "unable to create a vertex from its name"));
0125         }
0126     };
0127
0128     /**
0129      * @brief Trait used to construct an instance of a @c VertexProperty,
0130      * which is a class type that stores the properties associated with a
0131      * vertex in a graph, from just the name of that vertex property. This
0132      * operation is used when an operation is required to map from a
0133      * vertex name to a vertex descriptor (e.g., to add an edge outgoing
0134      * from that vertex), but no vertex by the name exists. The function
0135      * object provided by this trait will be used to add new vertices
0136      * based only on their names. Since this cannot be done for arbitrary
0137      * types, the default behavior is to throw an exception when this
0138      * routine is called, which requires that all named vertices be added
0139      * before adding any edges by name.
0140      */
0141     template < typename VertexProperty > struct internal_vertex_constructor
0142     {
0143         /**
0144          * The @c type field provides a function object that constructs a
0145          * new instance of @c VertexProperty from the name of the vertex (as
0146          * determined by @c internal_vertex_name). The function object shall
0147          * accept a vertex name and return a @c VertexProperty. Predefined
0148          * options include:
0149          *
0150          *   @c vertex_from_name<VertexProperty>: construct an instance of
0151          *   @c VertexProperty directly from the name.
0152          *
0153          *   @c cannot_add_vertex<VertexProperty>: the default value, which
0154          *   throws an @c std::runtime_error if one attempts to add a vertex
0155          *   given just the name.
0156          */
0157         typedef cannot_add_vertex< VertexProperty > type;
0158     };
0159
0160     /**
0161      * Extract the internal vertex constructor from a @c property structure by
0162      * looking at its base.
0163      */
0164     template < typename Tag, typename T, typename Base >
0165     struct internal_vertex_constructor< property< Tag, T, Base > >
0166     : internal_vertex_constructor< Base >
0167     {
0168     };
0169
0170     /*******************************************************************
0171      * Named graph mixin                                               *
0172      *******************************************************************/
0173
0174     /**
0175      * named_graph is a mixin that provides names for the vertices of a
0176      * graph, including a mapping from names to vertices. Graph types that
0177      * may or may not be have vertex names (depending on the properties
0178      * supplied by the user) should use maybe_named_graph.
0179      *
0180      * Template parameters:
0181      *
0182      *   Graph: the graph type that derives from named_graph
0183      *
0184      *   Vertex: the type of a vertex descriptor in Graph. Note: we cannot
0185      *   use graph_traits here, because the Graph is not yet defined.
0186      *
0187      *   VertexProperty: the type stored with each vertex in the Graph.
0188      */
0189     template < typename Graph, typename Vertex, typename VertexProperty >
0190     class named_graph
0191     {
0192     public:
0193         /// The type of the function object that extracts names from vertex
0194         /// properties.
0195         typedef typename internal_vertex_name< VertexProperty >::type
0196             extract_name_type;
0197         /// The type of the "bundled" property, from which the name can be
0198         /// extracted.
0199         typedef typename lookup_one_property< VertexProperty,
0200             vertex_bundle_t >::type bundled_vertex_property_type;
0201
0202         /// The type of the function object that generates vertex properties
0203         /// from names, for the implicit addition of vertices.
0204         typedef typename internal_vertex_constructor< VertexProperty >::type
0205             vertex_constructor_type;
0206
0207         /// The type used to name vertices in the graph
0208         typedef typename remove_cv< typename remove_reference<
0209             typename extract_name_type::result_type >::type >::type
0210             vertex_name_type;
0211
0212         /// The type of vertex descriptors in the graph
0213         typedef Vertex vertex_descriptor;
0214
0215     private:
0216         /// Key extractor for use with the multi_index_container
0217         struct extract_name_from_vertex
0218         {
0219             typedef vertex_name_type result_type;
0220
0221             extract_name_from_vertex(
0222                 Graph& graph, const extract_name_type& extract)
0223             : graph(graph), extract(extract)
0224             {
0225             }
0226
0227             const result_type& operator()(Vertex vertex) const
0228             {
0229                 return extract(graph[vertex]);
0230             }
0231
0232             Graph& graph;
0233             extract_name_type extract;
0234         };
0235
0236     public:
0237         /// The type that maps names to vertices
0238         typedef multi_index::multi_index_container< Vertex,
0239             multi_index::indexed_by<
0240                 multi_index::hashed_unique< multi_index::tag< vertex_name_t >,
0241                     extract_name_from_vertex > > >
0242             named_vertices_type;
0243
0244         /// The set of vertices, indexed by name
0245         typedef
0246             typename named_vertices_type::template index< vertex_name_t >::type
0247                 vertices_by_name_type;
0248
0249         /// Construct an instance of the named graph mixin, using the given
0250         /// function object to extract a name from the bundled property
0251         /// associated with a vertex.
0252         named_graph(const extract_name_type& extract = extract_name_type(),
0253             const vertex_constructor_type& vertex_constructor
0254             = vertex_constructor_type());
0255
0256         /// Notify the named_graph that we have added the given vertex. The
0257         /// name of the vertex will be added to the mapping.
0258         void added_vertex(Vertex vertex);
0259
0260         /// Notify the named_graph that we are removing the given
0261         /// vertex. The name of the vertex will be removed from the mapping.
0262         template < typename VertexIterStability >
0263         void removing_vertex(Vertex vertex, VertexIterStability);
0264
0265         /// Notify the named_graph that we are clearing the graph.
0266         /// This will clear out all of the name->vertex mappings
0267         void clearing_graph();
0268
0269         /// Retrieve the derived instance
0270         Graph& derived() { return static_cast< Graph& >(*this); }
0271         const Graph& derived() const
0272         {
0273             return static_cast< const Graph& >(*this);
0274         }
0275
0276         /// Extract the name from a vertex property instance
0277         typename extract_name_type::result_type extract_name(
0278             const bundled_vertex_property_type& property);
0279
0280         /// Search for a vertex that has the given property (based on its
0281         /// name)
0282         optional< vertex_descriptor > vertex_by_property(
0283             const bundled_vertex_property_type& property);
0284
0285         /// Mapping from names to vertices
0286         named_vertices_type named_vertices;
0287
0288         /// Constructs a vertex from the name of that vertex
0289         vertex_constructor_type vertex_constructor;
0290     };
0291
0292 /// Helper macro containing the template parameters of named_graph
0293 #define BGL_NAMED_GRAPH_PARAMS \
0294     typename Graph, typename Vertex, typename VertexProperty
0295 /// Helper macro containing the named_graph<...> instantiation
0296 #define BGL_NAMED_GRAPH named_graph< Graph, Vertex, VertexProperty >
0297
0298     template < BGL_NAMED_GRAPH_PARAMS >
0299     BGL_NAMED_GRAPH::named_graph(const extract_name_type& extract,
0300         const vertex_constructor_type& vertex_constructor)
0301     : named_vertices(typename named_vertices_type::ctor_args_list(
0302         boost::make_tuple(boost::make_tuple(0, // initial number of buckets
0303             extract_name_from_vertex(derived(), extract),
0304             boost::hash< vertex_name_type >(),
0305             std::equal_to< vertex_name_type >()))))
0306     , vertex_constructor(vertex_constructor)
0307     {
0308     }
0309
0310     template < BGL_NAMED_GRAPH_PARAMS >
0311     inline void BGL_NAMED_GRAPH::added_vertex(Vertex vertex)
0312     {
0313         named_vertices.insert(vertex);
0314     }
0315
0316     template < BGL_NAMED_GRAPH_PARAMS >
0317     template < typename VertexIterStability >
0318     inline void BGL_NAMED_GRAPH::removing_vertex(
0319         Vertex vertex, VertexIterStability)
0320     {
0321         BOOST_STATIC_ASSERT_MSG(
0322             (boost::is_base_of< boost::graph_detail::stable_tag,
0323                 VertexIterStability >::value),
0324             "Named graphs cannot use vecS as vertex container and remove "
0325             "vertices; the lack of vertex descriptor stability (which iterator "
0326             "stability is a proxy for) means that the name -> vertex mapping "
0327             "would need to be completely rebuilt after each deletion.  See "
0328             "https://svn.boost.org/trac/boost/ticket/7863 for more information "
0329             "and a test case.");
0330         typedef typename BGL_NAMED_GRAPH::vertex_name_type vertex_name_type;
0331         const vertex_name_type& vertex_name = extract_name(derived()[vertex]);
0332         named_vertices.erase(vertex_name);
0333     }
0334
0335     template < BGL_NAMED_GRAPH_PARAMS >
0336     inline void BGL_NAMED_GRAPH::clearing_graph()
0337     {
0338         named_vertices.clear();
0339     }
0340
0341     template < BGL_NAMED_GRAPH_PARAMS >
0342     typename BGL_NAMED_GRAPH::extract_name_type::result_type
0343     BGL_NAMED_GRAPH::extract_name(const bundled_vertex_property_type& property)
0344     {
0345         return named_vertices.key_extractor().extract(property);
0346     }
0347
0348     template < BGL_NAMED_GRAPH_PARAMS >
0349     optional< typename BGL_NAMED_GRAPH::vertex_descriptor >
0350     BGL_NAMED_GRAPH::vertex_by_property(
0351         const bundled_vertex_property_type& property)
0352     {
0353         return find_vertex(extract_name(property), *this);
0354     }
0355
0356     /// Retrieve the vertex associated with the given name
0357     template < BGL_NAMED_GRAPH_PARAMS >
0358     optional< Vertex > find_vertex(
0359         typename BGL_NAMED_GRAPH::vertex_name_type const& name,
0360         const BGL_NAMED_GRAPH& g)
0361     {
0362         typedef typename BGL_NAMED_GRAPH::vertices_by_name_type
0363             vertices_by_name_type;
0364
0365         // Retrieve the set of vertices indexed by name
0366         vertices_by_name_type const& vertices_by_name
0367             = g.named_vertices.template get< vertex_name_t >();
0368
0369         /// Look for a vertex with the given name
0370         typename vertices_by_name_type::const_iterator iter
0371             = vertices_by_name.find(name);
0372
0373         if (iter == vertices_by_name.end())
0374             return optional< Vertex >(); // vertex not found
0375         else
0376             return *iter;
0377     }
0378
0379     /// Retrieve the vertex associated with the given name, or add a new
0380     /// vertex with that name if no such vertex is available.
0381     /// Note: This is enabled only when the vertex property type is different
0382     ///       from the vertex name to avoid ambiguous overload problems with
0383     ///       the add_vertex() function that takes a vertex property.
0384     template < BGL_NAMED_GRAPH_PARAMS >
0385     typename disable_if<
0386         is_same< typename BGL_NAMED_GRAPH::vertex_name_type, VertexProperty >,
0387         Vertex >::type
0388     add_vertex(typename BGL_NAMED_GRAPH::vertex_name_type const& name,
0389         BGL_NAMED_GRAPH& g)
0390     {
0391         if (optional< Vertex > vertex = find_vertex(name, g))
0392             /// We found the vertex, so return it
0393             return *vertex;
0394         else
0395             /// There is no vertex with the given name, so create one
0396             return add_vertex(g.vertex_constructor(name), g.derived());
0397     }
0398
0399     /// Add an edge using vertex names to refer to the vertices
0400     template < BGL_NAMED_GRAPH_PARAMS >
0401     std::pair< typename graph_traits< Graph >::edge_descriptor, bool > add_edge(
0402         typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
0403         typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
0404         BGL_NAMED_GRAPH& g)
0405     {
0406         return add_edge(add_vertex(u_name, g.derived()),
0407             add_vertex(v_name, g.derived()), g.derived());
0408     }
0409
0410     /// Add an edge using vertex descriptors or names to refer to the vertices
0411     template < BGL_NAMED_GRAPH_PARAMS >
0412     std::pair< typename graph_traits< Graph >::edge_descriptor, bool > add_edge(
0413         typename BGL_NAMED_GRAPH::vertex_descriptor const& u,
0414         typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
0415         BGL_NAMED_GRAPH& g)
0416     {
0417         return add_edge(u, add_vertex(v_name, g.derived()), g.derived());
0418     }
0419
0420     /// Add an edge using vertex descriptors or names to refer to the vertices
0421     template < BGL_NAMED_GRAPH_PARAMS >
0422     std::pair< typename graph_traits< Graph >::edge_descriptor, bool > add_edge(
0423         typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
0424         typename BGL_NAMED_GRAPH::vertex_descriptor const& v,
0425         BGL_NAMED_GRAPH& g)
0426     {
0427         return add_edge(add_vertex(u_name, g.derived()), v, g.derived());
0428     }
0429
0430     // Overloads to support EdgeMutablePropertyGraph graphs
0431     template < BGL_NAMED_GRAPH_PARAMS >
0432     std::pair< typename graph_traits< Graph >::edge_descriptor, bool > add_edge(
0433         typename BGL_NAMED_GRAPH::vertex_descriptor const& u,
0434         typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
0435         typename edge_property_type< Graph >::type const& p, BGL_NAMED_GRAPH& g)
0436     {
0437         return add_edge(u, add_vertex(v_name, g.derived()), p, g.derived());
0438     }
0439
0440     template < BGL_NAMED_GRAPH_PARAMS >
0441     std::pair< typename graph_traits< Graph >::edge_descriptor, bool > add_edge(
0442         typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
0443         typename BGL_NAMED_GRAPH::vertex_descriptor const& v,
0444         typename edge_property_type< Graph >::type const& p, BGL_NAMED_GRAPH& g)
0445     {
0446         return add_edge(add_vertex(u_name, g.derived()), v, p, g.derived());
0447     }
0448
0449     template < BGL_NAMED_GRAPH_PARAMS >
0450     std::pair< typename graph_traits< Graph >::edge_descriptor, bool > add_edge(
0451         typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
0452         typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
0453         typename edge_property_type< Graph >::type const& p, BGL_NAMED_GRAPH& g)
0454     {
0455         return add_edge(add_vertex(u_name, g.derived()),
0456             add_vertex(v_name, g.derived()), p, g.derived());
0457     }
0458
0459 #undef BGL_NAMED_GRAPH
0460 #undef BGL_NAMED_GRAPH_PARAMS
0461
0462     /*******************************************************************
0463      * Maybe named graph mixin                                         *
0464      *******************************************************************/
0465
0466     /**
0467      * A graph mixin that can provide a mapping from names to vertices,
0468      * and use that mapping to simplify creation and manipulation of
0469      * graphs.
0470      */
0471     template < typename Graph, typename Vertex, typename VertexProperty,
0472         typename ExtractName =
0473             typename internal_vertex_name< VertexProperty >::type >
0474     struct maybe_named_graph
0475     : public named_graph< Graph, Vertex, VertexProperty >
0476     {
0477     };
0478
0479     /**
0480      * A graph mixin that can provide a mapping from names to vertices,
0481      * and use that mapping to simplify creation and manipulation of
0482      * graphs. This partial specialization turns off this functionality
0483      * when the @c VertexProperty does not have an internal vertex name.
0484      */
0485     template < typename Graph, typename Vertex, typename VertexProperty >
0486     struct maybe_named_graph< Graph, Vertex, VertexProperty, void >
0487     {
0488         /// The type of the "bundled" property, from which the name can be
0489         /// extracted.
0490         typedef typename lookup_one_property< VertexProperty,
0491             vertex_bundle_t >::type bundled_vertex_property_type;
0492
0493         /// Notify the named_graph that we have added the given vertex. This
0494         /// is a no-op.
0495         void added_vertex(Vertex) {}
0496
0497         /// Notify the named_graph that we are removing the given
0498         /// vertex. This is a no-op.
0499         template < typename VertexIterStability >
0500         void removing_vertex(Vertex, VertexIterStability)
0501         {
0502         }
0503
0504         /// Notify the named_graph that we are clearing the graph. This is a
0505         /// no-op.
0506         void clearing_graph() {}
0507
0508         /// Search for a vertex that has the given property (based on its
0509         /// name). This always returns an empty optional<>
0510         optional< Vertex > vertex_by_property(
0511             const bundled_vertex_property_type&)
0512         {
0513             return optional< Vertex >();
0514         }
0515     };
0516
0517 }
0518 } // end namespace boost::graph
0519
0520 #endif // BOOST_GRAPH_NAMED_GRAPH_HPP