Chris@16: // (C) Copyright 2007-2009 Andrew Sutton
Chris@16: //
Chris@16: // Use, modification and distribution are subject to the
Chris@16: // Boost Software License, Version 1.0 (See accompanying file
Chris@16: // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_DIRECTED_GRAPH_HPP
Chris@16: #define BOOST_GRAPH_DIRECTED_GRAPH_HPP
Chris@16: 
Chris@16: #include <boost/graph/adjacency_list.hpp>
Chris@16: #include <boost/graph/properties.hpp>
Chris@16: #include <boost/pending/property.hpp>
Chris@16: #include <boost/property_map/transform_value_property_map.hpp>
Chris@16: #include <boost/type_traits.hpp>
Chris@16: #include <boost/mpl/if.hpp>
Chris@16: 
Chris@16: namespace boost
Chris@16: {
Chris@16: struct directed_graph_tag { };
Chris@16: 
Chris@16: /**
Chris@16:  * The directed_graph class template is a simplified version of the BGL
Chris@16:  * adjacency list. This class is provided for ease of use, but may not
Chris@16:  * perform as well as custom-defined adjacency list classes. Instances of
Chris@16:  * this template model the BidirectionalGraph, VertexIndexGraph, and
Chris@16:  * EdgeIndexGraph concepts. The graph is also fully mutable, supporting
Chris@16:  * both insertions and removals of vertices and edges.
Chris@16:  *
Chris@16:  * @note Special care must be taken when removing vertices or edges since
Chris@16:  * those operations can invalidate the numbering of vertices.
Chris@16:  */
Chris@16: template <
Chris@16:     typename VertexProp = no_property,
Chris@16:     typename EdgeProp = no_property,
Chris@16:     typename GraphProp = no_property>
Chris@16: class directed_graph
Chris@16: {
Chris@16: public:
Chris@16:     typedef GraphProp graph_property_type;
Chris@16:     typedef VertexProp vertex_property_type;
Chris@16:     typedef EdgeProp edge_property_type;
Chris@16:     typedef typename lookup_one_property<GraphProp, graph_bundle_t>::type graph_bundled;
Chris@16:     typedef typename lookup_one_property<VertexProp, vertex_bundle_t>::type vertex_bundled;
Chris@16:     typedef typename lookup_one_property<EdgeProp, edge_bundle_t>::type edge_bundled;
Chris@16: 
Chris@16: public:
Chris@16:     // Embed indices into the vertex type.
Chris@16:     typedef property<vertex_index_t, unsigned, vertex_property_type> internal_vertex_property;
Chris@16:     typedef property<edge_index_t, unsigned, edge_property_type> internal_edge_property;
Chris@16: public:
Chris@16:     typedef adjacency_list<
Chris@16:         listS, listS, bidirectionalS,
Chris@16:         internal_vertex_property, internal_edge_property, GraphProp,
Chris@16:         listS
Chris@16:     > graph_type;
Chris@16: 
Chris@16: private:
Chris@16:     // storage selectors
Chris@16:     typedef typename graph_type::vertex_list_selector vertex_list_selector;
Chris@16:     typedef typename graph_type::edge_list_selector edge_list_selector;
Chris@16:     typedef typename graph_type::out_edge_list_selector out_edge_list_selector;
Chris@16:     typedef typename graph_type::directed_selector directed_selector;
Chris@16: 
Chris@16: public:
Chris@16:     // more commonly used graph types
Chris@16:     typedef typename graph_type::stored_vertex stored_vertex;
Chris@16:     typedef typename graph_type::vertices_size_type vertices_size_type;
Chris@16:     typedef typename graph_type::edges_size_type edges_size_type;
Chris@16:     typedef typename graph_type::degree_size_type degree_size_type;
Chris@16:     typedef typename graph_type::vertex_descriptor vertex_descriptor;
Chris@16:     typedef typename graph_type::edge_descriptor edge_descriptor;
Chris@16: 
Chris@16:     // iterator types
Chris@16:     typedef typename graph_type::vertex_iterator vertex_iterator;
Chris@16:     typedef typename graph_type::edge_iterator edge_iterator;
Chris@16:     typedef typename graph_type::out_edge_iterator out_edge_iterator;
Chris@16:     typedef typename graph_type::in_edge_iterator in_edge_iterator;
Chris@16:     typedef typename graph_type::adjacency_iterator adjacency_iterator;
Chris@16: 
Chris@16:     // miscellaneous types
Chris@16:     typedef directed_graph_tag graph_tag;
Chris@16:     typedef typename graph_type::directed_category directed_category;
Chris@16:     typedef typename graph_type::edge_parallel_category edge_parallel_category;
Chris@16:     typedef typename graph_type::traversal_category traversal_category;
Chris@16: 
Chris@16:     typedef std::size_t vertex_index_type;
Chris@16:     typedef std::size_t edge_index_type;
Chris@16: 
Chris@16:     directed_graph(GraphProp const& p = GraphProp())
Chris@16:         : m_graph(p), m_num_vertices(0), m_num_edges(0), m_max_vertex_index(0)
Chris@16:         , m_max_edge_index(0)
Chris@16:     { }
Chris@16: 
Chris@16:     directed_graph(directed_graph const& x)
Chris@16:         : m_graph(x), m_num_vertices(x.m_num_vertices), m_num_edges(x.m_num_edges)
Chris@16:         , m_max_vertex_index(x.m_max_vertex_index), m_max_edge_index(x.m_max_edge_index)
Chris@16:     { }
Chris@16: 
Chris@16:     directed_graph(vertices_size_type n, GraphProp const& p = GraphProp())
Chris@16:         : m_graph(n, p), m_num_vertices(n), m_num_edges(0), m_max_vertex_index(n)
Chris@16:         , m_max_edge_index(0)
Chris@16:     { renumber_vertex_indices(); }
Chris@16: 
Chris@16:     template <typename EdgeIterator>
Chris@16:     directed_graph(EdgeIterator f,
Chris@16:                    EdgeIterator l,
Chris@16:                    vertices_size_type n,
Chris@16:                    edges_size_type m = 0,
Chris@16:                    GraphProp const& p = GraphProp())
Chris@16:         : m_graph(f, l, n, m, p), m_num_vertices(n), m_num_edges(0)
Chris@16:         , m_max_vertex_index(n), m_max_edge_index(0)
Chris@16:     {
Chris@16:         // Unfortunately, we have to renumber the entire graph.
Chris@16:         renumber_indices();
Chris@16: 
Chris@16:         // Can't always guarantee that the number of edges is actually
Chris@16:         // m if distance(f, l) != m (or is undefined).
Chris@16:         m_num_edges = m_max_edge_index = boost::num_edges(m_graph);
Chris@16:     }
Chris@16: 
Chris@16:     directed_graph& operator=(directed_graph const& g) {
Chris@16:         if(&g != this) {
Chris@16:             m_graph = g.m_graph;
Chris@16:             m_num_vertices = g.m_num_vertices;
Chris@16:             m_num_edges = g.m_num_edges;
Chris@16:             m_max_vertex_index = g.m_max_vertex_index;
Chris@16:             m_max_edge_index = g.m_max_edge_index;
Chris@16:         }
Chris@16:         return *this;
Chris@16:     }
Chris@16: 
Chris@16:     // The impl_() methods are not part of the public interface.
Chris@16:     graph_type& impl()
Chris@16:     { return m_graph; }
Chris@16: 
Chris@16:     graph_type const& impl() const
Chris@16:     { return m_graph; }
Chris@16: 
Chris@16:     // The following methods are not part of the public interface
Chris@16:     vertices_size_type num_vertices() const
Chris@16:     { return m_num_vertices; }
Chris@16: 
Chris@16: 
Chris@16: private:
Chris@16:     // This helper function manages the attribution of vertex indices.
Chris@16:     vertex_descriptor make_index(vertex_descriptor v) {
Chris@16:         boost::put(vertex_index, m_graph, v, m_max_vertex_index);
Chris@16:         m_num_vertices++;
Chris@16:         m_max_vertex_index++;
Chris@16:         return v;
Chris@16:     }
Chris@16: public:
Chris@16:     vertex_descriptor add_vertex()
Chris@16:     { return make_index(boost::add_vertex(m_graph)); }
Chris@16: 
Chris@16:     vertex_descriptor add_vertex(vertex_property_type const& p)
Chris@16:     { return make_index(boost::add_vertex(internal_vertex_property(0u, p), m_graph)); }
Chris@16: 
Chris@16:     void clear_vertex(vertex_descriptor v)
Chris@16:     {
Chris@16:         m_num_edges -= boost::degree(v, m_graph);
Chris@16:         boost::clear_vertex(v, m_graph);
Chris@16:     }
Chris@16: 
Chris@16:     void remove_vertex(vertex_descriptor v)
Chris@16:     {
Chris@16:         boost::remove_vertex(v, m_graph);
Chris@16:         --m_num_vertices;
Chris@16:     }
Chris@16: 
Chris@16:     edges_size_type num_edges() const
Chris@16:     { return m_num_edges; }
Chris@16: 
Chris@16: private:
Chris@16:     // A helper fucntion for managing edge index attributes.
Chris@16:     std::pair<edge_descriptor, bool> const&
Chris@16:     make_index(std::pair<edge_descriptor, bool> const& x)
Chris@16:     {
Chris@16:         if(x.second) {
Chris@16:             boost::put(edge_index, m_graph, x.first, m_max_edge_index);
Chris@16:             ++m_num_edges;
Chris@16:             ++m_max_edge_index;
Chris@16:         }
Chris@16:         return x;
Chris@16:     }
Chris@16: public:
Chris@16:     std::pair<edge_descriptor, bool>
Chris@16:     add_edge(vertex_descriptor u, vertex_descriptor v)
Chris@16:     { return make_index(boost::add_edge(u, v, m_graph)); }
Chris@16: 
Chris@16:     std::pair<edge_descriptor, bool>
Chris@16:     add_edge(vertex_descriptor u, vertex_descriptor v, edge_property_type const& p)
Chris@16:     { return make_index(boost::add_edge(u, v, internal_edge_property(0u, p), m_graph)); }
Chris@16: 
Chris@16:     void remove_edge(vertex_descriptor u, vertex_descriptor v)
Chris@16:     {
Chris@16:         // find all edges, (u, v)
Chris@16:         std::vector<edge_descriptor> edges;
Chris@16:         out_edge_iterator i, i_end;
Chris@16:         for(boost::tie(i, i_end) = boost::out_edges(u, m_graph); i != i_end; ++i) {
Chris@16:             if(boost::target(*i, m_graph) == v) {
Chris@16:                 edges.push_back(*i);
Chris@16:             }
Chris@16:         }
Chris@16:         // remove all edges, (u, v)
Chris@16:         typename std::vector<edge_descriptor>::iterator
Chris@16:         j = edges.begin(), j_end = edges.end();
Chris@16:         for( ; j != j_end; ++j) {
Chris@16:             remove_edge(*j);
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     void remove_edge(edge_iterator i)
Chris@16:     {
Chris@16:         remove_edge(*i);
Chris@16:     }
Chris@16: 
Chris@16:     void remove_edge(edge_descriptor e)
Chris@16:     {
Chris@16:         boost::remove_edge(e, m_graph);
Chris@16:         --m_num_edges;
Chris@16:     }
Chris@16: 
Chris@16:     vertex_index_type max_vertex_index() const
Chris@16:     { return m_max_vertex_index; }
Chris@16: 
Chris@16:     void
Chris@16:     renumber_vertex_indices()
Chris@16:     {
Chris@16:         vertex_iterator i, end;
Chris@16:         boost::tie(i, end) = vertices(m_graph);
Chris@16:         m_max_vertex_index = renumber_vertex_indices(i, end, 0);
Chris@16:     }
Chris@16: 
Chris@16:     void
Chris@16:     remove_vertex_and_renumber_indices(vertex_iterator i)
Chris@16:     {
Chris@16:         vertex_iterator j = next(i), end = vertices(m_graph).second;
Chris@16:         vertex_index_type n = get(vertex_index, m_graph, *i);
Chris@16: 
Chris@16:         // remove the offending vertex and renumber everything after
Chris@16:         remove_vertex(*i);
Chris@16:         m_max_vertex_index = renumber_vertex_indices(j, end, n);
Chris@16:     }
Chris@16: 
Chris@16:     edge_index_type
Chris@16:     max_edge_index() const
Chris@16:     { return m_max_edge_index; }
Chris@16: 
Chris@16:     void
Chris@16:     renumber_edge_indices()
Chris@16:     {
Chris@16:         edge_iterator i, end;
Chris@16:         boost::tie(i, end) = edges(m_graph);
Chris@16:         m_max_edge_index = renumber_edge_indices(i, end, 0);
Chris@16:     }
Chris@16: 
Chris@16:     void
Chris@16:     remove_edge_and_renumber_indices(edge_iterator i)
Chris@16:     {
Chris@16:         edge_iterator j = next(i), end = edges(m_graph).second;
Chris@16:         edge_index_type n = get(edge_index, m_graph, *i);
Chris@16: 
Chris@16:         // remove the offending edge and renumber everything after
Chris@16:         remove_edge(*i);
Chris@16:         m_max_edge_index = renumber_edge_indices(j, end, n);
Chris@16:     }
Chris@16: 
Chris@16:     void
Chris@16:     renumber_indices()
Chris@16:     {
Chris@16:         renumber_vertex_indices();
Chris@16:         renumber_edge_indices();
Chris@16:     }
Chris@16: 
Chris@16:     // bundled property support
Chris@16: #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
Chris@16:     vertex_bundled& operator[](vertex_descriptor v)
Chris@16:     { return m_graph[v]; }
Chris@16: 
Chris@16:     vertex_bundled const& operator[](vertex_descriptor v) const
Chris@16:     { return m_graph[v]; }
Chris@16: 
Chris@16:     edge_bundled& operator[](edge_descriptor e)
Chris@16:     { return m_graph[e]; }
Chris@16: 
Chris@16:     edge_bundled const& operator[](edge_descriptor e) const
Chris@16:     { return m_graph[e]; }
Chris@16: 
Chris@16:     graph_bundled& operator[](graph_bundle_t)
Chris@16:     { return get_property(*this); }
Chris@16: 
Chris@16:     graph_bundled const& operator[](graph_bundle_t) const
Chris@16:     { return get_property(*this); }
Chris@16: #endif
Chris@16: 
Chris@16:     // Graph concepts
Chris@16:     static vertex_descriptor null_vertex()
Chris@16:     { return graph_type::null_vertex(); }
Chris@16: 
Chris@16:     void clear()
Chris@16:     {
Chris@16:         m_graph.clear();
Chris@16:         m_num_vertices = m_max_vertex_index = 0;
Chris@16:         m_num_edges = m_max_edge_index = 0;
Chris@16:     }
Chris@16: 
Chris@16:     void swap(directed_graph& g)
Chris@16:     {
Chris@101:         m_graph.swap(g.m_graph);
Chris@16:         std::swap(m_num_vertices, g.m_num_vertices);
Chris@16:         std::swap(m_max_vertex_index, g.m_max_vertex_index);
Chris@16:         std::swap(m_num_edges, g.m_num_edges);
Chris@16:         std::swap(m_max_edge_index, g.m_max_edge_index);
Chris@16:     }
Chris@16: 
Chris@16: private:
Chris@16:     vertices_size_type
Chris@16:     renumber_vertex_indices(vertex_iterator i,
Chris@16:                             vertex_iterator end,
Chris@16:                             vertices_size_type n)
Chris@16:     {
Chris@16:         typedef typename property_map<graph_type, vertex_index_t>::type IndexMap;
Chris@16:         IndexMap indices = get(vertex_index, m_graph);
Chris@16:         for( ; i != end; ++i) {
Chris@16:             indices[*i] = n++;
Chris@16:         }
Chris@16:         return n;
Chris@16:     }
Chris@16: 
Chris@16:     vertices_size_type
Chris@16:     renumber_edge_indices(edge_iterator i,
Chris@16:                         edge_iterator end,
Chris@16:                         vertices_size_type n)
Chris@16:     {
Chris@16:         typedef typename property_map<graph_type, edge_index_t>::type IndexMap;
Chris@16:         IndexMap indices = get(edge_index, m_graph);
Chris@16:         for( ; i != end; ++i) {
Chris@16:             indices[*i] = n++;
Chris@16:         }
Chris@16:         return n;
Chris@16:     }
Chris@16: 
Chris@16:     graph_type m_graph;
Chris@16:     vertices_size_type m_num_vertices;
Chris@16:     edges_size_type m_num_edges;
Chris@16:     vertex_index_type m_max_vertex_index;
Chris@16:     edge_index_type m_max_edge_index;
Chris@16: };
Chris@16: 
Chris@16: #define DIRECTED_GRAPH_PARAMS typename VP, typename EP, typename GP
Chris@16: #define DIRECTED_GRAPH directed_graph<VP,EP,GP>
Chris@16: 
Chris@16: // IncidenceGraph concepts
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: inline typename DIRECTED_GRAPH::vertex_descriptor
Chris@16: source(typename DIRECTED_GRAPH::edge_descriptor e, DIRECTED_GRAPH const& g)
Chris@16: { return source(e, g.impl()); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: inline typename DIRECTED_GRAPH::vertex_descriptor
Chris@16: target(typename DIRECTED_GRAPH::edge_descriptor e, DIRECTED_GRAPH const& g)
Chris@16: { return target(e, g.impl()); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: inline typename DIRECTED_GRAPH::degree_size_type
Chris@16: out_degree(typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g)
Chris@16: { return out_degree(v, g.impl()); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: inline std::pair<
Chris@16:     typename DIRECTED_GRAPH::out_edge_iterator,
Chris@16:     typename DIRECTED_GRAPH::out_edge_iterator
Chris@16: >
Chris@16: out_edges(typename DIRECTED_GRAPH::vertex_descriptor v,
Chris@16:         DIRECTED_GRAPH const& g)
Chris@16: { return out_edges(v, g.impl()); }
Chris@16: 
Chris@16: // BidirectionalGraph concepts
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: inline typename DIRECTED_GRAPH::degree_size_type
Chris@16: in_degree(typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g)
Chris@16: { return in_degree(v, g.impl()); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: inline std::pair<
Chris@16:     typename DIRECTED_GRAPH::in_edge_iterator,
Chris@16:     typename DIRECTED_GRAPH::in_edge_iterator
Chris@16: >
Chris@16: in_edges(typename DIRECTED_GRAPH::vertex_descriptor v,
Chris@16:         DIRECTED_GRAPH const& g)
Chris@16: { return in_edges(v, g.impl()); }
Chris@16: 
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: inline typename DIRECTED_GRAPH::degree_size_type
Chris@16: degree(typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g)
Chris@16: { return degree(v, g.impl()); }
Chris@16: 
Chris@16: // AdjacencyGraph concepts
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: inline std::pair<
Chris@16:     typename DIRECTED_GRAPH::adjacency_iterator,
Chris@16:     typename DIRECTED_GRAPH::adjacency_iterator
Chris@16:     >
Chris@16: adjacent_vertices(typename DIRECTED_GRAPH::vertex_descriptor v,
Chris@16:                   DIRECTED_GRAPH const& g)
Chris@16: { return adjacent_vertices(v, g.impl()); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: typename DIRECTED_GRAPH::vertex_descriptor
Chris@16: vertex(typename DIRECTED_GRAPH::vertices_size_type n,
Chris@16:        DIRECTED_GRAPH const& g)
Chris@16: { return vertex(n, g.impl()); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: std::pair<typename DIRECTED_GRAPH::edge_descriptor, bool>
Chris@16: edge(typename DIRECTED_GRAPH::vertex_descriptor u,
Chris@16:      typename DIRECTED_GRAPH::vertex_descriptor v,
Chris@16:      DIRECTED_GRAPH const& g)
Chris@16: { return edge(u, v, g.impl()); }
Chris@16: 
Chris@16: // VertexListGraph concepts
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: inline typename DIRECTED_GRAPH::vertices_size_type
Chris@16: num_vertices(DIRECTED_GRAPH const& g)
Chris@16: { return g.num_vertices(); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: inline std::pair<
Chris@16:     typename DIRECTED_GRAPH::vertex_iterator,
Chris@16:     typename DIRECTED_GRAPH::vertex_iterator
Chris@16: >
Chris@16: vertices(DIRECTED_GRAPH const& g)
Chris@16: { return vertices(g.impl()); }
Chris@16: 
Chris@16: // EdgeListGraph concepts
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: inline typename DIRECTED_GRAPH::edges_size_type
Chris@16: num_edges(DIRECTED_GRAPH const& g)
Chris@16: { return g.num_edges(); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: inline std::pair<
Chris@16:     typename DIRECTED_GRAPH::edge_iterator,
Chris@16:     typename DIRECTED_GRAPH::edge_iterator
Chris@16: >
Chris@16: edges(DIRECTED_GRAPH const& g)
Chris@16: { return edges(g.impl()); }
Chris@16: 
Chris@16: // MutableGraph concepts
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: inline typename DIRECTED_GRAPH::vertex_descriptor
Chris@16: add_vertex(DIRECTED_GRAPH& g)
Chris@16: { return g.add_vertex(); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: inline typename DIRECTED_GRAPH::vertex_descriptor
Chris@16: add_vertex(typename DIRECTED_GRAPH::vertex_property_type const& p,
Chris@16:            DIRECTED_GRAPH& g)
Chris@16: { return g.add_vertex(p); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: inline void
Chris@16: clear_vertex(typename DIRECTED_GRAPH::vertex_descriptor v,
Chris@16: DIRECTED_GRAPH& g)
Chris@16: { return g.clear_vertex(v); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: inline void
Chris@16: remove_vertex(typename DIRECTED_GRAPH::vertex_descriptor v,
Chris@16:               DIRECTED_GRAPH& g)
Chris@16: { return g.remove_vertex(v); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: inline std::pair<typename DIRECTED_GRAPH::edge_descriptor, bool>
Chris@16: add_edge(typename DIRECTED_GRAPH::vertex_descriptor u,
Chris@16:          typename DIRECTED_GRAPH::vertex_descriptor v,
Chris@16:          DIRECTED_GRAPH& g)
Chris@16: { return g.add_edge(u, v); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: inline std::pair<typename DIRECTED_GRAPH::edge_descriptor, bool>
Chris@16: add_edge(typename DIRECTED_GRAPH::vertex_descriptor u,
Chris@16:          typename DIRECTED_GRAPH::vertex_descriptor v,
Chris@16:          typename DIRECTED_GRAPH::edge_property_type const& p,
Chris@16:          DIRECTED_GRAPH& g)
Chris@16: { return g.add_edge(u, v, p); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: inline void remove_edge(typename DIRECTED_GRAPH::vertex_descriptor u,
Chris@16:                         typename DIRECTED_GRAPH::vertex_descriptor v,
Chris@16:                         DIRECTED_GRAPH& g)
Chris@16: { return g.remove_edge(u, v); }
Chris@16: 
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: inline void remove_edge(typename DIRECTED_GRAPH::edge_descriptor e, DIRECTED_GRAPH& g)
Chris@16: { return g.remove_edge(e); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: inline void remove_edge(typename DIRECTED_GRAPH::edge_iterator i, DIRECTED_GRAPH& g)
Chris@16: { return g.remove_edge(i); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS, class Predicate>
Chris@16: inline void remove_edge_if(Predicate pred, DIRECTED_GRAPH& g)
Chris@16: { return remove_edge_if(pred, g.impl()); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS, class Predicate>
Chris@16: inline void
Chris@16: remove_out_edge_if(typename DIRECTED_GRAPH::vertex_descriptor v,
Chris@16:                    Predicate pred,
Chris@16:                    DIRECTED_GRAPH& g)
Chris@16: { return remove_out_edge_if(v, pred, g.impl()); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS, class Predicate>
Chris@16: inline void
Chris@16: remove_in_edge_if(typename DIRECTED_GRAPH::vertex_descriptor v,
Chris@16:                 Predicate pred,
Chris@16:                 DIRECTED_GRAPH& g)
Chris@16: { return remove_in_edge_if(v, pred, g.impl()); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS, typename Property>
Chris@16: struct property_map<DIRECTED_GRAPH, Property>: property_map<typename DIRECTED_GRAPH::graph_type, Property> {};
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: struct property_map<DIRECTED_GRAPH, vertex_all_t> {
Chris@16:   typedef transform_value_property_map<
Chris@16:             detail::remove_first_property,
Chris@16:             typename property_map<typename DIRECTED_GRAPH::graph_type, vertex_all_t>::const_type>
Chris@16:     const_type;
Chris@16:   typedef transform_value_property_map<
Chris@16:             detail::remove_first_property,
Chris@16:             typename property_map<typename DIRECTED_GRAPH::graph_type, vertex_all_t>::type>
Chris@16:     type;
Chris@16: };
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: struct property_map<DIRECTED_GRAPH, edge_all_t> {
Chris@16:   typedef transform_value_property_map<
Chris@16:             detail::remove_first_property,
Chris@16:             typename property_map<typename DIRECTED_GRAPH::graph_type, edge_all_t>::const_type>
Chris@16:     const_type;
Chris@16:   typedef transform_value_property_map<
Chris@16:             detail::remove_first_property,
Chris@16:             typename property_map<typename DIRECTED_GRAPH::graph_type, edge_all_t>::type>
Chris@16:     type;
Chris@16: };
Chris@16: 
Chris@16: // PropertyGraph concepts
Chris@16: template <DIRECTED_GRAPH_PARAMS, typename Property>
Chris@16: inline typename property_map<DIRECTED_GRAPH, Property>::type
Chris@16: get(Property p, DIRECTED_GRAPH& g)
Chris@16: { return get(p, g.impl()); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS, typename Property>
Chris@16: inline typename property_map<DIRECTED_GRAPH, Property>::const_type
Chris@16: get(Property p, DIRECTED_GRAPH const& g)
Chris@16: { return get(p, g.impl()); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: inline typename property_map<DIRECTED_GRAPH, vertex_all_t>::type
Chris@16: get(vertex_all_t, DIRECTED_GRAPH& g)
Chris@16: { return typename property_map<DIRECTED_GRAPH, vertex_all_t>::type(detail::remove_first_property(), get(vertex_all, g.impl())); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: inline typename property_map<DIRECTED_GRAPH, vertex_all_t>::const_type
Chris@16: get(vertex_all_t, DIRECTED_GRAPH const& g)
Chris@16: { return typename property_map<DIRECTED_GRAPH, vertex_all_t>::const_type(detail::remove_first_property(), get(vertex_all, g.impl())); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: inline typename property_map<DIRECTED_GRAPH, edge_all_t>::type
Chris@16: get(edge_all_t, DIRECTED_GRAPH& g)
Chris@16: { return typename property_map<DIRECTED_GRAPH, edge_all_t>::type(detail::remove_first_property(), get(edge_all, g.impl())); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: inline typename property_map<DIRECTED_GRAPH, edge_all_t>::const_type
Chris@16: get(edge_all_t, DIRECTED_GRAPH const& g)
Chris@16: { return typename property_map<DIRECTED_GRAPH, edge_all_t>::const_type(detail::remove_first_property(), get(edge_all, g.impl())); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS, typename Property, typename Key>
Chris@16: inline typename property_traits<
Chris@16:     typename property_map<
Chris@16:         typename DIRECTED_GRAPH::graph_type, Property
Chris@16:     >::const_type
Chris@16: >::value_type
Chris@16: get(Property p, DIRECTED_GRAPH const& g, Key const& k)
Chris@16: { return get(p, g.impl(), k); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS, typename Key>
Chris@16: inline typename property_traits<
Chris@16:     typename property_map<
Chris@16:         typename DIRECTED_GRAPH::graph_type, vertex_all_t
Chris@16:     >::const_type
Chris@16: >::value_type
Chris@16: get(vertex_all_t, DIRECTED_GRAPH const& g, Key const& k)
Chris@16: { return get(vertex_all, g.impl(), k).m_base; }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS, typename Key>
Chris@16: inline typename property_traits<
Chris@16:     typename property_map<
Chris@16:         typename DIRECTED_GRAPH::graph_type, edge_all_t
Chris@16:     >::const_type
Chris@16: >::value_type
Chris@16: get(edge_all_t, DIRECTED_GRAPH const& g, Key const& k)
Chris@16: { return get(edge_all, g.impl(), k).m_base; }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS, typename Property, typename Key, typename Value>
Chris@16: inline void put(Property p, DIRECTED_GRAPH& g, Key const& k, Value const& v)
Chris@16: { put(p, g.impl(), k, v); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS, typename Key, typename Value>
Chris@16: inline void put(vertex_all_t, DIRECTED_GRAPH& g, Key const& k, Value const& v)
Chris@16: { put(vertex_all, g.impl(), k,
Chris@16:       typename DIRECTED_GRAPH::internal_vertex_property(get(vertex_index, g.impl(), k), v));
Chris@16: }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS, typename Key, typename Value>
Chris@16: inline void put(edge_all_t, DIRECTED_GRAPH& g, Key const& k, Value const& v)
Chris@16: { put(edge_all, g.impl(), k,
Chris@16:       typename DIRECTED_GRAPH::internal_vertex_property(get(edge_index, g.impl(), k), v));
Chris@16: }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS, class Property>
Chris@16: typename graph_property<DIRECTED_GRAPH, Property>::type&
Chris@16: get_property(DIRECTED_GRAPH& g, Property p)
Chris@16: { return get_property(g.impl(), p); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS, class Property>
Chris@16: typename graph_property<DIRECTED_GRAPH, Property>::type const&
Chris@16: get_property(DIRECTED_GRAPH const& g, Property p)
Chris@16: { return get_property(g.impl(), p); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS, class Property, class Value>
Chris@16: void
Chris@16: set_property(DIRECTED_GRAPH& g, Property p, Value v)
Chris@16: { return set_property(g.impl(), p, v); }
Chris@16: 
Chris@16: // Vertex index management
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: inline typename DIRECTED_GRAPH::vertex_index_type
Chris@16: get_vertex_index(typename DIRECTED_GRAPH::vertex_descriptor v,
Chris@16:                 DIRECTED_GRAPH const& g)
Chris@16: { return get(vertex_index, g, v); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: typename DIRECTED_GRAPH::vertex_index_type
Chris@16: max_vertex_index(DIRECTED_GRAPH const& g)
Chris@16: { return g.max_vertex_index(); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: inline void
Chris@16: renumber_vertex_indices(DIRECTED_GRAPH& g)
Chris@16: { g.renumber_vertex_indices(); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: inline void
Chris@16: remove_vertex_and_renumber_indices(typename DIRECTED_GRAPH::vertex_iterator i,
Chris@16:                                 DIRECTED_GRAPH& g)
Chris@16: { g.remove_vertex_and_renumber_indices(i); }
Chris@16: 
Chris@16: // Edge index management
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: inline typename DIRECTED_GRAPH::edge_index_type
Chris@16: get_edge_index(typename DIRECTED_GRAPH::edge_descriptor v, DIRECTED_GRAPH const& g)
Chris@16: { return get(edge_index, g, v); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: typename DIRECTED_GRAPH::edge_index_type
Chris@16: max_edge_index(DIRECTED_GRAPH const& g)
Chris@16: { return g.max_edge_index(); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: inline void renumber_edge_indices(DIRECTED_GRAPH& g)
Chris@16: { g.renumber_edge_indices(); }
Chris@16: 
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: inline void
Chris@16: remove_edge_and_renumber_indices(typename DIRECTED_GRAPH::edge_iterator i,
Chris@16:                                  DIRECTED_GRAPH& g)
Chris@16: { g.remove_edge_and_renumber_indices(i); }
Chris@16: 
Chris@16: // Index management
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: inline void
Chris@16: renumber_indices(DIRECTED_GRAPH& g)
Chris@16: { g.renumber_indices(); }
Chris@16: 
Chris@16: // Mutability Traits
Chris@16: template <DIRECTED_GRAPH_PARAMS>
Chris@16: struct graph_mutability_traits<DIRECTED_GRAPH> {
Chris@16:     typedef mutable_property_graph_tag category;
Chris@16: };
Chris@16: 
Chris@16: #undef DIRECTED_GRAPH_PARAMS
Chris@16: #undef DIRECTED_GRAPH
Chris@16: 
Chris@16: } /* namespace boost */
Chris@16: 
Chris@16: #endif