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