source: NonGTP/Boost/boost/graph/leda_graph.hpp @ 857

Revision 857, 17.7 KB checked in by igarcia, 18 years ago (diff)
Line 
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
35namespace 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
167namespace 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
Note: See TracBrowser for help on using the repository browser.