1 //=======================================================================
2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
3 // Copyright 2004 The Trustees of Indiana University.
4 // Copyright 2007 University of Karlsruhe
5 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Douglas Gregor,
8 // Distributed under the Boost Software License, Version 1.0. (See
9 // accompanying file LICENSE_1_0.txt or copy at
10 // http://www.boost.org/LICENSE_1_0.txt)
11 //=======================================================================
12 #ifndef BOOST_GRAPH_LEDA_HPP
13 #define BOOST_GRAPH_LEDA_HPP
15 #include <boost/config.hpp>
16 #include <boost/iterator/iterator_facade.hpp>
17 #include <boost/graph/graph_traits.hpp>
18 #include <boost/graph/properties.hpp>
20 #include <LEDA/graph/graph.h>
21 #include <LEDA/graph/node_array.h>
22 #include <LEDA/graph/node_map.h>
24 // The functions and classes in this file allows the user to
25 // treat a LEDA GRAPH object as a boost graph "as is". No
26 // wrapper is needed for the GRAPH object.
28 // Warning: this implementation relies on partial specialization
29 // for the graph_traits class (so it won't compile with Visual C++)
31 // Warning: this implementation is in alpha and has not been tested
35 struct leda_graph_traversal_category :
36 public virtual bidirectional_graph_tag,
37 public virtual adjacency_graph_tag,
38 public virtual vertex_list_graph_tag { };
40 template <class vtype, class etype>
41 struct graph_traits< leda::GRAPH<vtype,etype> > {
42 typedef leda::node vertex_descriptor;
43 typedef leda::edge edge_descriptor;
45 class adjacency_iterator
46 : public iterator_facade<adjacency_iterator,
48 bidirectional_traversal_tag,
53 adjacency_iterator(leda::node node = 0,
54 const leda::GRAPH<vtype, etype>* g = 0)
57 leda::node dereference() const { return leda::target(base); }
59 bool equal(const adjacency_iterator& other) const
60 { return base == other.base; }
62 void increment() { base = g->adj_succ(base); }
63 void decrement() { base = g->adj_pred(base); }
66 const leda::GRAPH<vtype, etype>* g;
68 friend class iterator_core_access;
71 class out_edge_iterator
72 : public iterator_facade<out_edge_iterator,
74 bidirectional_traversal_tag,
79 out_edge_iterator(leda::node node = 0,
80 const leda::GRAPH<vtype, etype>* g = 0)
84 const leda::edge& dereference() const { return base; }
86 bool equal(const out_edge_iterator& other) const
87 { return base == other.base; }
89 void increment() { base = g->adj_succ(base); }
90 void decrement() { base = g->adj_pred(base); }
93 const leda::GRAPH<vtype, etype>* g;
95 friend class iterator_core_access;
98 class in_edge_iterator
99 : public iterator_facade<in_edge_iterator,
101 bidirectional_traversal_tag,
106 in_edge_iterator(leda::node node = 0,
107 const leda::GRAPH<vtype, etype>* g = 0)
108 : base(node), g(g) {}
111 const leda::edge& dereference() const { return base; }
113 bool equal(const in_edge_iterator& other) const
114 { return base == other.base; }
116 void increment() { base = g->in_succ(base); }
117 void decrement() { base = g->in_pred(base); }
120 const leda::GRAPH<vtype, etype>* g;
122 friend class iterator_core_access;
125 class vertex_iterator
126 : public iterator_facade<vertex_iterator,
128 bidirectional_traversal_tag,
133 vertex_iterator(leda::node node = 0,
134 const leda::GRAPH<vtype, etype>* g = 0)
135 : base(node), g(g) {}
138 const leda::node& dereference() const { return base; }
140 bool equal(const vertex_iterator& other) const
141 { return base == other.base; }
143 void increment() { base = g->succ_node(base); }
144 void decrement() { base = g->pred_node(base); }
147 const leda::GRAPH<vtype, etype>* g;
149 friend class iterator_core_access;
153 : public iterator_facade<edge_iterator,
155 bidirectional_traversal_tag,
160 edge_iterator(leda::edge edge = 0,
161 const leda::GRAPH<vtype, etype>* g = 0)
162 : base(edge), g(g) {}
165 const leda::edge& dereference() const { return base; }
167 bool equal(const edge_iterator& other) const
168 { return base == other.base; }
170 void increment() { base = g->succ_edge(base); }
171 void decrement() { base = g->pred_edge(base); }
174 const leda::GRAPH<vtype, etype>* g;
176 friend class iterator_core_access;
179 typedef directed_tag directed_category;
180 typedef allow_parallel_edge_tag edge_parallel_category; // not sure here
181 typedef leda_graph_traversal_category traversal_category;
182 typedef int vertices_size_type;
183 typedef int edges_size_type;
184 typedef int degree_size_type;
190 struct graph_traits<leda::graph> {
191 typedef leda::node vertex_descriptor;
192 typedef leda::edge edge_descriptor;
194 class adjacency_iterator
195 : public iterator_facade<adjacency_iterator,
197 bidirectional_traversal_tag,
202 adjacency_iterator(leda::edge edge = 0,
203 const leda::graph* g = 0)
204 : base(edge), g(g) {}
207 leda::node dereference() const { return leda::target(base); }
209 bool equal(const adjacency_iterator& other) const
210 { return base == other.base; }
212 void increment() { base = g->adj_succ(base); }
213 void decrement() { base = g->adj_pred(base); }
216 const leda::graph* g;
218 friend class iterator_core_access;
221 class out_edge_iterator
222 : public iterator_facade<out_edge_iterator,
224 bidirectional_traversal_tag,
229 out_edge_iterator(leda::edge edge = 0,
230 const leda::graph* g = 0)
231 : base(edge), g(g) {}
234 const leda::edge& dereference() const { return base; }
236 bool equal(const out_edge_iterator& other) const
237 { return base == other.base; }
239 void increment() { base = g->adj_succ(base); }
240 void decrement() { base = g->adj_pred(base); }
243 const leda::graph* g;
245 friend class iterator_core_access;
248 class in_edge_iterator
249 : public iterator_facade<in_edge_iterator,
251 bidirectional_traversal_tag,
256 in_edge_iterator(leda::edge edge = 0,
257 const leda::graph* g = 0)
258 : base(edge), g(g) {}
261 const leda::edge& dereference() const { return base; }
263 bool equal(const in_edge_iterator& other) const
264 { return base == other.base; }
266 void increment() { base = g->in_succ(base); }
267 void decrement() { base = g->in_pred(base); }
270 const leda::graph* g;
272 friend class iterator_core_access;
275 class vertex_iterator
276 : public iterator_facade<vertex_iterator,
278 bidirectional_traversal_tag,
283 vertex_iterator(leda::node node = 0,
284 const leda::graph* g = 0)
285 : base(node), g(g) {}
288 const leda::node& dereference() const { return base; }
290 bool equal(const vertex_iterator& other) const
291 { return base == other.base; }
293 void increment() { base = g->succ_node(base); }
294 void decrement() { base = g->pred_node(base); }
297 const leda::graph* g;
299 friend class iterator_core_access;
303 : public iterator_facade<edge_iterator,
305 bidirectional_traversal_tag,
310 edge_iterator(leda::edge edge = 0,
311 const leda::graph* g = 0)
312 : base(edge), g(g) {}
315 const leda::edge& dereference() const { return base; }
317 bool equal(const edge_iterator& other) const
318 { return base == other.base; }
320 void increment() { base = g->succ_edge(base); }
321 void decrement() { base = g->pred_edge(base); }
324 const leda::graph* g;
326 friend class iterator_core_access;
329 typedef directed_tag directed_category;
330 typedef allow_parallel_edge_tag edge_parallel_category; // not sure here
331 typedef leda_graph_traversal_category traversal_category;
332 typedef int vertices_size_type;
333 typedef int edges_size_type;
334 typedef int degree_size_type;
341 //===========================================================================
342 // functions for GRAPH<vtype,etype>
344 template <class vtype, class etype>
345 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor
346 source(typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor e,
347 const leda::GRAPH<vtype,etype>& g)
352 template <class vtype, class etype>
353 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor
354 target(typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor e,
355 const leda::GRAPH<vtype,etype>& g)
360 template <class vtype, class etype>
362 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_iterator,
363 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_iterator >
364 vertices(const leda::GRAPH<vtype,etype>& g)
366 typedef typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_iterator
368 return std::make_pair( Iter(g.first_node(),&g), Iter(0,&g) );
371 template <class vtype, class etype>
373 typename graph_traits< leda::GRAPH<vtype,etype> >::edge_iterator,
374 typename graph_traits< leda::GRAPH<vtype,etype> >::edge_iterator >
375 edges(const leda::GRAPH<vtype,etype>& g)
377 typedef typename graph_traits< leda::GRAPH<vtype,etype> >::edge_iterator
379 return std::make_pair( Iter(g.first_edge(),&g), Iter(0,&g) );
382 template <class vtype, class etype>
384 typename graph_traits< leda::GRAPH<vtype,etype> >::out_edge_iterator,
385 typename graph_traits< leda::GRAPH<vtype,etype> >::out_edge_iterator >
387 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
388 const leda::GRAPH<vtype,etype>& g)
390 typedef typename graph_traits< leda::GRAPH<vtype,etype> >
391 ::out_edge_iterator Iter;
392 return std::make_pair( Iter(g.first_adj_edge(u,0),&g), Iter(0,&g) );
395 template <class vtype, class etype>
397 typename graph_traits< leda::GRAPH<vtype,etype> >::in_edge_iterator,
398 typename graph_traits< leda::GRAPH<vtype,etype> >::in_edge_iterator >
400 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
401 const leda::GRAPH<vtype,etype>& g)
403 typedef typename graph_traits< leda::GRAPH<vtype,etype> >
404 ::in_edge_iterator Iter;
405 return std::make_pair( Iter(g.first_adj_edge(u,1),&g), Iter(0,&g) );
408 template <class vtype, class etype>
410 typename graph_traits< leda::GRAPH<vtype,etype> >::adjacency_iterator,
411 typename graph_traits< leda::GRAPH<vtype,etype> >::adjacency_iterator >
413 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
414 const leda::GRAPH<vtype,etype>& g)
416 typedef typename graph_traits< leda::GRAPH<vtype,etype> >
417 ::adjacency_iterator Iter;
418 return std::make_pair( Iter(g.first_adj_edge(u,0),&g), Iter(0,&g) );
421 template <class vtype, class etype>
422 typename graph_traits< leda::GRAPH<vtype,etype> >::vertices_size_type
423 num_vertices(const leda::GRAPH<vtype,etype>& g)
425 return g.number_of_nodes();
428 template <class vtype, class etype>
429 typename graph_traits< leda::GRAPH<vtype,etype> >::edges_size_type
430 num_edges(const leda::GRAPH<vtype,etype>& g)
432 return g.number_of_edges();
435 template <class vtype, class etype>
436 typename graph_traits< leda::GRAPH<vtype,etype> >::degree_size_type
438 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
439 const leda::GRAPH<vtype,etype>& g)
444 template <class vtype, class etype>
445 typename graph_traits< leda::GRAPH<vtype,etype> >::degree_size_type
447 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
448 const leda::GRAPH<vtype,etype>& g)
453 template <class vtype, class etype>
454 typename graph_traits< leda::GRAPH<vtype,etype> >::degree_size_type
456 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
457 const leda::GRAPH<vtype,etype>& g)
459 return g.outdeg(u) + g.indeg(u);
462 template <class vtype, class etype>
463 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor
464 add_vertex(leda::GRAPH<vtype,etype>& g)
469 template <class vtype, class etype>
470 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor
471 add_vertex(const vtype& vp, leda::GRAPH<vtype,etype>& g)
473 return g.new_node(vp);
476 template <class vtype, class etype>
478 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
479 leda::GRAPH<vtype,etype>& g)
481 typename graph_traits< leda::GRAPH<vtype,etype> >::out_edge_iterator ei, ei_end;
482 for (boost::tie(ei, ei_end)=out_edges(u,g); ei!=ei_end; ei++)
485 typename graph_traits< leda::GRAPH<vtype,etype> >::in_edge_iterator iei, iei_end;
486 for (boost::tie(iei, iei_end)=in_edges(u,g); iei!=iei_end; iei++)
490 template <class vtype, class etype>
492 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
493 leda::GRAPH<vtype,etype>& g)
498 template <class vtype, class etype>
500 typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor,
503 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
504 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor v,
505 leda::GRAPH<vtype,etype>& g)
507 return std::make_pair(g.new_edge(u, v), true);
510 template <class vtype, class etype>
512 typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor,
515 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
516 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor v,
518 leda::GRAPH<vtype,etype>& g)
520 return std::make_pair(g.new_edge(u, v, et), true);
523 template <class vtype, class etype>
526 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u,
527 typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor v,
528 leda::GRAPH<vtype,etype>& g)
530 typename graph_traits< leda::GRAPH<vtype,etype> >::out_edge_iterator
532 for (boost::tie(i,iend) = out_edges(u,g); i != iend; ++i)
533 if (target(*i,g) == v)
537 template <class vtype, class etype>
540 typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor e,
541 leda::GRAPH<vtype,etype>& g)
546 //===========================================================================
547 // functions for graph (non-templated version)
549 graph_traits<leda::graph>::vertex_descriptor
550 source(graph_traits<leda::graph>::edge_descriptor e,
551 const leda::graph& g)
556 graph_traits<leda::graph>::vertex_descriptor
557 target(graph_traits<leda::graph>::edge_descriptor e,
558 const leda::graph& g)
564 graph_traits<leda::graph>::vertex_iterator,
565 graph_traits<leda::graph>::vertex_iterator >
566 vertices(const leda::graph& g)
568 typedef graph_traits<leda::graph>::vertex_iterator
570 return std::make_pair( Iter(g.first_node(),&g), Iter(0,&g) );
574 graph_traits<leda::graph>::edge_iterator,
575 graph_traits<leda::graph>::edge_iterator >
576 edges(const leda::graph& g)
578 typedef graph_traits<leda::graph>::edge_iterator
580 return std::make_pair( Iter(g.first_edge(),&g), Iter(0,&g) );
584 graph_traits<leda::graph>::out_edge_iterator,
585 graph_traits<leda::graph>::out_edge_iterator >
587 graph_traits<leda::graph>::vertex_descriptor u, const leda::graph& g)
589 typedef graph_traits<leda::graph>::out_edge_iterator Iter;
590 return std::make_pair( Iter(g.first_adj_edge(u),&g), Iter(0,&g) );
594 graph_traits<leda::graph>::in_edge_iterator,
595 graph_traits<leda::graph>::in_edge_iterator >
597 graph_traits<leda::graph>::vertex_descriptor u,
598 const leda::graph& g)
600 typedef graph_traits<leda::graph>
601 ::in_edge_iterator Iter;
602 return std::make_pair( Iter(g.first_in_edge(u),&g), Iter(0,&g) );
606 graph_traits<leda::graph>::adjacency_iterator,
607 graph_traits<leda::graph>::adjacency_iterator >
609 graph_traits<leda::graph>::vertex_descriptor u,
610 const leda::graph& g)
612 typedef graph_traits<leda::graph>
613 ::adjacency_iterator Iter;
614 return std::make_pair( Iter(g.first_adj_edge(u),&g), Iter(0,&g) );
617 graph_traits<leda::graph>::vertices_size_type
618 num_vertices(const leda::graph& g)
620 return g.number_of_nodes();
623 graph_traits<leda::graph>::edges_size_type
624 num_edges(const leda::graph& g)
626 return g.number_of_edges();
629 graph_traits<leda::graph>::degree_size_type
631 graph_traits<leda::graph>::vertex_descriptor u,
632 const leda::graph& g)
637 graph_traits<leda::graph>::degree_size_type
639 graph_traits<leda::graph>::vertex_descriptor u,
640 const leda::graph& g)
645 graph_traits<leda::graph>::degree_size_type
647 graph_traits<leda::graph>::vertex_descriptor u,
648 const leda::graph& g)
650 return g.outdeg(u) + g.indeg(u);
653 graph_traits<leda::graph>::vertex_descriptor
654 add_vertex(leda::graph& g)
661 graph_traits<leda::graph>::vertex_descriptor u,
662 graph_traits<leda::graph>::vertex_descriptor v,
665 graph_traits<leda::graph>::out_edge_iterator
667 for (boost::tie(i,iend) = out_edges(u,g); i != iend; ++i)
668 if (target(*i,g) == v)
674 graph_traits<leda::graph>::edge_descriptor e,
681 graph_traits<leda::graph>::vertex_descriptor u,
684 graph_traits<leda::graph>::out_edge_iterator ei, ei_end;
685 for (boost::tie(ei, ei_end)=out_edges(u,g); ei!=ei_end; ei++)
688 graph_traits<leda::graph>::in_edge_iterator iei, iei_end;
689 for (boost::tie(iei, iei_end)=in_edges(u,g); iei!=iei_end; iei++)
690 remove_edge(*iei, g);
694 graph_traits<leda::graph>::vertex_descriptor u,
701 graph_traits<leda::graph>::edge_descriptor,
704 graph_traits<leda::graph>::vertex_descriptor u,
705 graph_traits<leda::graph>::vertex_descriptor v,
708 return std::make_pair(g.new_edge(u, v), true);
712 //===========================================================================
713 // property maps for GRAPH<vtype,etype>
715 class leda_graph_id_map
716 : public put_get_helper<int, leda_graph_id_map>
719 typedef readable_property_map_tag category;
720 typedef int value_type;
721 typedef int reference;
722 typedef leda::node key_type;
723 leda_graph_id_map() { }
725 long operator[](T x) const { return x->id(); }
727 template <class vtype, class etype>
728 inline leda_graph_id_map
729 get(vertex_index_t, const leda::GRAPH<vtype, etype>& g) {
730 return leda_graph_id_map();
732 template <class vtype, class etype>
733 inline leda_graph_id_map
734 get(edge_index_t, const leda::GRAPH<vtype, etype>& g) {
735 return leda_graph_id_map();
739 struct leda_property_map { };
742 struct leda_property_map<vertex_index_t> {
743 template <class vtype, class etype>
745 typedef leda_graph_id_map type;
746 typedef leda_graph_id_map const_type;
750 struct leda_property_map<edge_index_t> {
751 template <class vtype, class etype>
753 typedef leda_graph_id_map type;
754 typedef leda_graph_id_map const_type;
759 template <class Data, class DataRef, class GraphPtr>
760 class leda_graph_data_map
761 : public put_get_helper<DataRef,
762 leda_graph_data_map<Data,DataRef,GraphPtr> >
765 typedef Data value_type;
766 typedef DataRef reference;
767 typedef void key_type;
768 typedef lvalue_property_map_tag category;
769 leda_graph_data_map(GraphPtr g) : m_g(g) { }
770 template <class NodeOrEdge>
771 DataRef operator[](NodeOrEdge x) const { return (*m_g)[x]; }
777 struct leda_property_map<vertex_all_t> {
778 template <class vtype, class etype>
780 typedef leda_graph_data_map<vtype, vtype&, leda::GRAPH<vtype, etype>*> type;
781 typedef leda_graph_data_map<vtype, const vtype&,
782 const leda::GRAPH<vtype, etype>*> const_type;
785 template <class vtype, class etype >
786 inline typename property_map< leda::GRAPH<vtype, etype>, vertex_all_t>::type
787 get(vertex_all_t, leda::GRAPH<vtype, etype>& g) {
788 typedef typename property_map< leda::GRAPH<vtype, etype>, vertex_all_t>::type
790 return pmap_type(&g);
792 template <class vtype, class etype >
793 inline typename property_map< leda::GRAPH<vtype, etype>, vertex_all_t>::const_type
794 get(vertex_all_t, const leda::GRAPH<vtype, etype>& g) {
795 typedef typename property_map< leda::GRAPH<vtype, etype>,
796 vertex_all_t>::const_type pmap_type;
797 return pmap_type(&g);
801 struct leda_property_map<edge_all_t> {
802 template <class vtype, class etype>
804 typedef leda_graph_data_map<etype, etype&, leda::GRAPH<vtype, etype>*> type;
805 typedef leda_graph_data_map<etype, const etype&,
806 const leda::GRAPH<vtype, etype>*> const_type;
809 template <class vtype, class etype >
810 inline typename property_map< leda::GRAPH<vtype, etype>, edge_all_t>::type
811 get(edge_all_t, leda::GRAPH<vtype, etype>& g) {
812 typedef typename property_map< leda::GRAPH<vtype, etype>, edge_all_t>::type
814 return pmap_type(&g);
816 template <class vtype, class etype >
817 inline typename property_map< leda::GRAPH<vtype, etype>, edge_all_t>::const_type
818 get(edge_all_t, const leda::GRAPH<vtype, etype>& g) {
819 typedef typename property_map< leda::GRAPH<vtype, etype>,
820 edge_all_t>::const_type pmap_type;
821 return pmap_type(&g);
824 // property map interface to the LEDA node_array class
826 template <class E, class ERef, class NodeMapPtr>
827 class leda_node_property_map
828 : public put_get_helper<ERef, leda_node_property_map<E, ERef, NodeMapPtr> >
831 typedef E value_type;
832 typedef ERef reference;
833 typedef leda::node key_type;
834 typedef lvalue_property_map_tag category;
835 leda_node_property_map(NodeMapPtr a) : m_array(a) { }
836 ERef operator[](leda::node n) const { return (*m_array)[n]; }
841 leda_node_property_map<E, const E&, const leda::node_array<E>*>
842 make_leda_node_property_map(const leda::node_array<E>& a)
844 typedef leda_node_property_map<E, const E&, const leda::node_array<E>*>
846 return pmap_type(&a);
849 leda_node_property_map<E, E&, leda::node_array<E>*>
850 make_leda_node_property_map(leda::node_array<E>& a)
852 typedef leda_node_property_map<E, E&, leda::node_array<E>*> pmap_type;
853 return pmap_type(&a);
857 leda_node_property_map<E, const E&, const leda::node_map<E>*>
858 make_leda_node_property_map(const leda::node_map<E>& a)
860 typedef leda_node_property_map<E,const E&,const leda::node_map<E>*>
862 return pmap_type(&a);
865 leda_node_property_map<E, E&, leda::node_map<E>*>
866 make_leda_node_property_map(leda::node_map<E>& a)
868 typedef leda_node_property_map<E, E&, leda::node_map<E>*> pmap_type;
869 return pmap_type(&a);
872 // g++ 'enumeral_type' in template unification not implemented workaround
873 template <class vtype, class etype, class Tag>
874 struct property_map<leda::GRAPH<vtype, etype>, Tag> {
876 leda_property_map<Tag>::template bind_<vtype, etype> map_gen;
877 typedef typename map_gen::type type;
878 typedef typename map_gen::const_type const_type;
881 template <class vtype, class etype, class PropertyTag, class Key>
883 typename boost::property_traits<
884 typename boost::property_map<leda::GRAPH<vtype, etype>,PropertyTag>::const_type
886 get(PropertyTag p, const leda::GRAPH<vtype, etype>& g, const Key& key) {
887 return get(get(p, g), key);
890 template <class vtype, class etype, class PropertyTag, class Key,class Value>
892 put(PropertyTag p, leda::GRAPH<vtype, etype>& g,
893 const Key& key, const Value& value)
895 typedef typename property_map<leda::GRAPH<vtype, etype>, PropertyTag>::type Map;
896 Map pmap = get(p, g);
897 put(pmap, key, value);
900 // property map interface to the LEDA edge_array class
902 template <class E, class ERef, class EdgeMapPtr>
903 class leda_edge_property_map
904 : public put_get_helper<ERef, leda_edge_property_map<E, ERef, EdgeMapPtr> >
907 typedef E value_type;
908 typedef ERef reference;
909 typedef leda::edge key_type;
910 typedef lvalue_property_map_tag category;
911 leda_edge_property_map(EdgeMapPtr a) : m_array(a) { }
912 ERef operator[](leda::edge n) const { return (*m_array)[n]; }
917 leda_edge_property_map<E, const E&, const leda::edge_array<E>*>
918 make_leda_node_property_map(const leda::node_array<E>& a)
920 typedef leda_edge_property_map<E, const E&, const leda::node_array<E>*>
922 return pmap_type(&a);
925 leda_edge_property_map<E, E&, leda::edge_array<E>*>
926 make_leda_edge_property_map(leda::edge_array<E>& a)
928 typedef leda_edge_property_map<E, E&, leda::edge_array<E>*> pmap_type;
929 return pmap_type(&a);
933 leda_edge_property_map<E, const E&, const leda::edge_map<E>*>
934 make_leda_edge_property_map(const leda::edge_map<E>& a)
936 typedef leda_edge_property_map<E,const E&,const leda::edge_map<E>*>
938 return pmap_type(&a);
941 leda_edge_property_map<E, E&, leda::edge_map<E>*>
942 make_leda_edge_property_map(leda::edge_map<E>& a)
944 typedef leda_edge_property_map<E, E&, leda::edge_map<E>*> pmap_type;
945 return pmap_type(&a);
950 #endif // BOOST_GRAPH_LEDA_HPP