boost/graph/leda_graph.hpp

   1 //=======================================================================
   2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
   3 // Copyright 2004 The Trustees of Indiana University.
   4 // Copyright 2007 University of Karlsruhe
   5 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Douglas Gregor,
   6 //          Jens Mueller
   7 //
   8 // Distributed under the Boost Software License, Version 1.0. (See
   9 // accompanying file LICENSE_1_0.txt or copy at
  10 // http://www.boost.org/LICENSE_1_0.txt)
  11 //=======================================================================
  12 #ifndef BOOST_GRAPH_LEDA_HPP
  13 #define BOOST_GRAPH_LEDA_HPP
  14
  15 #include <boost/config.hpp>
  16 #include <boost/iterator/iterator_facade.hpp>
  17 #include <boost/graph/graph_traits.hpp>
  18 #include <boost/graph/properties.hpp>
  19
  20 #include <LEDA/graph.h>
  21 #include <LEDA/node_array.h>
  22 #include <LEDA/node_map.h>
  23
  24 // The functions and classes in this file allows the user to
  25 // treat a LEDA GRAPH object as a boost graph "as is". No
  26 // wrapper is needed for the GRAPH object.
  27
  28 // Warning: this implementation relies on partial specialization
  29 // for the graph_traits class (so it won't compile with Visual C++)
  30
  31 // Warning: this implementation is in alpha and has not been tested
  32
  33 #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
  34 namespace boost {
  35
  36   struct leda_graph_traversal_category :
  37     public virtual bidirectional_graph_tag,
  38     public virtual adjacency_graph_tag,
  39     public virtual vertex_list_graph_tag { };
  40
  41   template <class vtype, class etype>
  42   struct graph_traits< leda::GRAPH<vtype,etype> > {
  43     typedef leda::node vertex_descriptor;
  44     typedef leda::edge edge_descriptor;
  45
  46     class adjacency_iterator
  47       : public iterator_facade<adjacency_iterator,
  48                                leda::node,
  49                                bidirectional_traversal_tag,
  50                                leda::node,
  51                                const leda::node*>
  52     {
  53     public:
  54       adjacency_iterator(leda::node node = 0,
  55                       const leda::GRAPH<vtype, etype>* g = 0)
  56         : base(node), g(g) {}
  57     private:
  58       leda::node dereference() const { return leda::target(base); }
  59
  60       bool equal(const adjacency_iterator& other) const
  61       { return base == other.base; }
  62
  63       void increment() { base = g->adj_succ(base); }
  64       void decrement() { base = g->adj_pred(base); }
  65
  66       leda::edge base;
  67       const leda::GRAPH<vtype, etype>* g;
  68
  69       friend class iterator_core_access;
  70     };
  71
  72     class out_edge_iterator
  73       : public iterator_facade<out_edge_iterator,
  74                                leda::edge,
  75                                bidirectional_traversal_tag,
  76                                const leda::edge&,
  77                                const leda::edge*>
  78     {
  79     public:
  80       out_edge_iterator(leda::node node = 0,
  81                       const leda::GRAPH<vtype, etype>* g = 0)
  82         : base(node), g(g) {}
  83
  84     private:
  85       const leda::edge& dereference() const { return base; }
  86
  87       bool equal(const out_edge_iterator& other) const
  88       { return base == other.base; }
  89
  90       void increment() { base = g->adj_succ(base); }
  91       void decrement() { base = g->adj_pred(base); }
  92
  93       leda::edge base;
  94       const leda::GRAPH<vtype, etype>* g;
  95
  96       friend class iterator_core_access;
  97     };
  98
  99     class in_edge_iterator
 100       : public iterator_facade<in_edge_iterator,
 101                                leda::edge,
 102                                bidirectional_traversal_tag,
 103                                const leda::edge&,
 104                                const leda::edge*>
 105     {
 106     public:
 107       in_edge_iterator(leda::node node = 0,
 108                       const leda::GRAPH<vtype, etype>* g = 0)
 109         : base(node), g(g) {}
 110
 111     private:
 112       const leda::edge& dereference() const { return base; }
 113
 114       bool equal(const in_edge_iterator& other) const
 115       { return base == other.base; }
 116
 117       void increment() { base = g->in_succ(base); }
 118       void decrement() { base = g->in_pred(base); }
 119
 120       leda::edge base;
 121       const leda::GRAPH<vtype, etype>* g;
 122
 123       friend class iterator_core_access;
 124     };
 125
 126     class vertex_iterator
 127       : public iterator_facade<vertex_iterator,
 128                                leda::node,
 129                                bidirectional_traversal_tag,
 130                                const leda::node&,
 131                                const leda::node*>
 132     {
 133     public:
 134       vertex_iterator(leda::node node = 0,
 135                       const leda::GRAPH<vtype, etype>* g = 0)
 136         : base(node), g(g) {}
 137
 138     private:
 139       const leda::node& dereference() const { return base; }
 140
 141       bool equal(const vertex_iterator& other) const
 142       { return base == other.base; }
 143
 144       void increment() { base = g->succ_node(base); }
 145       void decrement() { base = g->pred_node(base); }
 146
 147       leda::node base;
 148       const leda::GRAPH<vtype, etype>* g;
 149
 150       friend class iterator_core_access;
 151     };
 152
 153     class edge_iterator
 154       : public iterator_facade<edge_iterator,
 155                                leda::edge,
 156                                bidirectional_traversal_tag,
 157                                const leda::edge&,
 158                                const leda::edge*>
 159     {
 160     public:
 161       edge_iterator(leda::edge edge = 0,
 162                       const leda::GRAPH<vtype, etype>* g = 0)
 163         : base(edge), g(g) {}
 164
 165     private:
 166       const leda::edge& dereference() const { return base; }
 167
 168       bool equal(const edge_iterator& other) const
 169       { return base == other.base; }
 170
 171       void increment() { base = g->succ_edge(base); }
 172       void decrement() { base = g->pred_edge(base); }
 173
 174       leda::node base;
 175       const leda::GRAPH<vtype, etype>* g;
 176
 177       friend class iterator_core_access;
 178     };
 179
 180     typedef directed_tag directed_category;
 181     typedef allow_parallel_edge_tag edge_parallel_category; // not sure here
 182     typedef leda_graph_traversal_category traversal_category;
 183     typedef int vertices_size_type;
 184     typedef int edges_size_type;
 185     typedef int degree_size_type;
 186   };
 187
 188
 189
 190   template<>
 191   struct graph_traits<leda::graph> {
 192     typedef leda::node vertex_descriptor;
 193     typedef leda::edge edge_descriptor;
 194
 195     class adjacency_iterator
 196       : public iterator_facade<adjacency_iterator,
 197                                leda::node,
 198                                bidirectional_traversal_tag,
 199                                leda::node,
 200                                const leda::node*>
 201     {
 202     public:
 203       adjacency_iterator(leda::edge edge = 0,
 204                       const leda::graph* g = 0)
 205         : base(edge), g(g) {}
 206
 207     private:
 208       leda::node dereference() const { return leda::target(base); }
 209
 210       bool equal(const adjacency_iterator& other) const
 211       { return base == other.base; }
 212
 213       void increment() { base = g->adj_succ(base); }
 214       void decrement() { base = g->adj_pred(base); }
 215
 216       leda::edge base;
 217       const leda::graph* g;
 218
 219       friend class iterator_core_access;
 220     };
 221
 222     class out_edge_iterator
 223       : public iterator_facade<out_edge_iterator,
 224                                leda::edge,
 225                                bidirectional_traversal_tag,
 226                                const leda::edge&,
 227                                const leda::edge*>
 228     {
 229     public:
 230       out_edge_iterator(leda::edge edge = 0,
 231                       const leda::graph* g = 0)
 232         : base(edge), g(g) {}
 233
 234     private:
 235       const leda::edge& dereference() const { return base; }
 236
 237       bool equal(const out_edge_iterator& other) const
 238       { return base == other.base; }
 239
 240       void increment() { base = g->adj_succ(base); }
 241       void decrement() { base = g->adj_pred(base); }
 242
 243       leda::edge base;
 244       const leda::graph* g;
 245
 246       friend class iterator_core_access;
 247     };
 248
 249     class in_edge_iterator
 250       : public iterator_facade<in_edge_iterator,
 251                                leda::edge,
 252                                bidirectional_traversal_tag,
 253                                const leda::edge&,
 254                                const leda::edge*>
 255     {
 256     public:
 257       in_edge_iterator(leda::edge edge = 0,
 258                       const leda::graph* g = 0)
 259         : base(edge), g(g) {}
 260
 261     private:
 262       const leda::edge& dereference() const { return base; }
 263
 264       bool equal(const in_edge_iterator& other) const
 265       { return base == other.base; }
 266
 267       void increment() { base = g->in_succ(base); }
 268       void decrement() { base = g->in_pred(base); }
 269
 270       leda::edge base;
 271       const leda::graph* g;
 272
 273       friend class iterator_core_access;
 274     };
 275
 276     class vertex_iterator
 277       : public iterator_facade<vertex_iterator,
 278                                leda::node,
 279                                bidirectional_traversal_tag,
 280                                const leda::node&,
 281                                const leda::node*>
 282     {
 283     public:
 284       vertex_iterator(leda::node node = 0,
 285                       const leda::graph* g = 0)
 286         : base(node), g(g) {}
 287
 288     private:
 289       const leda::node& dereference() const { return base; }
 290
 291       bool equal(const vertex_iterator& other) const
 292       { return base == other.base; }
 293
 294       void increment() { base = g->succ_node(base); }
 295       void decrement() { base = g->pred_node(base); }
 296
 297       leda::node base;
 298       const leda::graph* g;
 299
 300       friend class iterator_core_access;
 301     };
 302
 303     class edge_iterator
 304       : public iterator_facade<edge_iterator,
 305                                leda::edge,
 306                                bidirectional_traversal_tag,
 307                                const leda::edge&,
 308                                const leda::edge*>
 309     {
 310     public:
 311       edge_iterator(leda::edge edge = 0,
 312                       const leda::graph* g = 0)
 313         : base(edge), g(g) {}
 314
 315     private:
 316       const leda::edge& dereference() const { return base; }
 317
 318       bool equal(const edge_iterator& other) const
 319       { return base == other.base; }
 320
 321       void increment() { base = g->succ_edge(base); }
 322       void decrement() { base = g->pred_edge(base); }
 323
 324       leda::edge base;
 325       const leda::graph* g;
 326
 327       friend class iterator_core_access;
 328     };
 329
 330     typedef directed_tag directed_category;
 331     typedef allow_parallel_edge_tag edge_parallel_category; // not sure here
 332     typedef leda_graph_traversal_category traversal_category;
 333     typedef int vertices_size_type;
 334     typedef int edges_size_type;
 335     typedef int degree_size_type;
 336   };
 337
 338 } // namespace boost
 339 #endif
 340
 341 namespace boost {
 342
 343   //===========================================================================
 344   // functions for GRAPH<vtype,etype>
 345
 346   template <class vtype, class etype>
 347   typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor
 348   source(typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor e,
 349          const leda::GRAPH<vtype,etype>& g)
 350   {
 351     return source(e);
 352   }
 353
 354   template <class vtype, class etype>
 355   typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor
 356   target(typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor e,
 357          const leda::GRAPH<vtype,etype>& g)
 358   {
 359     return target(e);
 360   }
 361
 362   template <class vtype, class etype>
 363   inline std::pair<
 364     typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_iterator,
 365     typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_iterator >
 366   vertices(const leda::GRAPH<vtype,etype>& g)
 367   {
 368     typedef typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_iterator
 369       Iter;
 370     return std::make_pair( Iter(g.first_node(),&g), Iter(0,&g) );
 371   }
 372
 373   template <class vtype, class etype>
 374   inline std::pair<
 375     typename graph_traits< leda::GRAPH<vtype,etype> >::edge_iterator,
 376     typename graph_traits< leda::GRAPH<vtype,etype> >::edge_iterator >
 377   edges(const leda::GRAPH<vtype,etype>& g)
 378   {
 379     typedef typename graph_traits< leda::GRAPH<vtype,etype> >::edge_iterator
 380       Iter;
 381     return std::make_pair( Iter(g.first_edge(),&g), Iter(0,&g) );
 382   }
 383
 384   template <class vtype, class etype>
 385   inline std::pair<
 386     typename graph_traits< leda::GRAPH<vtype,etype> >::out_edge_iterator,
 387     typename graph_traits< leda::GRAPH<vtype,etype> >::out_edge_iterator >
 388   out_edges(
 389     typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
 390     const leda::GRAPH<vtype,etype>& g)
 391   {
 392     typedef typename graph_traits< leda::GRAPH<vtype,etype> >
 393       ::out_edge_iterator Iter;
 394     return std::make_pair( Iter(g.first_adj_edge(u,0),&g), Iter(0,&g) );
 395   }
 396
 397   template <class vtype, class etype>
 398   inline std::pair<
 399     typename graph_traits< leda::GRAPH<vtype,etype> >::in_edge_iterator,
 400     typename graph_traits< leda::GRAPH<vtype,etype> >::in_edge_iterator >
 401   in_edges(
 402     typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
 403     const leda::GRAPH<vtype,etype>& g)
 404   {
 405     typedef typename graph_traits< leda::GRAPH<vtype,etype> >
 406       ::in_edge_iterator Iter;
 407     return std::make_pair( Iter(g.first_adj_edge(u,1),&g), Iter(0,&g) );
 408   }
 409
 410   template <class vtype, class etype>
 411   inline std::pair<
 412     typename graph_traits< leda::GRAPH<vtype,etype> >::adjacency_iterator,
 413     typename graph_traits< leda::GRAPH<vtype,etype> >::adjacency_iterator >
 414   adjacent_vertices(
 415     typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
 416     const leda::GRAPH<vtype,etype>& g)
 417   {
 418     typedef typename graph_traits< leda::GRAPH<vtype,etype> >
 419       ::adjacency_iterator Iter;
 420     return std::make_pair( Iter(g.first_adj_edge(u,0),&g), Iter(0,&g) );
 421   }
 422
 423   template <class vtype, class etype>
 424   typename graph_traits< leda::GRAPH<vtype,etype> >::vertices_size_type
 425   num_vertices(const leda::GRAPH<vtype,etype>& g)
 426   {
 427     return g.number_of_nodes();
 428   }
 429
 430   template <class vtype, class etype>
 431   typename graph_traits< leda::GRAPH<vtype,etype> >::edges_size_type
 432   num_edges(const leda::GRAPH<vtype,etype>& g)
 433   {
 434     return g.number_of_edges();
 435   }
 436
 437   template <class vtype, class etype>
 438   typename graph_traits< leda::GRAPH<vtype,etype> >::degree_size_type
 439   out_degree(
 440     typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
 441     const leda::GRAPH<vtype,etype>& g)
 442   {
 443     return g.outdeg(u);
 444   }
 445
 446   template <class vtype, class etype>
 447   typename graph_traits< leda::GRAPH<vtype,etype> >::degree_size_type
 448   in_degree(
 449     typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
 450     const leda::GRAPH<vtype,etype>& g)
 451   {
 452     return g.indeg(u);
 453   }
 454
 455   template <class vtype, class etype>
 456   typename graph_traits< leda::GRAPH<vtype,etype> >::degree_size_type
 457   degree(
 458     typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
 459     const leda::GRAPH<vtype,etype>& g)
 460   {
 461     return g.outdeg(u) + g.indeg(u);
 462   }
 463
 464   template <class vtype, class etype>
 465   typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor
 466   add_vertex(leda::GRAPH<vtype,etype>& g)
 467   {
 468     return g.new_node();
 469   }
 470
 471   template <class vtype, class etype>
 472   typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor
 473   add_vertex(const vtype& vp, leda::GRAPH<vtype,etype>& g)
 474   {
 475     return g.new_node(vp);
 476   }
 477
 478   template <class vtype, class etype>
 479   void clear_vertex(
 480     typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
 481     leda::GRAPH<vtype,etype>& g)
 482   {
 483     typename graph_traits< leda::GRAPH<vtype,etype> >::out_edge_iterator ei, ei_end;
 484     for (tie(ei, ei_end)=out_edges(u,g); ei!=ei_end; ei++)
 485       remove_edge(*ei);
 486
 487     typename graph_traits< leda::GRAPH<vtype,etype> >::in_edge_iterator iei, iei_end;
 488     for (tie(iei, iei_end)=in_edges(u,g); iei!=iei_end; iei++)
 489       remove_edge(*iei);
 490   }
 491
 492   template <class vtype, class etype>
 493   void remove_vertex(
 494     typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
 495     leda::GRAPH<vtype,etype>& g)
 496   {
 497     g.del_node(u);
 498   }
 499
 500   template <class vtype, class etype>
 501   std::pair<
 502     typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor,
 503     bool>
 504   add_edge(
 505     typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
 506     typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor v,
 507     leda::GRAPH<vtype,etype>& g)
 508   {
 509     return std::make_pair(g.new_edge(u, v), true);
 510   }
 511
 512   template <class vtype, class etype>
 513   std::pair<
 514     typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor,
 515     bool>
 516   add_edge(
 517     typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
 518     typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor v,
 519     const etype& et,
 520     leda::GRAPH<vtype,etype>& g)
 521   {
 522     return std::make_pair(g.new_edge(u, v, et), true);
 523   }
 524
 525   template <class vtype, class etype>
 526   void
 527   remove_edge(
 528     typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
 529     typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor v,
 530     leda::GRAPH<vtype,etype>& g)
 531   {
 532     typename graph_traits< leda::GRAPH<vtype,etype> >::out_edge_iterator
 533       i,iend;
 534     for (boost::tie(i,iend) = out_edges(u,g); i != iend; ++i)
 535       if (target(*i,g) == v)
 536         g.del_edge(*i);
 537   }
 538
 539   template <class vtype, class etype>
 540   void
 541   remove_edge(
 542     typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor e,
 543     leda::GRAPH<vtype,etype>& g)
 544   {
 545     g.del_edge(e);
 546   }
 547
 548   //===========================================================================
 549   // functions for graph (non-templated version)
 550
 551   graph_traits<leda::graph>::vertex_descriptor
 552   source(graph_traits<leda::graph>::edge_descriptor e,
 553          const leda::graph& g)
 554   {
 555     return source(e);
 556   }
 557
 558   graph_traits<leda::graph>::vertex_descriptor
 559   target(graph_traits<leda::graph>::edge_descriptor e,
 560          const leda::graph& g)
 561   {
 562     return target(e);
 563   }
 564
 565   inline std::pair<
 566     graph_traits<leda::graph>::vertex_iterator,
 567     graph_traits<leda::graph>::vertex_iterator >
 568   vertices(const leda::graph& g)
 569   {
 570     typedef graph_traits<leda::graph>::vertex_iterator
 571       Iter;
 572     return std::make_pair( Iter(g.first_node(),&g), Iter(0,&g) );
 573   }
 574
 575   inline std::pair<
 576     graph_traits<leda::graph>::edge_iterator,
 577     graph_traits<leda::graph>::edge_iterator >
 578   edges(const leda::graph& g)
 579   {
 580     typedef graph_traits<leda::graph>::edge_iterator
 581       Iter;
 582     return std::make_pair( Iter(g.first_edge(),&g), Iter(0,&g) );
 583   }
 584
 585   inline std::pair<
 586     graph_traits<leda::graph>::out_edge_iterator,
 587     graph_traits<leda::graph>::out_edge_iterator >
 588   out_edges(
 589     graph_traits<leda::graph>::vertex_descriptor u, const leda::graph& g)
 590   {
 591     typedef graph_traits<leda::graph>::out_edge_iterator Iter;
 592     return std::make_pair( Iter(g.first_adj_edge(u),&g), Iter(0,&g) );
 593   }
 594
 595   inline std::pair<
 596     graph_traits<leda::graph>::in_edge_iterator,
 597     graph_traits<leda::graph>::in_edge_iterator >
 598   in_edges(
 599     graph_traits<leda::graph>::vertex_descriptor u,
 600     const leda::graph& g)
 601   {
 602     typedef graph_traits<leda::graph>
 603       ::in_edge_iterator Iter;
 604     return std::make_pair( Iter(g.first_in_edge(u),&g), Iter(0,&g) );
 605   }
 606
 607   inline std::pair<
 608     graph_traits<leda::graph>::adjacency_iterator,
 609     graph_traits<leda::graph>::adjacency_iterator >
 610   adjacent_vertices(
 611     graph_traits<leda::graph>::vertex_descriptor u,
 612     const leda::graph& g)
 613   {
 614     typedef graph_traits<leda::graph>
 615       ::adjacency_iterator Iter;
 616     return std::make_pair( Iter(g.first_adj_edge(u),&g), Iter(0,&g) );
 617   }
 618
 619   graph_traits<leda::graph>::vertices_size_type
 620   num_vertices(const leda::graph& g)
 621   {
 622     return g.number_of_nodes();
 623   }
 624
 625   graph_traits<leda::graph>::edges_size_type
 626   num_edges(const leda::graph& g)
 627   {
 628     return g.number_of_edges();
 629   }
 630
 631   graph_traits<leda::graph>::degree_size_type
 632   out_degree(
 633     graph_traits<leda::graph>::vertex_descriptor u,
 634     const leda::graph& g)
 635   {
 636     return g.outdeg(u);
 637   }
 638
 639   graph_traits<leda::graph>::degree_size_type
 640   in_degree(
 641     graph_traits<leda::graph>::vertex_descriptor u,
 642     const leda::graph& g)
 643   {
 644     return g.indeg(u);
 645   }
 646
 647   graph_traits<leda::graph>::degree_size_type
 648   degree(
 649     graph_traits<leda::graph>::vertex_descriptor u,
 650     const leda::graph& g)
 651   {
 652     return g.outdeg(u) + g.indeg(u);
 653   }
 654
 655   graph_traits<leda::graph>::vertex_descriptor
 656   add_vertex(leda::graph& g)
 657   {
 658     return g.new_node();
 659   }
 660
 661   void
 662   remove_edge(
 663     graph_traits<leda::graph>::vertex_descriptor u,
 664     graph_traits<leda::graph>::vertex_descriptor v,
 665     leda::graph& g)
 666   {
 667     graph_traits<leda::graph>::out_edge_iterator
 668       i,iend;
 669     for (boost::tie(i,iend) = out_edges(u,g); i != iend; ++i)
 670       if (target(*i,g) == v)
 671         g.del_edge(*i);
 672   }
 673
 674   void
 675   remove_edge(
 676     graph_traits<leda::graph>::edge_descriptor e,
 677     leda::graph& g)
 678   {
 679     g.del_edge(e);
 680   }
 681
 682   void clear_vertex(
 683     graph_traits<leda::graph>::vertex_descriptor u,
 684     leda::graph& g)
 685   {
 686     graph_traits<leda::graph>::out_edge_iterator ei, ei_end;
 687     for (tie(ei, ei_end)=out_edges(u,g); ei!=ei_end; ei++)
 688       remove_edge(*ei, g);
 689
 690     graph_traits<leda::graph>::in_edge_iterator iei, iei_end;
 691     for (tie(iei, iei_end)=in_edges(u,g); iei!=iei_end; iei++)
 692       remove_edge(*iei, g);
 693   }
 694
 695   void remove_vertex(
 696     graph_traits<leda::graph>::vertex_descriptor u,
 697     leda::graph& g)
 698   {
 699     g.del_node(u);
 700   }
 701
 702   std::pair<
 703     graph_traits<leda::graph>::edge_descriptor,
 704     bool>
 705   add_edge(
 706     graph_traits<leda::graph>::vertex_descriptor u,
 707     graph_traits<leda::graph>::vertex_descriptor v,
 708     leda::graph& g)
 709   {
 710     return std::make_pair(g.new_edge(u, v), true);
 711   }
 712
 713
 714   //===========================================================================
 715   // property maps for GRAPH<vtype,etype>
 716
 717   class leda_graph_id_map
 718     : public put_get_helper<int, leda_graph_id_map>
 719   {
 720   public:
 721     typedef readable_property_map_tag category;
 722     typedef int value_type;
 723     typedef int reference;
 724     typedef leda::node key_type;
 725     leda_graph_id_map() { }
 726     template <class T>
 727     long operator[](T x) const { return x->id(); }
 728   };
 729   template <class vtype, class etype>
 730   inline leda_graph_id_map
 731   get(vertex_index_t, const leda::GRAPH<vtype, etype>& g) {
 732     return leda_graph_id_map();
 733   }
 734   template <class vtype, class etype>
 735   inline leda_graph_id_map
 736   get(edge_index_t, const leda::GRAPH<vtype, etype>& g) {
 737     return leda_graph_id_map();
 738   }
 739
 740   template <class Tag>
 741   struct leda_property_map { };
 742
 743   template <>
 744   struct leda_property_map<vertex_index_t> {
 745     template <class vtype, class etype>
 746     struct bind_ {
 747       typedef leda_graph_id_map type;
 748       typedef leda_graph_id_map const_type;
 749     };
 750   };
 751   template <>
 752   struct leda_property_map<edge_index_t> {
 753     template <class vtype, class etype>
 754     struct bind_ {
 755       typedef leda_graph_id_map type;
 756       typedef leda_graph_id_map const_type;
 757     };
 758   };
 759
 760
 761   template <class Data, class DataRef, class GraphPtr>
 762   class leda_graph_data_map
 763     : public put_get_helper<DataRef,
 764                             leda_graph_data_map<Data,DataRef,GraphPtr> >
 765   {
 766   public:
 767     typedef Data value_type;
 768     typedef DataRef reference;
 769     typedef void key_type;
 770     typedef lvalue_property_map_tag category;
 771     leda_graph_data_map(GraphPtr g) : m_g(g) { }
 772     template <class NodeOrEdge>
 773     DataRef operator[](NodeOrEdge x) const { return (*m_g)[x]; }
 774   protected:
 775     GraphPtr m_g;
 776   };
 777
 778   template <>
 779   struct leda_property_map<vertex_all_t> {
 780     template <class vtype, class etype>
 781     struct bind_ {
 782       typedef leda_graph_data_map<vtype, vtype&, leda::GRAPH<vtype, etype>*> type;
 783       typedef leda_graph_data_map<vtype, const vtype&,
 784         const leda::GRAPH<vtype, etype>*> const_type;
 785     };
 786   };
 787   template <class vtype, class etype >
 788   inline typename property_map< leda::GRAPH<vtype, etype>, vertex_all_t>::type
 789   get(vertex_all_t, leda::GRAPH<vtype, etype>& g) {
 790     typedef typename property_map< leda::GRAPH<vtype, etype>, vertex_all_t>::type
 791       pmap_type;
 792     return pmap_type(&g);
 793   }
 794   template <class vtype, class etype >
 795   inline typename property_map< leda::GRAPH<vtype, etype>, vertex_all_t>::const_type
 796   get(vertex_all_t, const leda::GRAPH<vtype, etype>& g) {
 797     typedef typename property_map< leda::GRAPH<vtype, etype>,
 798       vertex_all_t>::const_type pmap_type;
 799     return pmap_type(&g);
 800   }
 801
 802   template <>
 803   struct leda_property_map<edge_all_t> {
 804     template <class vtype, class etype>
 805     struct bind_ {
 806       typedef leda_graph_data_map<etype, etype&, leda::GRAPH<vtype, etype>*> type;
 807       typedef leda_graph_data_map<etype, const etype&,
 808         const leda::GRAPH<vtype, etype>*> const_type;
 809     };
 810   };
 811   template <class vtype, class etype >
 812   inline typename property_map< leda::GRAPH<vtype, etype>, edge_all_t>::type
 813   get(edge_all_t, leda::GRAPH<vtype, etype>& g) {
 814     typedef typename property_map< leda::GRAPH<vtype, etype>, edge_all_t>::type
 815       pmap_type;
 816     return pmap_type(&g);
 817   }
 818   template <class vtype, class etype >
 819   inline typename property_map< leda::GRAPH<vtype, etype>, edge_all_t>::const_type
 820   get(edge_all_t, const leda::GRAPH<vtype, etype>& g) {
 821     typedef typename property_map< leda::GRAPH<vtype, etype>,
 822       edge_all_t>::const_type pmap_type;
 823     return pmap_type(&g);
 824   }
 825
 826   // property map interface to the LEDA node_array class
 827
 828   template <class E, class ERef, class NodeMapPtr>
 829   class leda_node_property_map
 830     : public put_get_helper<ERef, leda_node_property_map<E, ERef, NodeMapPtr> >
 831   {
 832   public:
 833     typedef E value_type;
 834     typedef ERef reference;
 835     typedef leda::node key_type;
 836     typedef lvalue_property_map_tag category;
 837     leda_node_property_map(NodeMapPtr a) : m_array(a) { }
 838     ERef operator[](leda::node n) const { return (*m_array)[n]; }
 839   protected:
 840     NodeMapPtr m_array;
 841   };
 842   template <class E>
 843   leda_node_property_map<E, const E&, const leda::node_array<E>*>
 844   make_leda_node_property_map(const leda::node_array<E>& a)
 845   {
 846     typedef leda_node_property_map<E, const E&, const leda::node_array<E>*>
 847       pmap_type;
 848     return pmap_type(&a);
 849   }
 850   template <class E>
 851   leda_node_property_map<E, E&, leda::node_array<E>*>
 852   make_leda_node_property_map(leda::node_array<E>& a)
 853   {
 854     typedef leda_node_property_map<E, E&, leda::node_array<E>*> pmap_type;
 855     return pmap_type(&a);
 856   }
 857
 858   template <class E>
 859   leda_node_property_map<E, const E&, const leda::node_map<E>*>
 860   make_leda_node_property_map(const leda::node_map<E>& a)
 861   {
 862     typedef leda_node_property_map<E,const E&,const leda::node_map<E>*>
 863       pmap_type;
 864     return pmap_type(&a);
 865   }
 866   template <class E>
 867   leda_node_property_map<E, E&, leda::node_map<E>*>
 868   make_leda_node_property_map(leda::node_map<E>& a)
 869   {
 870     typedef leda_node_property_map<E, E&, leda::node_map<E>*> pmap_type;
 871     return pmap_type(&a);
 872   }
 873
 874   // g++ 'enumeral_type' in template unification not implemented workaround
 875   template <class vtype, class etype, class Tag>
 876   struct property_map<leda::GRAPH<vtype, etype>, Tag> {
 877     typedef typename
 878       leda_property_map<Tag>::template bind_<vtype, etype> map_gen;
 879     typedef typename map_gen::type type;
 880     typedef typename map_gen::const_type const_type;
 881   };
 882
 883   template <class vtype, class etype, class PropertyTag, class Key>
 884   inline
 885   typename boost::property_traits<
 886     typename boost::property_map<leda::GRAPH<vtype, etype>,PropertyTag>::const_type
 887 ::value_type
 888   get(PropertyTag p, const leda::GRAPH<vtype, etype>& g, const Key& key) {
 889     return get(get(p, g), key);
 890   }
 891
 892   template <class vtype, class etype, class PropertyTag, class Key,class Value>
 893   inline void
 894   put(PropertyTag p, leda::GRAPH<vtype, etype>& g,
 895       const Key& key, const Value& value)
 896   {
 897     typedef typename property_map<leda::GRAPH<vtype, etype>, PropertyTag>::type Map;
 898     Map pmap = get(p, g);
 899     put(pmap, key, value);
 900   }
 901
 902    // property map interface to the LEDA edge_array class
 903
 904   template <class E, class ERef, class EdgeMapPtr>
 905   class leda_edge_property_map
 906     : public put_get_helper<ERef, leda_edge_property_map<E, ERef, EdgeMapPtr> >
 907   {
 908   public:
 909     typedef E value_type;
 910     typedef ERef reference;
 911     typedef leda::edge key_type;
 912     typedef lvalue_property_map_tag category;
 913     leda_edge_property_map(EdgeMapPtr a) : m_array(a) { }
 914     ERef operator[](leda::edge n) const { return (*m_array)[n]; }
 915   protected:
 916     EdgeMapPtr m_array;
 917   };
 918   template <class E>
 919   leda_edge_property_map<E, const E&, const leda::edge_array<E>*>
 920   make_leda_node_property_map(const leda::node_array<E>& a)
 921   {
 922     typedef leda_edge_property_map<E, const E&, const leda::node_array<E>*>
 923       pmap_type;
 924     return pmap_type(&a);
 925   }
 926   template <class E>
 927   leda_edge_property_map<E, E&, leda::edge_array<E>*>
 928   make_leda_edge_property_map(leda::edge_array<E>& a)
 929   {
 930     typedef leda_edge_property_map<E, E&, leda::edge_array<E>*> pmap_type;
 931     return pmap_type(&a);
 932   }
 933
 934   template <class E>
 935   leda_edge_property_map<E, const E&, const leda::edge_map<E>*>
 936   make_leda_edge_property_map(const leda::edge_map<E>& a)
 937   {
 938     typedef leda_edge_property_map<E,const E&,const leda::edge_map<E>*>
 939       pmap_type;
 940     return pmap_type(&a);
 941   }
 942   template <class E>
 943   leda_edge_property_map<E, E&, leda::edge_map<E>*>
 944   make_leda_edge_property_map(leda::edge_map<E>& a)
 945   {
 946     typedef leda_edge_property_map<E, E&, leda::edge_map<E>*> pmap_type;
 947     return pmap_type(&a);
 948   }
 949
 950 } // namespace boost
 951
 952 #endif // BOOST_GRAPH_LEDA_HPP