Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / 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 // 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