1 //=======================================================================

     2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.

     3 // Copyright 2004 The Trustees of Indiana University.

     4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Douglas Gregor

     5 //

     6 // Distributed under the Boost Software License, Version 1.0. (See

     7 // accompanying file LICENSE_1_0.txt or copy at

     8 // http://www.boost.org/LICENSE_1_0.txt)

     9 //=======================================================================

    10 #ifndef BOOST_GRAPH_LEDA_HPP

    11 #define BOOST_GRAPH_LEDA_HPP

    12 

    13 #include <boost/config.hpp>

    14 #include <boost/iterator/iterator_facade.hpp>

    15 #include <boost/graph/graph_traits.hpp>

    16 #include <boost/graph/properties.hpp>

    17 

    18 #include <LEDA/graph.h>

    19 #include <LEDA/node_array.h>

    20 #include <LEDA/node_map.h>

    21 

    22 // The functions and classes in this file allows the user to

    23 // treat a LEDA GRAPH object as a boost graph "as is". No

    24 // wrapper is needed for the GRAPH object.

    25 

    26 // Remember to define LEDA_PREFIX so that LEDA types such as

    27 // leda_edge show up as "leda_edge" and not just "edge".

    28 

    29 // Warning: this implementation relies on partial specialization

    30 // for the graph_traits class (so it won't compile with Visual C++)

    31 

    32 // Warning: this implementation is in alpha and has not been tested

    33 

    34 #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION

    35 namespace boost {

    36 

    37   struct leda_graph_traversal_category : 

    38     public virtual bidirectional_graph_tag,

    39     public virtual adjacency_graph_tag,

    40     public virtual vertex_list_graph_tag { };

    41 

    42   template <class vtype, class etype>

    43   struct graph_traits< leda::GRAPH<vtype,etype> > {

    44     typedef leda_node vertex_descriptor;

    45     typedef leda_edge edge_descriptor;

    46 

    47     class adjacency_iterator 

    48       : public iterator_facade<adjacency_iterator,

    49                                leda_node,

    50                                bidirectional_traversal_tag,

    51                                leda_node,

    52                                const leda_node*>

    53     {

    54     public:

    55       explicit adjacency_iterator(leda_edge edge = 0) : base(edge) {}

    56 

    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 = Succ_Adj_Edge(base, 0); }

    64       void decrement() { base = Pred_Adj_Edge(base, 0); }

    65 

    66       leda_edge base;

    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       explicit out_edge_iterator(leda_edge edge = 0) : base(edge) {}

    80 

    81     private:

    82       const leda_edge& dereference() const { return base; }

    83 

    84       bool equal(const out_edge_iterator& other) const

    85       { return base == other.base; }

    86 

    87       void increment() { base = Succ_Adj_Edge(base, 0); }

    88       void decrement() { base = Pred_Adj_Edge(base, 0); }

    89 

    90       leda_edge base;

    91 

    92       friend class iterator_core_access;

    93     };

    94       

    95     class in_edge_iterator 

    96       : public iterator_facade<in_edge_iterator,

    97                                leda_edge,

    98                                bidirectional_traversal_tag,

    99                                const leda_edge&,

   100                                const leda_edge*>

   101     {

   102     public:

   103       explicit in_edge_iterator(leda_edge edge = 0) : base(edge) {}

   104 

   105     private:

   106       const leda_edge& dereference() const { return base; }

   107 

   108       bool equal(const in_edge_iterator& other) const

   109       { return base == other.base; }

   110 

   111       void increment() { base = Succ_Adj_Edge(base, 1); }

   112       void decrement() { base = Pred_Adj_Edge(base, 1); }

   113 

   114       leda_edge base;

   115 

   116       friend class iterator_core_access;

   117     };

   118 

   119     class vertex_iterator 

   120       : public iterator_facade<vertex_iterator,

   121                                leda_node,

   122                                bidirectional_traversal_tag,

   123                                const leda_node&,

   124                                const leda_node*>

   125     {

   126     public:

   127       vertex_iterator(leda_node node = 0, 

   128                       const leda::GRAPH<vtype, etype>* g = 0)

   129         : base(node), g(g) {}

   130 

   131     private:

   132       const leda_node& dereference() const { return base; }

   133 

   134       bool equal(const vertex_iterator& other) const

   135       { return base == other.base; }

   136 

   137       void increment() { base = g->succ_node(base); }

   138       void decrement() { base = g->pred_node(base); }

   139 

   140       leda_node base;

   141       const leda::GRAPH<vtype, etype>* g;

   142 

   143       friend class iterator_core_access;

   144     };

   145 

   146     typedef directed_tag directed_category;

   147     typedef allow_parallel_edge_tag edge_parallel_category; // not sure here

   148     typedef leda_graph_traversal_category traversal_category;

   149     typedef int vertices_size_type;

   150     typedef int edges_size_type;

   151     typedef int degree_size_type;

   152   };

   153 

   154   template <class vtype, class etype>

   155   struct vertex_property< leda::GRAPH<vtype,etype> > {

   156     typedef vtype type;

   157   };

   158 

   159   template <class vtype, class etype>

   160   struct edge_property< leda::GRAPH<vtype,etype> > {

   161     typedef etype type;

   162   };

   163 

   164 } // namespace boost

   165 #endif

   166 

   167 namespace boost {

   168 

   169   template <class vtype, class etype>

   170   typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor

   171   source(typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor e,

   172          const leda::GRAPH<vtype,etype>& g)

   173   {

   174     return source(e);

   175   }

   176 

   177   template <class vtype, class etype>

   178   typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor

   179   target(typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor e,

   180          const leda::GRAPH<vtype,etype>& g)

   181   {

   182     return target(e);

   183   }

   184 

   185   template <class vtype, class etype>

   186   inline std::pair<

   187     typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_iterator,

   188     typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_iterator >  

   189   vertices(const leda::GRAPH<vtype,etype>& g)

   190   {

   191     typedef typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_iterator

   192       Iter;

   193     return std::make_pair( Iter(g.first_node(),&g), Iter(0,&g) );

   194   }

   195 

   196   // no edges(g) function

   197 

   198   template <class vtype, class etype>

   199   inline std::pair<

   200     typename graph_traits< leda::GRAPH<vtype,etype> >::out_edge_iterator,

   201     typename graph_traits< leda::GRAPH<vtype,etype> >::out_edge_iterator >  

   202   out_edges(

   203     typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u, 

   204     const leda::GRAPH<vtype,etype>& g)

   205   {

   206     typedef typename graph_traits< leda::GRAPH<vtype,etype> >

   207       ::out_edge_iterator Iter;

   208     return std::make_pair( Iter(First_Adj_Edge(u,0)), Iter(0) );

   209   }

   210 

   211   template <class vtype, class etype>

   212   inline std::pair<

   213     typename graph_traits< leda::GRAPH<vtype,etype> >::in_edge_iterator,

   214     typename graph_traits< leda::GRAPH<vtype,etype> >::in_edge_iterator >  

   215   in_edges(

   216     typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u, 

   217     const leda::GRAPH<vtype,etype>& g)

   218   {

   219     typedef typename graph_traits< leda::GRAPH<vtype,etype> >

   220       ::in_edge_iterator Iter;

   221     return std::make_pair( Iter(First_Adj_Edge(u,1)), Iter(0) );

   222   }

   223 

   224   template <class vtype, class etype>

   225   inline std::pair<

   226     typename graph_traits< leda::GRAPH<vtype,etype> >::adjacency_iterator,

   227     typename graph_traits< leda::GRAPH<vtype,etype> >::adjacency_iterator >  

   228   adjacent_vertices(

   229     typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u, 

   230     const leda::GRAPH<vtype,etype>& g)

   231   {

   232     typedef typename graph_traits< leda::GRAPH<vtype,etype> >

   233       ::adjacency_iterator Iter;

   234     return std::make_pair( Iter(First_Adj_Edge(u,0)), Iter(0) );

   235   }

   236 

   237   template <class vtype, class etype>

   238   typename graph_traits< leda::GRAPH<vtype,etype> >::vertices_size_type

   239   num_vertices(const leda::GRAPH<vtype,etype>& g)

   240   {

   241     return g.number_of_nodes();

   242   }  

   243 

   244   template <class vtype, class etype>

   245   typename graph_traits< leda::GRAPH<vtype,etype> >::edges_size_type

   246   num_edges(const leda::GRAPH<vtype,etype>& g)

   247   {

   248     return g.number_of_edges();

   249   }  

   250 

   251   template <class vtype, class etype>

   252   typename graph_traits< leda::GRAPH<vtype,etype> >::degree_size_type

   253   out_degree(

   254     typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u, 

   255     const leda::GRAPH<vtype,etype>&)

   256   {

   257     return outdeg(u);

   258   }

   259 

   260   template <class vtype, class etype>

   261   typename graph_traits< leda::GRAPH<vtype,etype> >::degree_size_type

   262   in_degree(

   263     typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u, 

   264     const leda::GRAPH<vtype,etype>&)

   265   {

   266     return indeg(u);

   267   }

   268 

   269   template <class vtype, class etype>

   270   typename graph_traits< leda::GRAPH<vtype,etype> >::degree_size_type

   271   degree(

   272     typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u, 

   273     const leda::GRAPH<vtype,etype>&)

   274   {

   275     return outdeg(u) + indeg(u);

   276   }

   277   

   278   template <class vtype, class etype>

   279   typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor

   280   add_vertex(leda::GRAPH<vtype,etype>& g)

   281   {

   282     return g.new_node();

   283   }

   284 

   285   template <class vtype, class etype>

   286   typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor

   287   add_vertex(const vtype& vp, leda::GRAPH<vtype,etype>& g)

   288   {

   289     return g.new_node(vp);

   290   }

   291 

   292   // Hmm, LEDA doesn't have the equivalent of clear_vertex() -JGS

   293   // need to write an implementation

   294   template <class vtype, class etype>

   295   void clear_vertex(

   296     typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,

   297     leda::GRAPH<vtype,etype>& g)

   298   {

   299     g.del_node(u);

   300   }

   301 

   302   template <class vtype, class etype>

   303   void remove_vertex(

   304     typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,

   305     leda::GRAPH<vtype,etype>& g)

   306   {

   307     g.del_node(u);

   308   }

   309 

   310   template <class vtype, class etype>

   311   std::pair<

   312     typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor,

   313     bool>

   314   add_edge(

   315     typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,

   316     typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor v,

   317     leda::GRAPH<vtype,etype>& g)

   318   {

   319     return std::make_pair(g.new_edge(u, v), true);

   320   }

   321 

   322   template <class vtype, class etype>

   323   std::pair<

   324     typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor,

   325     bool>

   326   add_edge(

   327     typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,

   328     typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor v,

   329     const etype& et, 

   330     leda::GRAPH<vtype,etype>& g)

   331   {

   332     return std::make_pair(g.new_edge(u, v, et), true);

   333   }

   334 

   335   template <class vtype, class etype>

   336   void

   337   remove_edge(

   338     typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,

   339     typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor v,

   340     leda::GRAPH<vtype,etype>& g)

   341   {

   342     typename graph_traits< leda::GRAPH<vtype,etype> >::out_edge_iterator 

   343       i,iend;

   344     for (boost::tie(i,iend) = out_edges(u,g); i != iend; ++i)

   345       if (target(*i,g) == v)

   346         g.del_edge(*i);

   347   }

   348 

   349   template <class vtype, class etype>

   350   void

   351   remove_edge(

   352     typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor e,

   353     leda::GRAPH<vtype,etype>& g)

   354   {

   355     g.del_edge(e);

   356   }

   357 

   358   //===========================================================================

   359   // property maps

   360   

   361   class leda_graph_id_map

   362     : public put_get_helper<int, leda_graph_id_map>

   363   {

   364   public:

   365     typedef readable_property_map_tag category;

   366     typedef int value_type;

   367     typedef int reference;

   368     typedef leda_node key_type;

   369     leda_graph_id_map() { }

   370     template <class T>

   371     long operator[](T x) const { return x->id(); }

   372   };

   373   template <class vtype, class etype>

   374   inline leda_graph_id_map

   375   get(vertex_index_t, const leda::GRAPH<vtype, etype>& g) {

   376     return leda_graph_id_map();

   377   }

   378   template <class vtype, class etype>

   379   inline leda_graph_id_map

   380   get(edge_index_t, const leda::GRAPH<vtype, etype>& g) {

   381     return leda_graph_id_map();

   382   }

   383 

   384   template <class Tag>

   385   struct leda_property_map { };

   386 

   387   template <>

   388   struct leda_property_map<vertex_index_t> {

   389     template <class vtype, class etype>

   390     struct bind_ {

   391       typedef leda_graph_id_map type;

   392       typedef leda_graph_id_map const_type;

   393     };

   394   };

   395   template <>

   396   struct leda_property_map<edge_index_t> {

   397     template <class vtype, class etype>

   398     struct bind_ {

   399       typedef leda_graph_id_map type;

   400       typedef leda_graph_id_map const_type;

   401     };

   402   };

   403 

   404 

   405   template <class Data, class DataRef, class GraphPtr>

   406   class leda_graph_data_map

   407     : public put_get_helper<DataRef, 

   408                             leda_graph_data_map<Data,DataRef,GraphPtr> >

   409   {

   410   public:

   411     typedef Data value_type;

   412     typedef DataRef reference;

   413     typedef void key_type;

   414     typedef lvalue_property_map_tag category;

   415     leda_graph_data_map(GraphPtr g) : m_g(g) { }

   416     template <class NodeOrEdge>

   417     DataRef operator[](NodeOrEdge x) const { return (*m_g)[x]; }

   418   protected:

   419     GraphPtr m_g;

   420   };

   421 

   422   template <>

   423   struct leda_property_map<vertex_all_t> {

   424     template <class vtype, class etype>

   425     struct bind_ {

   426       typedef leda_graph_data_map<vtype, vtype&, leda::GRAPH<vtype, etype>*> type;

   427       typedef leda_graph_data_map<vtype, const vtype&, 

   428         const leda::GRAPH<vtype, etype>*> const_type;

   429     };

   430   };  

   431   template <class vtype, class etype >

   432   inline typename property_map< leda::GRAPH<vtype, etype>, vertex_all_t>::type

   433   get(vertex_all_t, leda::GRAPH<vtype, etype>& g) {

   434     typedef typename property_map< leda::GRAPH<vtype, etype>, vertex_all_t>::type 

   435       pmap_type;

   436     return pmap_type(&g);

   437   }

   438   template <class vtype, class etype >

   439   inline typename property_map< leda::GRAPH<vtype, etype>, vertex_all_t>::const_type

   440   get(vertex_all_t, const leda::GRAPH<vtype, etype>& g) {

   441     typedef typename property_map< leda::GRAPH<vtype, etype>, 

   442       vertex_all_t>::const_type pmap_type;

   443     return pmap_type(&g);

   444   }

   445 

   446   template <>

   447   struct leda_property_map<edge_all_t> {

   448     template <class vtype, class etype>

   449     struct bind_ {

   450       typedef leda_graph_data_map<etype, etype&, leda::GRAPH<vtype, etype>*> type;

   451       typedef leda_graph_data_map<etype, const etype&, 

   452         const leda::GRAPH<vtype, etype>*> const_type;

   453     };

   454   };

   455   template <class vtype, class etype >

   456   inline typename property_map< leda::GRAPH<vtype, etype>, edge_all_t>::type

   457   get(edge_all_t, leda::GRAPH<vtype, etype>& g) {

   458     typedef typename property_map< leda::GRAPH<vtype, etype>, edge_all_t>::type 

   459       pmap_type;

   460     return pmap_type(&g);

   461   }

   462   template <class vtype, class etype >

   463   inline typename property_map< leda::GRAPH<vtype, etype>, edge_all_t>::const_type

   464   get(edge_all_t, const leda::GRAPH<vtype, etype>& g) {

   465     typedef typename property_map< leda::GRAPH<vtype, etype>, 

   466       edge_all_t>::const_type pmap_type;

   467     return pmap_type(&g);

   468   }

   469 

   470   // property map interface to the LEDA node_array class

   471 

   472   template <class E, class ERef, class NodeMapPtr>

   473   class leda_node_property_map

   474     : public put_get_helper<ERef, leda_node_property_map<E, ERef, NodeMapPtr> >

   475   {

   476   public:

   477     typedef E value_type;

   478     typedef ERef reference;

   479     typedef leda_node key_type;

   480     typedef lvalue_property_map_tag category;

   481     leda_node_property_map(NodeMapPtr a) : m_array(a) { }

   482     ERef operator[](leda_node n) const { return (*m_array)[n]; }

   483   protected:

   484     NodeMapPtr m_array;

   485   };

   486   template <class E>

   487   leda_node_property_map<E, const E&, const leda_node_array<E>*>

   488   make_leda_node_property_map(const leda_node_array<E>& a)

   489   {

   490     typedef leda_node_property_map<E, const E&, const leda_node_array<E>*>

   491       pmap_type;

   492     return pmap_type(&a);

   493   }

   494   template <class E>

   495   leda_node_property_map<E, E&, leda_node_array<E>*>

   496   make_leda_node_property_map(leda_node_array<E>& a)

   497   {

   498     typedef leda_node_property_map<E, E&, leda_node_array<E>*> pmap_type;

   499     return pmap_type(&a);

   500   }

   501 

   502   template <class E>

   503   leda_node_property_map<E, const E&, const leda_node_map<E>*>

   504   make_leda_node_property_map(const leda_node_map<E>& a)

   505   {

   506     typedef leda_node_property_map<E,const E&,const leda_node_map<E>*> 

   507       pmap_type;

   508     return pmap_type(&a);

   509   }

   510   template <class E>

   511   leda_node_property_map<E, E&, leda_node_map<E>*>

   512   make_leda_node_property_map(leda_node_map<E>& a)

   513   {

   514     typedef leda_node_property_map<E, E&, leda_node_map<E>*> pmap_type;

   515     return pmap_type(&a);

   516   }

   517 

   518   // g++ 'enumeral_type' in template unification not implemented workaround

   519   template <class vtype, class etype, class Tag>

   520   struct property_map<leda::GRAPH<vtype, etype>, Tag> {

   521     typedef typename 

   522       leda_property_map<Tag>::template bind_<vtype, etype> map_gen;

   523     typedef typename map_gen::type type;

   524     typedef typename map_gen::const_type const_type;

   525   };

   526 

   527   template <class vtype, class etype, class PropertyTag, class Key>

   528   inline

   529   typename boost::property_traits<

   530     typename boost::property_map<leda::GRAPH<vtype, etype>,PropertyTag>::const_type

   531   >::value_type

   532   get(PropertyTag p, const leda::GRAPH<vtype, etype>& g, const Key& key) {

   533     return get(get(p, g), key);

   534   }

   535   

   536   template <class vtype, class etype, class PropertyTag, class Key,class Value>

   537   inline void

   538   put(PropertyTag p, leda::GRAPH<vtype, etype>& g, 

   539       const Key& key, const Value& value)

   540   {

   541     typedef typename property_map<leda::GRAPH<vtype, etype>, PropertyTag>::type Map;

   542     Map pmap = get(p, g);

   543     put(pmap, key, value);

   544   }

   545 

   546 } // namespace boost

   547 

   548 

   549 #endif // BOOST_GRAPH_LEDA_HPP