[Boost-commit] svn:boost r52914 - trunk/boost/graph

Subject: [Boost-commit] svn:boost r52914 - trunk/boost/graph
From: asutton_at_[hidden]
Date: 2009-05-11 13:42:10

Author: asutton
Date: 2009-05-11 13:42:10 EDT (Mon, 11 May 2009)
New Revision: 52914
URL: http://svn.boost.org/trac/boost/changeset/52914

Log:
Added a new labeled graph adaptor that maps vertices to user-defined
key types.

Added:
   trunk/boost/graph/labeled_graph.hpp   (contents, props changed)

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