boost/graph/leda_graph.hpp

0001 //=======================================================================
0002 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
0003 // Copyright 2004 The Trustees of Indiana University.
0004 // Copyright 2007 University of Karlsruhe
0005 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Douglas Gregor,
0006 //          Jens Mueller
0007 //
0008 // Distributed under the Boost Software License, Version 1.0. (See
0009 // accompanying file LICENSE_1_0.txt or copy at
0010 // http://www.boost.org/LICENSE_1_0.txt)
0011 //=======================================================================
0012 #ifndef BOOST_GRAPH_LEDA_HPP
0013 #define BOOST_GRAPH_LEDA_HPP
0014
0015 #include <boost/config.hpp>
0016 #include <boost/iterator/iterator_facade.hpp>
0017 #include <boost/graph/graph_traits.hpp>
0018 #include <boost/graph/properties.hpp>
0019
0020 #include <LEDA/graph/graph.h>
0021 #include <LEDA/graph/node_array.h>
0022 #include <LEDA/graph/node_map.h>
0023
0024 // The functions and classes in this file allows the user to
0025 // treat a LEDA GRAPH object as a boost graph "as is". No
0026 // wrapper is needed for the GRAPH object.
0027
0028 // Warning: this implementation relies on partial specialization
0029 // for the graph_traits class (so it won't compile with Visual C++)
0030
0031 // Warning: this implementation is in alpha and has not been tested
0032
0033 namespace boost
0034 {
0035
0036 struct leda_graph_traversal_category : public virtual bidirectional_graph_tag,
0037                                        public virtual adjacency_graph_tag,
0038                                        public virtual vertex_list_graph_tag
0039 {
0040 };
0041
0042 template < class vtype, class etype >
0043 struct graph_traits< leda::GRAPH< vtype, etype > >
0044 {
0045     typedef leda::node vertex_descriptor;
0046     typedef leda::edge edge_descriptor;
0047
0048     class adjacency_iterator
0049     : public iterator_facade< adjacency_iterator, leda::node,
0050           bidirectional_traversal_tag, leda::node, const leda::node* >
0051     {
0052     public:
0053         adjacency_iterator(
0054             leda::node node = 0, const leda::GRAPH< vtype, etype >* g = 0)
0055         : base(node), g(g)
0056         {
0057         }
0058
0059     private:
0060         leda::node dereference() const { return leda::target(base); }
0061
0062         bool equal(const adjacency_iterator& other) const
0063         {
0064             return base == other.base;
0065         }
0066
0067         void increment() { base = g->adj_succ(base); }
0068         void decrement() { base = g->adj_pred(base); }
0069
0070         leda::edge base;
0071         const leda::GRAPH< vtype, etype >* g;
0072
0073         friend class iterator_core_access;
0074     };
0075
0076     class out_edge_iterator
0077     : public iterator_facade< out_edge_iterator, leda::edge,
0078           bidirectional_traversal_tag, const leda::edge&, const leda::edge* >
0079     {
0080     public:
0081         out_edge_iterator(
0082             leda::node node = 0, const leda::GRAPH< vtype, etype >* g = 0)
0083         : base(node), g(g)
0084         {
0085         }
0086
0087     private:
0088         const leda::edge& dereference() const { return base; }
0089
0090         bool equal(const out_edge_iterator& other) const
0091         {
0092             return base == other.base;
0093         }
0094
0095         void increment() { base = g->adj_succ(base); }
0096         void decrement() { base = g->adj_pred(base); }
0097
0098         leda::edge base;
0099         const leda::GRAPH< vtype, etype >* g;
0100
0101         friend class iterator_core_access;
0102     };
0103
0104     class in_edge_iterator
0105     : public iterator_facade< in_edge_iterator, leda::edge,
0106           bidirectional_traversal_tag, const leda::edge&, const leda::edge* >
0107     {
0108     public:
0109         in_edge_iterator(
0110             leda::node node = 0, const leda::GRAPH< vtype, etype >* g = 0)
0111         : base(node), g(g)
0112         {
0113         }
0114
0115     private:
0116         const leda::edge& dereference() const { return base; }
0117
0118         bool equal(const in_edge_iterator& other) const
0119         {
0120             return base == other.base;
0121         }
0122
0123         void increment() { base = g->in_succ(base); }
0124         void decrement() { base = g->in_pred(base); }
0125
0126         leda::edge base;
0127         const leda::GRAPH< vtype, etype >* g;
0128
0129         friend class iterator_core_access;
0130     };
0131
0132     class vertex_iterator
0133     : public iterator_facade< vertex_iterator, leda::node,
0134           bidirectional_traversal_tag, const leda::node&, const leda::node* >
0135     {
0136     public:
0137         vertex_iterator(
0138             leda::node node = 0, const leda::GRAPH< vtype, etype >* g = 0)
0139         : base(node), g(g)
0140         {
0141         }
0142
0143     private:
0144         const leda::node& dereference() const { return base; }
0145
0146         bool equal(const vertex_iterator& other) const
0147         {
0148             return base == other.base;
0149         }
0150
0151         void increment() { base = g->succ_node(base); }
0152         void decrement() { base = g->pred_node(base); }
0153
0154         leda::node base;
0155         const leda::GRAPH< vtype, etype >* g;
0156
0157         friend class iterator_core_access;
0158     };
0159
0160     class edge_iterator
0161     : public iterator_facade< edge_iterator, leda::edge,
0162           bidirectional_traversal_tag, const leda::edge&, const leda::edge* >
0163     {
0164     public:
0165         edge_iterator(
0166             leda::edge edge = 0, const leda::GRAPH< vtype, etype >* g = 0)
0167         : base(edge), g(g)
0168         {
0169         }
0170
0171     private:
0172         const leda::edge& dereference() const { return base; }
0173
0174         bool equal(const edge_iterator& other) const
0175         {
0176             return base == other.base;
0177         }
0178
0179         void increment() { base = g->succ_edge(base); }
0180         void decrement() { base = g->pred_edge(base); }
0181
0182         leda::node base;
0183         const leda::GRAPH< vtype, etype >* g;
0184
0185         friend class iterator_core_access;
0186     };
0187
0188     typedef directed_tag directed_category;
0189     typedef allow_parallel_edge_tag edge_parallel_category; // not sure here
0190     typedef leda_graph_traversal_category traversal_category;
0191     typedef int vertices_size_type;
0192     typedef int edges_size_type;
0193     typedef int degree_size_type;
0194 };
0195
0196 template <> struct graph_traits< leda::graph >
0197 {
0198     typedef leda::node vertex_descriptor;
0199     typedef leda::edge edge_descriptor;
0200
0201     class adjacency_iterator
0202     : public iterator_facade< adjacency_iterator, leda::node,
0203           bidirectional_traversal_tag, leda::node, const leda::node* >
0204     {
0205     public:
0206         adjacency_iterator(leda::edge edge = 0, const leda::graph* g = 0)
0207         : base(edge), g(g)
0208         {
0209         }
0210
0211     private:
0212         leda::node dereference() const { return leda::target(base); }
0213
0214         bool equal(const adjacency_iterator& other) const
0215         {
0216             return base == other.base;
0217         }
0218
0219         void increment() { base = g->adj_succ(base); }
0220         void decrement() { base = g->adj_pred(base); }
0221
0222         leda::edge base;
0223         const leda::graph* g;
0224
0225         friend class iterator_core_access;
0226     };
0227
0228     class out_edge_iterator
0229     : public iterator_facade< out_edge_iterator, leda::edge,
0230           bidirectional_traversal_tag, const leda::edge&, const leda::edge* >
0231     {
0232     public:
0233         out_edge_iterator(leda::edge edge = 0, const leda::graph* g = 0)
0234         : base(edge), g(g)
0235         {
0236         }
0237
0238     private:
0239         const leda::edge& dereference() const { return base; }
0240
0241         bool equal(const out_edge_iterator& other) const
0242         {
0243             return base == other.base;
0244         }
0245
0246         void increment() { base = g->adj_succ(base); }
0247         void decrement() { base = g->adj_pred(base); }
0248
0249         leda::edge base;
0250         const leda::graph* g;
0251
0252         friend class iterator_core_access;
0253     };
0254
0255     class in_edge_iterator
0256     : public iterator_facade< in_edge_iterator, leda::edge,
0257           bidirectional_traversal_tag, const leda::edge&, const leda::edge* >
0258     {
0259     public:
0260         in_edge_iterator(leda::edge edge = 0, const leda::graph* g = 0)
0261         : base(edge), g(g)
0262         {
0263         }
0264
0265     private:
0266         const leda::edge& dereference() const { return base; }
0267
0268         bool equal(const in_edge_iterator& other) const
0269         {
0270             return base == other.base;
0271         }
0272
0273         void increment() { base = g->in_succ(base); }
0274         void decrement() { base = g->in_pred(base); }
0275
0276         leda::edge base;
0277         const leda::graph* g;
0278
0279         friend class iterator_core_access;
0280     };
0281
0282     class vertex_iterator
0283     : public iterator_facade< vertex_iterator, leda::node,
0284           bidirectional_traversal_tag, const leda::node&, const leda::node* >
0285     {
0286     public:
0287         vertex_iterator(leda::node node = 0, const leda::graph* g = 0)
0288         : base(node), g(g)
0289         {
0290         }
0291
0292     private:
0293         const leda::node& dereference() const { return base; }
0294
0295         bool equal(const vertex_iterator& other) const
0296         {
0297             return base == other.base;
0298         }
0299
0300         void increment() { base = g->succ_node(base); }
0301         void decrement() { base = g->pred_node(base); }
0302
0303         leda::node base;
0304         const leda::graph* g;
0305
0306         friend class iterator_core_access;
0307     };
0308
0309     class edge_iterator
0310     : public iterator_facade< edge_iterator, leda::edge,
0311           bidirectional_traversal_tag, const leda::edge&, const leda::edge* >
0312     {
0313     public:
0314         edge_iterator(leda::edge edge = 0, const leda::graph* g = 0)
0315         : base(edge), g(g)
0316         {
0317         }
0318
0319     private:
0320         const leda::edge& dereference() const { return base; }
0321
0322         bool equal(const edge_iterator& other) const
0323         {
0324             return base == other.base;
0325         }
0326
0327         void increment() { base = g->succ_edge(base); }
0328         void decrement() { base = g->pred_edge(base); }
0329
0330         leda::edge base;
0331         const leda::graph* g;
0332
0333         friend class iterator_core_access;
0334     };
0335
0336     typedef directed_tag directed_category;
0337     typedef allow_parallel_edge_tag edge_parallel_category; // not sure here
0338     typedef leda_graph_traversal_category traversal_category;
0339     typedef int vertices_size_type;
0340     typedef int edges_size_type;
0341     typedef int degree_size_type;
0342 };
0343
0344 } // namespace boost
0345
0346 namespace boost
0347 {
0348
0349 //===========================================================================
0350 // functions for GRAPH<vtype,etype>
0351
0352 template < class vtype, class etype >
0353 typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor source(
0354     typename graph_traits< leda::GRAPH< vtype, etype > >::edge_descriptor e,
0355     const leda::GRAPH< vtype, etype >& g)
0356 {
0357     return source(e);
0358 }
0359
0360 template < class vtype, class etype >
0361 typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor target(
0362     typename graph_traits< leda::GRAPH< vtype, etype > >::edge_descriptor e,
0363     const leda::GRAPH< vtype, etype >& g)
0364 {
0365     return target(e);
0366 }
0367
0368 template < class vtype, class etype >
0369 inline std::pair<
0370     typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_iterator,
0371     typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_iterator >
0372 vertices(const leda::GRAPH< vtype, etype >& g)
0373 {
0374     typedef
0375         typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_iterator
0376             Iter;
0377     return std::make_pair(Iter(g.first_node(), &g), Iter(0, &g));
0378 }
0379
0380 template < class vtype, class etype >
0381 inline std::pair<
0382     typename graph_traits< leda::GRAPH< vtype, etype > >::edge_iterator,
0383     typename graph_traits< leda::GRAPH< vtype, etype > >::edge_iterator >
0384 edges(const leda::GRAPH< vtype, etype >& g)
0385 {
0386     typedef typename graph_traits< leda::GRAPH< vtype, etype > >::edge_iterator
0387         Iter;
0388     return std::make_pair(Iter(g.first_edge(), &g), Iter(0, &g));
0389 }
0390
0391 template < class vtype, class etype >
0392 inline std::pair<
0393     typename graph_traits< leda::GRAPH< vtype, etype > >::out_edge_iterator,
0394     typename graph_traits< leda::GRAPH< vtype, etype > >::out_edge_iterator >
0395 out_edges(
0396     typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u,
0397     const leda::GRAPH< vtype, etype >& g)
0398 {
0399     typedef
0400         typename graph_traits< leda::GRAPH< vtype, etype > >::out_edge_iterator
0401             Iter;
0402     return std::make_pair(Iter(g.first_adj_edge(u, 0), &g), Iter(0, &g));
0403 }
0404
0405 template < class vtype, class etype >
0406 inline std::pair<
0407     typename graph_traits< leda::GRAPH< vtype, etype > >::in_edge_iterator,
0408     typename graph_traits< leda::GRAPH< vtype, etype > >::in_edge_iterator >
0409 in_edges(
0410     typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u,
0411     const leda::GRAPH< vtype, etype >& g)
0412 {
0413     typedef
0414         typename graph_traits< leda::GRAPH< vtype, etype > >::in_edge_iterator
0415             Iter;
0416     return std::make_pair(Iter(g.first_adj_edge(u, 1), &g), Iter(0, &g));
0417 }
0418
0419 template < class vtype, class etype >
0420 inline std::pair<
0421     typename graph_traits< leda::GRAPH< vtype, etype > >::adjacency_iterator,
0422     typename graph_traits< leda::GRAPH< vtype, etype > >::adjacency_iterator >
0423 adjacent_vertices(
0424     typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u,
0425     const leda::GRAPH< vtype, etype >& g)
0426 {
0427     typedef
0428         typename graph_traits< leda::GRAPH< vtype, etype > >::adjacency_iterator
0429             Iter;
0430     return std::make_pair(Iter(g.first_adj_edge(u, 0), &g), Iter(0, &g));
0431 }
0432
0433 template < class vtype, class etype >
0434 typename graph_traits< leda::GRAPH< vtype, etype > >::vertices_size_type
0435 num_vertices(const leda::GRAPH< vtype, etype >& g)
0436 {
0437     return g.number_of_nodes();
0438 }
0439
0440 template < class vtype, class etype >
0441 typename graph_traits< leda::GRAPH< vtype, etype > >::edges_size_type num_edges(
0442     const leda::GRAPH< vtype, etype >& g)
0443 {
0444     return g.number_of_edges();
0445 }
0446
0447 template < class vtype, class etype >
0448 typename graph_traits< leda::GRAPH< vtype, etype > >::degree_size_type
0449 out_degree(
0450     typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u,
0451     const leda::GRAPH< vtype, etype >& g)
0452 {
0453     return g.outdeg(u);
0454 }
0455
0456 template < class vtype, class etype >
0457 typename graph_traits< leda::GRAPH< vtype, etype > >::degree_size_type
0458 in_degree(
0459     typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u,
0460     const leda::GRAPH< vtype, etype >& g)
0461 {
0462     return g.indeg(u);
0463 }
0464
0465 template < class vtype, class etype >
0466 typename graph_traits< leda::GRAPH< vtype, etype > >::degree_size_type degree(
0467     typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u,
0468     const leda::GRAPH< vtype, etype >& g)
0469 {
0470     return g.outdeg(u) + g.indeg(u);
0471 }
0472
0473 template < class vtype, class etype >
0474 typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor
0475 add_vertex(leda::GRAPH< vtype, etype >& g)
0476 {
0477     return g.new_node();
0478 }
0479
0480 template < class vtype, class etype >
0481 typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor
0482 add_vertex(const vtype& vp, leda::GRAPH< vtype, etype >& g)
0483 {
0484     return g.new_node(vp);
0485 }
0486
0487 template < class vtype, class etype >
0488 void clear_vertex(
0489     typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u,
0490     leda::GRAPH< vtype, etype >& g)
0491 {
0492     typename graph_traits< leda::GRAPH< vtype, etype > >::out_edge_iterator ei,
0493         ei_end;
0494     for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ei++)
0495         remove_edge(*ei);
0496
0497     typename graph_traits< leda::GRAPH< vtype, etype > >::in_edge_iterator iei,
0498         iei_end;
0499     for (boost::tie(iei, iei_end) = in_edges(u, g); iei != iei_end; iei++)
0500         remove_edge(*iei);
0501 }
0502
0503 template < class vtype, class etype >
0504 void remove_vertex(
0505     typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u,
0506     leda::GRAPH< vtype, etype >& g)
0507 {
0508     g.del_node(u);
0509 }
0510
0511 template < class vtype, class etype >
0512 std::pair<
0513     typename graph_traits< leda::GRAPH< vtype, etype > >::edge_descriptor,
0514     bool >
0515 add_edge(
0516     typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u,
0517     typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor v,
0518     leda::GRAPH< vtype, etype >& g)
0519 {
0520     return std::make_pair(g.new_edge(u, v), true);
0521 }
0522
0523 template < class vtype, class etype >
0524 std::pair<
0525     typename graph_traits< leda::GRAPH< vtype, etype > >::edge_descriptor,
0526     bool >
0527 add_edge(
0528     typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u,
0529     typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor v,
0530     const etype& et, leda::GRAPH< vtype, etype >& g)
0531 {
0532     return std::make_pair(g.new_edge(u, v, et), true);
0533 }
0534
0535 template < class vtype, class etype >
0536 void remove_edge(
0537     typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor u,
0538     typename graph_traits< leda::GRAPH< vtype, etype > >::vertex_descriptor v,
0539     leda::GRAPH< vtype, etype >& g)
0540 {
0541     typename graph_traits< leda::GRAPH< vtype, etype > >::out_edge_iterator i,
0542         iend;
0543     for (boost::tie(i, iend) = out_edges(u, g); i != iend; ++i)
0544         if (target(*i, g) == v)
0545             g.del_edge(*i);
0546 }
0547
0548 template < class vtype, class etype >
0549 void remove_edge(
0550     typename graph_traits< leda::GRAPH< vtype, etype > >::edge_descriptor e,
0551     leda::GRAPH< vtype, etype >& g)
0552 {
0553     g.del_edge(e);
0554 }
0555
0556 //===========================================================================
0557 // functions for graph (non-templated version)
0558
0559 graph_traits< leda::graph >::vertex_descriptor source(
0560     graph_traits< leda::graph >::edge_descriptor e, const leda::graph& g)
0561 {
0562     return source(e);
0563 }
0564
0565 graph_traits< leda::graph >::vertex_descriptor target(
0566     graph_traits< leda::graph >::edge_descriptor e, const leda::graph& g)
0567 {
0568     return target(e);
0569 }
0570
0571 inline std::pair< graph_traits< leda::graph >::vertex_iterator,
0572     graph_traits< leda::graph >::vertex_iterator >
0573 vertices(const leda::graph& g)
0574 {
0575     typedef graph_traits< leda::graph >::vertex_iterator Iter;
0576     return std::make_pair(Iter(g.first_node(), &g), Iter(0, &g));
0577 }
0578
0579 inline std::pair< graph_traits< leda::graph >::edge_iterator,
0580     graph_traits< leda::graph >::edge_iterator >
0581 edges(const leda::graph& g)
0582 {
0583     typedef graph_traits< leda::graph >::edge_iterator Iter;
0584     return std::make_pair(Iter(g.first_edge(), &g), Iter(0, &g));
0585 }
0586
0587 inline std::pair< graph_traits< leda::graph >::out_edge_iterator,
0588     graph_traits< leda::graph >::out_edge_iterator >
0589 out_edges(
0590     graph_traits< leda::graph >::vertex_descriptor u, const leda::graph& g)
0591 {
0592     typedef graph_traits< leda::graph >::out_edge_iterator Iter;
0593     return std::make_pair(Iter(g.first_adj_edge(u), &g), Iter(0, &g));
0594 }
0595
0596 inline std::pair< graph_traits< leda::graph >::in_edge_iterator,
0597     graph_traits< leda::graph >::in_edge_iterator >
0598 in_edges(graph_traits< leda::graph >::vertex_descriptor u, const leda::graph& g)
0599 {
0600     typedef graph_traits< leda::graph >::in_edge_iterator Iter;
0601     return std::make_pair(Iter(g.first_in_edge(u), &g), Iter(0, &g));
0602 }
0603
0604 inline std::pair< graph_traits< leda::graph >::adjacency_iterator,
0605     graph_traits< leda::graph >::adjacency_iterator >
0606 adjacent_vertices(
0607     graph_traits< leda::graph >::vertex_descriptor u, const leda::graph& g)
0608 {
0609     typedef graph_traits< leda::graph >::adjacency_iterator Iter;
0610     return std::make_pair(Iter(g.first_adj_edge(u), &g), Iter(0, &g));
0611 }
0612
0613 graph_traits< leda::graph >::vertices_size_type num_vertices(
0614     const leda::graph& g)
0615 {
0616     return g.number_of_nodes();
0617 }
0618
0619 graph_traits< leda::graph >::edges_size_type num_edges(const leda::graph& g)
0620 {
0621     return g.number_of_edges();
0622 }
0623
0624 graph_traits< leda::graph >::degree_size_type out_degree(
0625     graph_traits< leda::graph >::vertex_descriptor u, const leda::graph& g)
0626 {
0627     return g.outdeg(u);
0628 }
0629
0630 graph_traits< leda::graph >::degree_size_type in_degree(
0631     graph_traits< leda::graph >::vertex_descriptor u, const leda::graph& g)
0632 {
0633     return g.indeg(u);
0634 }
0635
0636 graph_traits< leda::graph >::degree_size_type degree(
0637     graph_traits< leda::graph >::vertex_descriptor u, const leda::graph& g)
0638 {
0639     return g.outdeg(u) + g.indeg(u);
0640 }
0641
0642 graph_traits< leda::graph >::vertex_descriptor add_vertex(leda::graph& g)
0643 {
0644     return g.new_node();
0645 }
0646
0647 void remove_edge(graph_traits< leda::graph >::vertex_descriptor u,
0648     graph_traits< leda::graph >::vertex_descriptor v, leda::graph& g)
0649 {
0650     graph_traits< leda::graph >::out_edge_iterator i, iend;
0651     for (boost::tie(i, iend) = out_edges(u, g); i != iend; ++i)
0652         if (target(*i, g) == v)
0653             g.del_edge(*i);
0654 }
0655
0656 void remove_edge(graph_traits< leda::graph >::edge_descriptor e, leda::graph& g)
0657 {
0658     g.del_edge(e);
0659 }
0660
0661 void clear_vertex(
0662     graph_traits< leda::graph >::vertex_descriptor u, leda::graph& g)
0663 {
0664     graph_traits< leda::graph >::out_edge_iterator ei, ei_end;
0665     for (boost::tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ei++)
0666         remove_edge(*ei, g);
0667
0668     graph_traits< leda::graph >::in_edge_iterator iei, iei_end;
0669     for (boost::tie(iei, iei_end) = in_edges(u, g); iei != iei_end; iei++)
0670         remove_edge(*iei, g);
0671 }
0672
0673 void remove_vertex(
0674     graph_traits< leda::graph >::vertex_descriptor u, leda::graph& g)
0675 {
0676     g.del_node(u);
0677 }
0678
0679 std::pair< graph_traits< leda::graph >::edge_descriptor, bool > add_edge(
0680     graph_traits< leda::graph >::vertex_descriptor u,
0681     graph_traits< leda::graph >::vertex_descriptor v, leda::graph& g)
0682 {
0683     return std::make_pair(g.new_edge(u, v), true);
0684 }
0685
0686 //===========================================================================
0687 // property maps for GRAPH<vtype,etype>
0688
0689 class leda_graph_id_map : public put_get_helper< int, leda_graph_id_map >
0690 {
0691 public:
0692     typedef readable_property_map_tag category;
0693     typedef int value_type;
0694     typedef int reference;
0695     typedef leda::node key_type;
0696     leda_graph_id_map() {}
0697     template < class T > long operator[](T x) const { return x->id(); }
0698 };
0699 template < class vtype, class etype >
0700 inline leda_graph_id_map get(
0701     vertex_index_t, const leda::GRAPH< vtype, etype >& g)
0702 {
0703     return leda_graph_id_map();
0704 }
0705 template < class vtype, class etype >
0706 inline leda_graph_id_map get(edge_index_t, const leda::GRAPH< vtype, etype >& g)
0707 {
0708     return leda_graph_id_map();
0709 }
0710
0711 template < class Tag > struct leda_property_map
0712 {
0713 };
0714
0715 template <> struct leda_property_map< vertex_index_t >
0716 {
0717     template < class vtype, class etype > struct bind_
0718     {
0719         typedef leda_graph_id_map type;
0720         typedef leda_graph_id_map const_type;
0721     };
0722 };
0723 template <> struct leda_property_map< edge_index_t >
0724 {
0725     template < class vtype, class etype > struct bind_
0726     {
0727         typedef leda_graph_id_map type;
0728         typedef leda_graph_id_map const_type;
0729     };
0730 };
0731
0732 template < class Data, class DataRef, class GraphPtr >
0733 class leda_graph_data_map : public put_get_helper< DataRef,
0734                                 leda_graph_data_map< Data, DataRef, GraphPtr > >
0735 {
0736 public:
0737     typedef Data value_type;
0738     typedef DataRef reference;
0739     typedef void key_type;
0740     typedef lvalue_property_map_tag category;
0741     leda_graph_data_map(GraphPtr g) : m_g(g) {}
0742     template < class NodeOrEdge > DataRef operator[](NodeOrEdge x) const
0743     {
0744         return (*m_g)[x];
0745     }
0746
0747 protected:
0748     GraphPtr m_g;
0749 };
0750
0751 template <> struct leda_property_map< vertex_all_t >
0752 {
0753     template < class vtype, class etype > struct bind_
0754     {
0755         typedef leda_graph_data_map< vtype, vtype&,
0756             leda::GRAPH< vtype, etype >* >
0757             type;
0758         typedef leda_graph_data_map< vtype, const vtype&,
0759             const leda::GRAPH< vtype, etype >* >
0760             const_type;
0761     };
0762 };
0763 template < class vtype, class etype >
0764 inline typename property_map< leda::GRAPH< vtype, etype >, vertex_all_t >::type
0765 get(vertex_all_t, leda::GRAPH< vtype, etype >& g)
0766 {
0767     typedef
0768         typename property_map< leda::GRAPH< vtype, etype >, vertex_all_t >::type
0769             pmap_type;
0770     return pmap_type(&g);
0771 }
0772 template < class vtype, class etype >
0773 inline typename property_map< leda::GRAPH< vtype, etype >,
0774     vertex_all_t >::const_type
0775 get(vertex_all_t, const leda::GRAPH< vtype, etype >& g)
0776 {
0777     typedef typename property_map< leda::GRAPH< vtype, etype >,
0778         vertex_all_t >::const_type pmap_type;
0779     return pmap_type(&g);
0780 }
0781
0782 template <> struct leda_property_map< edge_all_t >
0783 {
0784     template < class vtype, class etype > struct bind_
0785     {
0786         typedef leda_graph_data_map< etype, etype&,
0787             leda::GRAPH< vtype, etype >* >
0788             type;
0789         typedef leda_graph_data_map< etype, const etype&,
0790             const leda::GRAPH< vtype, etype >* >
0791             const_type;
0792     };
0793 };
0794 template < class vtype, class etype >
0795 inline typename property_map< leda::GRAPH< vtype, etype >, edge_all_t >::type
0796 get(edge_all_t, leda::GRAPH< vtype, etype >& g)
0797 {
0798     typedef
0799         typename property_map< leda::GRAPH< vtype, etype >, edge_all_t >::type
0800             pmap_type;
0801     return pmap_type(&g);
0802 }
0803 template < class vtype, class etype >
0804 inline
0805     typename property_map< leda::GRAPH< vtype, etype >, edge_all_t >::const_type
0806     get(edge_all_t, const leda::GRAPH< vtype, etype >& g)
0807 {
0808     typedef typename property_map< leda::GRAPH< vtype, etype >,
0809         edge_all_t >::const_type pmap_type;
0810     return pmap_type(&g);
0811 }
0812
0813 // property map interface to the LEDA node_array class
0814
0815 template < class E, class ERef, class NodeMapPtr >
0816 class leda_node_property_map
0817 : public put_get_helper< ERef, leda_node_property_map< E, ERef, NodeMapPtr > >
0818 {
0819 public:
0820     typedef E value_type;
0821     typedef ERef reference;
0822     typedef leda::node key_type;
0823     typedef lvalue_property_map_tag category;
0824     leda_node_property_map(NodeMapPtr a) : m_array(a) {}
0825     ERef operator[](leda::node n) const { return (*m_array)[n]; }
0826
0827 protected:
0828     NodeMapPtr m_array;
0829 };
0830 template < class E >
0831 leda_node_property_map< E, const E&, const leda::node_array< E >* >
0832 make_leda_node_property_map(const leda::node_array< E >& a)
0833 {
0834     typedef leda_node_property_map< E, const E&, const leda::node_array< E >* >
0835         pmap_type;
0836     return pmap_type(&a);
0837 }
0838 template < class E >
0839 leda_node_property_map< E, E&, leda::node_array< E >* >
0840 make_leda_node_property_map(leda::node_array< E >& a)
0841 {
0842     typedef leda_node_property_map< E, E&, leda::node_array< E >* > pmap_type;
0843     return pmap_type(&a);
0844 }
0845
0846 template < class E >
0847 leda_node_property_map< E, const E&, const leda::node_map< E >* >
0848 make_leda_node_property_map(const leda::node_map< E >& a)
0849 {
0850     typedef leda_node_property_map< E, const E&, const leda::node_map< E >* >
0851         pmap_type;
0852     return pmap_type(&a);
0853 }
0854 template < class E >
0855 leda_node_property_map< E, E&, leda::node_map< E >* >
0856 make_leda_node_property_map(leda::node_map< E >& a)
0857 {
0858     typedef leda_node_property_map< E, E&, leda::node_map< E >* > pmap_type;
0859     return pmap_type(&a);
0860 }
0861
0862 // g++ 'enumeral_type' in template unification not implemented workaround
0863 template < class vtype, class etype, class Tag >
0864 struct property_map< leda::GRAPH< vtype, etype >, Tag >
0865 {
0866     typedef typename leda_property_map< Tag >::template bind_< vtype, etype >
0867         map_gen;
0868     typedef typename map_gen::type type;
0869     typedef typename map_gen::const_type const_type;
0870 };
0871
0872 template < class vtype, class etype, class PropertyTag, class Key >
0873 inline typename boost::property_traits< typename boost::property_map<
0874     leda::GRAPH< vtype, etype >, PropertyTag >::const_type >::value_type
0875 get(PropertyTag p, const leda::GRAPH< vtype, etype >& g, const Key& key)
0876 {
0877     return get(get(p, g), key);
0878 }
0879
0880 template < class vtype, class etype, class PropertyTag, class Key, class Value >
0881 inline void put(PropertyTag p, leda::GRAPH< vtype, etype >& g, const Key& key,
0882     const Value& value)
0883 {
0884     typedef
0885         typename property_map< leda::GRAPH< vtype, etype >, PropertyTag >::type
0886             Map;
0887     Map pmap = get(p, g);
0888     put(pmap, key, value);
0889 }
0890
0891 // property map interface to the LEDA edge_array class
0892
0893 template < class E, class ERef, class EdgeMapPtr >
0894 class leda_edge_property_map
0895 : public put_get_helper< ERef, leda_edge_property_map< E, ERef, EdgeMapPtr > >
0896 {
0897 public:
0898     typedef E value_type;
0899     typedef ERef reference;
0900     typedef leda::edge key_type;
0901     typedef lvalue_property_map_tag category;
0902     leda_edge_property_map(EdgeMapPtr a) : m_array(a) {}
0903     ERef operator[](leda::edge n) const { return (*m_array)[n]; }
0904
0905 protected:
0906     EdgeMapPtr m_array;
0907 };
0908 template < class E >
0909 leda_edge_property_map< E, const E&, const leda::edge_array< E >* >
0910 make_leda_node_property_map(const leda::node_array< E >& a)
0911 {
0912     typedef leda_edge_property_map< E, const E&, const leda::node_array< E >* >
0913         pmap_type;
0914     return pmap_type(&a);
0915 }
0916 template < class E >
0917 leda_edge_property_map< E, E&, leda::edge_array< E >* >
0918 make_leda_edge_property_map(leda::edge_array< E >& a)
0919 {
0920     typedef leda_edge_property_map< E, E&, leda::edge_array< E >* > pmap_type;
0921     return pmap_type(&a);
0922 }
0923
0924 template < class E >
0925 leda_edge_property_map< E, const E&, const leda::edge_map< E >* >
0926 make_leda_edge_property_map(const leda::edge_map< E >& a)
0927 {
0928     typedef leda_edge_property_map< E, const E&, const leda::edge_map< E >* >
0929         pmap_type;
0930     return pmap_type(&a);
0931 }
0932 template < class E >
0933 leda_edge_property_map< E, E&, leda::edge_map< E >* >
0934 make_leda_edge_property_map(leda::edge_map< E >& a)
0935 {
0936     typedef leda_edge_property_map< E, E&, leda::edge_map< E >* > pmap_type;
0937     return pmap_type(&a);
0938 }
0939
0940 } // namespace boost
0941
0942 #endif // BOOST_GRAPH_LEDA_HPP