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