epoc32/include/stdapis/boost/graph/leda_graph.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:33:34 +0100
branchSymbian3
changeset 4 837f303aceeb
permissions -rw-r--r--
Current Symbian^3 public API header files (from PDK 3.0.h)
This is the epoc32/include tree with the "platform" subtrees removed, and
all but a selected few mbg and rsg files removed.
     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