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