ceph/src/boost/libs/graph/include/boost/graph/labeled_graph.hpp

   1 // Copyright (C) 2009 Andrew Sutton
   2
   3 // Use, modification and distribution is subject to the Boost Software
   4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   5 // http://www.boost.org/LICENSE_1_0.txt)
   6
   7 #ifndef BOOST_GRAPH_LABELED_GRAPH_HPP
   8 #define BOOST_GRAPH_LABELED_GRAPH_HPP
   9
  10 #include <boost/config.hpp>
  11 #include <vector>
  12 #include <map>
  13
  14 #include <boost/static_assert.hpp>
  15 #include <boost/mpl/if.hpp>
  16 #include <boost/mpl/bool.hpp>
  17 #include <boost/unordered_map.hpp>
  18 #include <boost/type_traits/is_same.hpp>
  19 #include <boost/type_traits/is_unsigned.hpp>
  20 #include <boost/pending/container_traits.hpp>
  21 #include <boost/graph/graph_traits.hpp>
  22
  23 // This file implements a utility for creating mappings from arbitrary
  24 // identifiers to the vertices of a graph.
  25
  26 namespace boost {
  27
  28 // A type selector that denotes the use of some default value.
  29 struct defaultS { };
  30
  31 /** @internal */
  32 namespace graph_detail {
  33     /** Returns true if the selector is the default selector. */
  34     template <typename Selector>
  35     struct is_default
  36         : mpl::bool_<is_same<Selector, defaultS>::value>
  37     { };
  38
  39     /**
  40      * Choose the default map instance. If Label is an unsigned integral type
  41      * the we can use a vector to store the information.
  42      */
  43     template <typename Label, typename Vertex>
  44     struct choose_default_map {
  45         typedef typename mpl::if_<
  46             is_unsigned<Label>,
  47             std::vector<Vertex>,
  48             std::map<Label, Vertex> // TODO: Should use unordered_map?
  49         >::type type;
  50     };
  51
  52     /**
  53      * @name Generate Label Map
  54      * These type generators are responsible for instantiating an associative
  55      * container for the the labeled graph. Note that the Selector must be
  56      * select a pair associative container or a vecS, which is only valid if
  57      * Label is an integral type.
  58      */
  59     //@{
  60     template <typename Selector, typename Label, typename Vertex>
  61     struct generate_label_map { };
  62
  63     template <typename Label, typename Vertex>
  64     struct generate_label_map<vecS, Label, Vertex>
  65     { typedef std::vector<Vertex> type; };
  66
  67     template <typename Label, typename Vertex>
  68     struct generate_label_map<mapS, Label, Vertex>
  69     { typedef std::map<Label, Vertex> type; };
  70
  71     template <typename Label, typename Vertex>
  72     struct generate_label_map<multimapS, Label, Vertex>
  73     { typedef std::multimap<Label, Vertex> type; };
  74
  75     template <typename Label, typename Vertex>
  76     struct generate_label_map<hash_mapS, Label, Vertex>
  77     { typedef boost::unordered_map<Label, Vertex> type; };
  78
  79     template <typename Label, typename Vertex>
  80     struct generate_label_map<hash_multimapS, Label, Vertex>
  81     { typedef boost::unordered_multimap<Label, Vertex> type; };
  82
  83     template <typename Selector, typename Label, typename Vertex>
  84     struct choose_custom_map {
  85         typedef typename generate_label_map<Selector, Label, Vertex>::type type;
  86     };
  87     //@}
  88
  89     /**
  90      * Choose and instantiate an "associative" container. Note that this can
  91      * also choose vector.
  92      */
  93     template <typename Selector, typename Label, typename Vertex>
  94     struct choose_map {
  95         typedef typename mpl::eval_if<
  96             is_default<Selector>,
  97             choose_default_map<Label, Vertex>,
  98             choose_custom_map<Selector, Label, Vertex>
  99         >::type type;
 100     };
 101
 102     /** @name Insert Labeled Vertex */
 103     //@{
 104     // Tag dispatch on random access containers (i.e., vectors). This function
 105     // basically requires a) that Container is vector<Label> and that Label
 106     // is an unsigned integral value. Note that this will resize the vector
 107     // to accommodate indices.
 108     template <typename Container, typename Graph, typename Label, typename Prop>
 109     std::pair<typename graph_traits<Graph>::vertex_descriptor, bool>
 110     insert_labeled_vertex(Container& c, Graph& g, Label const& l, Prop const& p,
 111                           random_access_container_tag)
 112     {
 113         typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
 114
 115         // If the label is out of bounds, resize the vector to accommodate.
 116         // Resize by 2x the index so we don't cause quadratic insertions over
 117         // time.
 118         if(l >= c.size()) {
 119             c.resize((l + 1) * 2);
 120         }
 121         Vertex v = add_vertex(p, g);
 122         c[l] = v;
 123         return std::make_pair(c[l], true);
 124     }
 125
 126     // Tag dispatch on multi associative containers (i.e. multimaps).
 127     template <typename Container, typename Graph, typename Label, typename Prop>
 128     std::pair<typename graph_traits<Graph>::vertex_descriptor, bool>
 129     insert_labeled_vertex(Container& c, Graph& g, Label const& l, Prop const& p,
 130                           multiple_associative_container_tag const&)
 131     {
 132         // Note that insertion always succeeds so we can add the vertex first
 133         // and then the mapping to the label.
 134         typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
 135         Vertex v = add_vertex(p, g);
 136         c.insert(std::make_pair(l, v));
 137         return std::make_pair(v, true);
 138     }
 139
 140     // Tag dispatch on unique associative containers (i.e. maps).
 141     template <typename Container, typename Graph, typename Label, typename Prop>
 142     std::pair<typename graph_traits<Graph>::vertex_descriptor, bool>
 143     insert_labeled_vertex(Container& c, Graph& g, Label const& l, Prop const& p,
 144                           unique_associative_container_tag)
 145     {
 146         // Here, we actually have to try the insertion first, and only add
 147         // the vertex if we get a new element.
 148         typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
 149         typedef typename Container::iterator Iterator;
 150         std::pair<Iterator, bool> x = c.insert(std::make_pair(l, Vertex()));
 151         if(x.second) {
 152             x.first->second = add_vertex(g);
 153             put(boost::vertex_all, g, x.first->second, p);
 154         }
 155         return std::make_pair(x.first->second, x.second);
 156     }
 157
 158     // Dispatcher
 159     template <typename Container, typename Graph, typename Label, typename Prop>
 160     std::pair<typename graph_traits<Graph>::vertex_descriptor, bool>
 161     insert_labeled_vertex(Container& c, Graph& g, Label const& l, Prop const& p)
 162     { return insert_labeled_vertex(c, g, l, p, container_category(c)); }
 163     //@}
 164
 165     /** @name Find Labeled Vertex */
 166     //@{
 167     // Tag dispatch for sequential maps (i.e., vectors).
 168     template <typename Container, typename Graph, typename Label>
 169     typename graph_traits<Graph>::vertex_descriptor
 170     find_labeled_vertex(Container const& c, Graph const&, Label const& l,
 171                         random_access_container_tag)
 172     { return l < c.size() ? c[l] : graph_traits<Graph>::null_vertex(); }
 173
 174     // Tag dispatch for pair associative maps (more or less).
 175     template <typename Container, typename Graph, typename Label>
 176     typename graph_traits<Graph>::vertex_descriptor
 177     find_labeled_vertex(Container const& c, Graph const&, Label const& l,
 178                         associative_container_tag)
 179     {
 180         typename Container::const_iterator i = c.find(l);
 181         return i != c.end() ? i->second : graph_traits<Graph>::null_vertex();
 182     }
 183
 184     // Dispatcher
 185     template <typename Container, typename Graph, typename Label>
 186     typename graph_traits<Graph>::vertex_descriptor
 187     find_labeled_vertex(Container const& c, Graph const& g, Label const& l)
 188     { return find_labeled_vertex(c, g, l, container_category(c)); }
 189     //@}
 190
 191     /** @name Put Vertex Label */
 192     //@{
 193     // Tag dispatch on vectors.
 194     template <typename Container, typename Label, typename Graph, typename Vertex>
 195     bool put_vertex_label(Container& c, Graph const&, Label const& l, Vertex v,
 196                           random_access_container_tag)
 197     {
 198         // If the element is already occupied, then we probably don't want to
 199         // overwrite it.
 200         if(c[l] == graph_traits<Graph>::null_vertex()) return false;
 201         c[l] = v;
 202         return true;
 203     }
 204
 205     // Attempt the insertion and return its result.
 206     template <typename Container, typename Label, typename Graph, typename Vertex>
 207     bool put_vertex_label(Container& c, Graph const&, Label const& l, Vertex v,
 208                           unique_associative_container_tag)
 209     { return c.insert(std::make_pair(l, v)).second; }
 210
 211     // Insert the pair and return true.
 212     template <typename Container, typename Label, typename Graph, typename Vertex>
 213     bool put_vertex_label(Container& c, Graph const&, Label const& l, Vertex v,
 214                           multiple_associative_container_tag)
 215     {
 216         c.insert(std::make_pair(l, v));
 217         return true;
 218     }
 219
 220     // Dispatcher
 221     template <typename Container, typename Label, typename Graph, typename Vertex>
 222     bool put_vertex_label(Container& c, Graph const& g, Label const& l, Vertex v)
 223     { return put_vertex_label(c, g, l, v, container_category(c)); }
 224     //@}
 225
 226 } // namespace detail
 227
 228 struct labeled_graph_class_tag { };
 229
 230 /** @internal
 231  * This class is responsible for the deduction and declaration of type names
 232  * for the labeled_graph class template.
 233  */
 234 template <typename Graph, typename Label, typename Selector>
 235 struct labeled_graph_types {
 236     typedef Graph graph_type;
 237
 238     // Label and maps
 239     typedef Label label_type;
 240     typedef typename graph_detail::choose_map<
 241         Selector, Label, typename graph_traits<Graph>::vertex_descriptor
 242     >::type map_type;
 243 };
 244
 245 /**
 246  * The labeled_graph class is a graph adaptor that maintains a mapping between
 247  * vertex labels and vertex descriptors.
 248  *
 249  * @todo This class is somewhat redundant for adjacency_list<*, vecS>  if
 250  * the intended label is an unsigned int (and perhaps some other cases), but
 251  * it does avoid some weird ambiguities (i.e. adding a vertex with a label that
 252  * does not match its target index).
 253  *
 254  * @todo This needs to be reconciled with the named_graph, but since there is
 255  * no documentation or examples, its not going to happen.
 256  */
 257 template <typename Graph, typename Label, typename Selector = defaultS>
 258 class labeled_graph
 259     : protected labeled_graph_types<Graph, Label, Selector>
 260 {
 261     typedef labeled_graph_types<Graph, Label, Selector> Base;
 262 public:
 263     typedef labeled_graph_class_tag graph_tag;
 264
 265     typedef typename Base::graph_type graph_type;
 266     typedef typename graph_traits<graph_type>::vertex_descriptor vertex_descriptor;
 267     typedef typename graph_traits<graph_type>::edge_descriptor edge_descriptor;
 268     typedef typename graph_traits<graph_type>::directed_category directed_category;
 269     typedef typename graph_traits<graph_type>::edge_parallel_category edge_parallel_category;
 270     typedef typename graph_traits<graph_type>::traversal_category traversal_category;
 271
 272     typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
 273     typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
 274     typedef typename graph_traits<graph_type>::adjacency_iterator adjacency_iterator;
 275     typedef typename graph_traits<graph_type>::degree_size_type degree_size_type;
 276
 277     typedef typename graph_traits<graph_type>::vertex_iterator vertex_iterator;
 278     typedef typename graph_traits<graph_type>::vertices_size_type vertices_size_type;
 279     typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
 280     typedef typename graph_traits<graph_type>::edges_size_type edges_size_type;
 281
 282     typedef typename graph_type::graph_property_type graph_property_type;
 283     typedef typename graph_type::graph_bundled graph_bundled;
 284
 285     typedef typename graph_type::vertex_property_type vertex_property_type;
 286     typedef typename graph_type::vertex_bundled vertex_bundled;
 287
 288     typedef typename graph_type::edge_property_type edge_property_type;
 289     typedef typename graph_type::edge_bundled edge_bundled;
 290
 291     typedef typename Base::label_type label_type;
 292     typedef typename Base::map_type map_type;
 293
 294 public:
 295     labeled_graph(graph_property_type const& gp = graph_property_type())
 296         : _graph(gp), _map()
 297     { }
 298
 299     labeled_graph(labeled_graph const& x)
 300         : _graph(x._graph), _map(x._map)
 301     { }
 302
 303     // This constructor can only be used if map_type supports positional
 304     // range insertion (i.e. its a vector). This is the only case where we can
 305     // try to guess the intended labels for graph.
 306     labeled_graph(vertices_size_type n,
 307                   graph_property_type const& gp = graph_property_type())
 308         : _graph(n, gp), _map()
 309     {
 310         std::pair<vertex_iterator, vertex_iterator> rng = vertices(_graph);
 311         _map.insert(_map.end(), rng.first, rng.second);
 312     }
 313
 314     // Construct a graph over n vertices, each of which receives a label from
 315     // the range [l, l + n). Note that the graph is not directly constructed
 316     // over the n vertices, but added sequentially. This constructor is
 317     // necessarily slower than the underlying counterpart.
 318     template <typename LabelIter>
 319     labeled_graph(vertices_size_type n, LabelIter l,
 320                   graph_property_type const& gp = graph_property_type())
 321         : _graph(gp)
 322     { while(n-- > 0) add_vertex(*l++); }
 323
 324     // Construct the graph over n vertices each of which has a label in the
 325     // range [l, l + n) and a property in the range [p, p + n).
 326     template <typename LabelIter, typename PropIter>
 327     labeled_graph(vertices_size_type n, LabelIter l, PropIter p,
 328                   graph_property_type const& gp = graph_property_type())
 329         : _graph(gp)
 330     { while(n-- > 0) add_vertex(*l++, *p++); }
 331
 332     labeled_graph& operator=(labeled_graph const& x) {
 333         _graph = x._graph;
 334         _map = x._map;
 335         return *this;
 336     }
 337
 338     /** @name Graph Accessors */
 339     //@{
 340     graph_type& graph() { return _graph; }
 341     graph_type const& graph() const { return _graph; }
 342     //@}
 343
 344     /**
 345      * Create a new label for the given vertex, returning false, if the label
 346      * cannot be created.
 347      */
 348     bool label_vertex(vertex_descriptor v, Label const& l)
 349     { return graph_detail::put_vertex_label(_map, _graph, l, v); }
 350
 351     /** @name Add Vertex
 352      * Add a vertex to the graph, returning the descriptor. If the vertices
 353      * are uniquely labeled and the label already exists within the graph,
 354      * then no vertex is added, and the returned descriptor refers to the
 355      * existing vertex. A vertex property can be given as a parameter, if
 356      * needed.
 357      */
 358     //@{
 359     vertex_descriptor add_vertex(Label const& l) {
 360         return graph_detail::insert_labeled_vertex(
 361             _map, _graph, l, vertex_property_type()
 362             ).first;
 363     }
 364
 365     vertex_descriptor add_vertex(Label const& l, vertex_property_type const& p)
 366     { return graph_detail::insert_labeled_vertex(_map, _graph, l, p).first; }
 367     //@}
 368
 369     /** @name Insert Vertex
 370      * Insert a vertex into the graph, returning a pair containing the
 371      * descriptor of a vertex and a boolean value that describes whether or not
 372      * a new vertex was inserted. If vertices are not uniquely labeled, then
 373      * insertion will always succeed.
 374      */
 375     //@{
 376     std::pair<vertex_descriptor, bool> insert_vertex(Label const& l) {
 377         return graph_detail::insert_labeled_vertex(
 378             _map, _graph, l, vertex_property_type()
 379         );
 380     }
 381
 382     std::pair<vertex_descriptor, bool>
 383     insert_vertex(Label const& l, vertex_property_type const& p)
 384     { return graph_detail::insert_labeled_vertex(_map, _graph, l, p); }
 385     //@}
 386
 387     /** Remove the vertex with the given label. */
 388     void remove_vertex(Label const& l)
 389     { return boost::remove_vertex(vertex(l), _graph); }
 390
 391     /** Return a descriptor for the given label. */
 392     vertex_descriptor vertex(Label const& l) const
 393     { return graph_detail::find_labeled_vertex(_map, _graph, l); }
 394
 395 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
 396     /** @name Bundled Properties */
 397     //@{
 398     // Lookup the requested vertex and return the bundle.
 399     vertex_bundled& operator[](Label const& l)
 400     { return _graph[vertex(l)]; }
 401
 402     vertex_bundled const& operator[](Label const& l) const
 403     { return _graph[vertex(l)]; }
 404
 405     // Delegate edge lookup to the underlying graph.
 406     edge_bundled& operator[](edge_descriptor e)
 407     { return _graph[e]; }
 408
 409     edge_bundled const& operator[](edge_descriptor e) const
 410     { return _graph[e]; }
 411     //@}
 412 #endif
 413
 414     /** Return a null descriptor */
 415     static vertex_descriptor null_vertex()
 416     { return graph_traits<graph_type>::null_vertex(); }
 417
 418 private:
 419     graph_type _graph;
 420     map_type _map;
 421 };
 422
 423 /**
 424  * The partial specialization over graph pointers allows the construction
 425  * of temporary labeled graph objects. In this case, the labels are destructed
 426  * when the wrapper goes out of scope.
 427  */
 428 template <typename Graph, typename Label, typename Selector>
 429 class labeled_graph<Graph*, Label, Selector>
 430     : protected labeled_graph_types<Graph, Label, Selector>
 431 {
 432     typedef labeled_graph_types<Graph, Label, Selector> Base;
 433 public:
 434     typedef labeled_graph_class_tag graph_tag;
 435
 436     typedef typename Base::graph_type graph_type;
 437     typedef typename graph_traits<graph_type>::vertex_descriptor vertex_descriptor;
 438     typedef typename graph_traits<graph_type>::edge_descriptor edge_descriptor;
 439     typedef typename graph_traits<graph_type>::directed_category directed_category;
 440     typedef typename graph_traits<graph_type>::edge_parallel_category edge_parallel_category;
 441     typedef typename graph_traits<graph_type>::traversal_category traversal_category;
 442
 443     typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
 444     typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
 445     typedef typename graph_traits<graph_type>::adjacency_iterator adjacency_iterator;
 446     typedef typename graph_traits<graph_type>::degree_size_type degree_size_type;
 447
 448     typedef typename graph_traits<graph_type>::vertex_iterator vertex_iterator;
 449     typedef typename graph_traits<graph_type>::vertices_size_type vertices_size_type;
 450     typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
 451     typedef typename graph_traits<graph_type>::edges_size_type edges_size_type;
 452
 453     typedef typename graph_type::vertex_property_type vertex_property_type;
 454     typedef typename graph_type::edge_property_type edge_property_type;
 455     typedef typename graph_type::graph_property_type graph_property_type;
 456     typedef typename graph_type::vertex_bundled vertex_bundled;
 457     typedef typename graph_type::edge_bundled edge_bundled;
 458
 459     typedef typename Base::label_type label_type;
 460     typedef typename Base::map_type map_type;
 461
 462     labeled_graph(graph_type* g)
 463         : _graph(g)
 464     { }
 465
 466     /** @name Graph Access */
 467     //@{
 468     graph_type& graph() { return *_graph; }
 469     graph_type const& graph() const { return *_graph; }
 470     //@}
 471
 472     /**
 473      * Create a new label for the given vertex, returning false, if the label
 474      * cannot be created.
 475      */
 476     bool label_vertex(vertex_descriptor v, Label const& l)
 477     { return graph_detail::put_vertex_label(_map, *_graph, l, v); }
 478
 479     /** @name Add Vertex */
 480     //@{
 481     vertex_descriptor add_vertex(Label const& l) {
 482         return graph_detail::insert_labeled_vertex(
 483             _map, *_graph, l, vertex_property_type()
 484             ).first;
 485     }
 486
 487     vertex_descriptor add_vertex(Label const& l, vertex_property_type const& p)
 488     { return graph_detail::insert_labeled_vertex(_map, *_graph, l, p).first; }
 489
 490     std::pair<vertex_descriptor, bool> insert_vertex(Label const& l) {
 491         return graph_detail::insert_labeled_vertex(
 492             _map, *_graph, l, vertex_property_type()
 493         );
 494     }
 495     //@}
 496
 497     /** Try to insert a vertex with the given label. */
 498     std::pair<vertex_descriptor, bool>
 499     insert_vertex(Label const& l, vertex_property_type const& p)
 500     { return graph_detail::insert_labeled_vertex(_map, *_graph, l, p); }
 501
 502     /** Remove the vertex with the given label. */
 503     void remove_vertex(Label const& l)
 504     { return boost::remove_vertex(vertex(l), *_graph); }
 505
 506     /** Return a descriptor for the given label. */
 507     vertex_descriptor vertex(Label const& l) const
 508     { return graph_detail::find_labeled_vertex(_map, *_graph, l); }
 509
 510 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
 511     /** @name Bundled Properties */
 512     //@{
 513     // Lookup the requested vertex and return the bundle.
 514     vertex_bundled& operator[](Label const& l)
 515     { return (*_graph)[vertex(l)]; }
 516
 517     vertex_bundled const& operator[](Label const& l) const
 518     { return (*_graph)[vertex(l)]; }
 519
 520     // Delegate edge lookup to the underlying graph.
 521     edge_bundled& operator[](edge_descriptor e)
 522     { return (*_graph)[e]; }
 523
 524     edge_bundled const& operator[](edge_descriptor e) const
 525     { return (*_graph)[e]; }
 526     //@}
 527 #endif
 528
 529     static vertex_descriptor null_vertex()
 530     { return graph_traits<graph_type>::null_vertex(); }
 531
 532 private:
 533     graph_type* _graph;
 534     map_type _map;
 535 };
 536
 537 #define LABELED_GRAPH_PARAMS typename G, typename L, typename S
 538 #define LABELED_GRAPH labeled_graph<G,L,S>
 539
 540 /** @name Labeled Graph */
 541 //@{
 542 template <LABELED_GRAPH_PARAMS>
 543 inline bool label_vertex(typename LABELED_GRAPH::vertex_descriptor v,
 544                          typename LABELED_GRAPH::label_type const l,
 545                          LABELED_GRAPH& g)
 546 { return g.label_vertex(v, l); }
 547
 548 template <LABELED_GRAPH_PARAMS>
 549 inline typename LABELED_GRAPH::vertex_descriptor
 550 vertex_by_label(typename LABELED_GRAPH::label_type const l,
 551                 LABELED_GRAPH& g)
 552 { return g.vertex(l); }
 553 //@}
 554
 555 /** @name Graph */
 556 //@{
 557 template <LABELED_GRAPH_PARAMS>
 558 inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool>
 559 edge(typename LABELED_GRAPH::vertex_descriptor const& u,
 560      typename LABELED_GRAPH::vertex_descriptor const& v,
 561      LABELED_GRAPH const& g)
 562 { return edge(u, v, g.graph()); }
 563
 564 // Labeled Extensions
 565 template <LABELED_GRAPH_PARAMS>
 566 inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool>
 567 edge_by_label(typename LABELED_GRAPH::label_type const& u,
 568               typename LABELED_GRAPH::label_type const& v,
 569               LABELED_GRAPH const& g)
 570 { return edge(g.vertex(u), g.vertex(v), g); }
 571 //@}
 572
 573 /** @name Incidence Graph */
 574 //@{
 575 template <LABELED_GRAPH_PARAMS>
 576 inline std::pair<
 577     typename LABELED_GRAPH::out_edge_iterator,
 578     typename LABELED_GRAPH::out_edge_iterator>
 579 out_edges(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g)
 580 { return out_edges(v, g.graph()); }
 581
 582 template <LABELED_GRAPH_PARAMS>
 583 inline typename LABELED_GRAPH::degree_size_type
 584 out_degree(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g)
 585 { return out_degree(v, g.graph()); }
 586
 587 template <LABELED_GRAPH_PARAMS>
 588 inline typename LABELED_GRAPH::vertex_descriptor
 589 source(typename LABELED_GRAPH::edge_descriptor e, LABELED_GRAPH const& g)
 590 { return source(e, g.graph()); }
 591
 592 template <LABELED_GRAPH_PARAMS>
 593 inline typename LABELED_GRAPH::vertex_descriptor
 594 target(typename LABELED_GRAPH::edge_descriptor e, LABELED_GRAPH const& g)
 595 { return target(e, g.graph()); }
 596 //@}
 597
 598 /** @name Bidirectional Graph */
 599 //@{
 600 template <LABELED_GRAPH_PARAMS>
 601 inline std::pair<
 602     typename LABELED_GRAPH::in_edge_iterator,
 603     typename LABELED_GRAPH::in_edge_iterator>
 604 in_edges(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g)
 605 { return in_edges(v, g.graph()); }
 606
 607 template <LABELED_GRAPH_PARAMS>
 608 inline typename LABELED_GRAPH::degree_size_type
 609 in_degree(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g)
 610 { return in_degree(v, g.graph()); }
 611
 612 template <LABELED_GRAPH_PARAMS>
 613 inline typename LABELED_GRAPH::degree_size_type
 614 degree(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g)
 615 { return degree(v, g.graph()); }
 616 //@}
 617
 618 /** @name Adjacency Graph */
 619 //@{
 620 template <LABELED_GRAPH_PARAMS>
 621 inline std::pair<
 622     typename LABELED_GRAPH::adjacency_iterator,
 623     typename LABELED_GRAPH::adjacency_iterator>
 624 adjacenct_vertices(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g)
 625 { return adjacent_vertices(v, g.graph()); }
 626 //@}
 627
 628 /** @name VertexListGraph */
 629 //@{
 630 template <LABELED_GRAPH_PARAMS>
 631 inline std::pair<
 632     typename LABELED_GRAPH::vertex_iterator,
 633     typename LABELED_GRAPH::vertex_iterator>
 634 vertices(LABELED_GRAPH const& g)
 635 { return vertices(g.graph()); }
 636
 637 template <LABELED_GRAPH_PARAMS>
 638 inline typename LABELED_GRAPH::vertices_size_type
 639 num_vertices(LABELED_GRAPH const& g)
 640 { return num_vertices(g.graph()); }
 641 //@}
 642
 643 /** @name EdgeListGraph */
 644 //@{
 645 template <LABELED_GRAPH_PARAMS>
 646 inline std::pair<
 647     typename LABELED_GRAPH::edge_iterator,
 648     typename LABELED_GRAPH::edge_iterator>
 649 edges(LABELED_GRAPH const& g)
 650 { return edges(g.graph()); }
 651
 652 template <LABELED_GRAPH_PARAMS>
 653 inline typename LABELED_GRAPH::edges_size_type
 654 num_edges(LABELED_GRAPH const& g)
 655 { return num_edges(g.graph()); }
 656 //@}
 657
 658 /** @internal @name Property Lookup */
 659 //@{
 660 namespace graph_detail {
 661     struct labeled_graph_vertex_property_selector {
 662         template <class LabeledGraph, class Property, class Tag>
 663         struct bind_ {
 664             typedef typename LabeledGraph::graph_type Graph;
 665             typedef property_map<Graph, Tag> PropertyMap;
 666             typedef typename PropertyMap::type type;
 667             typedef typename PropertyMap::const_type const_type;
 668         };
 669     };
 670
 671     struct labeled_graph_edge_property_selector {
 672         template <class LabeledGraph, class Property, class Tag>
 673         struct bind_ {
 674             typedef typename LabeledGraph::graph_type Graph;
 675             typedef property_map<Graph, Tag> PropertyMap;
 676             typedef typename PropertyMap::type type;
 677             typedef typename PropertyMap::const_type const_type;
 678         };
 679     };
 680 }
 681
 682 template <>
 683 struct vertex_property_selector<labeled_graph_class_tag> {
 684     typedef graph_detail::labeled_graph_vertex_property_selector type;
 685 };
 686
 687 template <>
 688 struct edge_property_selector<labeled_graph_class_tag> {
 689     typedef graph_detail::labeled_graph_edge_property_selector type;
 690 };
 691 //@}
 692
 693 /** @name Property Graph */
 694 //@{
 695 template <LABELED_GRAPH_PARAMS, typename Prop>
 696 inline typename property_map<LABELED_GRAPH, Prop>::type
 697 get(Prop p, LABELED_GRAPH& g)
 698 { return get(p, g.graph()); }
 699
 700 template <LABELED_GRAPH_PARAMS, typename Prop>
 701 inline typename property_map<LABELED_GRAPH, Prop>::const_type
 702 get(Prop p, LABELED_GRAPH const& g)
 703 { return get(p, g.graph()); }
 704
 705 template <LABELED_GRAPH_PARAMS, typename Prop, typename Key>
 706 inline typename property_traits<
 707     typename property_map<typename LABELED_GRAPH::graph_type, Prop>::const_type
 708 >::value_type
 709 get(Prop p, LABELED_GRAPH const& g, const Key& k)
 710 { return get(p, g.graph(), k); }
 711
 712 template <LABELED_GRAPH_PARAMS, typename Prop, typename Key, typename Value>
 713 inline void
 714 put(Prop p, LABELED_GRAPH& g, Key const& k, Value const& v)
 715 { put(p, g.graph(), k, v); }
 716 //@}
 717
 718 /** @name Mutable Graph */
 719 //@{
 720 template <LABELED_GRAPH_PARAMS>
 721 inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool>
 722 add_edge(typename LABELED_GRAPH::vertex_descriptor const& u,
 723          typename LABELED_GRAPH::vertex_descriptor const& v,
 724          LABELED_GRAPH& g)
 725 { return add_edge(u, v, g.graph()); }
 726
 727 template <LABELED_GRAPH_PARAMS>
 728 inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool>
 729 add_edge(typename LABELED_GRAPH::vertex_descriptor const& u,
 730          typename LABELED_GRAPH::vertex_descriptor const& v,
 731          typename LABELED_GRAPH::edge_property_type const& p,
 732          LABELED_GRAPH& g)
 733 { return add_edge(u, v, p, g.graph()); }
 734
 735 template <LABELED_GRAPH_PARAMS>
 736 inline void
 737 clear_vertex(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH& g)
 738 { return clear_vertex(v, g.graph()); }
 739
 740 template <LABELED_GRAPH_PARAMS>
 741 inline void
 742 remove_edge(typename LABELED_GRAPH::edge_descriptor e, LABELED_GRAPH& g)
 743 { return remove_edge(e, g.graph()); }
 744
 745 template <LABELED_GRAPH_PARAMS>
 746 inline void
 747 remove_edge(typename LABELED_GRAPH::vertex_descriptor u,
 748             typename LABELED_GRAPH::vertex_descriptor v,
 749             LABELED_GRAPH& g)
 750 { return remove_edge(u, v, g.graph()); }
 751
 752 // Labeled extensions
 753 template <LABELED_GRAPH_PARAMS>
 754 inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool>
 755 add_edge_by_label(typename LABELED_GRAPH::label_type const& u,
 756                   typename LABELED_GRAPH::label_type const& v,
 757                   LABELED_GRAPH& g)
 758 { return add_edge(g.vertex(u), g.vertex(v), g); }
 759
 760 template <LABELED_GRAPH_PARAMS>
 761 inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool>
 762 add_edge_by_label(typename LABELED_GRAPH::label_type const& u,
 763                   typename LABELED_GRAPH::label_type const& v,
 764                   typename LABELED_GRAPH::edge_property_type const& p,
 765                   LABELED_GRAPH& g)
 766 { return add_edge(g.vertex(u), g.vertex(v), p, g); }
 767
 768 template <LABELED_GRAPH_PARAMS>
 769 inline void
 770 clear_vertex_by_label(typename LABELED_GRAPH::label_type const& l, LABELED_GRAPH& g)
 771 { clear_vertex(g.vertex(l), g.graph()); }
 772
 773 template <LABELED_GRAPH_PARAMS>
 774 inline void
 775 remove_edge_by_label(typename LABELED_GRAPH::label_type const& u,
 776                      typename LABELED_GRAPH::label_type const& v,
 777                      LABELED_GRAPH& g)
 778 { remove_edge(g.vertex(u), g.vertex(v), g.graph()); }
 779 //@}
 780
 781 /** @name Labeled Mutable Graph
 782  * The labeled mutable graph hides the add_ and remove_ vertex functions from
 783  * the mutable graph concept. Note that the remove_vertex is hidden because
 784  * removing the vertex without its key could leave a dangling reference in
 785  * the map.
 786  */
 787 //@{
 788 template <LABELED_GRAPH_PARAMS>
 789 inline typename LABELED_GRAPH::vertex_descriptor
 790 add_vertex(typename LABELED_GRAPH::label_type const& l,
 791            LABELED_GRAPH& g)
 792 { return g.add_vertex(l); }
 793
 794 // MutableLabeledPropertyGraph::add_vertex(l, vp, g)
 795 template <LABELED_GRAPH_PARAMS>
 796 inline typename LABELED_GRAPH::vertex_descriptor
 797 add_vertex(typename LABELED_GRAPH::label_type const& l,
 798            typename LABELED_GRAPH::vertex_property_type const& p,
 799            LABELED_GRAPH& g)
 800 { return g.add_vertex(l, p); }
 801
 802 template <LABELED_GRAPH_PARAMS>
 803 inline void
 804 remove_vertex(typename LABELED_GRAPH::label_type const& l, LABELED_GRAPH& g)
 805 { g.remove_vertex(l); }
 806 //@}
 807
 808 #undef LABELED_GRAPH_PARAMS
 809 #undef LABELED_GRAPH
 810
 811 } // namespace boost
 812
 813 // Pull the labeled graph traits
 814 #include <boost/graph/detail/labeled_graph_traits.hpp>
 815
 816 #endif // BOOST_GRAPH_LABELED_GRAPH_HPP