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