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