boost/graph/directed_graph.hpp

0001 // (C) Copyright 2007-2009 Andrew Sutton
0002 //
0003 // Use, modification and distribution are subject to the
0004 // Boost Software License, Version 1.0 (See accompanying file
0005 // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
0006
0007 #ifndef BOOST_GRAPH_DIRECTED_GRAPH_HPP
0008 #define BOOST_GRAPH_DIRECTED_GRAPH_HPP
0009
0010 #include <boost/graph/adjacency_list.hpp>
0011 #include <boost/graph/properties.hpp>
0012 #include <boost/pending/property.hpp>
0013 #include <boost/property_map/transform_value_property_map.hpp>
0014 #include <boost/type_traits.hpp>
0015 #include <boost/mpl/if.hpp>
0016
0017 namespace boost
0018 {
0019 struct directed_graph_tag
0020 {
0021 };
0022
0023 /**
0024  * The directed_graph class template is a simplified version of the BGL
0025  * adjacency list. This class is provided for ease of use, but may not
0026  * perform as well as custom-defined adjacency list classes. Instances of
0027  * this template model the BidirectionalGraph, VertexIndexGraph, and
0028  * EdgeIndexGraph concepts. The graph is also fully mutable, supporting
0029  * both insertions and removals of vertices and edges.
0030  *
0031  * @note Special care must be taken when removing vertices or edges since
0032  * those operations can invalidate the numbering of vertices.
0033  */
0034 template < typename VertexProp = no_property, typename EdgeProp = no_property,
0035     typename GraphProp = no_property >
0036 class directed_graph
0037 {
0038 public:
0039     typedef GraphProp graph_property_type;
0040     typedef VertexProp vertex_property_type;
0041     typedef EdgeProp edge_property_type;
0042     typedef typename lookup_one_property< GraphProp, graph_bundle_t >::type
0043         graph_bundled;
0044     typedef typename lookup_one_property< VertexProp, vertex_bundle_t >::type
0045         vertex_bundled;
0046     typedef typename lookup_one_property< EdgeProp, edge_bundle_t >::type
0047         edge_bundled;
0048
0049 public:
0050     // Embed indices into the vertex type.
0051     typedef property< vertex_index_t, unsigned, vertex_property_type >
0052         internal_vertex_property;
0053     typedef property< edge_index_t, unsigned, edge_property_type >
0054         internal_edge_property;
0055
0056 public:
0057     typedef adjacency_list< listS, listS, bidirectionalS,
0058         internal_vertex_property, internal_edge_property, GraphProp, listS >
0059         graph_type;
0060
0061 private:
0062     // storage selectors
0063     typedef typename graph_type::vertex_list_selector vertex_list_selector;
0064     typedef typename graph_type::edge_list_selector edge_list_selector;
0065     typedef typename graph_type::out_edge_list_selector out_edge_list_selector;
0066     typedef typename graph_type::directed_selector directed_selector;
0067
0068 public:
0069     // more commonly used graph types
0070     typedef typename graph_type::stored_vertex stored_vertex;
0071     typedef typename graph_type::vertices_size_type vertices_size_type;
0072     typedef typename graph_type::edges_size_type edges_size_type;
0073     typedef typename graph_type::degree_size_type degree_size_type;
0074     typedef typename graph_type::vertex_descriptor vertex_descriptor;
0075     typedef typename graph_type::edge_descriptor edge_descriptor;
0076
0077     // iterator types
0078     typedef typename graph_type::vertex_iterator vertex_iterator;
0079     typedef typename graph_type::edge_iterator edge_iterator;
0080     typedef typename graph_type::out_edge_iterator out_edge_iterator;
0081     typedef typename graph_type::in_edge_iterator in_edge_iterator;
0082     typedef typename graph_type::adjacency_iterator adjacency_iterator;
0083
0084     // miscellaneous types
0085     typedef directed_graph_tag graph_tag;
0086     typedef typename graph_type::directed_category directed_category;
0087     typedef typename graph_type::edge_parallel_category edge_parallel_category;
0088     typedef typename graph_type::traversal_category traversal_category;
0089
0090     typedef std::size_t vertex_index_type;
0091     typedef std::size_t edge_index_type;
0092
0093     directed_graph(GraphProp const& p = GraphProp())
0094     : m_graph(p)
0095     , m_num_vertices(0)
0096     , m_num_edges(0)
0097     , m_max_vertex_index(0)
0098     , m_max_edge_index(0)
0099     {
0100     }
0101
0102     directed_graph(directed_graph const& x)
0103     : m_graph(x.m_graph)
0104     , m_num_vertices(x.m_num_vertices)
0105     , m_num_edges(x.m_num_edges)
0106     , m_max_vertex_index(x.m_max_vertex_index)
0107     , m_max_edge_index(x.m_max_edge_index)
0108     {
0109     }
0110
0111     directed_graph(vertices_size_type n, GraphProp const& p = GraphProp())
0112     : m_graph(n, p)
0113     , m_num_vertices(n)
0114     , m_num_edges(0)
0115     , m_max_vertex_index(n)
0116     , m_max_edge_index(0)
0117     {
0118         renumber_vertex_indices();
0119     }
0120
0121     template < typename EdgeIterator >
0122     directed_graph(EdgeIterator f, EdgeIterator l, vertices_size_type n,
0123         edges_size_type m = 0, GraphProp const& p = GraphProp())
0124     : m_graph(f, l, n, m, p)
0125     , m_num_vertices(n)
0126     , m_num_edges(0)
0127     , m_max_vertex_index(n)
0128     , m_max_edge_index(0)
0129     {
0130         // Unfortunately, we have to renumber the entire graph.
0131         renumber_indices();
0132
0133         // Can't always guarantee that the number of edges is actually
0134         // m if distance(f, l) != m (or is undefined).
0135         m_num_edges = m_max_edge_index = boost::num_edges(m_graph);
0136     }
0137
0138     directed_graph& operator=(directed_graph const& g)
0139     {
0140         if (&g != this)
0141         {
0142             m_graph = g.m_graph;
0143             m_num_vertices = g.m_num_vertices;
0144             m_num_edges = g.m_num_edges;
0145             m_max_vertex_index = g.m_max_vertex_index;
0146             m_max_edge_index = g.m_max_edge_index;
0147         }
0148         return *this;
0149     }
0150
0151     // The impl_() methods are not part of the public interface.
0152     graph_type& impl() { return m_graph; }
0153
0154     graph_type const& impl() const { return m_graph; }
0155
0156     // The following methods are not part of the public interface
0157     vertices_size_type num_vertices() const { return m_num_vertices; }
0158
0159 private:
0160     // This helper function manages the attribution of vertex indices.
0161     vertex_descriptor make_index(vertex_descriptor v)
0162     {
0163         boost::put(vertex_index, m_graph, v, m_max_vertex_index);
0164         m_num_vertices++;
0165         m_max_vertex_index++;
0166         return v;
0167     }
0168
0169 public:
0170     vertex_descriptor add_vertex()
0171     {
0172         return make_index(boost::add_vertex(m_graph));
0173     }
0174
0175     vertex_descriptor add_vertex(vertex_property_type const& p)
0176     {
0177         return make_index(
0178             boost::add_vertex(internal_vertex_property(0u, p), m_graph));
0179     }
0180
0181     void clear_vertex(vertex_descriptor v)
0182     {
0183         m_num_edges -= boost::degree(v, m_graph);
0184         boost::clear_vertex(v, m_graph);
0185     }
0186
0187     void remove_vertex(vertex_descriptor v)
0188     {
0189         boost::remove_vertex(v, m_graph);
0190         --m_num_vertices;
0191     }
0192
0193     edges_size_type num_edges() const { return m_num_edges; }
0194
0195 private:
0196     // A helper function for managing edge index attributes.
0197     std::pair< edge_descriptor, bool > const& make_index(
0198         std::pair< edge_descriptor, bool > const& x)
0199     {
0200         if (x.second)
0201         {
0202             boost::put(edge_index, m_graph, x.first, m_max_edge_index);
0203             ++m_num_edges;
0204             ++m_max_edge_index;
0205         }
0206         return x;
0207     }
0208
0209 public:
0210     std::pair< edge_descriptor, bool > add_edge(
0211         vertex_descriptor u, vertex_descriptor v)
0212     {
0213         return make_index(boost::add_edge(u, v, m_graph));
0214     }
0215
0216     std::pair< edge_descriptor, bool > add_edge(
0217         vertex_descriptor u, vertex_descriptor v, edge_property_type const& p)
0218     {
0219         return make_index(
0220             boost::add_edge(u, v, internal_edge_property(0u, p), m_graph));
0221     }
0222
0223     void remove_edge(vertex_descriptor u, vertex_descriptor v)
0224     {
0225         // find all edges, (u, v)
0226         std::vector< edge_descriptor > edges;
0227         out_edge_iterator i, i_end;
0228         for (boost::tie(i, i_end) = boost::out_edges(u, m_graph); i != i_end;
0229              ++i)
0230         {
0231             if (boost::target(*i, m_graph) == v)
0232             {
0233                 edges.push_back(*i);
0234             }
0235         }
0236         // remove all edges, (u, v)
0237         typename std::vector< edge_descriptor >::iterator j = edges.begin(),
0238                                                           j_end = edges.end();
0239         for (; j != j_end; ++j)
0240         {
0241             remove_edge(*j);
0242         }
0243     }
0244
0245     void remove_edge(edge_iterator i) { remove_edge(*i); }
0246
0247     void remove_edge(edge_descriptor e)
0248     {
0249         boost::remove_edge(e, m_graph);
0250         --m_num_edges;
0251     }
0252
0253     vertex_index_type max_vertex_index() const { return m_max_vertex_index; }
0254
0255     void renumber_vertex_indices()
0256     {
0257         vertex_iterator i, end;
0258         boost::tie(i, end) = vertices(m_graph);
0259         m_max_vertex_index = renumber_vertex_indices(i, end, 0);
0260     }
0261
0262     void remove_vertex_and_renumber_indices(vertex_iterator i)
0263     {
0264         vertex_iterator j = next(i), end = vertices(m_graph).second;
0265         vertex_index_type n = get(vertex_index, m_graph, *i);
0266
0267         // remove the offending vertex and renumber everything after
0268         remove_vertex(*i);
0269         m_max_vertex_index = renumber_vertex_indices(j, end, n);
0270     }
0271
0272     edge_index_type max_edge_index() const { return m_max_edge_index; }
0273
0274     void renumber_edge_indices()
0275     {
0276         edge_iterator i, end;
0277         boost::tie(i, end) = edges(m_graph);
0278         m_max_edge_index = renumber_edge_indices(i, end, 0);
0279     }
0280
0281     void remove_edge_and_renumber_indices(edge_iterator i)
0282     {
0283         edge_iterator j = next(i), end = edges(m_graph).second;
0284         edge_index_type n = get(edge_index, m_graph, *i);
0285
0286         // remove the offending edge and renumber everything after
0287         remove_edge(*i);
0288         m_max_edge_index = renumber_edge_indices(j, end, n);
0289     }
0290
0291     void renumber_indices()
0292     {
0293         renumber_vertex_indices();
0294         renumber_edge_indices();
0295     }
0296
0297     // bundled property support
0298 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
0299     vertex_bundled& operator[](vertex_descriptor v) { return m_graph[v]; }
0300
0301     vertex_bundled const& operator[](vertex_descriptor v) const
0302     {
0303         return m_graph[v];
0304     }
0305
0306     edge_bundled& operator[](edge_descriptor e) { return m_graph[e]; }
0307
0308     edge_bundled const& operator[](edge_descriptor e) const
0309     {
0310         return m_graph[e];
0311     }
0312
0313     graph_bundled& operator[](graph_bundle_t) { return get_property(*this); }
0314
0315     graph_bundled const& operator[](graph_bundle_t) const
0316     {
0317         return get_property(*this);
0318     }
0319 #endif
0320
0321     // Graph concepts
0322     static vertex_descriptor null_vertex() { return graph_type::null_vertex(); }
0323
0324     void clear()
0325     {
0326         m_graph.clear();
0327         m_num_vertices = m_max_vertex_index = 0;
0328         m_num_edges = m_max_edge_index = 0;
0329     }
0330
0331     void swap(directed_graph& g)
0332     {
0333         m_graph.swap(g.m_graph);
0334         std::swap(m_num_vertices, g.m_num_vertices);
0335         std::swap(m_max_vertex_index, g.m_max_vertex_index);
0336         std::swap(m_num_edges, g.m_num_edges);
0337         std::swap(m_max_edge_index, g.m_max_edge_index);
0338     }
0339
0340 private:
0341     vertices_size_type renumber_vertex_indices(
0342         vertex_iterator i, vertex_iterator end, vertices_size_type n)
0343     {
0344         typedef
0345             typename property_map< graph_type, vertex_index_t >::type IndexMap;
0346         IndexMap indices = get(vertex_index, m_graph);
0347         for (; i != end; ++i)
0348         {
0349             indices[*i] = n++;
0350         }
0351         return n;
0352     }
0353
0354     vertices_size_type renumber_edge_indices(
0355         edge_iterator i, edge_iterator end, vertices_size_type n)
0356     {
0357         typedef
0358             typename property_map< graph_type, edge_index_t >::type IndexMap;
0359         IndexMap indices = get(edge_index, m_graph);
0360         for (; i != end; ++i)
0361         {
0362             indices[*i] = n++;
0363         }
0364         return n;
0365     }
0366
0367     graph_type m_graph;
0368     vertices_size_type m_num_vertices;
0369     edges_size_type m_num_edges;
0370     vertex_index_type m_max_vertex_index;
0371     edge_index_type m_max_edge_index;
0372 };
0373
0374 #define DIRECTED_GRAPH_PARAMS typename VP, typename EP, typename GP
0375 #define DIRECTED_GRAPH directed_graph< VP, EP, GP >
0376
0377 // IncidenceGraph concepts
0378 template < DIRECTED_GRAPH_PARAMS >
0379 inline typename DIRECTED_GRAPH::vertex_descriptor source(
0380     typename DIRECTED_GRAPH::edge_descriptor e, DIRECTED_GRAPH const& g)
0381 {
0382     return source(e, g.impl());
0383 }
0384
0385 template < DIRECTED_GRAPH_PARAMS >
0386 inline typename DIRECTED_GRAPH::vertex_descriptor target(
0387     typename DIRECTED_GRAPH::edge_descriptor e, DIRECTED_GRAPH const& g)
0388 {
0389     return target(e, g.impl());
0390 }
0391
0392 template < DIRECTED_GRAPH_PARAMS >
0393 inline typename DIRECTED_GRAPH::degree_size_type out_degree(
0394     typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g)
0395 {
0396     return out_degree(v, g.impl());
0397 }
0398
0399 template < DIRECTED_GRAPH_PARAMS >
0400 inline std::pair< typename DIRECTED_GRAPH::out_edge_iterator,
0401     typename DIRECTED_GRAPH::out_edge_iterator >
0402 out_edges(typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g)
0403 {
0404     return out_edges(v, g.impl());
0405 }
0406
0407 // BidirectionalGraph concepts
0408 template < DIRECTED_GRAPH_PARAMS >
0409 inline typename DIRECTED_GRAPH::degree_size_type in_degree(
0410     typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g)
0411 {
0412     return in_degree(v, g.impl());
0413 }
0414
0415 template < DIRECTED_GRAPH_PARAMS >
0416 inline std::pair< typename DIRECTED_GRAPH::in_edge_iterator,
0417     typename DIRECTED_GRAPH::in_edge_iterator >
0418 in_edges(typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g)
0419 {
0420     return in_edges(v, g.impl());
0421 }
0422
0423 template < DIRECTED_GRAPH_PARAMS >
0424 inline typename DIRECTED_GRAPH::degree_size_type degree(
0425     typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g)
0426 {
0427     return degree(v, g.impl());
0428 }
0429
0430 // AdjacencyGraph concepts
0431 template < DIRECTED_GRAPH_PARAMS >
0432 inline std::pair< typename DIRECTED_GRAPH::adjacency_iterator,
0433     typename DIRECTED_GRAPH::adjacency_iterator >
0434 adjacent_vertices(
0435     typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g)
0436 {
0437     return adjacent_vertices(v, g.impl());
0438 }
0439
0440 template < DIRECTED_GRAPH_PARAMS >
0441 typename DIRECTED_GRAPH::vertex_descriptor vertex(
0442     typename DIRECTED_GRAPH::vertices_size_type n, DIRECTED_GRAPH const& g)
0443 {
0444     return vertex(n, g.impl());
0445 }
0446
0447 template < DIRECTED_GRAPH_PARAMS >
0448 std::pair< typename DIRECTED_GRAPH::edge_descriptor, bool > edge(
0449     typename DIRECTED_GRAPH::vertex_descriptor u,
0450     typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g)
0451 {
0452     return edge(u, v, g.impl());
0453 }
0454
0455 // VertexListGraph concepts
0456 template < DIRECTED_GRAPH_PARAMS >
0457 inline typename DIRECTED_GRAPH::vertices_size_type num_vertices(
0458     DIRECTED_GRAPH const& g)
0459 {
0460     return g.num_vertices();
0461 }
0462
0463 template < DIRECTED_GRAPH_PARAMS >
0464 inline std::pair< typename DIRECTED_GRAPH::vertex_iterator,
0465     typename DIRECTED_GRAPH::vertex_iterator >
0466 vertices(DIRECTED_GRAPH const& g)
0467 {
0468     return vertices(g.impl());
0469 }
0470
0471 // EdgeListGraph concepts
0472 template < DIRECTED_GRAPH_PARAMS >
0473 inline typename DIRECTED_GRAPH::edges_size_type num_edges(
0474     DIRECTED_GRAPH const& g)
0475 {
0476     return g.num_edges();
0477 }
0478
0479 template < DIRECTED_GRAPH_PARAMS >
0480 inline std::pair< typename DIRECTED_GRAPH::edge_iterator,
0481     typename DIRECTED_GRAPH::edge_iterator >
0482 edges(DIRECTED_GRAPH const& g)
0483 {
0484     return edges(g.impl());
0485 }
0486
0487 // MutableGraph concepts
0488 template < DIRECTED_GRAPH_PARAMS >
0489 inline typename DIRECTED_GRAPH::vertex_descriptor add_vertex(DIRECTED_GRAPH& g)
0490 {
0491     return g.add_vertex();
0492 }
0493
0494 template < DIRECTED_GRAPH_PARAMS >
0495 inline typename DIRECTED_GRAPH::vertex_descriptor add_vertex(
0496     typename DIRECTED_GRAPH::vertex_property_type const& p, DIRECTED_GRAPH& g)
0497 {
0498     return g.add_vertex(p);
0499 }
0500
0501 template < DIRECTED_GRAPH_PARAMS >
0502 inline void clear_vertex(
0503     typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH& g)
0504 {
0505     return g.clear_vertex(v);
0506 }
0507
0508 template < DIRECTED_GRAPH_PARAMS >
0509 inline void remove_vertex(
0510     typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH& g)
0511 {
0512     return g.remove_vertex(v);
0513 }
0514
0515 template < DIRECTED_GRAPH_PARAMS >
0516 inline std::pair< typename DIRECTED_GRAPH::edge_descriptor, bool > add_edge(
0517     typename DIRECTED_GRAPH::vertex_descriptor u,
0518     typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH& g)
0519 {
0520     return g.add_edge(u, v);
0521 }
0522
0523 template < DIRECTED_GRAPH_PARAMS >
0524 inline std::pair< typename DIRECTED_GRAPH::edge_descriptor, bool > add_edge(
0525     typename DIRECTED_GRAPH::vertex_descriptor u,
0526     typename DIRECTED_GRAPH::vertex_descriptor v,
0527     typename DIRECTED_GRAPH::edge_property_type const& p, DIRECTED_GRAPH& g)
0528 {
0529     return g.add_edge(u, v, p);
0530 }
0531
0532 template < DIRECTED_GRAPH_PARAMS >
0533 inline void remove_edge(typename DIRECTED_GRAPH::vertex_descriptor u,
0534     typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH& g)
0535 {
0536     return g.remove_edge(u, v);
0537 }
0538
0539 template < DIRECTED_GRAPH_PARAMS >
0540 inline void remove_edge(
0541     typename DIRECTED_GRAPH::edge_descriptor e, DIRECTED_GRAPH& g)
0542 {
0543     return g.remove_edge(e);
0544 }
0545
0546 template < DIRECTED_GRAPH_PARAMS >
0547 inline void remove_edge(
0548     typename DIRECTED_GRAPH::edge_iterator i, DIRECTED_GRAPH& g)
0549 {
0550     return g.remove_edge(i);
0551 }
0552
0553 template < DIRECTED_GRAPH_PARAMS, class Predicate >
0554 inline void remove_edge_if(Predicate pred, DIRECTED_GRAPH& g)
0555 {
0556     return remove_edge_if(pred, g.impl());
0557 }
0558
0559 template < DIRECTED_GRAPH_PARAMS, class Predicate >
0560 inline void remove_out_edge_if(typename DIRECTED_GRAPH::vertex_descriptor v,
0561     Predicate pred, DIRECTED_GRAPH& g)
0562 {
0563     return remove_out_edge_if(v, pred, g.impl());
0564 }
0565
0566 template < DIRECTED_GRAPH_PARAMS, class Predicate >
0567 inline void remove_in_edge_if(typename DIRECTED_GRAPH::vertex_descriptor v,
0568     Predicate pred, DIRECTED_GRAPH& g)
0569 {
0570     return remove_in_edge_if(v, pred, g.impl());
0571 }
0572
0573 template < DIRECTED_GRAPH_PARAMS, typename Property >
0574 struct property_map< DIRECTED_GRAPH, Property >
0575 : property_map< typename DIRECTED_GRAPH::graph_type, Property >
0576 {
0577 };
0578
0579 template < DIRECTED_GRAPH_PARAMS >
0580 struct property_map< DIRECTED_GRAPH, vertex_all_t >
0581 {
0582     typedef transform_value_property_map< detail::remove_first_property,
0583         typename property_map< typename DIRECTED_GRAPH::graph_type,
0584             vertex_all_t >::const_type >
0585         const_type;
0586     typedef transform_value_property_map< detail::remove_first_property,
0587         typename property_map< typename DIRECTED_GRAPH::graph_type,
0588             vertex_all_t >::type >
0589         type;
0590 };
0591
0592 template < DIRECTED_GRAPH_PARAMS >
0593 struct property_map< DIRECTED_GRAPH, edge_all_t >
0594 {
0595     typedef transform_value_property_map< detail::remove_first_property,
0596         typename property_map< typename DIRECTED_GRAPH::graph_type,
0597             edge_all_t >::const_type >
0598         const_type;
0599     typedef transform_value_property_map< detail::remove_first_property,
0600         typename property_map< typename DIRECTED_GRAPH::graph_type,
0601             edge_all_t >::type >
0602         type;
0603 };
0604
0605 // PropertyGraph concepts
0606 template < DIRECTED_GRAPH_PARAMS, typename Property >
0607 inline typename property_map< DIRECTED_GRAPH, Property >::type get(
0608     Property p, DIRECTED_GRAPH& g)
0609 {
0610     return get(p, g.impl());
0611 }
0612
0613 template < DIRECTED_GRAPH_PARAMS, typename Property >
0614 inline typename property_map< DIRECTED_GRAPH, Property >::const_type get(
0615     Property p, DIRECTED_GRAPH const& g)
0616 {
0617     return get(p, g.impl());
0618 }
0619
0620 template < DIRECTED_GRAPH_PARAMS >
0621 inline typename property_map< DIRECTED_GRAPH, vertex_all_t >::type get(
0622     vertex_all_t, DIRECTED_GRAPH& g)
0623 {
0624     return typename property_map< DIRECTED_GRAPH, vertex_all_t >::type(
0625         detail::remove_first_property(), get(vertex_all, g.impl()));
0626 }
0627
0628 template < DIRECTED_GRAPH_PARAMS >
0629 inline typename property_map< DIRECTED_GRAPH, vertex_all_t >::const_type get(
0630     vertex_all_t, DIRECTED_GRAPH const& g)
0631 {
0632     return typename property_map< DIRECTED_GRAPH, vertex_all_t >::const_type(
0633         detail::remove_first_property(), get(vertex_all, g.impl()));
0634 }
0635
0636 template < DIRECTED_GRAPH_PARAMS >
0637 inline typename property_map< DIRECTED_GRAPH, edge_all_t >::type get(
0638     edge_all_t, DIRECTED_GRAPH& g)
0639 {
0640     return typename property_map< DIRECTED_GRAPH, edge_all_t >::type(
0641         detail::remove_first_property(), get(edge_all, g.impl()));
0642 }
0643
0644 template < DIRECTED_GRAPH_PARAMS >
0645 inline typename property_map< DIRECTED_GRAPH, edge_all_t >::const_type get(
0646     edge_all_t, DIRECTED_GRAPH const& g)
0647 {
0648     return typename property_map< DIRECTED_GRAPH, edge_all_t >::const_type(
0649         detail::remove_first_property(), get(edge_all, g.impl()));
0650 }
0651
0652 template < DIRECTED_GRAPH_PARAMS, typename Property, typename Key >
0653 inline typename property_traits< typename property_map<
0654     typename DIRECTED_GRAPH::graph_type, Property >::const_type >::value_type
0655 get(Property p, DIRECTED_GRAPH const& g, Key const& k)
0656 {
0657     return get(p, g.impl(), k);
0658 }
0659
0660 template < DIRECTED_GRAPH_PARAMS, typename Key >
0661 inline typename property_traits<
0662     typename property_map< typename DIRECTED_GRAPH::graph_type,
0663         vertex_all_t >::const_type >::value_type
0664 get(vertex_all_t, DIRECTED_GRAPH const& g, Key const& k)
0665 {
0666     return get(vertex_all, g.impl(), k).m_base;
0667 }
0668
0669 template < DIRECTED_GRAPH_PARAMS, typename Key >
0670 inline typename property_traits< typename property_map<
0671     typename DIRECTED_GRAPH::graph_type, edge_all_t >::const_type >::value_type
0672 get(edge_all_t, DIRECTED_GRAPH const& g, Key const& k)
0673 {
0674     return get(edge_all, g.impl(), k).m_base;
0675 }
0676
0677 template < DIRECTED_GRAPH_PARAMS, typename Property, typename Key,
0678     typename Value >
0679 inline void put(Property p, DIRECTED_GRAPH& g, Key const& k, Value const& v)
0680 {
0681     put(p, g.impl(), k, v);
0682 }
0683
0684 template < DIRECTED_GRAPH_PARAMS, typename Key, typename Value >
0685 inline void put(vertex_all_t, DIRECTED_GRAPH& g, Key const& k, Value const& v)
0686 {
0687     put(vertex_all, g.impl(), k,
0688         typename DIRECTED_GRAPH::internal_vertex_property(
0689             get(vertex_index, g.impl(), k), v));
0690 }
0691
0692 template < DIRECTED_GRAPH_PARAMS, typename Key, typename Value >
0693 inline void put(edge_all_t, DIRECTED_GRAPH& g, Key const& k, Value const& v)
0694 {
0695     put(edge_all, g.impl(), k,
0696         typename DIRECTED_GRAPH::internal_vertex_property(
0697             get(edge_index, g.impl(), k), v));
0698 }
0699
0700 template < DIRECTED_GRAPH_PARAMS, class Property >
0701 typename graph_property< DIRECTED_GRAPH, Property >::type& get_property(
0702     DIRECTED_GRAPH& g, Property p)
0703 {
0704     return get_property(g.impl(), p);
0705 }
0706
0707 template < DIRECTED_GRAPH_PARAMS, class Property >
0708 typename graph_property< DIRECTED_GRAPH, Property >::type const& get_property(
0709     DIRECTED_GRAPH const& g, Property p)
0710 {
0711     return get_property(g.impl(), p);
0712 }
0713
0714 template < DIRECTED_GRAPH_PARAMS, class Property, class Value >
0715 void set_property(DIRECTED_GRAPH& g, Property p, Value v)
0716 {
0717     return set_property(g.impl(), p, v);
0718 }
0719
0720 // Vertex index management
0721
0722 template < DIRECTED_GRAPH_PARAMS >
0723 inline typename DIRECTED_GRAPH::vertex_index_type get_vertex_index(
0724     typename DIRECTED_GRAPH::vertex_descriptor v, DIRECTED_GRAPH const& g)
0725 {
0726     return get(vertex_index, g, v);
0727 }
0728
0729 template < DIRECTED_GRAPH_PARAMS >
0730 typename DIRECTED_GRAPH::vertex_index_type max_vertex_index(
0731     DIRECTED_GRAPH const& g)
0732 {
0733     return g.max_vertex_index();
0734 }
0735
0736 template < DIRECTED_GRAPH_PARAMS >
0737 inline void renumber_vertex_indices(DIRECTED_GRAPH& g)
0738 {
0739     g.renumber_vertex_indices();
0740 }
0741
0742 template < DIRECTED_GRAPH_PARAMS >
0743 inline void remove_vertex_and_renumber_indices(
0744     typename DIRECTED_GRAPH::vertex_iterator i, DIRECTED_GRAPH& g)
0745 {
0746     g.remove_vertex_and_renumber_indices(i);
0747 }
0748
0749 // Edge index management
0750 template < DIRECTED_GRAPH_PARAMS >
0751 inline typename DIRECTED_GRAPH::edge_index_type get_edge_index(
0752     typename DIRECTED_GRAPH::edge_descriptor v, DIRECTED_GRAPH const& g)
0753 {
0754     return get(edge_index, g, v);
0755 }
0756
0757 template < DIRECTED_GRAPH_PARAMS >
0758 typename DIRECTED_GRAPH::edge_index_type max_edge_index(DIRECTED_GRAPH const& g)
0759 {
0760     return g.max_edge_index();
0761 }
0762
0763 template < DIRECTED_GRAPH_PARAMS >
0764 inline void renumber_edge_indices(DIRECTED_GRAPH& g)
0765 {
0766     g.renumber_edge_indices();
0767 }
0768
0769 template < DIRECTED_GRAPH_PARAMS >
0770 inline void remove_edge_and_renumber_indices(
0771     typename DIRECTED_GRAPH::edge_iterator i, DIRECTED_GRAPH& g)
0772 {
0773     g.remove_edge_and_renumber_indices(i);
0774 }
0775
0776 // Index management
0777 template < DIRECTED_GRAPH_PARAMS >
0778 inline void renumber_indices(DIRECTED_GRAPH& g)
0779 {
0780     g.renumber_indices();
0781 }
0782
0783 // Mutability Traits
0784 template < DIRECTED_GRAPH_PARAMS >
0785 struct graph_mutability_traits< DIRECTED_GRAPH >
0786 {
0787     typedef mutable_property_graph_tag category;
0788 };
0789
0790 #undef DIRECTED_GRAPH_PARAMS
0791 #undef DIRECTED_GRAPH
0792
0793 } /* namespace boost */
0794
0795 #endif