Chris@16: // Copyright (C) 2009 Andrew Sutton
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: #ifndef BOOST_GRAPH_LABELED_GRAPH_HPP
Chris@16: #define BOOST_GRAPH_LABELED_GRAPH_HPP
Chris@16: 
Chris@16: #include <boost/config.hpp>
Chris@16: #include <vector>
Chris@16: #include <map>
Chris@16: 
Chris@16: #include <boost/static_assert.hpp>
Chris@16: #include <boost/mpl/if.hpp>
Chris@16: #include <boost/mpl/bool.hpp>
Chris@16: #include <boost/unordered_map.hpp>
Chris@16: #include <boost/type_traits/is_same.hpp>
Chris@16: #include <boost/type_traits/is_unsigned.hpp>
Chris@16: #include <boost/pending/container_traits.hpp>
Chris@16: #include <boost/graph/graph_traits.hpp>
Chris@16: 
Chris@16: // This file implements a utility for creating mappings from arbitrary
Chris@16: // identifiers to the vertices of a graph.
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16: // A type selector that denotes the use of some default value.
Chris@16: struct defaultS { };
Chris@16: 
Chris@16: /** @internal */
Chris@16: namespace graph_detail {
Chris@16:     /** Returns true if the selector is the default selector. */
Chris@16:     template <typename Selector>
Chris@16:     struct is_default
Chris@16:         : mpl::bool_<is_same<Selector, defaultS>::value>
Chris@16:     { };
Chris@16: 
Chris@16:     /**
Chris@16:      * Choose the default map instance. If Label is an unsigned integral type
Chris@16:      * the we can use a vector to store the information.
Chris@16:      */
Chris@16:     template <typename Label, typename Vertex>
Chris@16:     struct choose_default_map {
Chris@16:         typedef typename mpl::if_<
Chris@16:             is_unsigned<Label>,
Chris@16:             std::vector<Vertex>,
Chris@16:             std::map<Label, Vertex> // TODO: Should use unordered_map?
Chris@16:         >::type type;
Chris@16:     };
Chris@16: 
Chris@16:     /**
Chris@16:      * @name Generate Label Map
Chris@16:      * These type generators are responsible for instantiating an associative
Chris@16:      * container for the the labeled graph. Note that the Selector must be
Chris@16:      * select a pair associative container or a vecS, which is only valid if
Chris@16:      * Label is an integral type.
Chris@16:      */
Chris@16:     //@{
Chris@16:     template <typename Selector, typename Label, typename Vertex>
Chris@16:     struct generate_label_map { };
Chris@16: 
Chris@16:     template <typename Label, typename Vertex>
Chris@16:     struct generate_label_map<vecS, Label, Vertex>
Chris@16:     { typedef std::vector<Vertex> type; };
Chris@16: 
Chris@16:     template <typename Label, typename Vertex>
Chris@16:     struct generate_label_map<mapS, Label, Vertex>
Chris@16:     { typedef std::map<Label, Vertex> type; };
Chris@16: 
Chris@16:     template <typename Label, typename Vertex>
Chris@16:     struct generate_label_map<multimapS, Label, Vertex>
Chris@16:     { typedef std::multimap<Label, Vertex> type; };
Chris@16: 
Chris@16:     template <typename Label, typename Vertex>
Chris@16:     struct generate_label_map<hash_mapS, Label, Vertex>
Chris@16:     { typedef boost::unordered_map<Label, Vertex> type; };
Chris@16: 
Chris@16:     template <typename Label, typename Vertex>
Chris@16:     struct generate_label_map<hash_multimapS, Label, Vertex>
Chris@16:     { typedef boost::unordered_multimap<Label, Vertex> type; };
Chris@16: 
Chris@16:     template <typename Selector, typename Label, typename Vertex>
Chris@16:     struct choose_custom_map {
Chris@16:         typedef typename generate_label_map<Selector, Label, Vertex>::type type;
Chris@16:     };
Chris@16:     //@}
Chris@16: 
Chris@16:     /**
Chris@16:      * Choose and instantiate an "associative" container. Note that this can
Chris@16:      * also choose vector.
Chris@16:      */
Chris@16:     template <typename Selector, typename Label, typename Vertex>
Chris@16:     struct choose_map {
Chris@16:         typedef typename mpl::eval_if<
Chris@16:             is_default<Selector>,
Chris@16:             choose_default_map<Label, Vertex>,
Chris@16:             choose_custom_map<Selector, Label, Vertex>
Chris@16:         >::type type;
Chris@16:     };
Chris@16: 
Chris@16:     /** @name Insert Labeled Vertex */
Chris@16:     //@{
Chris@16:     // Tag dispatch on random access containers (i.e., vectors). This function
Chris@16:     // basically requires a) that Container is vector<Label> and that Label
Chris@16:     // is an unsigned integral value. Note that this will resize the vector
Chris@16:     // to accommodate indices.
Chris@16:     template <typename Container, typename Graph, typename Label, typename Prop>
Chris@16:     std::pair<typename graph_traits<Graph>::vertex_descriptor, bool>
Chris@16:     insert_labeled_vertex(Container& c, Graph& g, Label const& l, Prop const& p,
Chris@16:                           random_access_container_tag)
Chris@16:     {
Chris@16:         typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
Chris@16: 
Chris@16:         // If the label is out of bounds, resize the vector to accommodate.
Chris@16:         // Resize by 2x the index so we don't cause quadratic insertions over
Chris@16:         // time.
Chris@16:         if(l >= c.size()) {
Chris@16:             c.resize((l + 1) * 2);
Chris@16:         }
Chris@16:         Vertex v = add_vertex(p, g);
Chris@16:         c[l] = v;
Chris@16:         return std::make_pair(c[l], true);
Chris@16:     }
Chris@16: 
Chris@16:     // Tag dispatch on multi associative containers (i.e. multimaps).
Chris@16:     template <typename Container, typename Graph, typename Label, typename Prop>
Chris@16:     std::pair<typename graph_traits<Graph>::vertex_descriptor, bool>
Chris@16:     insert_labeled_vertex(Container& c, Graph& g, Label const& l, Prop const& p,
Chris@16:                           multiple_associative_container_tag const&)
Chris@16:     {
Chris@16:         // Note that insertion always succeeds so we can add the vertex first
Chris@16:         // and then the mapping to the label.
Chris@16:         typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
Chris@16:         Vertex v = add_vertex(g);
Chris@16:         c.insert(std::make_pair(l, v));
Chris@16:         return std::make_pair(v, true);
Chris@16:     }
Chris@16: 
Chris@16:     // Tag dispatch on unique associative containers (i.e. maps).
Chris@16:     template <typename Container, typename Graph, typename Label, typename Prop>
Chris@16:     std::pair<typename graph_traits<Graph>::vertex_descriptor, bool>
Chris@16:     insert_labeled_vertex(Container& c, Graph& g, Label const& l, Prop const& p,
Chris@16:                           unique_associative_container_tag)
Chris@16:     {
Chris@16:         // Here, we actually have to try the insertion first, and only add
Chris@16:         // the vertex if we get a new element.
Chris@16:         typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
Chris@16:         typedef typename Container::iterator Iterator;
Chris@16:         std::pair<Iterator, bool> x = c.insert(std::make_pair(l, Vertex()));
Chris@16:         if(x.second) {
Chris@16:             x.first->second = add_vertex(g);
Chris@16:             put(boost::vertex_all, g, x.first->second, p);
Chris@16:         }
Chris@16:         return std::make_pair(x.first->second, x.second);
Chris@16:     }
Chris@16: 
Chris@16:     // Dispatcher
Chris@16:     template <typename Container, typename Graph, typename Label, typename Prop>
Chris@16:     std::pair<typename graph_traits<Graph>::vertex_descriptor, bool>
Chris@16:     insert_labeled_vertex(Container& c, Graph& g, Label const& l, Prop const& p)
Chris@16:     { return insert_labeled_vertex(c, g, l, p, container_category(c)); }
Chris@16:     //@}
Chris@16: 
Chris@16:     /** @name Find Labeled Vertex */
Chris@16:     //@{
Chris@16:     // Tag dispatch for sequential maps (i.e., vectors).
Chris@16:     template <typename Container, typename Graph, typename Label>
Chris@16:     typename graph_traits<Graph>::vertex_descriptor
Chris@16:     find_labeled_vertex(Container const& c, Graph const&, Label const& l,
Chris@16:                         random_access_container_tag)
Chris@16:     { return l < c.size() ? c[l] : graph_traits<Graph>::null_vertex(); }
Chris@16: 
Chris@16:     // Tag dispatch for pair associative maps (more or less).
Chris@16:     template <typename Container, typename Graph, typename Label>
Chris@16:     typename graph_traits<Graph>::vertex_descriptor
Chris@16:     find_labeled_vertex(Container const& c, Graph const&, Label const& l,
Chris@16:                         associative_container_tag)
Chris@16:     {
Chris@16:         typename Container::const_iterator i = c.find(l);
Chris@16:         return i != c.end() ? i->second : graph_traits<Graph>::null_vertex();
Chris@16:     }
Chris@16: 
Chris@16:     // Dispatcher
Chris@16:     template <typename Container, typename Graph, typename Label>
Chris@16:     typename graph_traits<Graph>::vertex_descriptor
Chris@16:     find_labeled_vertex(Container const& c, Graph const& g, Label const& l)
Chris@16:     { return find_labeled_vertex(c, g, l, container_category(c)); }
Chris@16:     //@}
Chris@16: 
Chris@16:     /** @name Put Vertex Label */
Chris@16:     //@{
Chris@16:     // Tag dispatch on vectors.
Chris@16:     template <typename Container, typename Label, typename Graph, typename Vertex>
Chris@16:     bool put_vertex_label(Container& c, Graph const&, Label const& l, Vertex v,
Chris@16:                           random_access_container_tag)
Chris@16:     {
Chris@16:         // If the element is already occupied, then we probably don't want to
Chris@16:         // overwrite it.
Chris@16:         if(c[l] == graph_traits<Graph>::null_vertex()) return false;
Chris@16:         c[l] = v;
Chris@16:         return true;
Chris@16:     }
Chris@16: 
Chris@16:     // Attempt the insertion and return its result.
Chris@16:     template <typename Container, typename Label, typename Graph, typename Vertex>
Chris@16:     bool put_vertex_label(Container& c, Graph const&, Label const& l, Vertex v,
Chris@16:                           unique_associative_container_tag)
Chris@16:     { return c.insert(std::make_pair(l, v)).second; }
Chris@16: 
Chris@16:     // Insert the pair and return true.
Chris@16:     template <typename Container, typename Label, typename Graph, typename Vertex>
Chris@16:     bool put_vertex_label(Container& c, Graph const&, Label const& l, Vertex v,
Chris@16:                           multiple_associative_container_tag)
Chris@16:     {
Chris@16:         c.insert(std::make_pair(l, v));
Chris@16:         return true;
Chris@16:     }
Chris@16: 
Chris@16:     // Dispatcher
Chris@16:     template <typename Container, typename Label, typename Graph, typename Vertex>
Chris@16:     bool put_vertex_label(Container& c, Graph const& g, Label const& l, Vertex v)
Chris@16:     { return put_vertex_label(c, g, l, v, container_category(c)); }
Chris@16:     //@}
Chris@16: 
Chris@16: } // namespace detail
Chris@16: 
Chris@16: struct labeled_graph_class_tag { };
Chris@16: 
Chris@16: /** @internal
Chris@16:  * This class is responsible for the deduction and declaration of type names
Chris@16:  * for the labeled_graph class template.
Chris@16:  */
Chris@16: template <typename Graph, typename Label, typename Selector>
Chris@16: struct labeled_graph_types {
Chris@16:     typedef Graph graph_type;
Chris@16: 
Chris@16:     // Label and maps
Chris@16:     typedef Label label_type;
Chris@16:     typedef typename graph_detail::choose_map<
Chris@16:         Selector, Label, typename graph_traits<Graph>::vertex_descriptor
Chris@16:     >::type map_type;
Chris@16: };
Chris@16: 
Chris@16: /**
Chris@16:  * The labeled_graph class is a graph adaptor that maintains a mapping between
Chris@16:  * vertex labels and vertex descriptors.
Chris@16:  *
Chris@16:  * @todo This class is somewhat redundant for adjacency_list<*, vecS>  if
Chris@16:  * the intended label is an unsigned int (and perhaps some other cases), but
Chris@16:  * it does avoid some weird ambiguities (i.e. adding a vertex with a label that
Chris@16:  * does not match its target index).
Chris@16:  *
Chris@16:  * @todo This needs to be reconciled with the named_graph, but since there is
Chris@16:  * no documentation or examples, its not going to happen.
Chris@16:  */
Chris@16: template <typename Graph, typename Label, typename Selector = defaultS>
Chris@16: class labeled_graph
Chris@16:     : protected labeled_graph_types<Graph, Label, Selector>
Chris@16: {
Chris@16:     typedef labeled_graph_types<Graph, Label, Selector> Base;
Chris@16: public:
Chris@16:     typedef labeled_graph_class_tag graph_tag;
Chris@16: 
Chris@16:     typedef typename Base::graph_type graph_type;
Chris@16:     typedef typename graph_traits<graph_type>::vertex_descriptor vertex_descriptor;
Chris@16:     typedef typename graph_traits<graph_type>::edge_descriptor edge_descriptor;
Chris@16:     typedef typename graph_traits<graph_type>::directed_category directed_category;
Chris@16:     typedef typename graph_traits<graph_type>::edge_parallel_category edge_parallel_category;
Chris@16:     typedef typename graph_traits<graph_type>::traversal_category traversal_category;
Chris@16: 
Chris@16:     typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
Chris@16:     typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
Chris@16:     typedef typename graph_traits<graph_type>::adjacency_iterator adjacency_iterator;
Chris@16:     typedef typename graph_traits<graph_type>::degree_size_type degree_size_type;
Chris@16: 
Chris@16:     typedef typename graph_traits<graph_type>::vertex_iterator vertex_iterator;
Chris@16:     typedef typename graph_traits<graph_type>::vertices_size_type vertices_size_type;
Chris@16:     typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
Chris@16:     typedef typename graph_traits<graph_type>::edges_size_type edges_size_type;
Chris@16: 
Chris@16:     typedef typename graph_type::graph_property_type graph_property_type;
Chris@16:     typedef typename graph_type::graph_bundled graph_bundled;
Chris@16: 
Chris@16:     typedef typename graph_type::vertex_property_type vertex_property_type;
Chris@16:     typedef typename graph_type::vertex_bundled vertex_bundled;
Chris@16: 
Chris@16:     typedef typename graph_type::edge_property_type edge_property_type;
Chris@16:     typedef typename graph_type::edge_bundled edge_bundled;
Chris@16: 
Chris@16:     typedef typename Base::label_type label_type;
Chris@16:     typedef typename Base::map_type map_type;
Chris@16: 
Chris@16: public:
Chris@16:     labeled_graph(graph_property_type const& gp = graph_property_type())
Chris@16:         : _graph(gp), _map()
Chris@16:     { }
Chris@16: 
Chris@16:     labeled_graph(labeled_graph const& x)
Chris@16:         : _graph(x._graph), _map(x._map)
Chris@16:     { }
Chris@16: 
Chris@16:     // This constructor can only be used if map_type supports positional
Chris@16:     // range insertion (i.e. its a vector). This is the only case where we can
Chris@16:     // try to guess the intended labels for graph.
Chris@16:     labeled_graph(vertices_size_type n,
Chris@16:                   graph_property_type const& gp = graph_property_type())
Chris@16:         : _graph(n, gp), _map()
Chris@16:     {
Chris@16:         std::pair<vertex_iterator, vertex_iterator> rng = vertices(_graph);
Chris@16:         _map.insert(_map.end(), rng.first, rng.second);
Chris@16:     }
Chris@16: 
Chris@16:     // Construct a graph over n vertices, each of which receives a label from
Chris@16:     // the range [l, l + n). Note that the graph is not directly constructed
Chris@16:     // over the n vertices, but added sequentially. This constructor is
Chris@16:     // necessarily slower than the underlying counterpart.
Chris@16:     template <typename LabelIter>
Chris@16:     labeled_graph(vertices_size_type n, LabelIter l,
Chris@16:                   graph_property_type const& gp = graph_property_type())
Chris@16:         : _graph(gp)
Chris@16:     { while(n-- >= 0) add_vertex(*l++); }
Chris@16: 
Chris@16:     // Construct the graph over n vertices each of which has a label in the
Chris@16:     // range [l, l + n) and a property in the range [p, p + n).
Chris@16:     template <typename LabelIter, typename PropIter>
Chris@16:     labeled_graph(vertices_size_type n, LabelIter l, PropIter p,
Chris@16:                   graph_property_type const& gp = graph_property_type())
Chris@16:     { while(n-- >= 0) add_vertex(*l++, *p++); }
Chris@16: 
Chris@16:     labeled_graph& operator=(labeled_graph const& x) {
Chris@16:         _graph = x._graph;
Chris@16:         _map = x._map;
Chris@16:         return *this;
Chris@16:     }
Chris@16: 
Chris@16:     /** @name Graph Accessors */
Chris@16:     //@{
Chris@16:     graph_type& graph() { return _graph; }
Chris@16:     graph_type const& graph() const { return _graph; }
Chris@16:     //@}
Chris@16: 
Chris@16:     /**
Chris@16:      * Create a new label for the given vertex, returning false, if the label
Chris@16:      * cannot be created.
Chris@16:      */
Chris@16:     bool label_vertex(vertex_descriptor v, Label const& l)
Chris@16:     { return graph_detail::put_vertex_label(_map, _graph, l, v); }
Chris@16: 
Chris@16:     /** @name Add Vertex
Chris@16:      * Add a vertex to the graph, returning the descriptor. If the vertices
Chris@16:      * are uniquely labeled and the label already exists within the graph,
Chris@16:      * then no vertex is added, and the returned descriptor refers to the
Chris@16:      * existing vertex. A vertex property can be given as a parameter, if
Chris@16:      * needed.
Chris@16:      */
Chris@16:     //@{
Chris@16:     vertex_descriptor add_vertex(Label const& l) {
Chris@16:         return graph_detail::insert_labeled_vertex(
Chris@16:             _map, _graph, l, vertex_property_type()
Chris@16:             ).first;
Chris@16:     }
Chris@16: 
Chris@16:     vertex_descriptor add_vertex(Label const& l, vertex_property_type const& p)
Chris@16:     { return graph_detail::insert_labeled_vertex(_map, _graph, l, p).first; }
Chris@16:     //@}
Chris@16: 
Chris@16:     /** @name Insert Vertex
Chris@16:      * Insert a vertex into the graph, returning a pair containing the
Chris@16:      * descriptor of a vertex and a boolean value that describes whether or not
Chris@16:      * a new vertex was inserted. If vertices are not uniquely labeled, then
Chris@16:      * insertion will always succeed.
Chris@16:      */
Chris@16:     //@{
Chris@16:     std::pair<vertex_descriptor, bool> insert_vertex(Label const& l) {
Chris@16:         return graph_detail::insert_labeled_vertex(
Chris@16:             _map, _graph, l, vertex_property_type()
Chris@16:         );
Chris@16:     }
Chris@16: 
Chris@16:     std::pair<vertex_descriptor, bool>
Chris@16:     insert_vertex(Label const& l, vertex_property_type const& p)
Chris@16:     { return graph_detail::insert_labeled_vertex(_map, _graph, l, p); }
Chris@16:     //@}
Chris@16: 
Chris@16:     /** Remove the vertex with the given label. */
Chris@16:     void remove_vertex(Label const& l)
Chris@16:     { return boost::remove_vertex(vertex(l), _graph); }
Chris@16: 
Chris@16:     /** Return a descriptor for the given label. */
Chris@16:     vertex_descriptor vertex(Label const& l) const
Chris@16:     { return graph_detail::find_labeled_vertex(_map, _graph, l); }
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
Chris@16:     /** @name Bundled Properties */
Chris@16:     //@{
Chris@16:     // Lookup the requested vertex and return the bundle.
Chris@16:     vertex_bundled& operator[](Label const& l)
Chris@16:     { return _graph[vertex(l)]; }
Chris@16: 
Chris@16:     vertex_bundled const& operator[](Label const& l) const
Chris@16:     { return _graph[vertex(l)]; }
Chris@16: 
Chris@16:     // Delegate edge lookup to the underlying graph.
Chris@16:     edge_bundled& operator[](edge_descriptor e)
Chris@16:     { return _graph[e]; }
Chris@16: 
Chris@16:     edge_bundled const& operator[](edge_descriptor e) const
Chris@16:     { return _graph[e]; }
Chris@16:     //@}
Chris@16: #endif
Chris@16: 
Chris@16:     /** Return a null descriptor */
Chris@16:     static vertex_descriptor null_vertex()
Chris@16:     { return graph_traits<graph_type>::null_vertex(); }
Chris@16: 
Chris@16: private:
Chris@16:     graph_type _graph;
Chris@16:     map_type _map;
Chris@16: };
Chris@16: 
Chris@16: /**
Chris@16:  * The partial specialization over graph pointers allows the construction
Chris@16:  * of temporary labeled graph objects. In this case, the labels are destructed
Chris@16:  * when the wrapper goes out of scope.
Chris@16:  */
Chris@16: template <typename Graph, typename Label, typename Selector>
Chris@16: class labeled_graph<Graph*, Label, Selector>
Chris@16:     : protected labeled_graph_types<Graph, Label, Selector>
Chris@16: {
Chris@16:     typedef labeled_graph_types<Graph, Label, Selector> Base;
Chris@16: public:
Chris@16:     typedef labeled_graph_class_tag graph_tag;
Chris@16: 
Chris@16:     typedef typename Base::graph_type graph_type;
Chris@16:     typedef typename graph_traits<graph_type>::vertex_descriptor vertex_descriptor;
Chris@16:     typedef typename graph_traits<graph_type>::edge_descriptor edge_descriptor;
Chris@16:     typedef typename graph_traits<graph_type>::directed_category directed_category;
Chris@16:     typedef typename graph_traits<graph_type>::edge_parallel_category edge_parallel_category;
Chris@16:     typedef typename graph_traits<graph_type>::traversal_category traversal_category;
Chris@16: 
Chris@16:     typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
Chris@16:     typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
Chris@16:     typedef typename graph_traits<graph_type>::adjacency_iterator adjacency_iterator;
Chris@16:     typedef typename graph_traits<graph_type>::degree_size_type degree_size_type;
Chris@16: 
Chris@16:     typedef typename graph_traits<graph_type>::vertex_iterator vertex_iterator;
Chris@16:     typedef typename graph_traits<graph_type>::vertices_size_type vertices_size_type;
Chris@16:     typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
Chris@16:     typedef typename graph_traits<graph_type>::edges_size_type edges_size_type;
Chris@16: 
Chris@16:     typedef typename graph_type::vertex_property_type vertex_property_type;
Chris@16:     typedef typename graph_type::edge_property_type edge_property_type;
Chris@16:     typedef typename graph_type::graph_property_type graph_property_type;
Chris@16:     typedef typename graph_type::vertex_bundled vertex_bundled;
Chris@16:     typedef typename graph_type::edge_bundled edge_bundled;
Chris@16: 
Chris@16:     typedef typename Base::label_type label_type;
Chris@16:     typedef typename Base::map_type map_type;
Chris@16: 
Chris@16:     labeled_graph(graph_type* g)
Chris@16:         : _graph(g)
Chris@16:     { }
Chris@16: 
Chris@16:     /** @name Graph Access */
Chris@16:     //@{
Chris@16:     graph_type& graph() { return *_graph; }
Chris@16:     graph_type const& graph() const { return *_graph; }
Chris@16:     //@}
Chris@16: 
Chris@16:     /**
Chris@16:      * Create a new label for the given vertex, returning false, if the label
Chris@16:      * cannot be created.
Chris@16:      */
Chris@16:     bool label_vertex(vertex_descriptor v, Label const& l)
Chris@16:     { return graph_detail::put_vertex_label(_map, *_graph, l, v); }
Chris@16: 
Chris@16:     /** @name Add Vertex */
Chris@16:     //@{
Chris@16:     vertex_descriptor add_vertex(Label const& l) {
Chris@16:         return graph_detail::insert_labeled_vertex(
Chris@16:             _map, *_graph, l, vertex_property_type()
Chris@16:             ).first;
Chris@16:     }
Chris@16: 
Chris@16:     vertex_descriptor add_vertex(Label const& l, vertex_property_type const& p)
Chris@16:     { return graph_detail::insert_labeled_vertex(_map, *_graph, l, p).first; }
Chris@16: 
Chris@16:     std::pair<vertex_descriptor, bool> insert_vertex(Label const& l) {
Chris@16:         return graph_detail::insert_labeled_vertex(
Chris@16:             _map, *_graph, l, vertex_property_type()
Chris@16:         );
Chris@16:     }
Chris@16:     //@}
Chris@16: 
Chris@16:     /** Try to insert a vertex with the given label. */
Chris@16:     std::pair<vertex_descriptor, bool>
Chris@16:     insert_vertex(Label const& l, vertex_property_type const& p)
Chris@16:     { return graph_detail::insert_labeled_vertex(_map, *_graph, l, p); }
Chris@16: 
Chris@16:     /** Remove the vertex with the given label. */
Chris@16:     void remove_vertex(Label const& l)
Chris@16:     { return boost::remove_vertex(vertex(l), *_graph); }
Chris@16: 
Chris@16:     /** Return a descriptor for the given label. */
Chris@16:     vertex_descriptor vertex(Label const& l) const
Chris@16:     { return graph_detail::find_labeled_vertex(_map, *_graph, l); }
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
Chris@16:     /** @name Bundled Properties */
Chris@16:     //@{
Chris@16:     // Lookup the requested vertex and return the bundle.
Chris@16:     vertex_bundled& operator[](Label const& l)
Chris@16:     { return (*_graph)[vertex(l)]; }
Chris@16: 
Chris@16:     vertex_bundled const& operator[](Label const& l) const
Chris@16:     { return (*_graph)[vertex(l)]; }
Chris@16: 
Chris@16:     // Delegate edge lookup to the underlying graph.
Chris@16:     edge_bundled& operator[](edge_descriptor e)
Chris@16:     { return (*_graph)[e]; }
Chris@16: 
Chris@16:     edge_bundled const& operator[](edge_descriptor e) const
Chris@16:     { return (*_graph)[e]; }
Chris@16:     //@}
Chris@16: #endif
Chris@16: 
Chris@16:     static vertex_descriptor null_vertex()
Chris@16:     { return graph_traits<graph_type>::null_vertex(); }
Chris@16: 
Chris@16: private:
Chris@16:     graph_type* _graph;
Chris@16:     map_type _map;
Chris@16: };
Chris@16: 
Chris@16: #define LABELED_GRAPH_PARAMS typename G, typename L, typename S
Chris@16: #define LABELED_GRAPH labeled_graph<G,L,S>
Chris@16: 
Chris@16: /** @name Labeled Graph */
Chris@16: //@{
Chris@16: template <LABELED_GRAPH_PARAMS>
Chris@16: inline bool label_vertex(typename LABELED_GRAPH::vertex_descriptor v,
Chris@16:                          typename LABELED_GRAPH::label_type const l,
Chris@16:                          LABELED_GRAPH& g)
Chris@16: { return g.label_vertex(v, l); }
Chris@16: 
Chris@16: template <LABELED_GRAPH_PARAMS>
Chris@16: inline typename LABELED_GRAPH::vertex_descriptor
Chris@16: vertex_by_label(typename LABELED_GRAPH::label_type const l,
Chris@16:                 LABELED_GRAPH& g)
Chris@16: { return g.vertex(l); }
Chris@16: //@}
Chris@16: 
Chris@16: /** @name Graph */
Chris@16: //@{
Chris@16: template <LABELED_GRAPH_PARAMS>
Chris@16: inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool>
Chris@16: edge(typename LABELED_GRAPH::vertex_descriptor const& u,
Chris@16:      typename LABELED_GRAPH::vertex_descriptor const& v,
Chris@16:      LABELED_GRAPH const& g)
Chris@16: { return edge(u, v, g.graph()); }
Chris@16: 
Chris@16: // Labeled Extensions
Chris@16: template <LABELED_GRAPH_PARAMS>
Chris@16: inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool>
Chris@16: edge_by_label(typename LABELED_GRAPH::label_type const& u,
Chris@16:               typename LABELED_GRAPH::label_type const& v,
Chris@16:               LABELED_GRAPH const& g)
Chris@16: { return edge(g.vertex(u), g.vertex(v), g); }
Chris@16: //@}
Chris@16: 
Chris@16: /** @name Incidence Graph */
Chris@16: //@{
Chris@16: template <LABELED_GRAPH_PARAMS>
Chris@16: inline std::pair<
Chris@16:     typename LABELED_GRAPH::out_edge_iterator,
Chris@16:     typename LABELED_GRAPH::out_edge_iterator>
Chris@16: out_edges(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g)
Chris@16: { return out_edges(v, g.graph()); }
Chris@16: 
Chris@16: template <LABELED_GRAPH_PARAMS>
Chris@16: inline typename LABELED_GRAPH::degree_size_type
Chris@16: out_degree(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g)
Chris@16: { return out_degree(v, g.graph()); }
Chris@16: 
Chris@16: template <LABELED_GRAPH_PARAMS>
Chris@16: inline typename LABELED_GRAPH::vertex_descriptor
Chris@16: source(typename LABELED_GRAPH::edge_descriptor e, LABELED_GRAPH const& g)
Chris@16: { return source(e, g.graph()); }
Chris@16: 
Chris@16: template <LABELED_GRAPH_PARAMS>
Chris@16: inline typename LABELED_GRAPH::vertex_descriptor
Chris@16: target(typename LABELED_GRAPH::edge_descriptor e, LABELED_GRAPH const& g)
Chris@16: { return target(e, g.graph()); }
Chris@16: //@}
Chris@16: 
Chris@16: /** @name Bidirectional Graph */
Chris@16: //@{
Chris@16: template <LABELED_GRAPH_PARAMS>
Chris@16: inline std::pair<
Chris@16:     typename LABELED_GRAPH::in_edge_iterator,
Chris@16:     typename LABELED_GRAPH::in_edge_iterator>
Chris@16: in_edges(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g)
Chris@16: { return in_edges(v, g.graph()); }
Chris@16: 
Chris@16: template <LABELED_GRAPH_PARAMS>
Chris@16: inline typename LABELED_GRAPH::degree_size_type
Chris@16: in_degree(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g)
Chris@16: { return in_degree(v, g.graph()); }
Chris@16: 
Chris@16: template <LABELED_GRAPH_PARAMS>
Chris@16: inline typename LABELED_GRAPH::degree_size_type
Chris@16: degree(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g)
Chris@16: { return degree(v, g.graph()); }
Chris@16: //@}
Chris@16: 
Chris@16: /** @name Adjacency Graph */
Chris@16: //@{
Chris@16: template <LABELED_GRAPH_PARAMS>
Chris@16: inline std::pair<
Chris@16:     typename LABELED_GRAPH::adjacency_iterator,
Chris@16:     typename LABELED_GRAPH::adjacency_iterator>
Chris@16: adjacenct_vertices(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g)
Chris@16: { return adjacent_vertices(v, g.graph()); }
Chris@16: //@}
Chris@16: 
Chris@16: /** @name VertexListGraph */
Chris@16: //@{
Chris@16: template <LABELED_GRAPH_PARAMS>
Chris@16: inline std::pair<
Chris@16:     typename LABELED_GRAPH::vertex_iterator,
Chris@16:     typename LABELED_GRAPH::vertex_iterator>
Chris@16: vertices(LABELED_GRAPH const& g)
Chris@16: { return vertices(g.graph()); }
Chris@16: 
Chris@16: template <LABELED_GRAPH_PARAMS>
Chris@16: inline typename LABELED_GRAPH::vertices_size_type
Chris@16: num_vertices(LABELED_GRAPH const& g)
Chris@16: { return num_vertices(g.graph()); }
Chris@16: //@}
Chris@16: 
Chris@16: /** @name EdgeListGraph */
Chris@16: //@{
Chris@16: template <LABELED_GRAPH_PARAMS>
Chris@16: inline std::pair<
Chris@16:     typename LABELED_GRAPH::edge_iterator,
Chris@16:     typename LABELED_GRAPH::edge_iterator>
Chris@16: edges(LABELED_GRAPH const& g)
Chris@16: { return edges(g.graph()); }
Chris@16: 
Chris@16: template <LABELED_GRAPH_PARAMS>
Chris@16: inline typename LABELED_GRAPH::edges_size_type
Chris@16: num_edges(LABELED_GRAPH const& g)
Chris@16: { return num_edges(g.graph()); }
Chris@16: //@}
Chris@16: 
Chris@16: /** @internal @name Property Lookup */
Chris@16: //@{
Chris@16: namespace graph_detail {
Chris@16:     struct labeled_graph_vertex_property_selector {
Chris@16:         template <class LabeledGraph, class Property, class Tag>
Chris@16:         struct bind_ {
Chris@16:             typedef typename LabeledGraph::graph_type Graph;
Chris@16:             typedef property_map<Graph, Tag> PropertyMap;
Chris@16:             typedef typename PropertyMap::type type;
Chris@16:             typedef typename PropertyMap::const_type const_type;
Chris@16:         };
Chris@16:     };
Chris@16: 
Chris@16:     struct labeled_graph_edge_property_selector {
Chris@16:         template <class LabeledGraph, class Property, class Tag>
Chris@16:         struct bind_ {
Chris@16:             typedef typename LabeledGraph::graph_type Graph;
Chris@16:             typedef property_map<Graph, Tag> PropertyMap;
Chris@16:             typedef typename PropertyMap::type type;
Chris@16:             typedef typename PropertyMap::const_type const_type;
Chris@16:         };
Chris@16:     };
Chris@16: }
Chris@16: 
Chris@16: template <>
Chris@16: struct vertex_property_selector<labeled_graph_class_tag> {
Chris@16:     typedef graph_detail::labeled_graph_vertex_property_selector type;
Chris@16: };
Chris@16: 
Chris@16: template <>
Chris@16: struct edge_property_selector<labeled_graph_class_tag> {
Chris@16:     typedef graph_detail::labeled_graph_edge_property_selector type;
Chris@16: };
Chris@16: //@}
Chris@16: 
Chris@16: /** @name Property Graph */
Chris@16: //@{
Chris@16: template <LABELED_GRAPH_PARAMS, typename Prop>
Chris@16: inline typename property_map<LABELED_GRAPH, Prop>::type
Chris@16: get(Prop p, LABELED_GRAPH& g)
Chris@16: { return get(p, g.graph()); }
Chris@16: 
Chris@16: template <LABELED_GRAPH_PARAMS, typename Prop>
Chris@16: inline typename property_map<LABELED_GRAPH, Prop>::const_type
Chris@16: get(Prop p, LABELED_GRAPH const& g)
Chris@16: { return get(p, g.graph()); }
Chris@16: 
Chris@16: template <LABELED_GRAPH_PARAMS, typename Prop, typename Key>
Chris@16: inline typename property_traits<
Chris@16:     typename property_map<typename LABELED_GRAPH::graph_type, Prop>::const_type
Chris@16: >::value_type
Chris@16: get(Prop p, LABELED_GRAPH const& g, const Key& k)
Chris@16: { return get(p, g.graph(), k); }
Chris@16: 
Chris@16: template <LABELED_GRAPH_PARAMS, typename Prop, typename Key, typename Value>
Chris@16: inline void
Chris@16: put(Prop p, LABELED_GRAPH& g, Key const& k, Value const& v)
Chris@16: { put(p, g.graph(), k, v); }
Chris@16: //@}
Chris@16: 
Chris@16: /** @name Mutable Graph */
Chris@16: //@{
Chris@16: template <LABELED_GRAPH_PARAMS>
Chris@16: inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool>
Chris@16: add_edge(typename LABELED_GRAPH::vertex_descriptor const& u,
Chris@16:          typename LABELED_GRAPH::vertex_descriptor const& v,
Chris@16:          LABELED_GRAPH& g)
Chris@16: { return add_edge(u, v, g.graph()); }
Chris@16: 
Chris@16: template <LABELED_GRAPH_PARAMS>
Chris@16: inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool>
Chris@16: add_edge(typename LABELED_GRAPH::vertex_descriptor const& u,
Chris@16:          typename LABELED_GRAPH::vertex_descriptor const& v,
Chris@16:          typename LABELED_GRAPH::edge_property_type const& p,
Chris@16:          LABELED_GRAPH& g)
Chris@16: { return add_edge(u, v, p, g.graph()); }
Chris@16: 
Chris@16: template <LABELED_GRAPH_PARAMS>
Chris@16: inline void
Chris@16: clear_vertex(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH& g)
Chris@16: { return clear_vertex(v, g.graph()); }
Chris@16: 
Chris@16: template <LABELED_GRAPH_PARAMS>
Chris@16: inline void
Chris@16: remove_edge(typename LABELED_GRAPH::edge_descriptor e, LABELED_GRAPH& g)
Chris@16: { return remove_edge(e, g.graph()); }
Chris@16: 
Chris@16: template <LABELED_GRAPH_PARAMS>
Chris@16: inline void
Chris@16: remove_edge(typename LABELED_GRAPH::vertex_descriptor u,
Chris@16:             typename LABELED_GRAPH::vertex_descriptor v,
Chris@16:             LABELED_GRAPH& g)
Chris@16: { return remove_edge(u, v, g.graph()); }
Chris@16: 
Chris@16: // Labeled extensions
Chris@16: template <LABELED_GRAPH_PARAMS>
Chris@16: inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool>
Chris@16: add_edge_by_label(typename LABELED_GRAPH::label_type const& u,
Chris@16:                   typename LABELED_GRAPH::label_type const& v,
Chris@16:                   LABELED_GRAPH& g)
Chris@16: { return add_edge(g.vertex(u), g.vertex(v), g); }
Chris@16: 
Chris@16: template <LABELED_GRAPH_PARAMS>
Chris@16: inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool>
Chris@16: add_edge_by_label(typename LABELED_GRAPH::label_type const& u,
Chris@16:                   typename LABELED_GRAPH::label_type const& v,
Chris@16:                   typename LABELED_GRAPH::edge_property_type const& p,
Chris@16:                   LABELED_GRAPH& g)
Chris@16: { return add_edge(g.vertex(u), g.vertex(v), p, g); }
Chris@16: 
Chris@16: template <LABELED_GRAPH_PARAMS>
Chris@16: inline void
Chris@16: clear_vertex_by_label(typename LABELED_GRAPH::label_type const& l, LABELED_GRAPH& g)
Chris@16: { clear_vertex(g.vertex(l), g.graph()); }
Chris@16: 
Chris@16: template <LABELED_GRAPH_PARAMS>
Chris@16: inline void
Chris@16: remove_edge_by_label(typename LABELED_GRAPH::label_type const& u,
Chris@16:                      typename LABELED_GRAPH::label_type const& v,
Chris@16:                      LABELED_GRAPH& g)
Chris@16: { remove_edge(g.vertex(u), g.vertex(v), g.graph()); }
Chris@16: //@}
Chris@16: 
Chris@16: /** @name Labeled Mutable Graph
Chris@16:  * The labeled mutable graph hides the add_ and remove_ vertex functions from
Chris@16:  * the mutable graph concept. Note that the remove_vertex is hidden because
Chris@16:  * removing the vertex without its key could leave a dangling reference in
Chris@16:  * the map.
Chris@16:  */
Chris@16: //@{
Chris@16: template <LABELED_GRAPH_PARAMS>
Chris@16: inline typename LABELED_GRAPH::vertex_descriptor
Chris@16: add_vertex(typename LABELED_GRAPH::label_type const& l,
Chris@16:            LABELED_GRAPH& g)
Chris@16: { return g.add_vertex(l); }
Chris@16: 
Chris@16: // MutableLabeledPropertyGraph::add_vertex(l, vp, g)
Chris@16: template <LABELED_GRAPH_PARAMS>
Chris@16: inline typename LABELED_GRAPH::vertex_descriptor
Chris@16: add_vertex(typename LABELED_GRAPH::label_type const& l,
Chris@16:            typename LABELED_GRAPH::vertex_property_type const& p,
Chris@16:            LABELED_GRAPH& g)
Chris@16: { return g.add_vertex(l, p); }
Chris@16: 
Chris@16: template <LABELED_GRAPH_PARAMS>
Chris@16: inline void
Chris@16: remove_vertex(typename LABELED_GRAPH::label_type const& l, LABELED_GRAPH& g)
Chris@16: { g.remove_vertex(l); }
Chris@16: //@}
Chris@16: 
Chris@16: #undef LABELED_GRAPH_PARAMS
Chris@16: #undef LABELED_GRAPH
Chris@16: 
Chris@16: } // namespace boost
Chris@16: 
Chris@16: // Pull the labeled graph traits
Chris@16: #include <boost/graph/detail/labeled_graph_traits.hpp>
Chris@16: 
Chris@16: #endif // BOOST_GRAPH_LABELED_GRAPH_HPP