boost/graph/undirected_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_UNDIRECTED_GRAPH_HPP
0008 #define BOOST_GRAPH_UNDIRECTED_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 undirected_graph_tag
0020 {
0021 };
0022
0023 /**
0024  * The undirected_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 VertexIndexGraph, and EdgeIndexGraph concepts. The
0028  * graph is also fully mutable, supporting both insertions and removals of
0029  * 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 undirected_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, undirectedS, internal_vertex_property,
0058         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 undirected_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     inline undirected_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     inline undirected_graph(undirected_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     inline undirected_graph(
0112         vertices_size_type n, GraphProp const& p = GraphProp())
0113     : m_graph(n, p)
0114     , m_num_vertices(n)
0115     , m_num_edges(0)
0116     , m_max_vertex_index(n)
0117     , m_max_edge_index(0)
0118     {
0119         renumber_vertex_indices();
0120     }
0121
0122     template < typename EdgeIterator >
0123     inline undirected_graph(EdgeIterator f, EdgeIterator l,
0124         vertices_size_type n, edges_size_type m = 0,
0125         GraphProp const& p = GraphProp())
0126     : m_graph(f, l, n, m, p)
0127     , m_num_vertices(n)
0128     , m_num_edges(0)
0129     , m_max_vertex_index(n)
0130     , m_max_edge_index(0)
0131     {
0132         // Unfortunately, we have to renumber to ensure correct indexing.
0133         renumber_indices();
0134
0135         // Can't always guarantee that the number of edges is actually
0136         // m if distance(f, l) != m (or is undefined).
0137         m_num_edges = m_max_edge_index = boost::num_edges(m_graph);
0138     }
0139
0140     undirected_graph& operator=(undirected_graph const& g)
0141     {
0142         if (&g != this)
0143         {
0144             m_graph = g.m_graph;
0145             m_num_vertices = g.m_num_vertices;
0146             m_num_edges = g.m_num_edges;
0147             m_max_vertex_index = g.m_max_vertex_index;
0148         }
0149         return *this;
0150     }
0151
0152     // The impl_() methods are not part of the public interface.
0153     graph_type& impl() { return m_graph; }
0154
0155     graph_type const& impl() const { return m_graph; }
0156
0157     // The following methods are not part of the public interface
0158     vertices_size_type num_vertices() const { return m_num_vertices; }
0159
0160 private:
0161     // This helper function manages the attribution of vertex indices.
0162     vertex_descriptor make_index(vertex_descriptor v)
0163     {
0164         boost::put(vertex_index, m_graph, v, m_max_vertex_index);
0165         m_num_vertices++;
0166         m_max_vertex_index++;
0167         return v;
0168     }
0169
0170 public:
0171     vertex_descriptor add_vertex()
0172     {
0173         return make_index(boost::add_vertex(m_graph));
0174     }
0175
0176     vertex_descriptor add_vertex(vertex_property_type const& p)
0177     {
0178         return make_index(
0179             boost::add_vertex(internal_vertex_property(0u, p), m_graph));
0180     }
0181
0182     void clear_vertex(vertex_descriptor v)
0183     {
0184         std::pair< out_edge_iterator, out_edge_iterator > p
0185             = boost::out_edges(v, m_graph);
0186         m_num_edges -= std::distance(p.first, p.second);
0187         boost::clear_vertex(v, m_graph);
0188     }
0189
0190     void remove_vertex(vertex_descriptor v)
0191     {
0192         boost::remove_vertex(v, m_graph);
0193         --m_num_vertices;
0194     }
0195
0196     edges_size_type num_edges() const { return m_num_edges; }
0197
0198 private:
0199     // A helper fucntion for managing edge index attributes.
0200     std::pair< edge_descriptor, bool > const& make_index(
0201         std::pair< edge_descriptor, bool > const& x)
0202     {
0203         if (x.second)
0204         {
0205             boost::put(edge_index, m_graph, x.first, m_max_edge_index);
0206             ++m_num_edges;
0207             ++m_max_edge_index;
0208         }
0209         return x;
0210     }
0211
0212 public:
0213     std::pair< edge_descriptor, bool > add_edge(
0214         vertex_descriptor u, vertex_descriptor v)
0215     {
0216         return make_index(boost::add_edge(u, v, m_graph));
0217     }
0218
0219     std::pair< edge_descriptor, bool > add_edge(
0220         vertex_descriptor u, vertex_descriptor v, edge_property_type const& p)
0221     {
0222         return make_index(
0223             boost::add_edge(u, v, internal_edge_property(0u, p), m_graph));
0224     }
0225
0226     void remove_edge(vertex_descriptor u, vertex_descriptor v)
0227     {
0228         // find all edges, (u, v)
0229         std::vector< edge_descriptor > edges;
0230         out_edge_iterator i, i_end;
0231         for (boost::tie(i, i_end) = boost::out_edges(u, m_graph); i != i_end;
0232              ++i)
0233         {
0234             if (boost::target(*i, m_graph) == v)
0235             {
0236                 edges.push_back(*i);
0237             }
0238         }
0239         // remove all edges, (u, v)
0240         typename std::vector< edge_descriptor >::iterator j = edges.begin(),
0241                                                           j_end = edges.end();
0242         for (; j != j_end; ++j)
0243         {
0244             remove_edge(*j);
0245         }
0246     }
0247
0248     void remove_edge(edge_iterator i) { remove_edge(*i); }
0249
0250     void remove_edge(edge_descriptor e)
0251     {
0252         boost::remove_edge(e, m_graph);
0253         --m_num_edges;
0254     }
0255
0256     vertex_index_type max_vertex_index() const { return m_max_vertex_index; }
0257
0258     void renumber_vertex_indices()
0259     {
0260         vertex_iterator i, i_end;
0261         boost::tie(i, i_end) = vertices(m_graph);
0262         m_max_vertex_index = renumber_vertex_indices(i, i_end, 0);
0263     }
0264
0265     void remove_vertex_and_renumber_indices(vertex_iterator i)
0266     {
0267         vertex_iterator j = next(i), end = vertices(m_graph).second;
0268         vertex_index_type n = get(vertex_index, m_graph, *i);
0269
0270         // remove the offending vertex and renumber everything after
0271         remove_vertex(*i);
0272         m_max_vertex_index = renumber_vertex_indices(j, end, n);
0273     }
0274
0275     edge_index_type max_edge_index() const { return m_max_edge_index; }
0276
0277     void renumber_edge_indices()
0278     {
0279         edge_iterator i, end;
0280         boost::tie(i, end) = edges(m_graph);
0281         m_max_edge_index = renumber_edge_indices(i, end, 0);
0282     }
0283
0284     void remove_edge_and_renumber_indices(edge_iterator i)
0285     {
0286         edge_iterator j = next(i), end = edges(m_graph.second);
0287         edge_index_type n = get(edge_index, m_graph, *i);
0288
0289         // remove the edge and renumber everything after it
0290         remove_edge(*i);
0291         m_max_edge_index = renumber_edge_indices(j, end, n);
0292     }
0293
0294     void renumber_indices()
0295     {
0296         renumber_vertex_indices();
0297         renumber_edge_indices();
0298     }
0299
0300     // bundled property support
0301 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
0302     vertex_bundled& operator[](vertex_descriptor v) { return m_graph[v]; }
0303
0304     vertex_bundled const& operator[](vertex_descriptor v) const
0305     {
0306         return m_graph[v];
0307     }
0308
0309     edge_bundled& operator[](edge_descriptor e) { return m_graph[e]; }
0310
0311     edge_bundled const& operator[](edge_descriptor e) const
0312     {
0313         return m_graph[e];
0314     }
0315
0316     graph_bundled& operator[](graph_bundle_t) { return get_property(*this); }
0317
0318     graph_bundled const& operator[](graph_bundle_t) const
0319     {
0320         return get_property(*this);
0321     }
0322 #endif
0323
0324     // Graph concepts
0325     static vertex_descriptor null_vertex() { return graph_type::null_vertex(); }
0326
0327     void clear()
0328     {
0329         m_graph.clear();
0330         m_num_vertices = m_max_vertex_index = 0;
0331         m_num_edges = m_max_edge_index = 0;
0332     }
0333
0334     void swap(undirected_graph& g)
0335     {
0336         m_graph.swap(g.m_graph);
0337         std::swap(m_num_vertices, g.m_num_vertices);
0338         std::swap(m_max_vertex_index, g.m_max_vertex_index);
0339         std::swap(m_num_edges, g.m_num_edges);
0340         std::swap(m_max_edge_index, g.m_max_edge_index);
0341     }
0342
0343 private:
0344     vertices_size_type renumber_vertex_indices(
0345         vertex_iterator i, vertex_iterator end, vertices_size_type n)
0346     {
0347         typedef
0348             typename property_map< graph_type, vertex_index_t >::type IndexMap;
0349         IndexMap indices = get(vertex_index, m_graph);
0350         for (; i != end; ++i)
0351         {
0352             indices[*i] = n++;
0353         }
0354         return n;
0355     }
0356
0357     edges_size_type renumber_edge_indices(
0358         edge_iterator i, edge_iterator end, edges_size_type n)
0359     {
0360         typedef
0361             typename property_map< graph_type, edge_index_t >::type IndexMap;
0362         IndexMap indices = get(edge_index, m_graph);
0363         for (; i != end; ++i)
0364         {
0365             indices[*i] = n++;
0366         }
0367         return n;
0368     }
0369
0370     graph_type m_graph;
0371     vertices_size_type m_num_vertices;
0372     edges_size_type m_num_edges;
0373     vertex_index_type m_max_vertex_index;
0374     edge_index_type m_max_edge_index;
0375 };
0376
0377 #define UNDIRECTED_GRAPH_PARAMS typename VP, typename EP, typename GP
0378 #define UNDIRECTED_GRAPH undirected_graph< VP, EP, GP >
0379
0380 // IncidenceGraph concepts
0381 template < UNDIRECTED_GRAPH_PARAMS >
0382 inline typename UNDIRECTED_GRAPH::vertex_descriptor source(
0383     typename UNDIRECTED_GRAPH::edge_descriptor e, UNDIRECTED_GRAPH const& g)
0384 {
0385     return source(e, g.impl());
0386 }
0387
0388 template < UNDIRECTED_GRAPH_PARAMS >
0389 inline typename UNDIRECTED_GRAPH::vertex_descriptor target(
0390     typename UNDIRECTED_GRAPH::edge_descriptor e, UNDIRECTED_GRAPH const& g)
0391 {
0392     return target(e, g.impl());
0393 }
0394
0395 template < UNDIRECTED_GRAPH_PARAMS >
0396 inline typename UNDIRECTED_GRAPH::degree_size_type out_degree(
0397     typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g)
0398 {
0399     return out_degree(v, g.impl());
0400 }
0401
0402 template < UNDIRECTED_GRAPH_PARAMS >
0403 inline std::pair< typename UNDIRECTED_GRAPH::out_edge_iterator,
0404     typename UNDIRECTED_GRAPH::out_edge_iterator >
0405 out_edges(
0406     typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g)
0407 {
0408     return out_edges(v, g.impl());
0409 }
0410
0411 // BidirectionalGraph concepts
0412 template < UNDIRECTED_GRAPH_PARAMS >
0413 inline typename UNDIRECTED_GRAPH::degree_size_type in_degree(
0414     typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g)
0415 {
0416     return in_degree(v, g.impl());
0417 }
0418
0419 template < UNDIRECTED_GRAPH_PARAMS >
0420 inline std::pair< typename UNDIRECTED_GRAPH::in_edge_iterator,
0421     typename UNDIRECTED_GRAPH::in_edge_iterator >
0422 in_edges(
0423     typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g)
0424 {
0425     return in_edges(v, g.impl());
0426 }
0427
0428 template < UNDIRECTED_GRAPH_PARAMS >
0429 inline std::pair< typename UNDIRECTED_GRAPH::out_edge_iterator,
0430     typename UNDIRECTED_GRAPH::out_edge_iterator >
0431 incident_edges(
0432     typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g)
0433 {
0434     return out_edges(v, g.impl());
0435 }
0436
0437 template < UNDIRECTED_GRAPH_PARAMS >
0438 inline typename UNDIRECTED_GRAPH::degree_size_type degree(
0439     typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g)
0440 {
0441     return degree(v, g.impl());
0442 }
0443
0444 // AdjacencyGraph concepts
0445 template < UNDIRECTED_GRAPH_PARAMS >
0446 inline std::pair< typename UNDIRECTED_GRAPH::adjacency_iterator,
0447     typename UNDIRECTED_GRAPH::adjacency_iterator >
0448 adjacent_vertices(
0449     typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g)
0450 {
0451     return adjacent_vertices(v, g.impl());
0452 }
0453
0454 template < UNDIRECTED_GRAPH_PARAMS >
0455 typename UNDIRECTED_GRAPH::vertex_descriptor vertex(
0456     typename UNDIRECTED_GRAPH::vertices_size_type n, UNDIRECTED_GRAPH const& g)
0457 {
0458     return vertex(n, g.impl());
0459 }
0460
0461 template < UNDIRECTED_GRAPH_PARAMS >
0462 std::pair< typename UNDIRECTED_GRAPH::edge_descriptor, bool > edge(
0463     typename UNDIRECTED_GRAPH::vertex_descriptor u,
0464     typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g)
0465 {
0466     return edge(u, v, g.impl());
0467 }
0468
0469 // VertexListGraph concepts
0470 template < UNDIRECTED_GRAPH_PARAMS >
0471 inline typename UNDIRECTED_GRAPH::vertices_size_type num_vertices(
0472     UNDIRECTED_GRAPH const& g)
0473 {
0474     return g.num_vertices();
0475 }
0476
0477 template < UNDIRECTED_GRAPH_PARAMS >
0478 inline std::pair< typename UNDIRECTED_GRAPH::vertex_iterator,
0479     typename UNDIRECTED_GRAPH::vertex_iterator >
0480 vertices(UNDIRECTED_GRAPH const& g)
0481 {
0482     return vertices(g.impl());
0483 }
0484
0485 // EdgeListGraph concepts
0486 template < UNDIRECTED_GRAPH_PARAMS >
0487 inline typename UNDIRECTED_GRAPH::edges_size_type num_edges(
0488     UNDIRECTED_GRAPH const& g)
0489 {
0490     return g.num_edges();
0491 }
0492
0493 template < UNDIRECTED_GRAPH_PARAMS >
0494 inline std::pair< typename UNDIRECTED_GRAPH::edge_iterator,
0495     typename UNDIRECTED_GRAPH::edge_iterator >
0496 edges(UNDIRECTED_GRAPH const& g)
0497 {
0498     return edges(g.impl());
0499 }
0500
0501 // MutableGraph concepts
0502 template < UNDIRECTED_GRAPH_PARAMS >
0503 inline typename UNDIRECTED_GRAPH::vertex_descriptor add_vertex(
0504     UNDIRECTED_GRAPH& g)
0505 {
0506     return g.add_vertex();
0507 }
0508
0509 template < UNDIRECTED_GRAPH_PARAMS >
0510 inline typename UNDIRECTED_GRAPH::vertex_descriptor add_vertex(
0511     typename UNDIRECTED_GRAPH::vertex_property_type const& p,
0512     UNDIRECTED_GRAPH& g)
0513 {
0514     return g.add_vertex(p);
0515 }
0516
0517 template < UNDIRECTED_GRAPH_PARAMS >
0518 inline void clear_vertex(
0519     typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH& g)
0520 {
0521     return g.clear_vertex(v);
0522 }
0523
0524 template < UNDIRECTED_GRAPH_PARAMS >
0525 inline void remove_vertex(
0526     typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH& g)
0527 {
0528     return g.remove_vertex(v);
0529 }
0530
0531 template < UNDIRECTED_GRAPH_PARAMS >
0532 inline std::pair< typename UNDIRECTED_GRAPH::edge_descriptor, bool > add_edge(
0533     typename UNDIRECTED_GRAPH::vertex_descriptor u,
0534     typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH& g)
0535 {
0536     return g.add_edge(u, v);
0537 }
0538
0539 template < UNDIRECTED_GRAPH_PARAMS >
0540 inline std::pair< typename UNDIRECTED_GRAPH::edge_descriptor, bool > add_edge(
0541     typename UNDIRECTED_GRAPH::vertex_descriptor u,
0542     typename UNDIRECTED_GRAPH::vertex_descriptor v,
0543     typename UNDIRECTED_GRAPH::edge_property_type const& p, UNDIRECTED_GRAPH& g)
0544 {
0545     return g.add_edge(u, v, p);
0546 }
0547
0548 template < UNDIRECTED_GRAPH_PARAMS >
0549 inline void remove_edge(typename UNDIRECTED_GRAPH::vertex_descriptor u,
0550     typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH& g)
0551 {
0552     return g.remove_edge(u, v);
0553 }
0554
0555 template < UNDIRECTED_GRAPH_PARAMS >
0556 inline void remove_edge(
0557     typename UNDIRECTED_GRAPH::edge_descriptor e, UNDIRECTED_GRAPH& g)
0558 {
0559     return g.remove_edge(e);
0560 }
0561
0562 template < UNDIRECTED_GRAPH_PARAMS >
0563 inline void remove_edge(
0564     typename UNDIRECTED_GRAPH::edge_iterator i, UNDIRECTED_GRAPH& g)
0565 {
0566     return g.remove_edge(i);
0567 }
0568
0569 template < UNDIRECTED_GRAPH_PARAMS, class Predicate >
0570 inline void remove_edge_if(Predicate pred, UNDIRECTED_GRAPH& g)
0571 {
0572     return remove_edge_if(pred, g.impl());
0573 }
0574
0575 template < UNDIRECTED_GRAPH_PARAMS, class Predicate >
0576 inline void remove_incident_edge_if(
0577     typename UNDIRECTED_GRAPH::vertex_descriptor v, Predicate pred,
0578     UNDIRECTED_GRAPH& g)
0579 {
0580     return remove_out_edge_if(v, pred, g.impl());
0581 }
0582
0583 template < UNDIRECTED_GRAPH_PARAMS, class Predicate >
0584 inline void remove_out_edge_if(typename UNDIRECTED_GRAPH::vertex_descriptor v,
0585     Predicate pred, UNDIRECTED_GRAPH& g)
0586 {
0587     return remove_out_edge_if(v, pred, g.impl());
0588 }
0589
0590 template < UNDIRECTED_GRAPH_PARAMS, class Predicate >
0591 inline void remove_in_edge_if(typename UNDIRECTED_GRAPH::vertex_descriptor v,
0592     Predicate pred, UNDIRECTED_GRAPH& g)
0593 {
0594     return remove_in_edge_if(v, pred, g.impl());
0595 }
0596
0597 template < UNDIRECTED_GRAPH_PARAMS, typename Property >
0598 struct property_map< UNDIRECTED_GRAPH, Property >
0599 : property_map< typename UNDIRECTED_GRAPH::graph_type, Property >
0600 {
0601 };
0602
0603 template < UNDIRECTED_GRAPH_PARAMS >
0604 struct property_map< UNDIRECTED_GRAPH, vertex_all_t >
0605 {
0606     typedef transform_value_property_map< detail::remove_first_property,
0607         typename property_map< typename UNDIRECTED_GRAPH::graph_type,
0608             vertex_all_t >::const_type >
0609         const_type;
0610     typedef transform_value_property_map< detail::remove_first_property,
0611         typename property_map< typename UNDIRECTED_GRAPH::graph_type,
0612             vertex_all_t >::type >
0613         type;
0614 };
0615
0616 template < UNDIRECTED_GRAPH_PARAMS >
0617 struct property_map< UNDIRECTED_GRAPH, edge_all_t >
0618 {
0619     typedef transform_value_property_map< detail::remove_first_property,
0620         typename property_map< typename UNDIRECTED_GRAPH::graph_type,
0621             edge_all_t >::const_type >
0622         const_type;
0623     typedef transform_value_property_map< detail::remove_first_property,
0624         typename property_map< typename UNDIRECTED_GRAPH::graph_type,
0625             edge_all_t >::type >
0626         type;
0627 };
0628
0629 // PropertyGraph concepts
0630 template < UNDIRECTED_GRAPH_PARAMS, typename Property >
0631 inline typename property_map< UNDIRECTED_GRAPH, Property >::type get(
0632     Property p, UNDIRECTED_GRAPH& g)
0633 {
0634     return get(p, g.impl());
0635 }
0636
0637 template < UNDIRECTED_GRAPH_PARAMS, typename Property >
0638 inline typename property_map< UNDIRECTED_GRAPH, Property >::const_type get(
0639     Property p, UNDIRECTED_GRAPH const& g)
0640 {
0641     return get(p, g.impl());
0642 }
0643
0644 template < UNDIRECTED_GRAPH_PARAMS >
0645 inline typename property_map< UNDIRECTED_GRAPH, vertex_all_t >::type get(
0646     vertex_all_t, UNDIRECTED_GRAPH& g)
0647 {
0648     return typename property_map< UNDIRECTED_GRAPH, vertex_all_t >::type(
0649         detail::remove_first_property(), get(vertex_all, g.impl()));
0650 }
0651
0652 template < UNDIRECTED_GRAPH_PARAMS >
0653 inline typename property_map< UNDIRECTED_GRAPH, vertex_all_t >::const_type get(
0654     vertex_all_t, UNDIRECTED_GRAPH const& g)
0655 {
0656     return typename property_map< UNDIRECTED_GRAPH, vertex_all_t >::const_type(
0657         detail::remove_first_property(), get(vertex_all, g.impl()));
0658 }
0659
0660 template < UNDIRECTED_GRAPH_PARAMS >
0661 inline typename property_map< UNDIRECTED_GRAPH, edge_all_t >::type get(
0662     edge_all_t, UNDIRECTED_GRAPH& g)
0663 {
0664     return typename property_map< UNDIRECTED_GRAPH, edge_all_t >::type(
0665         detail::remove_first_property(), get(edge_all, g.impl()));
0666 }
0667
0668 template < UNDIRECTED_GRAPH_PARAMS >
0669 inline typename property_map< UNDIRECTED_GRAPH, edge_all_t >::const_type get(
0670     edge_all_t, UNDIRECTED_GRAPH const& g)
0671 {
0672     return typename property_map< UNDIRECTED_GRAPH, edge_all_t >::const_type(
0673         detail::remove_first_property(), get(edge_all, g.impl()));
0674 }
0675
0676 template < UNDIRECTED_GRAPH_PARAMS, typename Property, typename Key >
0677 inline typename property_traits< typename property_map<
0678     typename UNDIRECTED_GRAPH::graph_type, Property >::const_type >::value_type
0679 get(Property p, UNDIRECTED_GRAPH const& g, Key const& k)
0680 {
0681     return get(p, g.impl(), k);
0682 }
0683
0684 template < UNDIRECTED_GRAPH_PARAMS, typename Key >
0685 inline typename property_traits<
0686     typename property_map< typename UNDIRECTED_GRAPH::graph_type,
0687         vertex_all_t >::const_type >::value_type
0688 get(vertex_all_t, UNDIRECTED_GRAPH const& g, Key const& k)
0689 {
0690     return get(vertex_all, g.impl(), k).m_base;
0691 }
0692
0693 template < UNDIRECTED_GRAPH_PARAMS, typename Key >
0694 inline typename property_traits<
0695     typename property_map< typename UNDIRECTED_GRAPH::graph_type,
0696         edge_all_t >::const_type >::value_type
0697 get(edge_all_t, UNDIRECTED_GRAPH const& g, Key const& k)
0698 {
0699     return get(edge_all, g.impl(), k).m_base;
0700 }
0701
0702 template < UNDIRECTED_GRAPH_PARAMS, typename Property, typename Key,
0703     typename Value >
0704 inline void put(Property p, UNDIRECTED_GRAPH& g, Key const& k, Value const& v)
0705 {
0706     put(p, g.impl(), k, v);
0707 }
0708
0709 template < UNDIRECTED_GRAPH_PARAMS, typename Key, typename Value >
0710 inline void put(vertex_all_t, UNDIRECTED_GRAPH& g, Key const& k, Value const& v)
0711 {
0712     put(vertex_all, g.impl(), k,
0713         typename UNDIRECTED_GRAPH::internal_vertex_property(
0714             get(vertex_index, g.impl(), k), v));
0715 }
0716
0717 template < UNDIRECTED_GRAPH_PARAMS, typename Key, typename Value >
0718 inline void put(edge_all_t, UNDIRECTED_GRAPH& g, Key const& k, Value const& v)
0719 {
0720     put(edge_all, g.impl(), k,
0721         typename UNDIRECTED_GRAPH::internal_vertex_property(
0722             get(edge_index, g.impl(), k), v));
0723 }
0724
0725 template < UNDIRECTED_GRAPH_PARAMS, class Property >
0726 inline typename graph_property< UNDIRECTED_GRAPH, Property >::type&
0727 get_property(UNDIRECTED_GRAPH& g, Property p)
0728 {
0729     return get_property(g.impl(), p);
0730 }
0731
0732 template < UNDIRECTED_GRAPH_PARAMS, class Property >
0733 inline typename graph_property< UNDIRECTED_GRAPH, Property >::type const&
0734 get_property(UNDIRECTED_GRAPH const& g, Property p)
0735 {
0736     return get_property(g.impl(), p);
0737 }
0738
0739 template < UNDIRECTED_GRAPH_PARAMS, class Property, class Value >
0740 inline void set_property(UNDIRECTED_GRAPH& g, Property p, Value v)
0741 {
0742     return set_property(g.impl(), p, v);
0743 }
0744
0745 // Indexed Vertex graph
0746
0747 template < UNDIRECTED_GRAPH_PARAMS >
0748 inline typename UNDIRECTED_GRAPH::vertex_index_type get_vertex_index(
0749     typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH const& g)
0750 {
0751     return get(vertex_index, g, v);
0752 }
0753
0754 template < UNDIRECTED_GRAPH_PARAMS >
0755 typename UNDIRECTED_GRAPH::vertex_index_type max_vertex_index(
0756     UNDIRECTED_GRAPH const& g)
0757 {
0758     return g.max_vertex_index();
0759 }
0760
0761 template < UNDIRECTED_GRAPH_PARAMS >
0762 inline void renumber_vertex_indices(UNDIRECTED_GRAPH& g)
0763 {
0764     g.renumber_vertex_indices();
0765 }
0766
0767 template < UNDIRECTED_GRAPH_PARAMS >
0768 inline void remove_vertex_and_renumber_indices(
0769     typename UNDIRECTED_GRAPH::vertex_iterator i, UNDIRECTED_GRAPH& g)
0770 {
0771     g.remove_vertex_and_renumber_indices(i);
0772 }
0773
0774 // Edge index management
0775
0776 template < UNDIRECTED_GRAPH_PARAMS >
0777 inline typename UNDIRECTED_GRAPH::edge_index_type get_edge_index(
0778     typename UNDIRECTED_GRAPH::edge_descriptor v, UNDIRECTED_GRAPH const& g)
0779 {
0780     return get(edge_index, g, v);
0781 }
0782
0783 template < UNDIRECTED_GRAPH_PARAMS >
0784 typename UNDIRECTED_GRAPH::edge_index_type max_edge_index(
0785     UNDIRECTED_GRAPH const& g)
0786 {
0787     return g.max_edge_index();
0788 }
0789
0790 template < UNDIRECTED_GRAPH_PARAMS >
0791 inline void renumber_edge_indices(UNDIRECTED_GRAPH& g)
0792 {
0793     g.renumber_edge_indices();
0794 }
0795
0796 template < UNDIRECTED_GRAPH_PARAMS >
0797 inline void remove_edge_and_renumber_indices(
0798     typename UNDIRECTED_GRAPH::edge_iterator i, UNDIRECTED_GRAPH& g)
0799 {
0800     g.remove_edge_and_renumber_indices(i);
0801 }
0802
0803 // Index management
0804 template < UNDIRECTED_GRAPH_PARAMS >
0805 inline void renumber_indices(UNDIRECTED_GRAPH& g)
0806 {
0807     g.renumber_indices();
0808 }
0809
0810 // Mutability Traits
0811 template < UNDIRECTED_GRAPH_PARAMS >
0812 struct graph_mutability_traits< UNDIRECTED_GRAPH >
0813 {
0814     typedef mutable_property_graph_tag category;
0815 };
0816
0817 #undef UNDIRECTED_GRAPH_PARAMS
0818 #undef UNDIRECTED_GRAPH
0819
0820 } /* namespace boost */
0821
0822 #endif