Ticket #1326: leda_graph.hpp

File leda_graph.hpp, 19.0 KB (added by iouri.smirnov@…, 9 years ago)

Patched LEDA graph adapter

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#ifndef BOOST_GRAPH_LEDA_NAMESPACE
14#define BOOST_GRAPH_LEDA_NAMESPACE leda
15#endif
16#ifndef BOOST_GRAPH_LEDA_DECL
17#define BOOST_GRAPH_LEDA_DECL(VT,ET) BOOST_GRAPH_LEDA_NAMESPACE::GRAPH< VT, ET >
18#endif
19
20#include <boost/config.hpp>
21#include <boost/iterator/iterator_facade.hpp>
22#include <boost/graph/graph_traits.hpp>
23#include <boost/graph/properties.hpp>
24
25#include <LEDA/graph.h>
26#include <LEDA/node_array.h>
27#include <LEDA/node_map.h>
28
29// The functions and classes in this file allows the user to
30// treat a LEDA GRAPH object as a boost graph "as is". No
31// wrapper is needed for the GRAPH object.
32
33// Remember to define LEDA_PREFIX so that LEDA types such as
34// leda_edge show up as "leda_edge" and not just "edge".
35
36// Warning: this implementation relies on partial specialization
37// for the graph_traits class (so it won't compile with Visual C++)
38
39// Warning: this implementation is in alpha and has not been tested
40
41#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
42namespace boost {
43
44  struct leda_graph_traversal_category : 
45    public virtual bidirectional_graph_tag,
46    public virtual adjacency_graph_tag,
47    public virtual edge_list_graph_tag,
48    public virtual vertex_list_graph_tag { };
49
50  template <class vtype, class etype>
51  struct graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) > {
52    typedef leda_node vertex_descriptor;
53    typedef leda_edge edge_descriptor;
54
55    class adjacency_iterator 
56      : public iterator_facade<adjacency_iterator,
57                               leda_node,
58                               bidirectional_traversal_tag,
59                               leda_node>
60    {
61    public:
62      explicit adjacency_iterator(leda_edge edge = 0) : base(edge) {}
63
64    private:
65      leda_node dereference() const { return BOOST_GRAPH_LEDA_NAMESPACE::target(base); }
66
67      bool equal(const adjacency_iterator& other) const
68      { return base == other.base; }
69
70      void increment() { base = Succ_Adj_Edge(base, 0); }
71      void decrement() { base = Pred_Adj_Edge(base, 0); }
72
73      leda_edge base;
74
75      friend class iterator_core_access;
76    };
77     
78    class out_edge_iterator 
79      : public iterator_facade<out_edge_iterator,
80                               leda_edge,
81                               bidirectional_traversal_tag,
82                               leda_edge>
83    {
84    public:
85      explicit out_edge_iterator(leda_edge edge = 0) : base(edge) {}
86
87    private:
88      leda_edge dereference() const { return base; }
89
90      bool equal(const out_edge_iterator& other) const
91      { return base == other.base; }
92
93      void increment() { base = Succ_Adj_Edge(base, 0); }
94      void decrement() { base = Pred_Adj_Edge(base, 0); }
95
96      leda_edge base;
97
98      friend class iterator_core_access;
99    };
100     
101    class in_edge_iterator 
102      : public iterator_facade<in_edge_iterator,
103                               leda_edge,
104                               bidirectional_traversal_tag,
105                               leda_edge>
106    {
107    public:
108      explicit in_edge_iterator(leda_edge edge = 0) : base(edge) {}
109
110    private:
111      leda_edge dereference() const { return base; }
112
113      bool equal(const in_edge_iterator& other) const
114      { return base == other.base; }
115
116      void increment() { base = Succ_Adj_Edge(base, 1); }
117      void decrement() { base = Pred_Adj_Edge(base, 1); }
118
119      leda_edge base;
120
121      friend class iterator_core_access;
122    };
123
124    class edge_iterator 
125      : public iterator_facade<edge_iterator,
126                               leda_edge,
127                               bidirectional_traversal_tag,
128                               leda_edge>
129    {
130    public:
131      explicit edge_iterator(leda_edge edge = 0) : base(edge) {}
132
133    private:
134      leda_edge dereference() const { return base; }
135
136      bool equal(const edge_iterator& other) const
137      { return base == other.base; }
138
139      void increment() { base = graph_of(base)->succ_edge(base); }
140      void decrement() { base = graph_of(base)->pred_edge(base); }
141
142      leda_edge base;
143
144      friend class iterator_core_access;
145    };
146
147    class vertex_iterator 
148      : public iterator_facade<vertex_iterator,
149                               leda_node,
150                               bidirectional_traversal_tag,
151                               leda_node>
152    {
153    public:
154      explicit vertex_iterator(leda_node node = 0) : base(node) {}
155
156    private:
157      leda_node dereference() const { return base; }
158
159      bool equal(const vertex_iterator& other) const
160      { return base == other.base; }
161
162      void increment() { base = graph_of(base)->succ_node(base); }
163      void decrement() { base = graph_of(base)->pred_node(base); }
164
165      leda_node base;
166
167      friend class iterator_core_access;
168    };
169
170    typedef directed_tag directed_category;
171    typedef allow_parallel_edge_tag edge_parallel_category; // not sure here
172    typedef leda_graph_traversal_category traversal_category;
173    typedef int vertices_size_type;
174    typedef int edges_size_type;
175    typedef int degree_size_type;
176  };
177
178  template <class vtype, class etype>
179  struct vertex_property< BOOST_GRAPH_LEDA_DECL(vtype,etype) > {
180    typedef vtype type;
181  };
182
183  template <class vtype, class etype>
184  struct edge_property< BOOST_GRAPH_LEDA_DECL(vtype,etype) > {
185    typedef etype type;
186  };
187
188} // namespace boost
189#endif
190
191namespace boost {
192
193  template <class vtype, class etype>
194  typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor
195  source(typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::edge_descriptor e,
196         const BOOST_GRAPH_LEDA_DECL(vtype,etype)& g)
197  {
198    return source(e);
199  }
200
201  template <class vtype, class etype>
202  typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor
203  target(typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::edge_descriptor e,
204         const BOOST_GRAPH_LEDA_DECL(vtype,etype)& g)
205  {
206    return target(e);
207  }
208
209  template <class vtype, class etype>
210  inline std::pair<
211    typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_iterator,
212    typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_iterator > 
213  vertices(const BOOST_GRAPH_LEDA_DECL(vtype,etype)& g)
214  {
215    typedef typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_iterator
216      Iter;
217    return std::make_pair( Iter(g.first_node()), Iter(0) );
218  }
219
220  template <class vtype, class etype>
221  inline std::pair<
222    typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::edge_iterator,
223    typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::edge_iterator > 
224  edges(const BOOST_GRAPH_LEDA_DECL(vtype,etype)& g)
225  {
226    typedef typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::edge_iterator
227      Iter;
228    return std::make_pair( Iter(g.first_edge()), Iter(0) );
229  }
230
231  template <class vtype, class etype>
232  inline std::pair<
233    typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::out_edge_iterator,
234    typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::out_edge_iterator > 
235  out_edges(
236    typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor u, 
237    const BOOST_GRAPH_LEDA_DECL(vtype,etype)& g)
238  {
239    typedef typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >
240      ::out_edge_iterator Iter;
241    return std::make_pair( Iter(First_Adj_Edge(u,0)), Iter(0) );
242  }
243
244  template <class vtype, class etype>
245  inline std::pair<
246    typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::in_edge_iterator,
247    typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::in_edge_iterator > 
248  in_edges(
249    typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor u, 
250    const BOOST_GRAPH_LEDA_DECL(vtype,etype)& g)
251  {
252    typedef typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >
253      ::in_edge_iterator Iter;
254    return std::make_pair( Iter(First_Adj_Edge(u,1)), Iter(0) );
255  }
256
257  template <class vtype, class etype>
258  inline std::pair<
259    typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::adjacency_iterator,
260    typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::adjacency_iterator > 
261  adjacent_vertices(
262    typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor u, 
263    const BOOST_GRAPH_LEDA_DECL(vtype,etype)& g)
264  {
265    typedef typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >
266      ::adjacency_iterator Iter;
267    return std::make_pair( Iter(First_Adj_Edge(u,0)), Iter(0) );
268  }
269
270  template <class vtype, class etype>
271  typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertices_size_type
272  num_vertices(const BOOST_GRAPH_LEDA_DECL(vtype,etype)& g)
273  {
274    return g.number_of_nodes();
275  } 
276
277  template <class vtype, class etype>
278  typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::edges_size_type
279  num_edges(const BOOST_GRAPH_LEDA_DECL(vtype,etype)& g)
280  {
281    return g.number_of_edges();
282  } 
283
284  template <class vtype, class etype>
285  typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::degree_size_type
286  out_degree(
287    typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor u, 
288    const BOOST_GRAPH_LEDA_DECL(vtype,etype)&)
289  {
290    return outdeg(u);
291  }
292
293  template <class vtype, class etype>
294  typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::degree_size_type
295  in_degree(
296    typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor u, 
297    const BOOST_GRAPH_LEDA_DECL(vtype,etype)&)
298  {
299    return indeg(u);
300  }
301
302  template <class vtype, class etype>
303  typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::degree_size_type
304  degree(
305    typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor u, 
306    const BOOST_GRAPH_LEDA_DECL(vtype,etype)&)
307  {
308    return outdeg(u) + indeg(u);
309  }
310 
311  template <class vtype, class etype>
312  typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor
313  add_vertex(BOOST_GRAPH_LEDA_DECL(vtype,etype)& g)
314  {
315    return g.new_node();
316  }
317
318  template <class vtype, class etype>
319  typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor
320  add_vertex(const vtype& vp, BOOST_GRAPH_LEDA_DECL(vtype,etype)& g)
321  {
322    return g.new_node(vp);
323  }
324
325  // Hmm, LEDA doesn't have the equivalent of clear_vertex() -JGS
326  // need to write an implementation
327  template <class vtype, class etype>
328  void clear_vertex(
329    typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor u,
330    BOOST_GRAPH_LEDA_DECL(vtype,etype)& g)
331  {
332    g.del_node(u);
333  }
334
335  template <class vtype, class etype>
336  void remove_vertex(
337    typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor u,
338    BOOST_GRAPH_LEDA_DECL(vtype,etype)& g)
339  {
340    g.del_node(u);
341  }
342
343  template <class vtype, class etype>
344  std::pair<
345    typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::edge_descriptor,
346    bool>
347  add_edge(
348    typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor u,
349    typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor v,
350    BOOST_GRAPH_LEDA_DECL(vtype,etype)& g)
351  {
352    return std::make_pair(g.new_edge(u, v), true);
353  }
354
355  template <class vtype, class etype>
356  std::pair<
357    typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::edge_descriptor,
358    bool>
359  add_edge(
360    typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor u,
361    typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor v,
362    const etype& et, 
363    BOOST_GRAPH_LEDA_DECL(vtype,etype)& g)
364  {
365    return std::make_pair(g.new_edge(u, v, et), true);
366  }
367
368  template <class vtype, class etype>
369  void
370  remove_edge(
371    typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor u,
372    typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::vertex_descriptor v,
373    BOOST_GRAPH_LEDA_DECL(vtype,etype)& g)
374  {
375    typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::out_edge_iterator
376      i,iend;
377    for (boost::tie(i,iend) = out_edges(u,g); i != iend; ++i)
378      if (target(*i,g) == v)
379        g.del_edge(*i);
380  }
381
382  template <class vtype, class etype>
383  void
384  remove_edge(
385    typename graph_traits< BOOST_GRAPH_LEDA_DECL(vtype,etype) >::edge_descriptor e,
386    BOOST_GRAPH_LEDA_DECL(vtype,etype)& g)
387  {
388    g.del_edge(e);
389  }
390
391  //===========================================================================
392  // property maps
393 
394  class leda_graph_id_map
395    : public put_get_helper<int, leda_graph_id_map>
396  {
397  public:
398    typedef readable_property_map_tag category;
399    typedef int value_type;
400    typedef int reference;
401    typedef leda_node key_type;
402    leda_graph_id_map() { }
403    template <class T>
404    long operator[](T x) const { return x->id(); }
405  };
406  template <class vtype, class etype>
407  inline leda_graph_id_map
408  get(vertex_index_t, const BOOST_GRAPH_LEDA_DECL(vtype,etype)& g) {
409    return leda_graph_id_map();
410  }
411  template <class vtype, class etype>
412  inline leda_graph_id_map
413  get(edge_index_t, const BOOST_GRAPH_LEDA_DECL(vtype,etype)& g) {
414    return leda_graph_id_map();
415  }
416
417  template <class Tag>
418  struct leda_property_map { };
419
420  template <>
421  struct leda_property_map<vertex_index_t> {
422    template <class vtype, class etype>
423    struct bind_ {
424      typedef leda_graph_id_map type;
425      typedef leda_graph_id_map const_type;
426    };
427  };
428  template <>
429  struct leda_property_map<edge_index_t> {
430    template <class vtype, class etype>
431    struct bind_ {
432      typedef leda_graph_id_map type;
433      typedef leda_graph_id_map const_type;
434    };
435  };
436
437
438  template <class Data, class DataRef, class GraphPtr>
439  class leda_graph_data_map
440    : public put_get_helper<DataRef, 
441                            leda_graph_data_map<Data,DataRef,GraphPtr> >
442  {
443  public:
444    typedef Data value_type;
445    typedef DataRef reference;
446    typedef void key_type;
447    typedef lvalue_property_map_tag category;
448    leda_graph_data_map(GraphPtr g) : m_g(g) { }
449    template <class NodeOrEdge>
450    DataRef operator[](NodeOrEdge x) const { return (*m_g)[x]; }
451  protected:
452    GraphPtr m_g;
453  };
454
455  template <>
456  struct leda_property_map<vertex_all_t> {
457    template <class vtype, class etype>
458    struct bind_ {
459      typedef leda_graph_data_map<vtype, vtype&, BOOST_GRAPH_LEDA_DECL(vtype,etype)*> type;
460      typedef leda_graph_data_map<vtype, const vtype&, 
461        const BOOST_GRAPH_LEDA_DECL(vtype,etype)*> const_type;
462    };
463  }; 
464  template <class vtype, class etype >
465  inline typename property_map< BOOST_GRAPH_LEDA_DECL(vtype,etype), vertex_all_t>::type
466  get(vertex_all_t, BOOST_GRAPH_LEDA_DECL(vtype,etype)& g) {
467    typedef typename property_map< BOOST_GRAPH_LEDA_DECL(vtype,etype), vertex_all_t>::type
468      pmap_type;
469    return pmap_type(&g);
470  }
471  template <class vtype, class etype >
472  inline typename property_map< BOOST_GRAPH_LEDA_DECL(vtype,etype), vertex_all_t>::const_type
473  get(vertex_all_t, const BOOST_GRAPH_LEDA_DECL(vtype,etype)& g) {
474    typedef typename property_map< BOOST_GRAPH_LEDA_DECL(vtype,etype), 
475      vertex_all_t>::const_type pmap_type;
476    return pmap_type(&g);
477  }
478
479  template <>
480  struct leda_property_map<edge_all_t> {
481    template <class vtype, class etype>
482    struct bind_ {
483      typedef leda_graph_data_map<etype, etype&, BOOST_GRAPH_LEDA_DECL(vtype,etype)*> type;
484      typedef leda_graph_data_map<etype, const etype&, 
485        const BOOST_GRAPH_LEDA_DECL(vtype,etype)*> const_type;
486    };
487  };
488  template <class vtype, class etype >
489  inline typename property_map< BOOST_GRAPH_LEDA_DECL(vtype,etype), edge_all_t>::type
490  get(edge_all_t, BOOST_GRAPH_LEDA_DECL(vtype,etype)& g) {
491    typedef typename property_map< BOOST_GRAPH_LEDA_DECL(vtype,etype), edge_all_t>::type
492      pmap_type;
493    return pmap_type(&g);
494  }
495  template <class vtype, class etype >
496  inline typename property_map< BOOST_GRAPH_LEDA_DECL(vtype,etype), edge_all_t>::const_type
497  get(edge_all_t, const BOOST_GRAPH_LEDA_DECL(vtype,etype)& g) {
498    typedef typename property_map< BOOST_GRAPH_LEDA_DECL(vtype,etype), 
499      edge_all_t>::const_type pmap_type;
500    return pmap_type(&g);
501  }
502
503  // property map interface to the LEDA node_array class
504
505  template <class E, class ERef, class NodeMapPtr>
506  class leda_node_property_map
507    : public put_get_helper<ERef, leda_node_property_map<E, ERef, NodeMapPtr> >
508  {
509  public:
510    typedef E value_type;
511    typedef ERef reference;
512    typedef leda_node key_type;
513    typedef lvalue_property_map_tag category;
514    leda_node_property_map(NodeMapPtr a) : m_array(a) { }
515    ERef operator[](leda_node n) const { return (*m_array)[n]; }
516  protected:
517    NodeMapPtr m_array;
518  };
519  template <class E>
520  leda_node_property_map<E, const E&, const leda_node_array<E>*>
521  make_leda_node_property_map(const leda_node_array<E>& a)
522  {
523    typedef leda_node_property_map<E, const E&, const leda_node_array<E>*>
524      pmap_type;
525    return pmap_type(&a);
526  }
527  template <class E>
528  leda_node_property_map<E, E&, leda_node_array<E>*>
529  make_leda_node_property_map(leda_node_array<E>& a)
530  {
531    typedef leda_node_property_map<E, E&, leda_node_array<E>*> pmap_type;
532    return pmap_type(&a);
533  }
534
535  template <class E>
536  leda_node_property_map<E, const E&, const leda_node_map<E>*>
537  make_leda_node_property_map(const leda_node_map<E>& a)
538  {
539    typedef leda_node_property_map<E,const E&,const leda_node_map<E>*> 
540      pmap_type;
541    return pmap_type(&a);
542  }
543  template <class E>
544  leda_node_property_map<E, E&, leda_node_map<E>*>
545  make_leda_node_property_map(leda_node_map<E>& a)
546  {
547    typedef leda_node_property_map<E, E&, leda_node_map<E>*> pmap_type;
548    return pmap_type(&a);
549  }
550
551  // g++ 'enumeral_type' in template unification not implemented workaround
552  template <class vtype, class etype, class Tag>
553  struct property_map<BOOST_GRAPH_LEDA_DECL(vtype,etype), Tag> {
554    typedef typename 
555      leda_property_map<Tag>::template bind_<vtype, etype> map_gen;
556    typedef typename map_gen::type type;
557    typedef typename map_gen::const_type const_type;
558  };
559
560  template <class vtype, class etype, class PropertyTag, class Key>
561  inline
562  typename boost::property_traits<
563    typename boost::property_map<BOOST_GRAPH_LEDA_DECL(vtype,etype),PropertyTag>::const_type
564  >::value_type
565  get(PropertyTag p, const BOOST_GRAPH_LEDA_DECL(vtype,etype)& g, const Key& key) {
566    return get(get(p, g), key);
567  }
568 
569  template <class vtype, class etype, class PropertyTag, class Key,class Value>
570  inline void
571  put(PropertyTag p, BOOST_GRAPH_LEDA_DECL(vtype,etype)& g, 
572      const Key& key, const Value& value)
573  {
574    typedef typename property_map<BOOST_GRAPH_LEDA_DECL(vtype,etype), PropertyTag>::type Map;
575    Map pmap = get(p, g);
576    put(pmap, key, value);
577  }
578
579} // namespace boost
580
581
582#endif // BOOST_GRAPH_LEDA_HPP