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 // identifers 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 #if !defined BOOST_NO_HASH
  76     template <typename Label, typename Vertex>
  77     struct generate_label_map<hash_mapS, Label, Vertex>
  78     { typedef boost::unordered_map<Label, Vertex> type; };
  79
  80     template <typename Label, typename Vertex>
  81     struct generate_label_map<hash_multimapS, Label, Vertex>
  82     { typedef boost::unordered_multimap<Label, Vertex> type; };
  83 #endif
  84     template <typename Selector, typename Label, typename Vertex>
  85     struct choose_custom_map {
  86         typedef typename generate_label_map<Selector, Label, Vertex>::type type;
  87     };
  88     //@}
  89
  90     /**
  91      * Choose and instantiate an "associative" container. Note that this can
  92      * also choose vector.
  93      */
  94     template <typename Selector, typename Label, typename Vertex>
  95     struct choose_map {
  96         typedef typename mpl::eval_if<
  97             is_default<Selector>,
  98             choose_default_map<Label, Vertex>,
  99             choose_custom_map<Selector, Label, Vertex>
 100         >::type type;
 101     };
 102
 103     /** @name Insert Labeled Vertex */
 104     //@{
 105     // Tag dispatch on random access containers (i.e., vectors). This function
 106     // basically requires a) that Container is vector<Label> and that Label
 107     // is an unsigned integral value. Note that this will resize the vector
 108     // to accomodate indices.
 109     template <typename Container, typename Graph, typename Label, typename Prop>
 110     std::pair<typename graph_traits<Graph>::vertex_descriptor, bool>
 111     insert_labeled_vertex(Container& c, Graph& g, Label const& l, Prop const& p,
 112                           random_access_container_tag)
 113     {
 114         typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
 115
 116         // If the label is out of bounds, resize the vector to accomodate.
 117         // Resize by 2x the index so we don't cause quadratic insertions over
 118         // time.
 119         if(l >= c.size()) {
 120             c.resize((l + 1) * 2);
 121         }
 122         Vertex v = add_vertex(p, g);
 123         c[l] = v;
 124         return std::make_pair(c[l], true);
 125     }
 126
 127     // Tag dispatch on multi associative containers (i.e. multimaps).
 128     template <typename Container, typename Graph, typename Label, typename Prop>
 129     std::pair<typename graph_traits<Graph>::vertex_descriptor, bool>
 130     insert_labeled_vertex(Container& c, Graph& g, Label const& l, Prop const& p,
 131                           multiple_associative_container_tag const&)
 132     {
 133         // Note that insertion always succeeds so we can add the vertex first
 134         // and then the mapping to the label.
 135         typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
 136         Vertex v = add_vertex(g);
 137         c.insert(std::make_pair(l, v));
 138         return std::make_pair(v, true);
 139     }
 140
 141     // Tag dispatch on unique associative containers (i.e. maps).
 142     template <typename Container, typename Graph, typename Label, typename Prop>
 143     std::pair<typename graph_traits<Graph>::vertex_descriptor, bool>
 144     insert_labeled_vertex(Container& c, Graph& g, Label const& l, Prop const& p,
 145                           unique_associative_container_tag)
 146     {
 147         // Here, we actually have to try the insertion first, and only add
 148         // the vertex if we get a new element.
 149         typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
 150         typedef typename Container::iterator Iterator;
 151         std::pair<Iterator, bool> x = c.insert(std::make_pair(l, Vertex()));
 152         if(x.second) {
 153             x.first->second = add_vertex(g);
 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::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 perhpahs 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::vertex_property_type vertex_property_type;
 283     typedef typename graph_type::edge_property_type edge_property_type;
 284     typedef typename graph_type::graph_property_type graph_property_type;
 285     typedef typename graph_type::vertex_bundled vertex_bundled;
 286     typedef typename graph_type::edge_bundled edge_bundled;
 287
 288     typedef typename Base::label_type label_type;
 289     typedef typename Base::map_type map_type;
 290
 291 public:
 292     labeled_graph(graph_property_type const& gp = graph_property_type())
 293         : _graph(gp), _map()
 294     { }
 295
 296     labeled_graph(labeled_graph const& x)
 297         : _graph(x._graph), _map(x._map)
 298     { }
 299
 300     // This constructor can only be used if map_type supports positional
 301     // range insertion (i.e. its a vector). This is the only case where we can
 302     // try to guess the intended labels for graph.
 303     labeled_graph(vertices_size_type n,
 304                   graph_property_type const& gp = graph_property_type())
 305         : _graph(n, gp), _map()
 306     {
 307         std::pair<vertex_iterator, vertex_iterator> rng = vertices(_graph);
 308         _map.insert(_map.end(), rng.first, rng.second);
 309     }
 310
 311     // Construct a grpah over n vertices, each of which receives a label from
 312     // the range [l, l + n). Note that the graph is not directly constructed
 313     // over the n vertices, but added sequentially. This constructor is
 314     // necessarily slower than the underlying counterpart.
 315     template <typename LabelIter>
 316     labeled_graph(vertices_size_type n, LabelIter l,
 317                   graph_property_type const& gp = graph_property_type())
 318         : _graph(gp)
 319     { while(n-- >= 0) add_vertex(*l++); }
 320
 321     // Construct the graph over n vertices each of which has a label in the
 322     // range [l, l + n) and a property in the range [p, p + n).
 323     template <typename LabelIter, typename PropIter>
 324     labeled_graph(vertices_size_type n, LabelIter l, PropIter p,
 325                   graph_property_type const& gp = graph_property_type())
 326     { while(n-- >= 0) add_vertex(*l++, *p++); }
 327
 328     labeled_graph& operator=(labeled_graph const& x) {
 329         _graph = x._graph;
 330         _map = x._map;
 331         return *this;
 332     }
 333
 334     /** @name Graph Accessors */
 335     //@{
 336     graph_type& graph() { return _graph; }
 337     graph_type const& graph() const { return _graph; }
 338     //@}
 339
 340     /**
 341      * Create a new label for the given vertex, returning false, if the label
 342      * cannot be created.
 343      */
 344     bool label_vertex(vertex_descriptor v, Label const& l)
 345     { return graph_detail::put_vertex_label(_map, _graph, l, v); }
 346
 347     /** @name Add Vertex
 348      * Add a vertex to the graph, returning the descriptor. If the vertices
 349      * are uniquely labeled and the label already exists within the graph,
 350      * then no vertex is added, and the returned descriptor refers to the
 351      * existing vertex. A vertex property can be given as a parameter, if
 352      * needed.
 353      */
 354     //@{
 355     vertex_descriptor add_vertex(Label const& l) {
 356         return graph_detail::insert_labeled_vertex(
 357             _map, _graph, l, vertex_property_type()
 358             ).first;
 359     }
 360
 361     vertex_descriptor add_vertex(Label const& l, vertex_property_type const& p)
 362     { return graph_detail::insert_labeled_vertex(_map, _graph, l, p).first; }
 363     //@}
 364
 365     /** @name Insert Vertex
 366      * Insert a vertex into the graph, returning a pair containing the
 367      * descriptor of a vertex and a boolean value that describes whether or not
 368      * a new vertex was inserted. If vertices are not uniquely labeled, then
 369      * insertion will always succeed.
 370      */
 371     //@{
 372     std::pair<vertex_descriptor, bool> insert_vertex(Label const& l) {
 373         return graph_detail::insert_labeled_vertex(
 374             _map, _graph, l, vertex_property_type()
 375         );
 376     }
 377
 378     std::pair<vertex_descriptor, bool>
 379     insert_vertex(Label const& l, vertex_property_type const& p)
 380     { return graph_detail::insert_labeled_vertex(_map, _graph, l, p); }
 381     //@}
 382
 383     /** Remove the vertex with the given label. */
 384     void remove_vertex(Label const& l)
 385     { return boost::remove_vertex(vertex(l), _graph); }
 386
 387     /** Return a descriptor for the given label. */
 388     vertex_descriptor vertex(Label const& l) const
 389     { return graph_detail::find_labeled_vertex(_map, _graph, l); }
 390
 391 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
 392     /** @name Bundled Properties */
 393     //@{
 394     // Lookup the requested vertex and return the bundle.
 395     vertex_bundled& operator[](Label const& l)
 396     { return _graph[vertex(l)]; }
 397
 398     vertex_bundled const& operator[](Label const& l) const
 399     { return _graph[vertex(l)]; }
 400
 401     // Delegate edge lookup to the underlying graph.
 402     edge_bundled& operator[](edge_descriptor e)
 403     { return _graph[e]; }
 404
 405     edge_bundled const& operator[](edge_descriptor e) const
 406     { return _graph[e]; }
 407     //@}
 408 #endif
 409
 410     /** Return a null descriptor */
 411     static vertex_descriptor null_vertex()
 412     { return graph_type::null_vertex(); }
 413
 414 private:
 415     graph_type _graph;
 416     map_type _map;
 417 };
 418
 419 /**
 420  * The partial specialization over graph pointers allows the construction
 421  * of temporary labeled graph objects. In this case, the labels are destructed
 422  * when the wrapper goes out of scope.
 423  */
 424 template <typename Graph, typename Label, typename Selector>
 425 class labeled_graph<Graph*, Label, Selector>
 426     : protected labeled_graph_types<Graph, Label, Selector>
 427 {
 428     typedef labeled_graph_types<Graph, Label, Selector> Base;
 429 public:
 430     typedef labeled_graph_class_tag graph_tag;
 431
 432     typedef typename Base::graph_type graph_type;
 433     typedef typename graph_traits<graph_type>::vertex_descriptor vertex_descriptor;
 434     typedef typename graph_traits<graph_type>::edge_descriptor edge_descriptor;
 435     typedef typename graph_traits<graph_type>::directed_category directed_category;
 436     typedef typename graph_traits<graph_type>::edge_parallel_category edge_parallel_category;
 437     typedef typename graph_traits<graph_type>::traversal_category traversal_category;
 438
 439     typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
 440     typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
 441     typedef typename graph_traits<graph_type>::adjacency_iterator adjacency_iterator;
 442     typedef typename graph_traits<graph_type>::degree_size_type degree_size_type;
 443
 444     typedef typename graph_traits<graph_type>::vertex_iterator vertex_iterator;
 445     typedef typename graph_traits<graph_type>::vertices_size_type vertices_size_type;
 446     typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
 447     typedef typename graph_traits<graph_type>::edges_size_type edges_size_type;
 448
 449     typedef typename graph_type::vertex_property_type vertex_property_type;
 450     typedef typename graph_type::edge_property_type edge_property_type;
 451     typedef typename graph_type::graph_property_type graph_property_type;
 452     typedef typename graph_type::vertex_bundled vertex_bundled;
 453     typedef typename graph_type::edge_bundled edge_bundled;
 454
 455     typedef typename Base::label_type label_type;
 456     typedef typename Base::map_type map_type;
 457
 458     labeled_graph(graph_type* g)
 459         : _graph(g)
 460     { }
 461
 462     /** @name Graph Access */
 463     //@{
 464     graph_type& graph() { return *_graph; }
 465     graph_type const& graph() const { return *_graph; }
 466     //@}
 467
 468     /**
 469      * Create a new label for the given vertex, returning false, if the label
 470      * cannot be created.
 471      */
 472     bool label_vertex(vertex_descriptor v, Label const& l)
 473     { return graph_detail::put_vertex_label(_map, *_graph, l, v); }
 474
 475     /** @name Add Vertex */
 476     //@{
 477     vertex_descriptor add_vertex(Label const& l) {
 478         return graph_detail::insert_labeled_vertex(
 479             _map, *_graph, l, vertex_property_type()
 480             ).first;
 481     }
 482
 483     vertex_descriptor add_vertex(Label const& l, vertex_property_type const& p)
 484     { return graph_detail::insert_labeled_vertex(_map, *_graph, l, p).first; }
 485
 486     std::pair<vertex_descriptor, bool> insert_vertex(Label const& l) {
 487         return graph_detail::insert_labeled_vertex(
 488             _map, *_graph, l, vertex_property_type()
 489         );
 490     }
 491     //@}
 492
 493     /** Try to insert a vertex with the given label. */
 494     std::pair<vertex_descriptor, bool>
 495     insert_vertex(Label const& l, vertex_property_type const& p)
 496     { return graph_detail::insert_labeled_vertex(_map, *_graph, l, p); }
 497
 498     /** Remove the vertex with the given label. */
 499     void remove_vertex(Label const& l)
 500     { return boost::remove_vertex(vertex(l), *_graph); }
 501
 502     /** Return a descriptor for the given label. */
 503     vertex_descriptor vertex(Label const& l) const
 504     { return graph_detail::find_labeled_vertex(_map, _graph, l); }
 505
 506 #ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
 507     /** @name Bundled Properties */
 508     //@{
 509     // Lookup the requested vertex and return the bundle.
 510     vertex_bundled& operator[](Label const& l)
 511     { return (*_graph)[vertex(l)]; }
 512
 513     vertex_bundled const& operator[](Label const& l) const
 514     { return (*_graph)[vertex(l)]; }
 515
 516     // Delegate edge lookup to the underlying graph.
 517     edge_bundled& operator[](edge_descriptor e)
 518     { return (*_graph)[e]; }
 519
 520     edge_bundled const& operator[](edge_descriptor e) const
 521     { return (*_graph)[e]; }
 522     //@}
 523 #endif
 524
 525     static vertex_descriptor null_vertex()
 526     { return graph_type::null_vertex(); }
 527
 528 private:
 529     graph_type* _graph;
 530     map_type _map;
 531 };
 532
 533 #define LABELED_GRAPH_PARAMS typename G, typename L, typename S
 534 #define LABELED_GRAPH labeled_graph<G,L,S>
 535
 536 /** @name Labeled Graph */
 537 //@{
 538 template <LABELED_GRAPH_PARAMS>
 539 inline bool label_vertex(typename LABELED_GRAPH::vertex_descriptor v,
 540                          typename LABELED_GRAPH::label_type const l,
 541                          LABELED_GRAPH& g)
 542 { return g.label_vertex(v, l); }
 543
 544 template <LABELED_GRAPH_PARAMS>
 545 inline bool vertex_by_label(typename LABELED_GRAPH::label_type const l,
 546                             LABELED_GRAPH& g)
 547 { return g.vertex(l); }
 548 //@}
 549
 550 /** @name Graph */
 551 //@{
 552 template <LABELED_GRAPH_PARAMS>
 553 inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool>
 554 edge(typename LABELED_GRAPH::vertex_descriptor const& u,
 555      typename LABELED_GRAPH::vertex_descriptor const& v,
 556      LABELED_GRAPH const& g)
 557 { return edge(u, v, g.graph()); }
 558
 559 // Labeled Extensions
 560 template <LABELED_GRAPH_PARAMS>
 561 inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool>
 562 edge_by_label(typename LABELED_GRAPH::label_type const& u,
 563               typename LABELED_GRAPH::label_type const& v,
 564               LABELED_GRAPH const& g)
 565 { return edge(g.vertex(u), g.vertex(v), g); }
 566 //@}
 567
 568 /** @name Incidence Graph */
 569 //@{
 570 template <LABELED_GRAPH_PARAMS>
 571 inline std::pair<
 572     typename LABELED_GRAPH::out_edge_iterator,
 573     typename LABELED_GRAPH::out_edge_iterator>
 574 out_edges(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g)
 575 { return out_edges(v, g.graph()); }
 576
 577 template <LABELED_GRAPH_PARAMS>
 578 inline typename LABELED_GRAPH::degree_size_type
 579 out_degree(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g)
 580 { return out_degree(v, g.graph()); }
 581
 582 template <LABELED_GRAPH_PARAMS>
 583 inline typename LABELED_GRAPH::vertex_descriptor
 584 source(typename LABELED_GRAPH::edge_descriptor e, LABELED_GRAPH const& g)
 585 { return source(e, g.graph()); }
 586
 587 template <LABELED_GRAPH_PARAMS>
 588 inline typename LABELED_GRAPH::vertex_descriptor
 589 target(typename LABELED_GRAPH::edge_descriptor e, LABELED_GRAPH const& g)
 590 { return target(e, g.graph()); }
 591 //@}
 592
 593 /** @name Bidirectional Graph */
 594 //@{
 595 template <LABELED_GRAPH_PARAMS>
 596 inline std::pair<
 597     typename LABELED_GRAPH::in_edge_iterator,
 598     typename LABELED_GRAPH::in_edge_iterator>
 599 in_edges(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g)
 600 { return in_edges(v, g.graph()); }
 601
 602 template <LABELED_GRAPH_PARAMS>
 603 inline typename LABELED_GRAPH::degree_size_type
 604 in_degree(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g)
 605 { return in_degree(v, g.graph()); }
 606
 607 template <LABELED_GRAPH_PARAMS>
 608 inline typename LABELED_GRAPH::degree_size_type
 609 degree(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g)
 610 { return degree(v, g.graph()); }
 611 //@}
 612
 613 /** @name Adjacency Graph */
 614 //@{
 615 template <LABELED_GRAPH_PARAMS>
 616 inline std::pair<
 617     typename LABELED_GRAPH::adjacency_iterator,
 618     typename LABELED_GRAPH::adjacency_iterator>
 619 adjacenct_vertices(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH const& g)
 620 { return adjacent_vertices(v, g.graph()); }
 621 //@}
 622
 623 /** @name VertexListGraph */
 624 //@{
 625 template <LABELED_GRAPH_PARAMS>
 626 inline std::pair<
 627     typename LABELED_GRAPH::vertex_iterator,
 628     typename LABELED_GRAPH::vertex_iterator>
 629 vertices(LABELED_GRAPH const& g)
 630 { return vertices(g.graph()); }
 631
 632 template <LABELED_GRAPH_PARAMS>
 633 inline typename LABELED_GRAPH::vertices_size_type
 634 num_vertices(LABELED_GRAPH const& g)
 635 { return num_vertices(g.graph()); }
 636 //@}
 637
 638 /** @name EdgeListGraph */
 639 //@{
 640 template <LABELED_GRAPH_PARAMS>
 641 inline std::pair<
 642     typename LABELED_GRAPH::edge_iterator,
 643     typename LABELED_GRAPH::edge_iterator>
 644 edges(LABELED_GRAPH const& g)
 645 { return edges(g.graph()); }
 646
 647 template <LABELED_GRAPH_PARAMS>
 648 inline typename LABELED_GRAPH::edges_size_type
 649 num_edges(LABELED_GRAPH const& g)
 650 { return num_edges(g.graph()); }
 651 //@}
 652
 653 /** @internal @name Property Lookup */
 654 //@{
 655 namespace graph_detail {
 656     struct labeled_graph_vertex_property_selector {
 657         template <class LabeledGraph, class Property, class Tag>
 658         struct bind_ {
 659             typedef typename LabeledGraph::graph_type Graph;
 660             typedef property_map<Graph, Tag> PropertyMap;
 661             typedef typename PropertyMap::type type;
 662             typedef typename PropertyMap::const_type const_type;
 663         };
 664     };
 665
 666     struct labeled_graph_edge_property_selector {
 667         template <class LabeledGraph, class Property, class Tag>
 668         struct bind_ {
 669             typedef typename LabeledGraph::graph_type Graph;
 670             typedef property_map<Graph, Tag> PropertyMap;
 671             typedef typename PropertyMap::type type;
 672             typedef typename PropertyMap::const_type const_type;
 673         };
 674     };
 675 }
 676
 677 template <>
 678 struct vertex_property_selector<labeled_graph_class_tag> {
 679     typedef graph_detail::labeled_graph_vertex_property_selector type;
 680 };
 681
 682 template <>
 683 struct edge_property_selector<labeled_graph_class_tag> {
 684     typedef graph_detail::labeled_graph_edge_property_selector type;
 685 };
 686 //@}
 687
 688 /** @name Property Graph */
 689 //@{
 690 template <LABELED_GRAPH_PARAMS, typename Prop>
 691 inline typename property_map<LABELED_GRAPH, Prop>::type
 692 get(Prop p, LABELED_GRAPH& g)
 693 { return get(p, g.graph()); }
 694
 695 template <LABELED_GRAPH_PARAMS, typename Prop>
 696 inline typename property_map<LABELED_GRAPH, Prop>::const_type
 697 get(Prop p, LABELED_GRAPH const& g)
 698 { return get(p, g.impl()); }
 699
 700 template <LABELED_GRAPH_PARAMS, typename Prop, typename Key>
 701 inline typename property_traits<
 702     typename property_map<typename LABELED_GRAPH::graph_type, Prop>::const_type
 703 >::value_type
 704 get(Prop p, LABELED_GRAPH const& g, const Key& k)
 705 { return get(p, g.impl(), k); }
 706
 707 template <LABELED_GRAPH_PARAMS, typename Prop, typename Key, typename Value>
 708 inline void
 709 put(Prop p, LABELED_GRAPH& g, Key const& k, Value const& v)
 710 { put(p, g.impl(), k, v); }
 711 //@}
 712
 713 /** @name Mutable Graph */
 714 //@{
 715 template <LABELED_GRAPH_PARAMS>
 716 inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool>
 717 add_edge(typename LABELED_GRAPH::vertex_descriptor const& u,
 718          typename LABELED_GRAPH::vertex_descriptor const& v,
 719          LABELED_GRAPH& g)
 720 { return add_edge(u, v, g.graph()); }
 721
 722 template <LABELED_GRAPH_PARAMS>
 723 inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool>
 724 add_edge(typename LABELED_GRAPH::vertex_descriptor const& u,
 725          typename LABELED_GRAPH::vertex_descriptor const& v,
 726          typename LABELED_GRAPH::edge_property_type const& p,
 727          LABELED_GRAPH& g)
 728 { return add_edge(u, v, p, g.graph()); }
 729
 730 template <LABELED_GRAPH_PARAMS>
 731 inline void
 732 clear_vertex(typename LABELED_GRAPH::vertex_descriptor v, LABELED_GRAPH& g)
 733 { return clear_vertex(v, g.graph()); }
 734
 735 template <LABELED_GRAPH_PARAMS>
 736 inline void
 737 remove_edge(typename LABELED_GRAPH::edge_descriptor e, LABELED_GRAPH& g)
 738 { return remove_edge(e, g.graph()); }
 739
 740 template <LABELED_GRAPH_PARAMS>
 741 inline void
 742 remove_edge(typename LABELED_GRAPH::vertex_descriptor u,
 743             typename LABELED_GRAPH::vertex_descriptor v,
 744             LABELED_GRAPH& g)
 745 { return remove_edge(u, v, g.graph()); }
 746
 747 // Labeled extensions
 748 template <LABELED_GRAPH_PARAMS>
 749 inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool>
 750 add_edge_by_label(typename LABELED_GRAPH::label_type const& u,
 751                   typename LABELED_GRAPH::label_type const& v,
 752                   LABELED_GRAPH& g)
 753 { return add_edge(g.vertex(u), g.vertex(v), g); }
 754
 755 template <LABELED_GRAPH_PARAMS>
 756 inline std::pair<typename LABELED_GRAPH::edge_descriptor, bool>
 757 add_edge_by_label(typename LABELED_GRAPH::label_type const& u,
 758                   typename LABELED_GRAPH::label_type const& v,
 759                   typename LABELED_GRAPH::edge_property_type const& p,
 760                   LABELED_GRAPH& g)
 761 { return add_edge(g.vertex(u), g.vertex(v), p, g); }
 762
 763 template <LABELED_GRAPH_PARAMS>
 764 inline void
 765 clear_vertex_by_label(typename LABELED_GRAPH::label_type const& l, LABELED_GRAPH& g)
 766 { clear_vertex(g.vertex(l), g.graph()); }
 767
 768 template <LABELED_GRAPH_PARAMS>
 769 inline void
 770 remove_edge_by_label(typename LABELED_GRAPH::label_type const& u,
 771                      typename LABELED_GRAPH::label_type const& v,
 772                      LABELED_GRAPH& g)
 773 { remove_edge(g.vertex(u), g.vertex(v), g.graph()); }
 774 //@}
 775
 776 /** @name Labeled Mutable Graph
 777  * The labeled mutable graph hides the add_ and remove_ vertex functions from
 778  * the mutable graph concept.
 779  */
 780 //@{
 781 template <LABELED_GRAPH_PARAMS>
 782 inline typename LABELED_GRAPH::vertex_descriptor
 783 add_vertex(typename LABELED_GRAPH::label_type const& l,
 784            LABELED_GRAPH& g)
 785 { return g.add_vertex(l); }
 786
 787 // MutableLabeledPropertyGraph::add_vertex(l, vp, g)
 788 template <LABELED_GRAPH_PARAMS>
 789 inline typename LABELED_GRAPH::vertex_descriptor
 790 add_vertex(typename LABELED_GRAPH::label_type const& l,
 791            typename LABELED_GRAPH::vertex_property_type const& p,
 792            LABELED_GRAPH& g)
 793 { return g.add_vertex(l, p); }
 794
 795 template <LABELED_GRAPH_PARAMS>
 796 inline void
 797 remove_vertex(typename LABELED_GRAPH::label_type const& l, LABELED_GRAPH& g)
 798 { g.remove_vertex(l); }
 799 //@}
 800
 801 #undef LABELED_GRAPH_PARAMS
 802 #undef LABELED_GRAPH
 803
 804 } // namespace boost
 805
 806 // Pull the labeled graph traits
 807 #include <boost/graph/detail/labeled_graph_traits.hpp>
 808
 809 #endif // BOOST_GRAPH_LABELED_GRAPH_HPP