ceph/src/boost/boost/graph/undirected_graph.hpp

   1 // (C) Copyright 2007-2009 Andrew Sutton
   2 //
   3 // Use, modification and distribution are subject to the
   4 // Boost Software License, Version 1.0 (See accompanying file
   5 // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
   6
   7 #ifndef BOOST_GRAPH_UNDIRECTED_GRAPH_HPP
   8 #define BOOST_GRAPH_UNDIRECTED_GRAPH_HPP
   9
  10 #include <boost/graph/adjacency_list.hpp>
  11 #include <boost/graph/properties.hpp>
  12 #include <boost/pending/property.hpp>
  13 #include <boost/property_map/transform_value_property_map.hpp>
  14 #include <boost/type_traits.hpp>
  15 #include <boost/mpl/if.hpp>
  16
  17 namespace boost
  18 {
  19 struct undirected_graph_tag { };
  20
  21 /**
  22  * The undirected_graph class template is a simplified version of the BGL
  23  * adjacency list. This class is provided for ease of use, but may not
  24  * perform as well as custom-defined adjacency list classes. Instances of
  25  * this template model the VertexIndexGraph, and EdgeIndexGraph concepts. The
  26  * graph is also fully mutable, supporting both insertions and removals of
  27  * vertices and edges.
  28  *
  29  * @note Special care must be taken when removing vertices or edges since
  30  * those operations can invalidate the numbering of vertices.
  31  */
  32 template <
  33     typename VertexProp = no_property,
  34     typename EdgeProp = no_property,
  35     typename GraphProp = no_property>
  36 class undirected_graph
  37 {
  38 public:
  39     typedef GraphProp graph_property_type;
  40     typedef VertexProp vertex_property_type;
  41     typedef EdgeProp edge_property_type;
  42     typedef typename lookup_one_property<GraphProp, graph_bundle_t>::type graph_bundled;
  43     typedef typename lookup_one_property<VertexProp, vertex_bundle_t>::type vertex_bundled;
  44     typedef typename lookup_one_property<EdgeProp, edge_bundle_t>::type edge_bundled;
  45
  46 public:
  47     // Embed indices into the vertex type.
  48     typedef property<vertex_index_t, unsigned, vertex_property_type> internal_vertex_property;
  49     typedef property<edge_index_t, unsigned, edge_property_type> internal_edge_property;
  50 public:
  51     typedef adjacency_list<listS,
  52                 listS,
  53                 undirectedS,
  54                 internal_vertex_property,
  55                 internal_edge_property,
  56                 GraphProp,
  57                 listS> graph_type;
  58 private:
  59     // storage selectors
  60     typedef typename graph_type::vertex_list_selector vertex_list_selector;
  61     typedef typename graph_type::edge_list_selector edge_list_selector;
  62     typedef typename graph_type::out_edge_list_selector out_edge_list_selector;
  63     typedef typename graph_type::directed_selector directed_selector;
  64
  65 public:
  66     // more commonly used graph types
  67     typedef typename graph_type::stored_vertex stored_vertex;
  68     typedef typename graph_type::vertices_size_type vertices_size_type;
  69     typedef typename graph_type::edges_size_type edges_size_type;
  70     typedef typename graph_type::degree_size_type degree_size_type;
  71     typedef typename graph_type::vertex_descriptor vertex_descriptor;
  72     typedef typename graph_type::edge_descriptor edge_descriptor;
  73
  74     // iterator types
  75     typedef typename graph_type::vertex_iterator vertex_iterator;
  76     typedef typename graph_type::edge_iterator edge_iterator;
  77     typedef typename graph_type::out_edge_iterator out_edge_iterator;
  78     typedef typename graph_type::in_edge_iterator in_edge_iterator;
  79     typedef typename graph_type::adjacency_iterator adjacency_iterator;
  80
  81     // miscellaneous types
  82     typedef undirected_graph_tag graph_tag;
  83     typedef typename graph_type::directed_category directed_category;
  84     typedef typename graph_type::edge_parallel_category edge_parallel_category;
  85     typedef typename graph_type::traversal_category traversal_category;
  86
  87     typedef std::size_t vertex_index_type;
  88     typedef std::size_t edge_index_type;
  89
  90     inline undirected_graph(GraphProp const& p = GraphProp())
  91         : m_graph(p), m_num_vertices(0), m_num_edges(0), m_max_vertex_index(0)
  92         , m_max_edge_index(0)
  93     { }
  94
  95     inline undirected_graph(undirected_graph const& x)
  96         : m_graph(x.m_graph), m_num_vertices(x.m_num_vertices), m_num_edges(x.m_num_edges)
  97         , m_max_vertex_index(x.m_max_vertex_index), m_max_edge_index(x.m_max_edge_index)
  98     { }
  99
 100     inline undirected_graph(vertices_size_type n,
 101                             GraphProp const& p = GraphProp())
 102         : m_graph(n, p), m_num_vertices(n), m_num_edges(0), m_max_vertex_index(n)
 103         , m_max_edge_index(0)
 104     { renumber_vertex_indices(); }
 105
 106     template <typename EdgeIterator>
 107     inline undirected_graph(EdgeIterator f,
 108                             EdgeIterator l,
 109                             vertices_size_type n,
 110                             edges_size_type m = 0,
 111                             GraphProp const& p = GraphProp())
 112         : m_graph(f, l, n, m, p), m_num_vertices(n), m_num_edges(0)
 113         , m_max_vertex_index(n), m_max_edge_index(0)
 114     {
 115         // Unfortunately, we have to renumber to ensure correct indexing.
 116         renumber_indices();
 117
 118         // Can't always guarantee that the number of edges is actually
 119         // m if distance(f, l) != m (or is undefined).
 120         m_num_edges = m_max_edge_index = boost::num_edges(m_graph);
 121     }
 122
 123     undirected_graph& operator =(undirected_graph const& g) {
 124         if(&g != this) {
 125             m_graph = g.m_graph;
 126             m_num_vertices = g.m_num_vertices;
 127             m_num_edges = g.m_num_edges;
 128             m_max_vertex_index = g.m_max_vertex_index;
 129         }
 130         return *this;
 131     }
 132
 133     // The impl_() methods are not part of the public interface.
 134     graph_type& impl()
 135     { return m_graph; }
 136
 137     graph_type const& impl() const
 138     { return m_graph; }
 139
 140     // The following methods are not part of the public interface
 141     vertices_size_type num_vertices() const
 142     { return m_num_vertices; }
 143
 144
 145 private:
 146     // This helper function manages the attribution of vertex indices.
 147     vertex_descriptor make_index(vertex_descriptor v) {
 148         boost::put(vertex_index, m_graph, v, m_max_vertex_index);
 149         m_num_vertices++;
 150         m_max_vertex_index++;
 151         return v;
 152     }
 153 public:
 154     vertex_descriptor add_vertex()
 155     { return make_index(boost::add_vertex(m_graph)); }
 156
 157     vertex_descriptor add_vertex(vertex_property_type const& p)
 158     { return make_index(boost::add_vertex(internal_vertex_property(0u, p), m_graph)); }
 159
 160     void clear_vertex(vertex_descriptor v) {
 161         std::pair<out_edge_iterator, out_edge_iterator>
 162         p = boost::out_edges(v, m_graph);
 163         m_num_edges -= std::distance(p.first, p.second);
 164         boost::clear_vertex(v, m_graph);
 165     }
 166
 167     void remove_vertex(vertex_descriptor v) {
 168         boost::remove_vertex(v, m_graph);
 169         --m_num_vertices;
 170     }
 171
 172     edges_size_type num_edges() const
 173     { return m_num_edges; }
 174
 175 private:
 176     // A helper fucntion for managing edge index attributes.
 177     std::pair<edge_descriptor, bool> const&
 178     make_index(std::pair<edge_descriptor, bool> const& x)
 179     {
 180         if(x.second) {
 181             boost::put(edge_index, m_graph, x.first, m_max_edge_index);
 182             ++m_num_edges;
 183             ++m_max_edge_index;
 184         }
 185         return x;
 186     }
 187 public:
 188     std::pair<edge_descriptor, bool>
 189     add_edge(vertex_descriptor u, vertex_descriptor v)
 190     { return make_index(boost::add_edge(u, v, m_graph)); }
 191
 192     std::pair<edge_descriptor, bool>
 193     add_edge(vertex_descriptor u, vertex_descriptor v,
 194              edge_property_type const& p)
 195     { return make_index(boost::add_edge(u, v, internal_edge_property(0u, p), m_graph)); }
 196
 197     void remove_edge(vertex_descriptor u, vertex_descriptor v) {
 198         // find all edges, (u, v)
 199         std::vector<edge_descriptor> edges;
 200         out_edge_iterator i, i_end;
 201         for(boost::tie(i, i_end) = boost::out_edges(u, m_graph); i != i_end; ++i) {
 202             if(boost::target(*i, m_graph) == v) {
 203                 edges.push_back(*i);
 204             }
 205         }
 206         // remove all edges, (u, v)
 207         typename std::vector<edge_descriptor>::iterator
 208         j = edges.begin(), j_end = edges.end();
 209         for( ; j != j_end; ++j) {
 210             remove_edge(*j);
 211         }
 212     }
 213
 214     void remove_edge(edge_iterator i) {
 215         remove_edge(*i);
 216     }
 217
 218     void remove_edge(edge_descriptor e) {
 219         boost::remove_edge(e, m_graph);
 220         --m_num_edges;
 221     }
 222
 223     vertex_index_type max_vertex_index() const
 224     { return m_max_vertex_index; }
 225
 226     void renumber_vertex_indices() {
 227         vertex_iterator i, i_end;
 228         boost::tie(i, i_end) = vertices(m_graph);
 229         m_max_vertex_index = renumber_vertex_indices(i, i_end, 0);
 230     }
 231
 232     void remove_vertex_and_renumber_indices(vertex_iterator i) {
 233         vertex_iterator j = next(i), end = vertices(m_graph).second;
 234         vertex_index_type n = get(vertex_index, m_graph, *i);
 235
 236         // remove the offending vertex and renumber everything after
 237         remove_vertex(*i);
 238         m_max_vertex_index = renumber_vertex_indices(j, end, n);
 239     }
 240
 241
 242     edge_index_type max_edge_index() const
 243     { return m_max_edge_index; }
 244
 245     void renumber_edge_indices() {
 246         edge_iterator i, end;
 247         boost::tie(i, end) = edges(m_graph);
 248         m_max_edge_index = renumber_edge_indices(i, end, 0);
 249     }
 250
 251     void remove_edge_and_renumber_indices(edge_iterator i) {
 252         edge_iterator j = next(i), end = edges(m_graph.second);
 253         edge_index_type n = get(edge_index, m_graph, *i);
 254
 255         // remove the edge and renumber everything after it
 256         remove_edge(*i);
 257         m_max_edge_index = renumber_edge_indices(j, end, n);
 258     }
 259
 260     void renumber_indices() {
 261         renumber_vertex_indices();
 262         renumber_edge_indices();
 263     }
 264
 265     // bundled property support
 266 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
 267     vertex_bundled& operator[](vertex_descriptor v)
 268     { return m_graph[v]; }
 269
 270     vertex_bundled const& operator[](vertex_descriptor v) const
 271     { return m_graph[v]; }
 272
 273     edge_bundled& operator[](edge_descriptor e)
 274     { return m_graph[e]; }
 275
 276     edge_bundled const& operator[](edge_descriptor e) const
 277     { return m_graph[e]; }
 278
 279     graph_bundled& operator[](graph_bundle_t)
 280     { return get_property(*this); }
 281
 282     graph_bundled const& operator[](graph_bundle_t) const
 283     { return get_property(*this); }
 284 #endif
 285
 286     // Graph concepts
 287     static vertex_descriptor null_vertex()
 288     { return graph_type::null_vertex(); }
 289
 290     void clear() {
 291         m_graph.clear();
 292         m_num_vertices = m_max_vertex_index = 0;
 293         m_num_edges = m_max_edge_index = 0;
 294     }
 295
 296     void swap(undirected_graph& g) {
 297         m_graph.swap(g.m_graph);
 298         std::swap(m_num_vertices, g.m_num_vertices);
 299         std::swap(m_max_vertex_index, g.m_max_vertex_index);
 300         std::swap(m_num_edges, g.m_num_edges);
 301         std::swap(m_max_edge_index, g.m_max_edge_index);
 302     }
 303
 304 private:
 305     vertices_size_type renumber_vertex_indices(vertex_iterator i,
 306                                                vertex_iterator end,
 307                                                vertices_size_type n)
 308     {
 309         typedef typename property_map<graph_type, vertex_index_t>::type IndexMap;
 310         IndexMap indices = get(vertex_index, m_graph);
 311         for( ; i != end; ++i) {
 312             indices[*i] = n++;
 313         }
 314         return n;
 315     }
 316
 317     edges_size_type renumber_edge_indices(edge_iterator i,
 318                                           edge_iterator end,
 319                                           edges_size_type n)
 320     {
 321         typedef typename property_map<graph_type, edge_index_t>::type IndexMap;
 322         IndexMap indices = get(edge_index, m_graph);
 323         for( ; i != end; ++i) {
 324             indices[*i] = n++;
 325         }
 326         return n;
 327     }
 328
 329     graph_type m_graph;
 330     vertices_size_type m_num_vertices;
 331     edges_size_type m_num_edges;
 332     vertex_index_type m_max_vertex_index;
 333     edge_index_type m_max_edge_index;
 334 };
 335
 336 #define UNDIRECTED_GRAPH_PARAMS typename VP, typename EP, typename GP
 337 #define UNDIRECTED_GRAPH undirected_graph<VP,EP,GP>
 338
 339 // IncidenceGraph concepts
 340 template <UNDIRECTED_GRAPH_PARAMS>
 341 inline typename UNDIRECTED_GRAPH::vertex_descriptor
 342 source(typename UNDIRECTED_GRAPH::edge_descriptor e,
 343        UNDIRECTED_GRAPH const& g)
 344 { return source(e, g.impl()); }
 345
 346 template <UNDIRECTED_GRAPH_PARAMS>
 347 inline typename UNDIRECTED_GRAPH::vertex_descriptor
 348 target(typename UNDIRECTED_GRAPH::edge_descriptor e,
 349        UNDIRECTED_GRAPH const& g)
 350 { return target(e, g.impl()); }
 351
 352 template <UNDIRECTED_GRAPH_PARAMS>
 353 inline typename UNDIRECTED_GRAPH::degree_size_type
 354 out_degree(typename UNDIRECTED_GRAPH::vertex_descriptor v,
 355            UNDIRECTED_GRAPH const& g)
 356 { return out_degree(v, g.impl()); }
 357
 358 template <UNDIRECTED_GRAPH_PARAMS>
 359 inline std::pair<
 360     typename UNDIRECTED_GRAPH::out_edge_iterator,
 361     typename UNDIRECTED_GRAPH::out_edge_iterator
 362 >
 363 out_edges(typename UNDIRECTED_GRAPH::vertex_descriptor v,
 364           UNDIRECTED_GRAPH const& g)
 365 { return out_edges(v, g.impl()); }
 366
 367 // BidirectionalGraph concepts
 368 template <UNDIRECTED_GRAPH_PARAMS>
 369 inline typename UNDIRECTED_GRAPH::degree_size_type
 370 in_degree(typename UNDIRECTED_GRAPH::vertex_descriptor v,
 371           UNDIRECTED_GRAPH const& g)
 372 { return in_degree(v, g.impl()); }
 373
 374 template <UNDIRECTED_GRAPH_PARAMS>
 375 inline std::pair<
 376     typename UNDIRECTED_GRAPH::in_edge_iterator,
 377     typename UNDIRECTED_GRAPH::in_edge_iterator
 378 >
 379 in_edges(typename UNDIRECTED_GRAPH::vertex_descriptor v,
 380          UNDIRECTED_GRAPH const& g)
 381 { return in_edges(v, g.impl()); }
 382
 383 template <UNDIRECTED_GRAPH_PARAMS>
 384 inline std::pair<
 385     typename UNDIRECTED_GRAPH::out_edge_iterator,
 386     typename UNDIRECTED_GRAPH::out_edge_iterator
 387 >
 388 incident_edges(typename UNDIRECTED_GRAPH::vertex_descriptor v,
 389                UNDIRECTED_GRAPH const& g)
 390 { return out_edges(v, g.impl()); }
 391
 392 template <UNDIRECTED_GRAPH_PARAMS>
 393 inline typename UNDIRECTED_GRAPH::degree_size_type
 394 degree(typename UNDIRECTED_GRAPH::vertex_descriptor v,
 395        UNDIRECTED_GRAPH const& g)
 396 { return degree(v, g.impl()); }
 397
 398 // AdjacencyGraph concepts
 399 template <UNDIRECTED_GRAPH_PARAMS>
 400 inline std::pair<
 401     typename UNDIRECTED_GRAPH::adjacency_iterator,
 402     typename UNDIRECTED_GRAPH::adjacency_iterator
 403     >
 404 adjacent_vertices(typename UNDIRECTED_GRAPH::vertex_descriptor v,
 405                   UNDIRECTED_GRAPH const& g)
 406 { return adjacent_vertices(v, g.impl()); }
 407
 408 template <UNDIRECTED_GRAPH_PARAMS>
 409 typename UNDIRECTED_GRAPH::vertex_descriptor
 410 vertex(typename UNDIRECTED_GRAPH::vertices_size_type n,
 411        UNDIRECTED_GRAPH const& g)
 412 { return vertex(n, g.impl()); }
 413
 414 template <UNDIRECTED_GRAPH_PARAMS>
 415 std::pair<typename UNDIRECTED_GRAPH::edge_descriptor, bool>
 416 edge(typename UNDIRECTED_GRAPH::vertex_descriptor u,
 417     typename UNDIRECTED_GRAPH::vertex_descriptor v,
 418     UNDIRECTED_GRAPH const& g)
 419 { return edge(u, v, g.impl()); }
 420
 421 // VertexListGraph concepts
 422 template <UNDIRECTED_GRAPH_PARAMS>
 423 inline typename UNDIRECTED_GRAPH::vertices_size_type
 424 num_vertices(UNDIRECTED_GRAPH const& g)
 425 { return g.num_vertices(); }
 426
 427 template <UNDIRECTED_GRAPH_PARAMS>
 428 inline std::pair<
 429     typename UNDIRECTED_GRAPH::vertex_iterator,
 430     typename UNDIRECTED_GRAPH::vertex_iterator
 431 >
 432 vertices(UNDIRECTED_GRAPH const& g)
 433 { return vertices(g.impl()); }
 434
 435 // EdgeListGraph concepts
 436 template <UNDIRECTED_GRAPH_PARAMS>
 437 inline typename UNDIRECTED_GRAPH::edges_size_type
 438 num_edges(UNDIRECTED_GRAPH const& g)
 439 { return g.num_edges(); }
 440
 441 template <UNDIRECTED_GRAPH_PARAMS>
 442 inline std::pair<
 443     typename UNDIRECTED_GRAPH::edge_iterator,
 444     typename UNDIRECTED_GRAPH::edge_iterator
 445 >
 446 edges(UNDIRECTED_GRAPH const& g)
 447 { return edges(g.impl()); }
 448
 449 // MutableGraph concepts
 450 template <UNDIRECTED_GRAPH_PARAMS>
 451 inline typename UNDIRECTED_GRAPH::vertex_descriptor
 452 add_vertex(UNDIRECTED_GRAPH& g)
 453 { return g.add_vertex(); }
 454
 455 template <UNDIRECTED_GRAPH_PARAMS>
 456 inline typename UNDIRECTED_GRAPH::vertex_descriptor
 457 add_vertex(typename UNDIRECTED_GRAPH::vertex_property_type const& p,
 458            UNDIRECTED_GRAPH& g)
 459 { return g.add_vertex(p); }
 460
 461 template <UNDIRECTED_GRAPH_PARAMS>
 462 inline void
 463 clear_vertex(typename UNDIRECTED_GRAPH::vertex_descriptor v,
 464              UNDIRECTED_GRAPH& g)
 465 { return g.clear_vertex(v); }
 466
 467 template <UNDIRECTED_GRAPH_PARAMS>
 468 inline void
 469 remove_vertex(typename UNDIRECTED_GRAPH::vertex_descriptor v, UNDIRECTED_GRAPH& g)
 470 { return g.remove_vertex(v); }
 471
 472 template <UNDIRECTED_GRAPH_PARAMS>
 473 inline std::pair<typename UNDIRECTED_GRAPH::edge_descriptor, bool>
 474 add_edge(typename UNDIRECTED_GRAPH::vertex_descriptor u,
 475          typename UNDIRECTED_GRAPH::vertex_descriptor v,
 476          UNDIRECTED_GRAPH& g)
 477 { return g.add_edge(u, v); }
 478
 479 template <UNDIRECTED_GRAPH_PARAMS>
 480 inline std::pair<typename UNDIRECTED_GRAPH::edge_descriptor, bool>
 481 add_edge(typename UNDIRECTED_GRAPH::vertex_descriptor u,
 482          typename UNDIRECTED_GRAPH::vertex_descriptor v,
 483          typename UNDIRECTED_GRAPH::edge_property_type const& p,
 484          UNDIRECTED_GRAPH& g)
 485 { return g.add_edge(u, v, p); }
 486
 487 template <UNDIRECTED_GRAPH_PARAMS>
 488 inline void
 489 remove_edge(typename UNDIRECTED_GRAPH::vertex_descriptor u,
 490             typename UNDIRECTED_GRAPH::vertex_descriptor v,
 491             UNDIRECTED_GRAPH& g)
 492 { return g.remove_edge(u, v); }
 493
 494 template <UNDIRECTED_GRAPH_PARAMS>
 495 inline void
 496 remove_edge(typename UNDIRECTED_GRAPH::edge_descriptor e, UNDIRECTED_GRAPH& g)
 497 { return g.remove_edge(e); }
 498
 499 template <UNDIRECTED_GRAPH_PARAMS>
 500 inline void
 501 remove_edge(typename UNDIRECTED_GRAPH::edge_iterator i, UNDIRECTED_GRAPH& g)
 502 { return g.remove_edge(i); }
 503
 504 template <UNDIRECTED_GRAPH_PARAMS, class Predicate>
 505 inline void remove_edge_if(Predicate pred, UNDIRECTED_GRAPH& g)
 506 { return remove_edge_if(pred, g.impl()); }
 507
 508 template <UNDIRECTED_GRAPH_PARAMS, class Predicate>
 509 inline void
 510 remove_incident_edge_if(typename UNDIRECTED_GRAPH::vertex_descriptor v,
 511                         Predicate pred,
 512                         UNDIRECTED_GRAPH& g)
 513 { return remove_out_edge_if(v, pred, g.impl()); }
 514
 515 template <UNDIRECTED_GRAPH_PARAMS, class Predicate>
 516 inline void
 517 remove_out_edge_if(typename UNDIRECTED_GRAPH::vertex_descriptor v,
 518                    Predicate pred,
 519                    UNDIRECTED_GRAPH& g)
 520 { return remove_out_edge_if(v, pred, g.impl()); }
 521
 522 template <UNDIRECTED_GRAPH_PARAMS, class Predicate>
 523 inline void
 524 remove_in_edge_if(typename UNDIRECTED_GRAPH::vertex_descriptor v,
 525                   Predicate pred,
 526                   UNDIRECTED_GRAPH& g)
 527 { return remove_in_edge_if(v, pred, g.impl()); }
 528
 529 template <UNDIRECTED_GRAPH_PARAMS, typename Property>
 530 struct property_map<UNDIRECTED_GRAPH, Property>: property_map<typename UNDIRECTED_GRAPH::graph_type, Property> {};
 531
 532 template <UNDIRECTED_GRAPH_PARAMS>
 533 struct property_map<UNDIRECTED_GRAPH, vertex_all_t> {
 534   typedef transform_value_property_map<
 535             detail::remove_first_property,
 536             typename property_map<typename UNDIRECTED_GRAPH::graph_type, vertex_all_t>::const_type>
 537     const_type;
 538   typedef transform_value_property_map<
 539             detail::remove_first_property,
 540             typename property_map<typename UNDIRECTED_GRAPH::graph_type, vertex_all_t>::type>
 541     type;
 542 };
 543
 544 template <UNDIRECTED_GRAPH_PARAMS>
 545 struct property_map<UNDIRECTED_GRAPH, edge_all_t> {
 546   typedef transform_value_property_map<
 547             detail::remove_first_property,
 548             typename property_map<typename UNDIRECTED_GRAPH::graph_type, edge_all_t>::const_type>
 549     const_type;
 550   typedef transform_value_property_map<
 551             detail::remove_first_property,
 552             typename property_map<typename UNDIRECTED_GRAPH::graph_type, edge_all_t>::type>
 553     type;
 554 };
 555
 556 // PropertyGraph concepts
 557 template <UNDIRECTED_GRAPH_PARAMS, typename Property>
 558 inline typename property_map<UNDIRECTED_GRAPH, Property>::type
 559 get(Property p, UNDIRECTED_GRAPH& g)
 560 { return get(p, g.impl()); }
 561
 562 template <UNDIRECTED_GRAPH_PARAMS, typename Property>
 563 inline typename property_map<UNDIRECTED_GRAPH, Property>::const_type
 564 get(Property p, UNDIRECTED_GRAPH const& g)
 565 { return get(p, g.impl()); }
 566
 567 template <UNDIRECTED_GRAPH_PARAMS>
 568 inline typename property_map<UNDIRECTED_GRAPH, vertex_all_t>::type
 569 get(vertex_all_t, UNDIRECTED_GRAPH& g)
 570 { return typename property_map<UNDIRECTED_GRAPH, vertex_all_t>::type(detail::remove_first_property(), get(vertex_all, g.impl())); }
 571
 572 template <UNDIRECTED_GRAPH_PARAMS>
 573 inline typename property_map<UNDIRECTED_GRAPH, vertex_all_t>::const_type
 574 get(vertex_all_t, UNDIRECTED_GRAPH const& g)
 575 { return typename property_map<UNDIRECTED_GRAPH, vertex_all_t>::const_type(detail::remove_first_property(), get(vertex_all, g.impl())); }
 576
 577 template <UNDIRECTED_GRAPH_PARAMS>
 578 inline typename property_map<UNDIRECTED_GRAPH, edge_all_t>::type
 579 get(edge_all_t, UNDIRECTED_GRAPH& g)
 580 { return typename property_map<UNDIRECTED_GRAPH, edge_all_t>::type(detail::remove_first_property(), get(edge_all, g.impl())); }
 581
 582 template <UNDIRECTED_GRAPH_PARAMS>
 583 inline typename property_map<UNDIRECTED_GRAPH, edge_all_t>::const_type
 584 get(edge_all_t, UNDIRECTED_GRAPH const& g)
 585 { return typename property_map<UNDIRECTED_GRAPH, edge_all_t>::const_type(detail::remove_first_property(), get(edge_all, g.impl())); }
 586
 587 template <UNDIRECTED_GRAPH_PARAMS, typename Property, typename Key>
 588 inline typename property_traits<
 589     typename property_map<
 590         typename UNDIRECTED_GRAPH::graph_type, Property
 591     >::const_type
 592 >::value_type
 593 get(Property p, UNDIRECTED_GRAPH const& g, Key const& k)
 594 { return get(p, g.impl(), k); }
 595
 596 template <UNDIRECTED_GRAPH_PARAMS, typename Key>
 597 inline typename property_traits<
 598     typename property_map<
 599         typename UNDIRECTED_GRAPH::graph_type, vertex_all_t
 600     >::const_type
 601 >::value_type
 602 get(vertex_all_t, UNDIRECTED_GRAPH const& g, Key const& k)
 603 { return get(vertex_all, g.impl(), k).m_base; }
 604
 605 template <UNDIRECTED_GRAPH_PARAMS, typename Key>
 606 inline typename property_traits<
 607     typename property_map<
 608         typename UNDIRECTED_GRAPH::graph_type, edge_all_t
 609     >::const_type
 610 >::value_type
 611 get(edge_all_t, UNDIRECTED_GRAPH const& g, Key const& k)
 612 { return get(edge_all, g.impl(), k).m_base; }
 613
 614 template <UNDIRECTED_GRAPH_PARAMS, typename Property, typename Key, typename Value>
 615 inline void put(Property p, UNDIRECTED_GRAPH& g, Key const& k, Value const& v)
 616 { put(p, g.impl(), k, v); }
 617
 618 template <UNDIRECTED_GRAPH_PARAMS, typename Key, typename Value>
 619 inline void put(vertex_all_t, UNDIRECTED_GRAPH& g, Key const& k, Value const& v)
 620 { put(vertex_all, g.impl(), k,
 621       typename UNDIRECTED_GRAPH::internal_vertex_property(get(vertex_index, g.impl(), k), v));
 622 }
 623
 624 template <UNDIRECTED_GRAPH_PARAMS, typename Key, typename Value>
 625 inline void put(edge_all_t, UNDIRECTED_GRAPH& g, Key const& k, Value const& v)
 626 { put(edge_all, g.impl(), k,
 627       typename UNDIRECTED_GRAPH::internal_vertex_property(get(edge_index, g.impl(), k), v));
 628 }
 629
 630 template <UNDIRECTED_GRAPH_PARAMS, class Property>
 631 inline typename graph_property<UNDIRECTED_GRAPH, Property>::type&
 632 get_property(UNDIRECTED_GRAPH& g, Property p)
 633 { return get_property(g.impl(), p); }
 634
 635 template <UNDIRECTED_GRAPH_PARAMS, class Property>
 636 inline typename graph_property<UNDIRECTED_GRAPH, Property>::type const&
 637 get_property(UNDIRECTED_GRAPH const& g, Property p)
 638 { return get_property(g.impl(), p); }
 639
 640 template <UNDIRECTED_GRAPH_PARAMS, class Property, class Value>
 641 inline void set_property(UNDIRECTED_GRAPH& g, Property p, Value v)
 642 { return set_property(g.impl(), p, v); }
 643
 644 // Indexed Vertex graph
 645
 646 template <UNDIRECTED_GRAPH_PARAMS>
 647 inline typename UNDIRECTED_GRAPH::vertex_index_type
 648 get_vertex_index(typename UNDIRECTED_GRAPH::vertex_descriptor v,
 649                  UNDIRECTED_GRAPH const& g)
 650 { return get(vertex_index, g, v); }
 651
 652 template <UNDIRECTED_GRAPH_PARAMS>
 653 typename UNDIRECTED_GRAPH::vertex_index_type
 654 max_vertex_index(UNDIRECTED_GRAPH const& g)
 655 { return g.max_vertex_index(); }
 656
 657 template <UNDIRECTED_GRAPH_PARAMS>
 658 inline void
 659 renumber_vertex_indices(UNDIRECTED_GRAPH& g)
 660 { g.renumber_vertex_indices(); }
 661
 662 template <UNDIRECTED_GRAPH_PARAMS>
 663 inline void
 664 remove_vertex_and_renumber_indices(typename UNDIRECTED_GRAPH::vertex_iterator i,
 665                                    UNDIRECTED_GRAPH& g)
 666 { g.remove_vertex_and_renumber_indices(i); }
 667
 668
 669 // Edge index management
 670
 671 template <UNDIRECTED_GRAPH_PARAMS>
 672 inline typename UNDIRECTED_GRAPH::edge_index_type
 673 get_edge_index(typename UNDIRECTED_GRAPH::edge_descriptor v,
 674                UNDIRECTED_GRAPH const& g)
 675 { return get(edge_index, g, v); }
 676
 677 template <UNDIRECTED_GRAPH_PARAMS>
 678 typename UNDIRECTED_GRAPH::edge_index_type
 679 max_edge_index(UNDIRECTED_GRAPH const& g)
 680 { return g.max_edge_index(); }
 681
 682 template <UNDIRECTED_GRAPH_PARAMS>
 683 inline void
 684 renumber_edge_indices(UNDIRECTED_GRAPH& g)
 685 { g.renumber_edge_indices(); }
 686
 687 template <UNDIRECTED_GRAPH_PARAMS>
 688 inline void
 689 remove_edge_and_renumber_indices(typename UNDIRECTED_GRAPH::edge_iterator i,
 690                                  UNDIRECTED_GRAPH& g)
 691 { g.remove_edge_and_renumber_indices(i); }
 692
 693 // Index management
 694 template <UNDIRECTED_GRAPH_PARAMS>
 695 inline void
 696 renumber_indices(UNDIRECTED_GRAPH& g)
 697 { g.renumber_indices(); }
 698
 699 // Mutability Traits
 700 template <UNDIRECTED_GRAPH_PARAMS>
 701 struct graph_mutability_traits<UNDIRECTED_GRAPH> {
 702     typedef mutable_property_graph_tag category;
 703 };
 704
 705 #undef UNDIRECTED_GRAPH_PARAMS
 706 #undef UNDIRECTED_GRAPH
 707
 708 } /* namespace boost */
 709
 710 #endif