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