Chris@16: // Copyright (C) 2007 Douglas Gregor
Chris@16: 
Chris@16: // Use, modification and distribution is subject to the Boost Software
Chris@16: // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: // Provides support for named vertices in graphs, allowing one to more
Chris@16: // easily associate unique external names (URLs, city names, employee
Chris@16: // ID numbers, etc.) with the vertices of a graph.
Chris@16: #ifndef BOOST_GRAPH_NAMED_GRAPH_HPP
Chris@16: #define BOOST_GRAPH_NAMED_GRAPH_HPP
Chris@16: 
Chris@16: #include <boost/config.hpp>
Chris@16: #include <boost/static_assert.hpp>
Chris@16: #include <boost/functional/hash.hpp>
Chris@16: #include <boost/graph/graph_traits.hpp>
Chris@16: #include <boost/graph/properties.hpp>
Chris@16: #include <boost/multi_index/hashed_index.hpp>
Chris@16: #include <boost/multi_index/member.hpp>
Chris@16: #include <boost/multi_index_container.hpp>
Chris@16: #include <boost/optional.hpp>
Chris@16: #include <boost/pending/property.hpp> // for boost::lookup_one_property
Chris@16: #include <boost/pending/container_traits.hpp>
Chris@16: #include <boost/throw_exception.hpp>
Chris@16: #include <boost/tuple/tuple.hpp> // for boost::make_tuple
Chris@16: #include <boost/type_traits/is_same.hpp>
Chris@16: #include <boost/type_traits/is_base_of.hpp>
Chris@16: #include <boost/type_traits/remove_cv.hpp>
Chris@16: #include <boost/type_traits/remove_reference.hpp>
Chris@16: #include <boost/utility/enable_if.hpp>
Chris@16: #include <functional> // for std::equal_to
Chris@16: #include <stdexcept> // for std::runtime_error
Chris@16: #include <utility> // for std::pair
Chris@16: 
Chris@16: namespace boost { namespace graph {
Chris@16: 
Chris@16: /*******************************************************************
Chris@16:  * User-customized traits                                          *
Chris@16:  *******************************************************************/
Chris@16: 
Chris@16: /**
Chris@16:  * @brief Trait used to extract the internal vertex name from a vertex
Chris@16:  * property.
Chris@16:  *
Chris@16:  * To enable the use of internal vertex names in a graph type,
Chris@16:  * specialize the @c internal_vertex_name trait for your graph
Chris@16:  * property (e.g., @c a City class, which stores information about the
Chris@16:  * vertices in a road map).
Chris@16:  */
Chris@16: template<typename VertexProperty>
Chris@16: struct internal_vertex_name
Chris@16: {
Chris@16:   /**
Chris@16:    *  The @c type field provides a function object that extracts a key
Chris@16:    *  from the @c VertexProperty. The function object type must have a
Chris@16:    *  nested @c result_type that provides the type of the key. For
Chris@16:    *  more information, see the @c KeyExtractor concept in the
Chris@16:    *  Boost.MultiIndex documentation: @c type must either be @c void
Chris@16:    *  (if @c VertexProperty does not have an internal vertex name) or
Chris@16:    *  a model of @c KeyExtractor.
Chris@16:    */
Chris@16:   typedef void type;
Chris@16: };
Chris@16: 
Chris@16: /**
Chris@16:  * Extract the internal vertex name from a @c property structure by
Chris@16:  * looking at its base.
Chris@16:  */
Chris@16: template<typename Tag, typename T, typename Base>
Chris@16: struct internal_vertex_name<property<Tag, T, Base> >
Chris@16:   : internal_vertex_name<Base> { };
Chris@16: 
Chris@16: /**
Chris@16:  * Construct an instance of @c VertexProperty directly from its
Chris@16:  * name. This function object should be used within the @c
Chris@16:  * internal_vertex_constructor trait.
Chris@16:  */
Chris@16: template<typename VertexProperty>
Chris@16: struct vertex_from_name
Chris@16: {
Chris@16: private:
Chris@16:   typedef typename internal_vertex_name<VertexProperty>::type extract_name_type;
Chris@16: 
Chris@16:   typedef typename remove_cv<
Chris@16:             typename remove_reference<
Chris@16:               typename extract_name_type::result_type>::type>::type
Chris@16:     vertex_name_type;
Chris@16: 
Chris@16: public:
Chris@16:   typedef vertex_name_type argument_type;
Chris@16:   typedef VertexProperty result_type;
Chris@16: 
Chris@16:   VertexProperty operator()(const vertex_name_type& name)
Chris@16:   {
Chris@16:     return VertexProperty(name);
Chris@16:   }
Chris@16: };
Chris@16: 
Chris@16: /**
Chris@16:  * Throw an exception whenever one tries to construct a @c
Chris@16:  * VertexProperty instance from its name.
Chris@16:  */
Chris@16: template<typename VertexProperty>
Chris@16: struct cannot_add_vertex
Chris@16: {
Chris@16: private:
Chris@16:   typedef typename internal_vertex_name<VertexProperty>::type extract_name_type;
Chris@16: 
Chris@16:   typedef typename remove_cv<
Chris@16:             typename remove_reference<
Chris@16:               typename extract_name_type::result_type>::type>::type
Chris@16:     vertex_name_type;
Chris@16: 
Chris@16: public:
Chris@16:   typedef vertex_name_type argument_type;
Chris@16:   typedef VertexProperty result_type;
Chris@16: 
Chris@16:   VertexProperty operator()(const vertex_name_type&)
Chris@16:   {
Chris@16:       boost::throw_exception(std::runtime_error("add_vertex: "
Chris@16:                                                 "unable to create a vertex from its name"));
Chris@16:   }
Chris@16: };
Chris@16: 
Chris@16: /**
Chris@16:  * @brief Trait used to construct an instance of a @c VertexProperty,
Chris@16:  * which is a class type that stores the properties associated with a
Chris@16:  * vertex in a graph, from just the name of that vertex property. This
Chris@16:  * operation is used when an operation is required to map from a
Chris@16:  * vertex name to a vertex descriptor (e.g., to add an edge outgoing
Chris@16:  * from that vertex), but no vertex by the name exists. The function
Chris@16:  * object provided by this trait will be used to add new vertices
Chris@16:  * based only on their names. Since this cannot be done for arbitrary
Chris@16:  * types, the default behavior is to throw an exception when this
Chris@16:  * routine is called, which requires that all named vertices be added
Chris@16:  * before adding any edges by name.
Chris@16:  */
Chris@16: template<typename VertexProperty>
Chris@16: struct internal_vertex_constructor
Chris@16: {
Chris@16:   /**
Chris@16:    * The @c type field provides a function object that constructs a
Chris@16:    * new instance of @c VertexProperty from the name of the vertex (as
Chris@16:    * determined by @c internal_vertex_name). The function object shall
Chris@16:    * accept a vertex name and return a @c VertexProperty. Predefined
Chris@16:    * options include:
Chris@16:    *
Chris@16:    *   @c vertex_from_name<VertexProperty>: construct an instance of
Chris@16:    *   @c VertexProperty directly from the name.
Chris@16:    *
Chris@16:    *   @c cannot_add_vertex<VertexProperty>: the default value, which
Chris@16:    *   throws an @c std::runtime_error if one attempts to add a vertex
Chris@16:    *   given just the name.
Chris@16:    */
Chris@16:   typedef cannot_add_vertex<VertexProperty> type;
Chris@16: };
Chris@16: 
Chris@16: /**
Chris@16:  * Extract the internal vertex constructor from a @c property structure by
Chris@16:  * looking at its base.
Chris@16:  */
Chris@16: template<typename Tag, typename T, typename Base>
Chris@16: struct internal_vertex_constructor<property<Tag, T, Base> >
Chris@16:   : internal_vertex_constructor<Base> { };
Chris@16: 
Chris@16: /*******************************************************************
Chris@16:  * Named graph mixin                                               *
Chris@16:  *******************************************************************/
Chris@16: 
Chris@16: /**
Chris@16:  * named_graph is a mixin that provides names for the vertices of a
Chris@16:  * graph, including a mapping from names to vertices. Graph types that
Chris@16:  * may or may not be have vertex names (depending on the properties
Chris@16:  * supplied by the user) should use maybe_named_graph.
Chris@16:  *
Chris@16:  * Template parameters:
Chris@16:  *
Chris@16:  *   Graph: the graph type that derives from named_graph
Chris@16:  *
Chris@16:  *   Vertex: the type of a vertex descriptor in Graph. Note: we cannot
Chris@16:  *   use graph_traits here, because the Graph is not yet defined.
Chris@16:  *
Chris@16:  *   VertexProperty: the type stored with each vertex in the Graph.
Chris@16:  */
Chris@16: template<typename Graph, typename Vertex, typename VertexProperty>
Chris@16: class named_graph
Chris@16: {
Chris@16: public:
Chris@16:   /// The type of the function object that extracts names from vertex
Chris@16:   /// properties.
Chris@16:   typedef typename internal_vertex_name<VertexProperty>::type extract_name_type;
Chris@16:   /// The type of the "bundled" property, from which the name can be
Chris@16:   /// extracted.
Chris@16:   typedef typename lookup_one_property<VertexProperty, vertex_bundle_t>::type
Chris@16:     bundled_vertex_property_type;
Chris@16: 
Chris@16:   /// The type of the function object that generates vertex properties
Chris@16:   /// from names, for the implicit addition of vertices.
Chris@16:   typedef typename internal_vertex_constructor<VertexProperty>::type
Chris@16:     vertex_constructor_type;
Chris@16: 
Chris@16:   /// The type used to name vertices in the graph
Chris@16:   typedef typename remove_cv<
Chris@16:             typename remove_reference<
Chris@16:               typename extract_name_type::result_type>::type>::type
Chris@16:     vertex_name_type;
Chris@16: 
Chris@16:   /// The type of vertex descriptors in the graph
Chris@16:   typedef Vertex vertex_descriptor;
Chris@16: 
Chris@16: private:
Chris@16:   /// Key extractor for use with the multi_index_container
Chris@16:   struct extract_name_from_vertex
Chris@16:   {
Chris@16:     typedef vertex_name_type result_type;
Chris@16: 
Chris@16:     extract_name_from_vertex(Graph& graph, const extract_name_type& extract)
Chris@16:       : graph(graph), extract(extract) { }
Chris@16: 
Chris@16:     const result_type& operator()(Vertex vertex) const
Chris@16:     {
Chris@16:       return extract(graph[vertex]);
Chris@16:     }
Chris@16: 
Chris@16:     Graph& graph;
Chris@16:     extract_name_type extract;
Chris@16:   };
Chris@16: 
Chris@16: public:
Chris@16:   /// The type that maps names to vertices
Chris@16:   typedef multi_index::multi_index_container<
Chris@16:             Vertex,
Chris@16:             multi_index::indexed_by<
Chris@16:               multi_index::hashed_unique<multi_index::tag<vertex_name_t>,
Chris@16:                                          extract_name_from_vertex> >
Chris@16:           > named_vertices_type;
Chris@16: 
Chris@16:   /// The set of vertices, indexed by name
Chris@16:   typedef typename named_vertices_type::template index<vertex_name_t>::type
Chris@16:     vertices_by_name_type;
Chris@16: 
Chris@16:   /// Construct an instance of the named graph mixin, using the given
Chris@16:   /// function object to extract a name from the bundled property
Chris@16:   /// associated with a vertex.
Chris@16:   named_graph(const extract_name_type& extract = extract_name_type(),
Chris@16:               const vertex_constructor_type& vertex_constructor
Chris@16:                 = vertex_constructor_type());
Chris@16: 
Chris@16:   /// Notify the named_graph that we have added the given vertex. The
Chris@16:   /// name of the vertex will be added to the mapping.
Chris@16:   void added_vertex(Vertex vertex);
Chris@16: 
Chris@16:   /// Notify the named_graph that we are removing the given
Chris@16:   /// vertex. The name of the vertex will be removed from the mapping.
Chris@16:   template <typename VertexIterStability>
Chris@16:   void removing_vertex(Vertex vertex, VertexIterStability);
Chris@16: 
Chris@16:   /// Notify the named_graph that we are clearing the graph.
Chris@16:   /// This will clear out all of the name->vertex mappings
Chris@16:   void clearing_graph();
Chris@16: 
Chris@16:   /// Retrieve the derived instance
Chris@16:   Graph&       derived()       { return static_cast<Graph&>(*this); }
Chris@16:   const Graph& derived() const { return static_cast<const Graph&>(*this); }
Chris@16: 
Chris@16:   /// Extract the name from a vertex property instance
Chris@16:   typename extract_name_type::result_type
Chris@16:   extract_name(const bundled_vertex_property_type& property);
Chris@16: 
Chris@16:   /// Search for a vertex that has the given property (based on its
Chris@16:   /// name)
Chris@16:   optional<vertex_descriptor>
Chris@16:   vertex_by_property(const bundled_vertex_property_type& property);
Chris@16: 
Chris@16:   /// Mapping from names to vertices
Chris@16:   named_vertices_type named_vertices;
Chris@16: 
Chris@16:   /// Constructs a vertex from the name of that vertex
Chris@16:   vertex_constructor_type vertex_constructor;
Chris@16: };
Chris@16: 
Chris@16: /// Helper macro containing the template parameters of named_graph
Chris@16: #define BGL_NAMED_GRAPH_PARAMS \
Chris@16:   typename Graph, typename Vertex, typename VertexProperty
Chris@16: /// Helper macro containing the named_graph<...> instantiation
Chris@16: #define BGL_NAMED_GRAPH \
Chris@16:   named_graph<Graph, Vertex, VertexProperty>
Chris@16: 
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: BGL_NAMED_GRAPH::named_graph(const extract_name_type& extract,
Chris@16:                              const vertex_constructor_type& vertex_constructor)
Chris@16:   : named_vertices(
Chris@16:       typename named_vertices_type::ctor_args_list(
Chris@16:         boost::make_tuple(
Chris@16:           boost::make_tuple(
Chris@16:             0, // initial number of buckets
Chris@16:             extract_name_from_vertex(derived(), extract),
Chris@16:             boost::hash<vertex_name_type>(),
Chris@16:             std::equal_to<vertex_name_type>())))),
Chris@16:     vertex_constructor(vertex_constructor)
Chris@16: {
Chris@16: }
Chris@16: 
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: inline void BGL_NAMED_GRAPH::added_vertex(Vertex vertex)
Chris@16: {
Chris@16:   named_vertices.insert(vertex);
Chris@16: }
Chris@16: 
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: template<typename VertexIterStability>
Chris@16: inline void BGL_NAMED_GRAPH::removing_vertex(Vertex vertex, VertexIterStability)
Chris@16: {
Chris@16:   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.");
Chris@16:   typedef typename BGL_NAMED_GRAPH::vertex_name_type vertex_name_type;
Chris@16:   const vertex_name_type& vertex_name = extract_name(derived()[vertex]);
Chris@16:   named_vertices.erase(vertex_name);
Chris@16: }
Chris@16: 
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: inline void BGL_NAMED_GRAPH::clearing_graph()
Chris@16: {
Chris@16:   named_vertices.clear();
Chris@16: }
Chris@16: 
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: typename BGL_NAMED_GRAPH::extract_name_type::result_type
Chris@16: BGL_NAMED_GRAPH::extract_name(const bundled_vertex_property_type& property)
Chris@16: {
Chris@16:   return named_vertices.key_extractor().extract(property);
Chris@16: }
Chris@16: 
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: optional<typename BGL_NAMED_GRAPH::vertex_descriptor>
Chris@16: BGL_NAMED_GRAPH::
Chris@16: vertex_by_property(const bundled_vertex_property_type& property)
Chris@16: {
Chris@16:   return find_vertex(extract_name(property), *this);
Chris@16: }
Chris@16: 
Chris@16: /// Retrieve the vertex associated with the given name
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: optional<Vertex>
Chris@16: find_vertex(typename BGL_NAMED_GRAPH::vertex_name_type const& name,
Chris@16:             const BGL_NAMED_GRAPH& g)
Chris@16: {
Chris@16:   typedef typename BGL_NAMED_GRAPH::vertices_by_name_type
Chris@16:     vertices_by_name_type;
Chris@16: 
Chris@16:   // Retrieve the set of vertices indexed by name
Chris@16:   vertices_by_name_type const& vertices_by_name
Chris@16:     = g.named_vertices.template get<vertex_name_t>();
Chris@16: 
Chris@16:   /// Look for a vertex with the given name
Chris@16:   typename vertices_by_name_type::const_iterator iter
Chris@16:     = vertices_by_name.find(name);
Chris@16: 
Chris@16:   if (iter == vertices_by_name.end())
Chris@16:     return optional<Vertex>(); // vertex not found
Chris@16:   else
Chris@16:     return *iter;
Chris@16: }
Chris@16: 
Chris@16: /// Retrieve the vertex associated with the given name, or add a new
Chris@16: /// vertex with that name if no such vertex is available.
Chris@16: /// Note: This is enabled only when the vertex property type is different
Chris@16: ///       from the vertex name to avoid ambiguous overload problems with
Chris@16: ///       the add_vertex() function that takes a vertex property.
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16:     typename disable_if<is_same<
Chris@16:         typename BGL_NAMED_GRAPH::vertex_name_type,
Chris@16:         VertexProperty
Chris@16:     >,
Chris@16: Vertex>::type
Chris@16: add_vertex(typename BGL_NAMED_GRAPH::vertex_name_type const& name,
Chris@16:            BGL_NAMED_GRAPH& g)
Chris@16: {
Chris@16:   if (optional<Vertex> vertex = find_vertex(name, g))
Chris@16:     /// We found the vertex, so return it
Chris@16:     return *vertex;
Chris@16:   else
Chris@16:     /// There is no vertex with the given name, so create one
Chris@16:     return add_vertex(g.vertex_constructor(name), g.derived());
Chris@16: }
Chris@16: 
Chris@16: /// Add an edge using vertex names to refer to the vertices
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
Chris@16: add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
Chris@16:          typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
Chris@16:          BGL_NAMED_GRAPH& g)
Chris@16: {
Chris@16:   return add_edge(add_vertex(u_name, g.derived()),
Chris@16:                   add_vertex(v_name, g.derived()),
Chris@16:                   g.derived());
Chris@16: }
Chris@16: 
Chris@16: /// Add an edge using vertex descriptors or names to refer to the vertices
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
Chris@16: add_edge(typename BGL_NAMED_GRAPH::vertex_descriptor const& u,
Chris@16:          typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
Chris@16:          BGL_NAMED_GRAPH& g)
Chris@16: {
Chris@16:   return add_edge(u,
Chris@16:                   add_vertex(v_name, g.derived()),
Chris@16:                   g.derived());
Chris@16: }
Chris@16: 
Chris@16: /// Add an edge using vertex descriptors or names to refer to the vertices
Chris@16: template<BGL_NAMED_GRAPH_PARAMS>
Chris@16: std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
Chris@16: add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
Chris@16:          typename BGL_NAMED_GRAPH::vertex_descriptor const& v,
Chris@16:          BGL_NAMED_GRAPH& g)
Chris@16: {
Chris@16:   return add_edge(add_vertex(u_name, g.derived()),
Chris@16:                   v,
Chris@16:                   g.derived());
Chris@16: }
Chris@16: 
Chris@16: // Overloads to support EdgeMutablePropertyGraph graphs
Chris@16: template <BGL_NAMED_GRAPH_PARAMS>
Chris@16: std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
Chris@16: add_edge(typename BGL_NAMED_GRAPH::vertex_descriptor const& u,
Chris@16:          typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
Chris@16:          typename edge_property_type<Graph>::type const& p,
Chris@16:          BGL_NAMED_GRAPH& g) {
Chris@16:     return add_edge(u, add_vertex(v_name, g.derived()), p, g.derived());
Chris@16: }
Chris@16: 
Chris@16: template <BGL_NAMED_GRAPH_PARAMS>
Chris@16: std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
Chris@16: add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
Chris@16:          typename BGL_NAMED_GRAPH::vertex_descriptor const& v,
Chris@16:          typename edge_property_type<Graph>::type const& p,
Chris@16:          BGL_NAMED_GRAPH& g) {
Chris@16:     return add_edge(add_vertex(u_name, g.derived()), v, p, g.derived());
Chris@16: }
Chris@16: 
Chris@16: template <BGL_NAMED_GRAPH_PARAMS>
Chris@16: std::pair<typename graph_traits<Graph>::edge_descriptor, bool>
Chris@16: add_edge(typename BGL_NAMED_GRAPH::vertex_name_type const& u_name,
Chris@16:          typename BGL_NAMED_GRAPH::vertex_name_type const& v_name,
Chris@16:          typename edge_property_type<Graph>::type const& p,
Chris@16:          BGL_NAMED_GRAPH& g) {
Chris@16:     return add_edge(add_vertex(u_name, g.derived()),
Chris@16:                     add_vertex(v_name, g.derived()), p, g.derived());
Chris@16: }
Chris@16: 
Chris@16: #undef BGL_NAMED_GRAPH
Chris@16: #undef BGL_NAMED_GRAPH_PARAMS
Chris@16: 
Chris@16: /*******************************************************************
Chris@16:  * Maybe named graph mixin                                         *
Chris@16:  *******************************************************************/
Chris@16: 
Chris@16: /**
Chris@16:  * A graph mixin that can provide a mapping from names to vertices,
Chris@16:  * and use that mapping to simplify creation and manipulation of
Chris@16:  * graphs.
Chris@16:  */
Chris@16: template<typename Graph, typename Vertex, typename VertexProperty,
Chris@16:          typename ExtractName
Chris@16:            = typename internal_vertex_name<VertexProperty>::type>
Chris@16: struct maybe_named_graph : public named_graph<Graph, Vertex, VertexProperty>
Chris@16: {
Chris@16: };
Chris@16: 
Chris@16: /**
Chris@16:  * A graph mixin that can provide a mapping from names to vertices,
Chris@16:  * and use that mapping to simplify creation and manipulation of
Chris@16:  * graphs. This partial specialization turns off this functionality
Chris@16:  * when the @c VertexProperty does not have an internal vertex name.
Chris@16:  */
Chris@16: template<typename Graph, typename Vertex, typename VertexProperty>
Chris@16: struct maybe_named_graph<Graph, Vertex, VertexProperty, void>
Chris@16: {
Chris@16:   /// The type of the "bundled" property, from which the name can be
Chris@16:   /// extracted.
Chris@16:   typedef typename lookup_one_property<VertexProperty, vertex_bundle_t>::type
Chris@16:     bundled_vertex_property_type;
Chris@16: 
Chris@16:   /// Notify the named_graph that we have added the given vertex. This
Chris@16:   /// is a no-op.
Chris@16:   void added_vertex(Vertex) { }
Chris@16: 
Chris@16:   /// Notify the named_graph that we are removing the given
Chris@16:   /// vertex. This is a no-op.
Chris@16:   template <typename VertexIterStability>
Chris@16:   void removing_vertex(Vertex, VertexIterStability) { }
Chris@16: 
Chris@16:   /// Notify the named_graph that we are clearing the graph. This is a
Chris@16:   /// no-op.
Chris@16:   void clearing_graph() { }
Chris@16: 
Chris@16:   /// Search for a vertex that has the given property (based on its
Chris@16:   /// name). This always returns an empty optional<>
Chris@16:   optional<Vertex>
Chris@16:   vertex_by_property(const bundled_vertex_property_type&)
Chris@16:   {
Chris@16:     return optional<Vertex>();
Chris@16:   }
Chris@16: };
Chris@16: 
Chris@16: } } // end namespace boost::graph
Chris@16: 
Chris@16: #endif // BOOST_GRAPH_NAMED_GRAPH_HPP