Hi all, I looked at the leda_graph.hpp and made the following changes: * property map interface to the LEDA edge_array class nearly 1:1 copy of node_array stuff * adapter for non-templated 'graph' class added nearly 1:1 copy of code for GRAPH<vtype,etype> * fixed access functions (outside iterator code) to use member functions of the graph/GRAPH class see http://www.algorithmic-solutions.info/leda_manual/graph.html * replaced leda_something by leda::something (node, edge) * make iterators use 'public' LEDA interfaces see http://www.algorithmic-solutions.info/leda_manual/graph.html * implemented clear_vertex * implemented EdgeListGraph concept * edge_iterator class * edges function Still have to test them, though, and clarify copyright stuff with my boss. I have one question about leda_graph_id_map: Is the id() member function for nodes (and edges) officially defined somewhere? Jens
Jens Müller wrote:
Hi all,
I looked at the leda_graph.hpp and made the following changes:
* property map interface to the LEDA edge_array class nearly 1:1 copy of node_array stuff * adapter for non-templated 'graph' class added nearly 1:1 copy of code for GRAPH<vtype,etype> * fixed access functions (outside iterator code) to use member functions of the graph/GRAPH class see http://www.algorithmic-solutions.info/leda_manual/graph.html * replaced leda_something by leda::something (node, edge) * make iterators use 'public' LEDA interfaces see http://www.algorithmic-solutions.info/leda_manual/graph.html * implemented clear_vertex * implemented EdgeListGraph concept * edge_iterator class * edges function
Still have to test them, though, and clarify copyright stuff with my boss.
OK, seems to be no problem submitting the code under Boost Software License. Here is the file, works fine for me so far, but I have not actually USED all parts. The comments at the beginning will of course have to be removed ... Btw: It seems to have become slower, but that could be the daily mood of my computer here ;-) I have no time to compile with the old headers atm, but will try later. /* TODO: * Are id maps really available for all kinds of LEDA graphs? What is the id() member function there? Where is it documented? CHANGES: * property map interface to the LEDA edge_array class nearly 1:1 copy of node_array stuff * adapter for non-templated 'graph' class added nearly 1:1 copy of code for GRAPH<vtype,etype> * fixed access functions (outside iterator code) to use member functions of the graph/GRAPH class see http://www.algorithmic-solutions.info/leda_manual/graph.html * replaced leda_something by leda::something * make iterators use 'public' LEDA interfaces see http://www.algorithmic-solutions.info/leda_manual/graph.html * implemented clear_vertex * implemented EdgeListGraph concept * edge_iterator class * edges function -> please add to documentation */ //======================================================================= // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. // Copyright 2004 The Trustees of Indiana University. // Copyright 2007 University of Karlsruhe // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Douglas Gregor, // Jens Mueller // // Distributed under the Boost Software License, Version 1.0. (See // accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) //======================================================================= #ifndef BOOST_GRAPH_LEDA_HPP #define BOOST_GRAPH_LEDA_HPP #include <boost/config.hpp> #include <boost/iterator/iterator_facade.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/graph/properties.hpp> #include <LEDA/graph.h> #include <LEDA/node_array.h> #include <LEDA/node_map.h> // The functions and classes in this file allows the user to // treat a LEDA GRAPH object as a boost graph "as is". No // wrapper is needed for the GRAPH object. // Warning: this implementation relies on partial specialization // for the graph_traits class (so it won't compile with Visual C++) // Warning: this implementation is in alpha and has not been tested #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION namespace boost { struct leda_graph_traversal_category : public virtual bidirectional_graph_tag, public virtual adjacency_graph_tag, public virtual vertex_list_graph_tag { }; template <class vtype, class etype> struct graph_traits< leda::GRAPH<vtype,etype> > { typedef leda::node vertex_descriptor; typedef leda::edge edge_descriptor; class adjacency_iterator : public iterator_facade<adjacency_iterator, leda::node, bidirectional_traversal_tag, leda::node, const leda::node*> { public: adjacency_iterator(leda::node node = 0, const leda::GRAPH<vtype, etype>* g = 0) : base(node), g(g) {} private: leda::node dereference() const { return leda::target(base); } bool equal(const adjacency_iterator& other) const { return base == other.base; } void increment() { base = g->adj_succ(base); } void decrement() { base = g->adj_pred(base); } leda::edge base; const leda::GRAPH<vtype, etype>* g; friend class iterator_core_access; }; class out_edge_iterator : public iterator_facade<out_edge_iterator, leda::edge, bidirectional_traversal_tag, const leda::edge&, const leda::edge*> { public: out_edge_iterator(leda::node node = 0, const leda::GRAPH<vtype, etype>* g = 0) : base(node), g(g) {} private: const leda::edge& dereference() const { return base; } bool equal(const out_edge_iterator& other) const { return base == other.base; } void increment() { base = g->adj_succ(base); } void decrement() { base = g->adj_pred(base); } leda::edge base; const leda::GRAPH<vtype, etype>* g; friend class iterator_core_access; }; class in_edge_iterator : public iterator_facade<in_edge_iterator, leda::edge, bidirectional_traversal_tag, const leda::edge&, const leda::edge*> { public: in_edge_iterator(leda::node node = 0, const leda::GRAPH<vtype, etype>* g = 0) : base(node), g(g) {} private: const leda::edge& dereference() const { return base; } bool equal(const in_edge_iterator& other) const { return base == other.base; } void increment() { base = g->in_succ(base); } void decrement() { base = g->in_pred(base); } leda::edge base; const leda::GRAPH<vtype, etype>* g; friend class iterator_core_access; }; class vertex_iterator : public iterator_facade<vertex_iterator, leda::node, bidirectional_traversal_tag, const leda::node&, const leda::node*> { public: vertex_iterator(leda::node node = 0, const leda::GRAPH<vtype, etype>* g = 0) : base(node), g(g) {} private: const leda::node& dereference() const { return base; } bool equal(const vertex_iterator& other) const { return base == other.base; } void increment() { base = g->succ_node(base); } void decrement() { base = g->pred_node(base); } leda::node base; const leda::GRAPH<vtype, etype>* g; friend class iterator_core_access; }; class edge_iterator : public iterator_facade<edge_iterator, leda::edge, bidirectional_traversal_tag, const leda::edge&, const leda::edge*> { public: edge_iterator(leda::edge edge = 0, const leda::GRAPH<vtype, etype>* g = 0) : base(edge), g(g) {} private: const leda::edge& dereference() const { return base; } bool equal(const edge_iterator& other) const { return base == other.base; } void increment() { base = g->succ_edge(base); } void decrement() { base = g->pred_edge(base); } leda::node base; const leda::GRAPH<vtype, etype>* g; friend class iterator_core_access; }; typedef directed_tag directed_category; typedef allow_parallel_edge_tag edge_parallel_category; // not sure here typedef leda_graph_traversal_category traversal_category; typedef int vertices_size_type; typedef int edges_size_type; typedef int degree_size_type; }; template<> struct graph_traits<leda::graph> { typedef leda::node vertex_descriptor; typedef leda::edge edge_descriptor; class adjacency_iterator : public iterator_facade<adjacency_iterator, leda::node, bidirectional_traversal_tag, leda::node, const leda::node*> { public: adjacency_iterator(leda::edge edge = 0, const leda::graph* g = 0) : base(edge), g(g) {} private: leda::node dereference() const { return leda::target(base); } bool equal(const adjacency_iterator& other) const { return base == other.base; } void increment() { base = g->adj_succ(base); } void decrement() { base = g->adj_pred(base); } leda::edge base; const leda::graph* g; friend class iterator_core_access; }; class out_edge_iterator : public iterator_facade<out_edge_iterator, leda::edge, bidirectional_traversal_tag, const leda::edge&, const leda::edge*> { public: out_edge_iterator(leda::edge edge = 0, const leda::graph* g = 0) : base(edge), g(g) {} private: const leda::edge& dereference() const { return base; } bool equal(const out_edge_iterator& other) const { return base == other.base; } void increment() { base = g->adj_succ(base); } void decrement() { base = g->adj_pred(base); } leda::edge base; const leda::graph* g; friend class iterator_core_access; }; class in_edge_iterator : public iterator_facade<in_edge_iterator, leda::edge, bidirectional_traversal_tag, const leda::edge&, const leda::edge*> { public: in_edge_iterator(leda::edge edge = 0, const leda::graph* g = 0) : base(edge), g(g) {} private: const leda::edge& dereference() const { return base; } bool equal(const in_edge_iterator& other) const { return base == other.base; } void increment() { base = g->in_succ(base); } void decrement() { base = g->in_pred(base); } leda::edge base; const leda::graph* g; friend class iterator_core_access; }; class vertex_iterator : public iterator_facade<vertex_iterator, leda::node, bidirectional_traversal_tag, const leda::node&, const leda::node*> { public: vertex_iterator(leda::node node = 0, const leda::graph* g = 0) : base(node), g(g) {} private: const leda::node& dereference() const { return base; } bool equal(const vertex_iterator& other) const { return base == other.base; } void increment() { base = g->succ_node(base); } void decrement() { base = g->pred_node(base); } leda::node base; const leda::graph* g; friend class iterator_core_access; }; class edge_iterator : public iterator_facade<edge_iterator, leda::edge, bidirectional_traversal_tag, const leda::edge&, const leda::edge*> { public: edge_iterator(leda::edge edge = 0, const leda::graph* g = 0) : base(edge), g(g) {} private: const leda::edge& dereference() const { return base; } bool equal(const edge_iterator& other) const { return base == other.base; } void increment() { base = g->succ_edge(base); } void decrement() { base = g->pred_edge(base); } leda::edge base; const leda::graph* g; friend class iterator_core_access; }; typedef directed_tag directed_category; typedef allow_parallel_edge_tag edge_parallel_category; // not sure here typedef leda_graph_traversal_category traversal_category; typedef int vertices_size_type; typedef int edges_size_type; typedef int degree_size_type; }; } // namespace boost #endif namespace boost { //=========================================================================== // functions for GRAPH<vtype,etype> template <class vtype, class etype> typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor source(typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor e, const leda::GRAPH<vtype,etype>& g) { return source(e); } template <class vtype, class etype> typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor target(typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor e, const leda::GRAPH<vtype,etype>& g) { return target(e); } template <class vtype, class etype> inline std::pair< typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_iterator, typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_iterator > vertices(const leda::GRAPH<vtype,etype>& g) { typedef typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_iterator Iter; return std::make_pair( Iter(g.first_node(),&g), Iter(0,&g) ); } template <class vtype, class etype> inline std::pair< typename graph_traits< leda::GRAPH<vtype,etype> >::edge_iterator, typename graph_traits< leda::GRAPH<vtype,etype> >::edge_iterator > edges(const leda::GRAPH<vtype,etype>& g) { typedef typename graph_traits< leda::GRAPH<vtype,etype> >::edge_iterator Iter; return std::make_pair( Iter(g.first_edge(),&g), Iter(0,&g) ); } template <class vtype, class etype> inline std::pair< typename graph_traits< leda::GRAPH<vtype,etype> >::out_edge_iterator, typename graph_traits< leda::GRAPH<vtype,etype> >::out_edge_iterator > out_edges( typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u, const leda::GRAPH<vtype,etype>& g) { typedef typename graph_traits< leda::GRAPH<vtype,etype> > ::out_edge_iterator Iter; return std::make_pair( Iter(g.first_adj_edge(u,0),&g), Iter(0,&g) ); } template <class vtype, class etype> inline std::pair< typename graph_traits< leda::GRAPH<vtype,etype> >::in_edge_iterator, typename graph_traits< leda::GRAPH<vtype,etype> >::in_edge_iterator > in_edges( typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u, const leda::GRAPH<vtype,etype>& g) { typedef typename graph_traits< leda::GRAPH<vtype,etype> > ::in_edge_iterator Iter; return std::make_pair( Iter(g.first_adj_edge(u,1),&g), Iter(0,&g) ); } template <class vtype, class etype> inline std::pair< typename graph_traits< leda::GRAPH<vtype,etype> >::adjacency_iterator, typename graph_traits< leda::GRAPH<vtype,etype> >::adjacency_iterator > adjacent_vertices( typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u, const leda::GRAPH<vtype,etype>& g) { typedef typename graph_traits< leda::GRAPH<vtype,etype> > ::adjacency_iterator Iter; return std::make_pair( Iter(g.first_adj_edge(u,0),&g), Iter(0,&g) ); } template <class vtype, class etype> typename graph_traits< leda::GRAPH<vtype,etype> >::vertices_size_type num_vertices(const leda::GRAPH<vtype,etype>& g) { return g.number_of_nodes(); } template <class vtype, class etype> typename graph_traits< leda::GRAPH<vtype,etype> >::edges_size_type num_edges(const leda::GRAPH<vtype,etype>& g) { return g.number_of_edges(); } template <class vtype, class etype> typename graph_traits< leda::GRAPH<vtype,etype> >::degree_size_type out_degree( typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u, const leda::GRAPH<vtype,etype>& g) { return g.outdeg(u); } template <class vtype, class etype> typename graph_traits< leda::GRAPH<vtype,etype> >::degree_size_type in_degree( typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u, const leda::GRAPH<vtype,etype>& g) { return g.indeg(u); } template <class vtype, class etype> typename graph_traits< leda::GRAPH<vtype,etype> >::degree_size_type degree( typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u, const leda::GRAPH<vtype,etype>& g) { return g.outdeg(u) + g.indeg(u); } template <class vtype, class etype> typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor add_vertex(leda::GRAPH<vtype,etype>& g) { return g.new_node(); } template <class vtype, class etype> typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor add_vertex(const vtype& vp, leda::GRAPH<vtype,etype>& g) { return g.new_node(vp); } template <class vtype, class etype> void clear_vertex( typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u, leda::GRAPH<vtype,etype>& g) { typename graph_traits< leda::GRAPH<vtype,etype> >::out_edge_iterator ei, ei_end; for (tie(ei, ei_end)=out_edges(u,g); ei!=ei_end; ei++) remove_edge(*ei); typename graph_traits< leda::GRAPH<vtype,etype> >::in_edge_iterator iei, iei_end; for (tie(iei, iei_end)=in_edges(u,g); iei!=iei_end; iei++) remove_edge(*iei); } template <class vtype, class etype> void remove_vertex( typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u, leda::GRAPH<vtype,etype>& g) { g.del_node(u); } template <class vtype, class etype> std::pair< typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor, bool> add_edge( typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u, typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor v, leda::GRAPH<vtype,etype>& g) { return std::make_pair(g.new_edge(u, v), true); } template <class vtype, class etype> std::pair< typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor, bool> add_edge( typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u, typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor v, const etype& et, leda::GRAPH<vtype,etype>& g) { return std::make_pair(g.new_edge(u, v, et), true); } template <class vtype, class etype> void remove_edge( typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u, typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor v, leda::GRAPH<vtype,etype>& g) { typename graph_traits< leda::GRAPH<vtype,etype> >::out_edge_iterator i,iend; for (boost::tie(i,iend) = out_edges(u,g); i != iend; ++i) if (target(*i,g) == v) g.del_edge(*i); } template <class vtype, class etype> void remove_edge( typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor e, leda::GRAPH<vtype,etype>& g) { g.del_edge(e); } //=========================================================================== // functions for graph (non-templated version) graph_traits<leda::graph>::vertex_descriptor source(graph_traits<leda::graph>::edge_descriptor e, const leda::graph& g) { return source(e); } graph_traits<leda::graph>::vertex_descriptor target(graph_traits<leda::graph>::edge_descriptor e, const leda::graph& g) { return target(e); } inline std::pair< graph_traits<leda::graph>::vertex_iterator, graph_traits<leda::graph>::vertex_iterator > vertices(const leda::graph& g) { typedef graph_traits<leda::graph>::vertex_iterator Iter; return std::make_pair( Iter(g.first_node(),&g), Iter(0,&g) ); } inline std::pair< graph_traits<leda::graph>::edge_iterator, graph_traits<leda::graph>::edge_iterator > edges(const leda::graph& g) { typedef graph_traits<leda::graph>::edge_iterator Iter; return std::make_pair( Iter(g.first_edge(),&g), Iter(0,&g) ); } inline std::pair< graph_traits<leda::graph>::out_edge_iterator, graph_traits<leda::graph>::out_edge_iterator > out_edges( graph_traits<leda::graph>::vertex_descriptor u, const leda::graph& g) { typedef graph_traits<leda::graph>::out_edge_iterator Iter; return std::make_pair( Iter(g.first_adj_edge(u),&g), Iter(0,&g) ); } inline std::pair< graph_traits<leda::graph>::in_edge_iterator, graph_traits<leda::graph>::in_edge_iterator > in_edges( graph_traits<leda::graph>::vertex_descriptor u, const leda::graph& g) { typedef graph_traits<leda::graph> ::in_edge_iterator Iter; return std::make_pair( Iter(g.first_in_edge(u),&g), Iter(0,&g) ); } inline std::pair< graph_traits<leda::graph>::adjacency_iterator, graph_traits<leda::graph>::adjacency_iterator > adjacent_vertices( graph_traits<leda::graph>::vertex_descriptor u, const leda::graph& g) { typedef graph_traits<leda::graph> ::adjacency_iterator Iter; return std::make_pair( Iter(g.first_adj_edge(u),&g), Iter(0,&g) ); } graph_traits<leda::graph>::vertices_size_type num_vertices(const leda::graph& g) { return g.number_of_nodes(); } graph_traits<leda::graph>::edges_size_type num_edges(const leda::graph& g) { return g.number_of_edges(); } graph_traits<leda::graph>::degree_size_type out_degree( graph_traits<leda::graph>::vertex_descriptor u, const leda::graph& g) { return g.outdeg(u); } graph_traits<leda::graph>::degree_size_type in_degree( graph_traits<leda::graph>::vertex_descriptor u, const leda::graph& g) { return g.indeg(u); } graph_traits<leda::graph>::degree_size_type degree( graph_traits<leda::graph>::vertex_descriptor u, const leda::graph& g) { return g.outdeg(u) + g.indeg(u); } graph_traits<leda::graph>::vertex_descriptor add_vertex(leda::graph& g) { return g.new_node(); } void remove_edge( graph_traits<leda::graph>::vertex_descriptor u, graph_traits<leda::graph>::vertex_descriptor v, leda::graph& g) { graph_traits<leda::graph>::out_edge_iterator i,iend; for (boost::tie(i,iend) = out_edges(u,g); i != iend; ++i) if (target(*i,g) == v) g.del_edge(*i); } void remove_edge( graph_traits<leda::graph>::edge_descriptor e, leda::graph& g) { g.del_edge(e); } void clear_vertex( graph_traits<leda::graph>::vertex_descriptor u, leda::graph& g) { graph_traits<leda::graph>::out_edge_iterator ei, ei_end; for (tie(ei, ei_end)=out_edges(u,g); ei!=ei_end; ei++) remove_edge(*ei, g); graph_traits<leda::graph>::in_edge_iterator iei, iei_end; for (tie(iei, iei_end)=in_edges(u,g); iei!=iei_end; iei++) remove_edge(*iei, g); } void remove_vertex( graph_traits<leda::graph>::vertex_descriptor u, leda::graph& g) { g.del_node(u); } std::pair< graph_traits<leda::graph>::edge_descriptor, bool> add_edge( graph_traits<leda::graph>::vertex_descriptor u, graph_traits<leda::graph>::vertex_descriptor v, leda::graph& g) { return std::make_pair(g.new_edge(u, v), true); } //=========================================================================== // property maps for GRAPH<vtype,etype> class leda_graph_id_map : public put_get_helper<int, leda_graph_id_map> { public: typedef readable_property_map_tag category; typedef int value_type; typedef int reference; typedef leda::node key_type; leda_graph_id_map() { } template <class T> long operator[](T x) const { return x->id(); } }; template <class vtype, class etype> inline leda_graph_id_map get(vertex_index_t, const leda::GRAPH<vtype, etype>& g) { return leda_graph_id_map(); } template <class vtype, class etype> inline leda_graph_id_map get(edge_index_t, const leda::GRAPH<vtype, etype>& g) { return leda_graph_id_map(); } template <class Tag> struct leda_property_map { }; template <> struct leda_property_map<vertex_index_t> { template <class vtype, class etype> struct bind_ { typedef leda_graph_id_map type; typedef leda_graph_id_map const_type; }; }; template <> struct leda_property_map<edge_index_t> { template <class vtype, class etype> struct bind_ { typedef leda_graph_id_map type; typedef leda_graph_id_map const_type; }; }; template <class Data, class DataRef, class GraphPtr> class leda_graph_data_map : public put_get_helper<DataRef, leda_graph_data_map<Data,DataRef,GraphPtr> > { public: typedef Data value_type; typedef DataRef reference; typedef void key_type; typedef lvalue_property_map_tag category; leda_graph_data_map(GraphPtr g) : m_g(g) { } template <class NodeOrEdge> DataRef operator[](NodeOrEdge x) const { return (*m_g)[x]; } protected: GraphPtr m_g; }; template <> struct leda_property_map<vertex_all_t> { template <class vtype, class etype> struct bind_ { typedef leda_graph_data_map<vtype, vtype&, leda::GRAPH<vtype, etype>*> type; typedef leda_graph_data_map<vtype, const vtype&, const leda::GRAPH<vtype, etype>*> const_type; }; }; template <class vtype, class etype > inline typename property_map< leda::GRAPH<vtype, etype>, vertex_all_t>::type get(vertex_all_t, leda::GRAPH<vtype, etype>& g) { typedef typename property_map< leda::GRAPH<vtype, etype>, vertex_all_t>::type pmap_type; return pmap_type(&g); } template <class vtype, class etype > inline typename property_map< leda::GRAPH<vtype, etype>, vertex_all_t>::const_type get(vertex_all_t, const leda::GRAPH<vtype, etype>& g) { typedef typename property_map< leda::GRAPH<vtype, etype>, vertex_all_t>::const_type pmap_type; return pmap_type(&g); } template <> struct leda_property_map<edge_all_t> { template <class vtype, class etype> struct bind_ { typedef leda_graph_data_map<etype, etype&, leda::GRAPH<vtype, etype>*> type; typedef leda_graph_data_map<etype, const etype&, const leda::GRAPH<vtype, etype>*> const_type; }; }; template <class vtype, class etype > inline typename property_map< leda::GRAPH<vtype, etype>, edge_all_t>::type get(edge_all_t, leda::GRAPH<vtype, etype>& g) { typedef typename property_map< leda::GRAPH<vtype, etype>, edge_all_t>::type pmap_type; return pmap_type(&g); } template <class vtype, class etype > inline typename property_map< leda::GRAPH<vtype, etype>, edge_all_t>::const_type get(edge_all_t, const leda::GRAPH<vtype, etype>& g) { typedef typename property_map< leda::GRAPH<vtype, etype>, edge_all_t>::const_type pmap_type; return pmap_type(&g); } // property map interface to the LEDA node_array class template <class E, class ERef, class NodeMapPtr> class leda_node_property_map : public put_get_helper<ERef, leda_node_property_map<E, ERef, NodeMapPtr> > { public: typedef E value_type; typedef ERef reference; typedef leda::node key_type; typedef lvalue_property_map_tag category; leda_node_property_map(NodeMapPtr a) : m_array(a) { } ERef operator[](leda::node n) const { return (*m_array)[n]; } protected: NodeMapPtr m_array; }; template <class E> leda_node_property_map<E, const E&, const leda::node_array<E>*> make_leda_node_property_map(const leda::node_array<E>& a) { typedef leda_node_property_map<E, const E&, const leda::node_array<E>*> pmap_type; return pmap_type(&a); } template <class E> leda_node_property_map<E, E&, leda::node_array<E>*> make_leda_node_property_map(leda::node_array<E>& a) { typedef leda_node_property_map<E, E&, leda::node_array<E>*> pmap_type; return pmap_type(&a); } template <class E> leda_node_property_map<E, const E&, const leda::node_map<E>*> make_leda_node_property_map(const leda::node_map<E>& a) { typedef leda_node_property_map<E,const E&,const leda::node_map<E>*> pmap_type; return pmap_type(&a); } template <class E> leda_node_property_map<E, E&, leda::node_map<E>*> make_leda_node_property_map(leda::node_map<E>& a) { typedef leda_node_property_map<E, E&, leda::node_map<E>*> pmap_type; return pmap_type(&a); } // g++ 'enumeral_type' in template unification not implemented workaround template <class vtype, class etype, class Tag> struct property_map<leda::GRAPH<vtype, etype>, Tag> { typedef typename leda_property_map<Tag>::template bind_<vtype, etype> map_gen; typedef typename map_gen::type type; typedef typename map_gen::const_type const_type; }; template <class vtype, class etype, class PropertyTag, class Key> inline typename boost::property_traits< typename boost::property_map<leda::GRAPH<vtype, etype>,PropertyTag>::const_type
::value_type get(PropertyTag p, const leda::GRAPH<vtype, etype>& g, const Key& key) { return get(get(p, g), key); }
template <class vtype, class etype, class PropertyTag, class Key,class Value> inline void put(PropertyTag p, leda::GRAPH<vtype, etype>& g, const Key& key, const Value& value) { typedef typename property_map<leda::GRAPH<vtype, etype>, PropertyTag>::type Map; Map pmap = get(p, g); put(pmap, key, value); } // property map interface to the LEDA edge_array class template <class E, class ERef, class EdgeMapPtr> class leda_edge_property_map : public put_get_helper<ERef, leda_edge_property_map<E, ERef, EdgeMapPtr> > { public: typedef E value_type; typedef ERef reference; typedef leda::edge key_type; typedef lvalue_property_map_tag category; leda_edge_property_map(EdgeMapPtr a) : m_array(a) { } ERef operator[](leda::edge n) const { return (*m_array)[n]; } protected: EdgeMapPtr m_array; }; template <class E> leda_edge_property_map<E, const E&, const leda::edge_array<E>*> make_leda_node_property_map(const leda::node_array<E>& a) { typedef leda_edge_property_map<E, const E&, const leda::node_array<E>*> pmap_type; return pmap_type(&a); } template <class E> leda_edge_property_map<E, E&, leda::edge_array<E>*> make_leda_edge_property_map(leda::edge_array<E>& a) { typedef leda_edge_property_map<E, E&, leda::edge_array<E>*> pmap_type; return pmap_type(&a); } template <class E> leda_edge_property_map<E, const E&, const leda::edge_map<E>*> make_leda_edge_property_map(const leda::edge_map<E>& a) { typedef leda_edge_property_map<E,const E&,const leda::edge_map<E>*> pmap_type; return pmap_type(&a); } template <class E> leda_edge_property_map<E, E&, leda::edge_map<E>*> make_leda_edge_property_map(leda::edge_map<E>& a) { typedef leda_edge_property_map<E, E&, leda::edge_map<E>*> pmap_type; return pmap_type(&a); } } // namespace boost #endif // BOOST_GRAPH_LEDA_HPP
On Jan 15, 2007, at 10:06 AM, Jens Müller wrote:
Here is the file, works fine for me so far, but I have not actually USED all parts. The comments at the beginning will of course have to be removed ...
Thanks! I've committed this to CVS HEAD. Sorry for the delay. Cheers, Doug
Doug Gregor wrote:
On Jan 15, 2007, at 10:06 AM, Jens Müller wrote:
Here is the file, works fine for me so far, but I have not actually USED all parts. The comments at the beginning will of course have to be removed ...
Thanks! I've committed this to CVS HEAD. Sorry for the delay.
There might still be small bugs in it - the setting in which I compiled it does not use all functions. Most importantly, I think there were some functions in the wrong order which I fixed later. I found it hard to adapt it to the graph.cpp test program, I think it makes a lot of assumptions not configurable in graph_type.hpp which are only true for adjacency_list.
Jens Müller wrote:
I found it hard to adapt it to the graph.cpp test program, I think it makes a lot of assumptions not configurable in graph_type.hpp which are only true for adjacency_list.
See attached error log ... An updated leda_graph.hpp with a tiny correction is attached as well. ...found 523 target(s)... ...updating 2 target(s)... C++ graph.o graph.cpp: In function `int main(int, char**)': graph.cpp:163: error: invalid initialization of non-const reference of type 'leda::graph&' from a temporary of type 'size_t' ././leda_graph.hpp:686: error: in passing argument 1 of `leda::node_struct* boost::add_vertex(leda::graph&)' graph.cpp:185: error: invalid initialization of non-const reference of type 'leda::graph&' from a temporary of type 'size_t' ././leda_graph.hpp:738: error: in passing argument 3 of `std::pair<leda::edge_struct*, bool> boost::add_edge(leda::node_struct*, leda::node_struct*, leda::graph&)' graph.cpp:227: warning: comparison between signed and unsigned integer expressions graph.cpp:267: warning: comparison between signed and unsigned integer expressions graph.cpp:289: error: non-lvalue in assignment graph.cpp:290: error: non-lvalue in assignment graph.cpp:389: error: no matching function for call to `boost::leda_graph_id_map::leda_graph_id_map(size_t)' ././leda_graph.hpp:748: note: candidates are: boost::leda_graph_id_map::leda_graph_id_map(const boost::leda_graph_id_map&) ././leda_graph.hpp:754: note: boost::leda_graph_id_map::leda_graph_id_map() graph.cpp:403: error: non-lvalue in assignment graph.cpp:427: warning: comparison between signed and unsigned integer expressions ././leda_graph.hpp: In constructor `boost::graph_traits<leda::GRAPH<vtype, etype> >::adjacency_iterator::adjacency_iterator(leda::node_struct*, const leda::GRAPH<vtype, etype>*) [with vtype = int, etype = int]': /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:264: instantiated from `bool boost::is_adj_dispatch(Graph&, Vertex, Vertex, boost::directed_tag) [with Graph = leda::GRAPH<int, int>, Vertex = leda::node_struct*]' /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:308: instantiated from `bool boost::is_adjacent(Graph&, Vertex, Vertex) [with Graph = Graph, Vertex = leda::node_struct*]' graph.cpp:98: instantiated from `bool check_edge_added(Graph&, Edge, typename boost::graph_traits<G>::vertex_descriptor, typename boost::graph_traits<G>::vertex_descriptor, EdgeID, size_t, bool) [with Graph = Graph, Edge = leda::edge_struct*, EdgeID = boost::leda_graph_id_map]' graph.cpp:197: instantiated from here ././leda_graph.hpp:84: error: cannot convert `leda::node_struct*' to `leda::edge_struct*' in initialization /./leda_graph.hpp: In function `std::pair<typename boost::graph_traits<leda::GRAPH<vtype, etype> >::adjacency_iterator, typename boost::graph_traits<leda::GRAPH<vtype, etype> >::adjacency_iterator> boost::adjacent_vertices(typename boost::graph_traits<leda::GRAPH<vtype, etype> >::vertex_descriptor, const leda::GRAPH<vtype, etype>&) [with vtype = int, etype = int]': /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:265: instantiated from `bool boost::is_adj_dispatch(Graph&, Vertex, Vertex, boost::directed_tag) [with Graph = leda::GRAPH<int, int>, Vertex = leda::node_struct*]' /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:308: instantiated from `bool boost::is_adjacent(Graph&, Vertex, Vertex) [with Graph = Graph, Vertex = leda::node_struct*]' graph.cpp:98: instantiated from `bool check_edge_added(Graph&, Edge, typename boost::graph_traits<G>::vertex_descriptor, typename boost::graph_traits<G>::vertex_descriptor, EdgeID, size_t, bool) [with Graph = Graph, Edge = leda::edge_struct*, EdgeID = boost::leda_graph_id_map]' graph.cpp:197: instantiated from here ././leda_graph.hpp:448: error: no matching function for call to `leda::GRAPH<int, int>::first_adj_edge(leda::node_struct*&, int) const' /sw/linux/LEDA/LEDA-5.0.1/incl_old/LEDA/graph.h:1473: note: candidates are: leda::edge_struct* leda::graph::first_adj_edge(leda::node_struct*) const ././leda_graph.hpp: In constructor `boost::graph_traits<leda::GRAPH<vtype, etype> >::out_edge_iterator::out_edge_iterator(leda::node_struct*, const leda::GRAPH<vtype, etype>*) [with vtype = int, etype = int]': /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:280: instantiated from `bool boost::is_adj_dispatch(Graph&, Vertex, Vertex, boost::directed_tag) [with Graph = leda::GRAPH<int, int>, Vertex = leda::node_struct*]' /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:308: instantiated from `bool boost::is_adjacent(Graph&, Vertex, Vertex) [with Graph = Graph, Vertex = leda::node_struct*]' graph.cpp:98: instantiated from `bool check_edge_added(Graph&, Edge, typename boost::graph_traits<G>::vertex_descriptor, typename boost::graph_traits<G>::vertex_descriptor, EdgeID, size_t, bool) [with Graph = Graph, Edge = leda::edge_struct*, EdgeID = boost::leda_graph_id_map]' graph.cpp:197: instantiated from here ././leda_graph.hpp:110: error: cannot convert `leda::node_struct*' to `leda::edge_struct*' in initialization ././leda_graph.hpp: In function `std::pair<typename boost::graph_traits<leda::GRAPH<vtype, etype> >::out_edge_iterator, typename boost::graph_traits<leda::GRAPH<vtype, etype> >::out_edge_iterator> boost::out_edges(typename boost::graph_traits<leda::GRAPH<vtype, etype> >::vertex_descriptor, const leda::GRAPH<vtype, etype>&) [with vtype = int, etype = int]': /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:282: instantiated from `bool boost::is_adj_dispatch(Graph&, Vertex, Vertex, boost::directed_tag) [with Graph = leda::GRAPH<int, int>, Vertex = leda::node_struct*]' /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:308: instantiated from `bool boost::is_adjacent(Graph&, Vertex, Vertex) [with Graph = Graph, Vertex = leda::node_struct*]' graph.cpp:98: instantiated from `bool check_edge_added(Graph&, Edge, typename boost::graph_traits<G>::vertex_descriptor, typename boost::graph_traits<G>::vertex_descriptor, EdgeID, size_t, bool) [with Graph = Graph, Edge = leda::edge_struct*, EdgeID = boost::leda_graph_id_map]' graph.cpp:197: instantiated from here ././leda_graph.hpp:422: error: no matching function for call to `leda::GRAPH<int, int>::first_adj_edge(leda::node_struct*&, int) const' /sw/linux/LEDA/LEDA-5.0.1/incl_old/LEDA/graph.h:1473: note: candidates are: leda::edge_struct* leda::graph::first_adj_edge(leda::node_struct*) const /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp: In function `bool boost::in_edge_set(Graph&, Edge) [with Graph = leda::GRAPH<int, int>, Edge = leda::edge_struct*]': graph.cpp:103: instantiated from `bool check_edge_added(Graph&, Edge, typename boost::graph_traits<G>::vertex_descriptor, typename boost::graph_traits<G>::vertex_descriptor, EdgeID, size_t, bool) [with Graph = Graph, Edge = leda::edge_struct*, EdgeID = boost::leda_graph_id_map]' graph.cpp:197: instantiated from here /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:314: error: no type named `edge_iterator' in `class leda::GRAPH<int, int>' /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:314: error: no type named `edge_iterator' in `class leda::GRAPH<int, int>' /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:314: error: no type named `edge_iterator' in `class leda::GRAPH<int, int>' ././leda_graph.hpp: In constructor `boost::graph_traits<leda::GRAPH<vtype, etype> >::edge_iterator::edge_iterator(leda::edge_struct*, const leda::GRAPH<vtype, etype>*) [with vtype = int, etype = int]': ././leda_graph.hpp:409: instantiated from `std::pair<typename boost::graph_traits<leda::GRAPH<vtype, etype> >::edge_iterator, typename boost::graph_traits<leda::GRAPH<vtype, etype> >::edge_iterator> boost::edges(const leda::GRAPH<vtype, etype>&) [with vtype = int, etype = int]' /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:315: instantiated from `bool boost::in_edge_set(Graph&, Edge) [with Graph = leda::GRAPH<int, int>, Edge = leda::edge_struct*]' graph.cpp:103: instantiated from `bool check_edge_added(Graph&, Edge, typename boost::graph_traits<G>::vertex_descriptor, typename boost::graph_traits<G>::vertex_descriptor, EdgeID, size_t, bool) [with Graph = Graph, Edge = leda::edge_struct*, EdgeID = boost::leda_graph_id_map]' graph.cpp:197: instantiated from here ././leda_graph.hpp:191: error: cannot convert `leda::edge_struct*' to `leda::node_struct*' in initialization /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp: In function `bool boost::in_edge_set(Graph&, Edge) [with Graph = leda::GRAPH<int, int>, Edge = leda::edge_struct*]': graph.cpp:103: instantiated from `bool check_edge_added(Graph&, Edge, typename boost::graph_traits<G>::vertex_descriptor, typename boost::graph_traits<G>::vertex_descriptor, EdgeID, size_t, bool) [with Graph = Graph, Edge = leda::edge_struct*, EdgeID = boost::leda_graph_id_map]' graph.cpp:197: instantiated from here /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:315: error: no type named `edge_iterator' in `class leda::GRAPH<int, int>' /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:315: error: no type named `edge_iterator' in `class leda::GRAPH<int, int>' /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:316: error: no type named `edge_iterator' in `class leda::GRAPH<int, int>' /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:316: error: no type named `edge_iterator' in `class leda::GRAPH<int, int>' /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:316: error: no type named `edge_iterator' in `class leda::GRAPH<int, int>' /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:317: error: no type named `edge_iterator' in `class leda::GRAPH<int, int>' /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:317: error: no type named `edge_iterator' in `class leda::GRAPH<int, int>' graph.cpp: In function `bool check_edge_added(Graph&, Edge, typename boost::graph_traits<G>::vertex_descriptor, typename boost::graph_traits<G>::vertex_descriptor, EdgeID, size_t, bool) [with Graph = Graph, Edge = leda::edge_struct*, EdgeID = boost::leda_graph_id_map]': graph.cpp:197: instantiated from here graph.cpp:108: warning: comparison between signed and unsigned integer expressions /sw/linux/LEDA/LEDA-5.0.1/incl_old/LEDA/graph.h:1363: error: `leda::edge' is not a function, /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/detail/adjacency_list.hpp:1546: error: conflict with `template<class Config, class Base> std::pair<typename Config::edge_descriptor, bool> boost::edge(typename Config::vertex_descriptor, typename Config::vertex_descriptor, const boost::adj_list_helper<Config, Base>&)' graph.cpp:113: error: in call to `edge' graph.cpp:113: error: no matching function for call to `edge(leda::node_struct*&, leda::node_struct*&, leda::GRAPH<int, int>&)' ././leda_graph.hpp: In member function `void boost::graph_traits<leda::GRAPH<vtype, etype> >::edge_iterator::increment() [with vtype = int, etype = int]': /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/iterator/iterator_facade.hpp:523: instantiated from `static void boost::iterator_core_access::increment(Facade&) [with Facade = boost::graph_traits<Graph>::edge_iterator]' /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/iterator/iterator_facade.hpp:665: instantiated from `Derived& boost::iterator_facade<I, V, TC, R, D>::operator++() [with Derived = boost::graph_traits<Graph>::edge_iterator, Value = leda::edge_struct*, CategoryOrTraversal = boost::bidirectional_traversal_tag, Reference = leda::edge_struct* const&, Difference = leda::edge_struct* const*]' graph.cpp:133: instantiated from `size_t count_edges(Graph&) [with Graph = Graph]' graph.cpp:118: instantiated from `bool check_edge_added(Graph&, Edge, typename boost::graph_traits<G>::vertex_descriptor, typename boost::graph_traits<G>::vertex_descriptor, EdgeID, size_t, bool) [with Graph = Graph, Edge = leda::edge_struct*, EdgeID = boost::leda_graph_id_map]' graph.cpp:197: instantiated from here ././leda_graph.hpp:199: error: no matching function for call to `leda::GRAPH<int, int>::succ_edge(leda::node_struct*&) const' /sw/linux/LEDA/LEDA-5.0.1/incl_old/LEDA/graph.h:1459: note: candidates are: leda::edge_struct* leda::graph::succ_edge(leda::edge_struct*) const graph.cpp: In function `bool check_edge_added(Graph&, Edge, typename boost::graph_traits<G>::vertex_descriptor, typename boost::graph_traits<G>::vertex_descriptor, EdgeID, size_t, bool) [with Graph = Graph, Edge = leda::edge_struct*, EdgeID = boost::leda_graph_id_map]': graph.cpp:197: instantiated from here graph.cpp:118: warning: comparison between signed and unsigned integer expressions /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp: In function `bool boost::in_edge_set(Graph&, Vertex, Vertex) [with Graph = Graph, Vertex = leda::node_struct*]': graph.cpp:226: instantiated from here /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:332: error: no type named `edge_iterator' in `class Graph' /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:332: error: no type named `edge_iterator' in `class Graph' /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:333: error: no type named `edge_iterator' in `class Graph' /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:333: error: no type named `edge_iterator' in `class Graph' /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:333: error: no type named `edge_iterator' in `class Graph' /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:333: error: no type named `edge_iterator' in `class Graph' /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:333: error: no type named `edge_iterator' in `class Graph' /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:334: error: no type named `edge_iterator' in `class Graph' /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:334: error: no type named `edge_iterator' in `class Graph' /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp: In function `bool boost::in_vertex_set(Graph&, Vertex) [with Graph = Graph, Vertex = leda::node_struct*]': graph.cpp:300: instantiated from here /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:323: error: no type named `vertex_iterator' in `class Graph' /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:323: error: no type named `vertex_iterator' in `class Graph' /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:323: error: no type named `vertex_iterator' in `class Graph' graph.cpp:300: instantiated from here /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:324: error: no type named `vertex_iterator' in `class Graph' /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:324: error: no type named `vertex_iterator' in `class Graph' /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:325: error: no type named `vertex_iterator' in `class Graph' /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:325: error: no type named `vertex_iterator' in `class Graph' /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:325: error: no type named `vertex_iterator' in `class Graph' /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:326: error: no type named `vertex_iterator' in `class Graph' /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/graph/graph_utility.hpp:326: error: no type named `vertex_iterator' in `class Graph' ././leda_graph.hpp: In member function `leda::edge_struct* const& boost::graph_traits<leda::GRAPH<vtype, etype> >::edge_iterator::dereference() const [with vtype = int, etype = int]': /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/iterator/iterator_facade.hpp:517: instantiated from `static typename Facade::reference boost::iterator_core_access::dereference(const Facade&) [with Facade = boost::graph_traits<Graph>::edge_iterator]' /home/jmueller/software-gcc34/boost/include/boost-1_33_1/boost/iterator/iterator_facade.hpp:635: instantiated from `Reference boost::iterator_facade<I, V, TC, R, D>::operator*() const [with Derived = boost::graph_traits<Graph>::edge_iterator, Value = leda::edge_struct*, CategoryOrTraversal = boost::bidirectional_traversal_tag, Reference = leda::edge_struct* const&, Difference = leda::edge_struct* const*]' graph.cpp:343: instantiated from here ././leda_graph.hpp:194: error: invalid initialization of reference of type 'leda::edge_struct* const&' from expression of type 'leda::node_struct* const' ././leda_graph.hpp: In function `void boost::clear_vertex(typename boost::graph_traits<leda::GRAPH<vtype, etype> >::vertex_descriptor, leda::GRAPH<vtype, etype>&) [with vtype = int, etype = int]': graph.cpp:421: instantiated from here ././leda_graph.hpp:561: error: no matching function for call to `remove_edge(leda::edge_struct* const&)' ././leda_graph.hpp:695: note: candidates are: void boost::remove_edge(leda::node_struct*, leda::node_struct*, leda::graph&) ././leda_graph.hpp:707: note: void boost::remove_edge(leda::edge_struct*, leda::graph&) ././leda_graph.hpp: In constructor `boost::graph_traits<leda::GRAPH<vtype, etype> >::in_edge_iterator::in_edge_iterator(leda::node_struct*, const leda::GRAPH<vtype, etype>*) [with vtype = int, etype = int]': ././leda_graph.hpp:563: instantiated from `void boost::clear_vertex(typename boost::graph_traits<leda::GRAPH<vtype, etype> >::vertex_descriptor, leda::GRAPH<vtype, etype>&) [with vtype = int, etype = int]' graph.cpp:421: instantiated from here ././leda_graph.hpp:137: error: cannot convert `leda::node_struct*' to `leda::edge_struct*' in initialization ././leda_graph.hpp: In function `std::pair<typename boost::graph_traits<leda::GRAPH<vtype, etype> >::in_edge_iterator, typename boost::graph_traits<leda::GRAPH<vtype, etype> >::in_edge_iterator> boost::in_edges(typename boost::graph_traits<leda::GRAPH<vtype, etype> >::vertex_descriptor, const leda::GRAPH<vtype, etype>&) [with vtype = int, etype = int]': ././leda_graph.hpp:564: instantiated from `void boost::clear_vertex(typename boost::graph_traits<leda::GRAPH<vtype, etype> >::vertex_descriptor, leda::GRAPH<vtype, etype>&) [with vtype = int, etype = int]' graph.cpp:421: instantiated from here ././leda_graph.hpp:435: error: no matching function for call to `leda::GRAPH<int, int>::first_adj_edge(leda::node_struct*&, int) const' /sw/linux/LEDA/LEDA-5.0.1/incl_old/LEDA/graph.h:1473: note: candidates are: leda::edge_struct* leda::graph::first_adj_edge(leda::node_struct*) const g++34 -c -o graph.o -g -Wall -Wno-deprecated -pipe -O -I. -I/home/jmueller/software-gcc34/boost/include/boost-1_33_1 -I/sw/linux/LEDA/LEDA-5.0.1/include -I/sw/linux/LEDA/LEDA-5.0.1/incl -I/sw/linux/LEDA/LEDA-5.0.1/incl_old graph.cpp ...failed C++ graph.o ... ...skipped graph for lack of <.>graph.o... ...failed updating 1 target(s)... ...skipped 1 target(s)... //======================================================================= // Copyright 2002 Indiana University. // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek // // Distributed under the Boost Software License, Version 1.0. (See // accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) //======================================================================= #include <boost/graph/adjacency_list.hpp> #include <./leda_graph.hpp> //typedef boost::adjacency_list<boost::setS, boost::setS, boost::undirectedS, boost::property<vertex_id_t, std::size_t>, boost::property<edge_id_t, std::size_t> > Graph; //typedef boost::property<vertex_id_t, std::size_t> VertexId; //typedef boost::property<edge_id_t, std::size_t> EdgeID; typedef leda::GRAPH<int, int> Graph; typedef boost::leda_graph_id_map VertexID; typedef boost::leda_graph_id_map EdgeID; /* TODO: * Are id maps really available for all kinds of LEDA graphs? What is the id() member function there? Where is it documented? CHANGES: * property map interface to the LEDA edge_array class nearly 1:1 copy of node_array stuff * adapter for non-templated 'graph' class added nearly 1:1 copy of code for GRAPH<vtype,etype> * fixed access functions (outside iterator code) to use member functions of the graph/GRAPH class see http://www.algorithmic-solutions.info/leda_manual/graph.html * replaced leda_something by leda::something * make iterators use 'public' LEDA interfaces see http://www.algorithmic-solutions.info/leda_manual/graph.html * implemented clear_vertex * implemented EdgeListGraph concept * edge_iterator class * edges function -> please add to documentation */ //======================================================================= // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. // Copyright 2004 The Trustees of Indiana University. // Copyright 2007 University of Karlsruhe // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Douglas Gregor, // Jens Mueller // // Distributed under the Boost Software License, Version 1.0. (See // accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) //======================================================================= #ifndef BOOST_GRAPH_LEDA_HPP #define BOOST_GRAPH_LEDA_HPP #include <boost/config.hpp> #include <boost/iterator/iterator_facade.hpp> #include <boost/graph/graph_traits.hpp> #include <boost/graph/properties.hpp> #include <LEDA/graph.h> #include <LEDA/node_array.h> #include <LEDA/node_map.h> // The functions and classes in this file allows the user to // treat a LEDA GRAPH object as a boost graph "as is". No // wrapper is needed for the GRAPH object. // Warning: this implementation relies on partial specialization // for the graph_traits class (so it won't compile with Visual C++) // Warning: this implementation is in alpha and has not been tested #if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION namespace boost { struct leda_graph_traversal_category : public virtual bidirectional_graph_tag, public virtual adjacency_graph_tag, public virtual vertex_list_graph_tag { }; template <class vtype, class etype> struct graph_traits< leda::GRAPH<vtype,etype> > { typedef leda::node vertex_descriptor; typedef leda::edge edge_descriptor; class adjacency_iterator : public iterator_facade<adjacency_iterator, leda::node, bidirectional_traversal_tag, leda::node, const leda::node*> { public: adjacency_iterator(leda::node node = 0, const leda::GRAPH<vtype, etype>* g = 0) : base(node), g(g) {} private: leda::node dereference() const { return leda::target(base); } bool equal(const adjacency_iterator& other) const { return base == other.base; } void increment() { base = g->adj_succ(base); } void decrement() { base = g->adj_pred(base); } leda::edge base; const leda::GRAPH<vtype, etype>* g; friend class iterator_core_access; }; class out_edge_iterator : public iterator_facade<out_edge_iterator, leda::edge, bidirectional_traversal_tag, const leda::edge&, const leda::edge*> { public: out_edge_iterator(leda::node node = 0, const leda::GRAPH<vtype, etype>* g = 0) : base(node), g(g) {} private: const leda::edge& dereference() const { return base; } bool equal(const out_edge_iterator& other) const { return base == other.base; } void increment() { base = g->adj_succ(base); } void decrement() { base = g->adj_pred(base); } leda::edge base; const leda::GRAPH<vtype, etype>* g; friend class iterator_core_access; }; class in_edge_iterator : public iterator_facade<in_edge_iterator, leda::edge, bidirectional_traversal_tag, const leda::edge&, const leda::edge*> { public: in_edge_iterator(leda::node node = 0, const leda::GRAPH<vtype, etype>* g = 0) : base(node), g(g) {} private: const leda::edge& dereference() const { return base; } bool equal(const in_edge_iterator& other) const { return base == other.base; } void increment() { base = g->in_succ(base); } void decrement() { base = g->in_pred(base); } leda::edge base; const leda::GRAPH<vtype, etype>* g; friend class iterator_core_access; }; class vertex_iterator : public iterator_facade<vertex_iterator, leda::node, bidirectional_traversal_tag, const leda::node&, const leda::node*> { public: vertex_iterator(leda::node node = 0, const leda::GRAPH<vtype, etype>* g = 0) : base(node), g(g) {} private: const leda::node& dereference() const { return base; } bool equal(const vertex_iterator& other) const { return base == other.base; } void increment() { base = g->succ_node(base); } void decrement() { base = g->pred_node(base); } leda::node base; const leda::GRAPH<vtype, etype>* g; friend class iterator_core_access; }; class edge_iterator : public iterator_facade<edge_iterator, leda::edge, bidirectional_traversal_tag, const leda::edge&, const leda::edge*> { public: edge_iterator(leda::edge edge = 0, const leda::GRAPH<vtype, etype>* g = 0) : base(edge), g(g) {} private: const leda::edge& dereference() const { return base; } bool equal(const edge_iterator& other) const { return base == other.base; } void increment() { base = g->succ_edge(base); } void decrement() { base = g->pred_edge(base); } leda::node base; const leda::GRAPH<vtype, etype>* g; friend class iterator_core_access; }; typedef directed_tag directed_category; typedef allow_parallel_edge_tag edge_parallel_category; // not sure here typedef leda_graph_traversal_category traversal_category; typedef int vertices_size_type; typedef int edges_size_type; typedef int degree_size_type; }; template<> struct graph_traits<leda::graph> { typedef leda::node vertex_descriptor; typedef leda::edge edge_descriptor; class adjacency_iterator : public iterator_facade<adjacency_iterator, leda::node, bidirectional_traversal_tag, leda::node, const leda::node*> { public: adjacency_iterator(leda::edge edge = 0, const leda::graph* g = 0) : base(edge), g(g) {} private: leda::node dereference() const { return leda::target(base); } bool equal(const adjacency_iterator& other) const { return base == other.base; } void increment() { base = g->adj_succ(base); } void decrement() { base = g->adj_pred(base); } leda::edge base; const leda::graph* g; friend class iterator_core_access; }; class out_edge_iterator : public iterator_facade<out_edge_iterator, leda::edge, bidirectional_traversal_tag, const leda::edge&, const leda::edge*> { public: out_edge_iterator(leda::edge edge = 0, const leda::graph* g = 0) : base(edge), g(g) {} private: const leda::edge& dereference() const { return base; } bool equal(const out_edge_iterator& other) const { return base == other.base; } void increment() { base = g->adj_succ(base); } void decrement() { base = g->adj_pred(base); } leda::edge base; const leda::graph* g; friend class iterator_core_access; }; class in_edge_iterator : public iterator_facade<in_edge_iterator, leda::edge, bidirectional_traversal_tag, const leda::edge&, const leda::edge*> { public: in_edge_iterator(leda::edge edge = 0, const leda::graph* g = 0) : base(edge), g(g) {} private: const leda::edge& dereference() const { return base; } bool equal(const in_edge_iterator& other) const { return base == other.base; } void increment() { base = g->in_succ(base); } void decrement() { base = g->in_pred(base); } leda::edge base; const leda::graph* g; friend class iterator_core_access; }; class vertex_iterator : public iterator_facade<vertex_iterator, leda::node, bidirectional_traversal_tag, const leda::node&, const leda::node*> { public: vertex_iterator(leda::node node = 0, const leda::graph* g = 0) : base(node), g(g) {} private: const leda::node& dereference() const { return base; } bool equal(const vertex_iterator& other) const { return base == other.base; } void increment() { base = g->succ_node(base); } void decrement() { base = g->pred_node(base); } leda::node base; const leda::graph* g; friend class iterator_core_access; }; class edge_iterator : public iterator_facade<edge_iterator, leda::edge, bidirectional_traversal_tag, const leda::edge&, const leda::edge*> { public: edge_iterator(leda::edge edge = 0, const leda::graph* g = 0) : base(edge), g(g) {} private: const leda::edge& dereference() const { return base; } bool equal(const edge_iterator& other) const { return base == other.base; } void increment() { base = g->succ_edge(base); } void decrement() { base = g->pred_edge(base); } leda::edge base; const leda::graph* g; friend class iterator_core_access; }; typedef directed_tag directed_category; typedef allow_parallel_edge_tag edge_parallel_category; // not sure here typedef leda_graph_traversal_category traversal_category; typedef int vertices_size_type; typedef int edges_size_type; typedef int degree_size_type; }; } // namespace boost #endif namespace boost { //=========================================================================== // functions for GRAPH<vtype,etype> template <class vtype, class etype> typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor source(typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor e, const leda::GRAPH<vtype,etype>& g) { return source(e); } template <class vtype, class etype> typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor target(typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor e, const leda::GRAPH<vtype,etype>& g) { return target(e); } template <class vtype, class etype> inline std::pair< typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_iterator, typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_iterator > vertices(const leda::GRAPH<vtype,etype>& g) { typedef typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_iterator Iter; return std::make_pair( Iter(g.first_node(),&g), Iter(0,&g) ); } template <class vtype, class etype> inline std::pair< typename graph_traits< leda::GRAPH<vtype,etype> >::edge_iterator, typename graph_traits< leda::GRAPH<vtype,etype> >::edge_iterator > edges(const leda::GRAPH<vtype,etype>& g) { typedef typename graph_traits< leda::GRAPH<vtype,etype> >::edge_iterator Iter; return std::make_pair( Iter(g.first_edge(),&g), Iter(0,&g) ); } template <class vtype, class etype> inline std::pair< typename graph_traits< leda::GRAPH<vtype,etype> >::out_edge_iterator, typename graph_traits< leda::GRAPH<vtype,etype> >::out_edge_iterator > out_edges( typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u, const leda::GRAPH<vtype,etype>& g) { typedef typename graph_traits< leda::GRAPH<vtype,etype> > ::out_edge_iterator Iter; return std::make_pair( Iter(g.first_adj_edge(u,0),&g), Iter(0,&g) ); } template <class vtype, class etype> inline std::pair< typename graph_traits< leda::GRAPH<vtype,etype> >::in_edge_iterator, typename graph_traits< leda::GRAPH<vtype,etype> >::in_edge_iterator > in_edges( typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u, const leda::GRAPH<vtype,etype>& g) { typedef typename graph_traits< leda::GRAPH<vtype,etype> > ::in_edge_iterator Iter; return std::make_pair( Iter(g.first_adj_edge(u,1),&g), Iter(0,&g) ); } template <class vtype, class etype> inline std::pair< typename graph_traits< leda::GRAPH<vtype,etype> >::adjacency_iterator, typename graph_traits< leda::GRAPH<vtype,etype> >::adjacency_iterator > adjacent_vertices( typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u, const leda::GRAPH<vtype,etype>& g) { typedef typename graph_traits< leda::GRAPH<vtype,etype> > ::adjacency_iterator Iter; return std::make_pair( Iter(g.first_adj_edge(u,0),&g), Iter(0,&g) ); } template <class vtype, class etype> typename graph_traits< leda::GRAPH<vtype,etype> >::vertices_size_type num_vertices(const leda::GRAPH<vtype,etype>& g) { return g.number_of_nodes(); } template <class vtype, class etype> typename graph_traits< leda::GRAPH<vtype,etype> >::edges_size_type num_edges(const leda::GRAPH<vtype,etype>& g) { return g.number_of_edges(); } template <class vtype, class etype> typename graph_traits< leda::GRAPH<vtype,etype> >::degree_size_type out_degree( typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u, const leda::GRAPH<vtype,etype>& g) { return g.outdeg(u); } template <class vtype, class etype> typename graph_traits< leda::GRAPH<vtype,etype> >::degree_size_type in_degree( typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u, const leda::GRAPH<vtype,etype>& g) { return g.indeg(u); } template <class vtype, class etype> typename graph_traits< leda::GRAPH<vtype,etype> >::degree_size_type degree( typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u, const leda::GRAPH<vtype,etype>& g) { return g.outdeg(u) + g.indeg(u); } template <class vtype, class etype> typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor add_vertex(leda::GRAPH<vtype,etype>& g) { return g.new_node(); } template <class vtype, class etype> typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor add_vertex(const vtype& vp, leda::GRAPH<vtype,etype>& g) { return g.new_node(vp); } template <class vtype, class etype> std::pair< typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor, bool> add_edge( typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u, typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor v, leda::GRAPH<vtype,etype>& g) { return std::make_pair(g.new_edge(u, v), true); } template <class vtype, class etype> std::pair< typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor, bool> add_edge( typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u, typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor v, const etype& et, leda::GRAPH<vtype,etype>& g) { return std::make_pair(g.new_edge(u, v, et), true); } template <class vtype, class etype> void remove_edge( typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u, typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor v, leda::GRAPH<vtype,etype>& g) { typename graph_traits< leda::GRAPH<vtype,etype> >::out_edge_iterator i,iend; for (boost::tie(i,iend) = out_edges(u,g); i != iend; ++i) if (target(*i,g) == v) g.del_edge(*i); } template <class vtype, class etype> void remove_edge( typename graph_traits< leda::GRAPH<vtype,etype> >::edge_descriptor e, leda::GRAPH<vtype,etype>& g) { g.del_edge(e); } template <class vtype, class etype> void clear_vertex( typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u, leda::GRAPH<vtype,etype>& g) { typename graph_traits< leda::GRAPH<vtype,etype> >::out_edge_iterator ei, ei_end; for (tie(ei, ei_end)=out_edges(u,g); ei!=ei_end; ei++) remove_edge(*ei); typename graph_traits< leda::GRAPH<vtype,etype> >::in_edge_iterator iei, iei_end; for (tie(iei, iei_end)=in_edges(u,g); iei!=iei_end; iei++) remove_edge(*iei, g); } template <class vtype, class etype> void remove_vertex( typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_descriptor u, leda::GRAPH<vtype,etype>& g) { g.del_node(u); } //=========================================================================== // functions for graph (non-templated version) graph_traits<leda::graph>::vertex_descriptor source(graph_traits<leda::graph>::edge_descriptor e, const leda::graph& g) { return source(e); } graph_traits<leda::graph>::vertex_descriptor target(graph_traits<leda::graph>::edge_descriptor e, const leda::graph& g) { return target(e); } inline std::pair< graph_traits<leda::graph>::vertex_iterator, graph_traits<leda::graph>::vertex_iterator > vertices(const leda::graph& g) { typedef graph_traits<leda::graph>::vertex_iterator Iter; return std::make_pair( Iter(g.first_node(),&g), Iter(0,&g) ); } inline std::pair< graph_traits<leda::graph>::edge_iterator, graph_traits<leda::graph>::edge_iterator > edges(const leda::graph& g) { typedef graph_traits<leda::graph>::edge_iterator Iter; return std::make_pair( Iter(g.first_edge(),&g), Iter(0,&g) ); } inline std::pair< graph_traits<leda::graph>::out_edge_iterator, graph_traits<leda::graph>::out_edge_iterator > out_edges( graph_traits<leda::graph>::vertex_descriptor u, const leda::graph& g) { typedef graph_traits<leda::graph>::out_edge_iterator Iter; return std::make_pair( Iter(g.first_adj_edge(u),&g), Iter(0,&g) ); } inline std::pair< graph_traits<leda::graph>::in_edge_iterator, graph_traits<leda::graph>::in_edge_iterator > in_edges( graph_traits<leda::graph>::vertex_descriptor u, const leda::graph& g) { typedef graph_traits<leda::graph> ::in_edge_iterator Iter; return std::make_pair( Iter(g.first_in_edge(u),&g), Iter(0,&g) ); } inline std::pair< graph_traits<leda::graph>::adjacency_iterator, graph_traits<leda::graph>::adjacency_iterator > adjacent_vertices( graph_traits<leda::graph>::vertex_descriptor u, const leda::graph& g) { typedef graph_traits<leda::graph> ::adjacency_iterator Iter; return std::make_pair( Iter(g.first_adj_edge(u),&g), Iter(0,&g) ); } graph_traits<leda::graph>::vertices_size_type num_vertices(const leda::graph& g) { return g.number_of_nodes(); } graph_traits<leda::graph>::edges_size_type num_edges(const leda::graph& g) { return g.number_of_edges(); } graph_traits<leda::graph>::degree_size_type out_degree( graph_traits<leda::graph>::vertex_descriptor u, const leda::graph& g) { return g.outdeg(u); } graph_traits<leda::graph>::degree_size_type in_degree( graph_traits<leda::graph>::vertex_descriptor u, const leda::graph& g) { return g.indeg(u); } graph_traits<leda::graph>::degree_size_type degree( graph_traits<leda::graph>::vertex_descriptor u, const leda::graph& g) { return g.outdeg(u) + g.indeg(u); } graph_traits<leda::graph>::vertex_descriptor add_vertex(leda::graph& g) { return g.new_node(); } void remove_edge( graph_traits<leda::graph>::vertex_descriptor u, graph_traits<leda::graph>::vertex_descriptor v, leda::graph& g) { graph_traits<leda::graph>::out_edge_iterator i,iend; for (boost::tie(i,iend) = out_edges(u,g); i != iend; ++i) if (target(*i,g) == v) g.del_edge(*i); } void remove_edge( graph_traits<leda::graph>::edge_descriptor e, leda::graph& g) { g.del_edge(e); } void clear_vertex( graph_traits<leda::graph>::vertex_descriptor u, leda::graph& g) { graph_traits<leda::graph>::out_edge_iterator ei, ei_end; for (tie(ei, ei_end)=out_edges(u,g); ei!=ei_end; ei++) remove_edge(*ei, g); graph_traits<leda::graph>::in_edge_iterator iei, iei_end; for (tie(iei, iei_end)=in_edges(u,g); iei!=iei_end; iei++) remove_edge(*iei, g); } void remove_vertex( graph_traits<leda::graph>::vertex_descriptor u, leda::graph& g) { g.del_node(u); } std::pair< graph_traits<leda::graph>::edge_descriptor, bool> add_edge( graph_traits<leda::graph>::vertex_descriptor u, graph_traits<leda::graph>::vertex_descriptor v, leda::graph& g) { return std::make_pair(g.new_edge(u, v), true); } //=========================================================================== // property maps for GRAPH<vtype,etype> class leda_graph_id_map : public put_get_helper<int, leda_graph_id_map> { public: typedef readable_property_map_tag category; typedef int value_type; typedef int reference; typedef leda::node key_type; leda_graph_id_map() { } template <class T> long operator[](T x) const { return x->id(); } }; template <class vtype, class etype> inline leda_graph_id_map get(vertex_index_t, const leda::GRAPH<vtype, etype>& g) { return leda_graph_id_map(); } template <class vtype, class etype> inline leda_graph_id_map get(edge_index_t, const leda::GRAPH<vtype, etype>& g) { return leda_graph_id_map(); } template <class Tag> struct leda_property_map { }; template <> struct leda_property_map<vertex_index_t> { template <class vtype, class etype> struct bind_ { typedef leda_graph_id_map type; typedef leda_graph_id_map const_type; }; }; template <> struct leda_property_map<edge_index_t> { template <class vtype, class etype> struct bind_ { typedef leda_graph_id_map type; typedef leda_graph_id_map const_type; }; }; template <class Data, class DataRef, class GraphPtr> class leda_graph_data_map : public put_get_helper<DataRef, leda_graph_data_map<Data,DataRef,GraphPtr> > { public: typedef Data value_type; typedef DataRef reference; typedef void key_type; typedef lvalue_property_map_tag category; leda_graph_data_map(GraphPtr g) : m_g(g) { } template <class NodeOrEdge> DataRef operator[](NodeOrEdge x) const { return (*m_g)[x]; } protected: GraphPtr m_g; }; template <> struct leda_property_map<vertex_all_t> { template <class vtype, class etype> struct bind_ { typedef leda_graph_data_map<vtype, vtype&, leda::GRAPH<vtype, etype>*> type; typedef leda_graph_data_map<vtype, const vtype&, const leda::GRAPH<vtype, etype>*> const_type; }; }; template <class vtype, class etype > inline typename property_map< leda::GRAPH<vtype, etype>, vertex_all_t>::type get(vertex_all_t, leda::GRAPH<vtype, etype>& g) { typedef typename property_map< leda::GRAPH<vtype, etype>, vertex_all_t>::type pmap_type; return pmap_type(&g); } template <class vtype, class etype > inline typename property_map< leda::GRAPH<vtype, etype>, vertex_all_t>::const_type get(vertex_all_t, const leda::GRAPH<vtype, etype>& g) { typedef typename property_map< leda::GRAPH<vtype, etype>, vertex_all_t>::const_type pmap_type; return pmap_type(&g); } template <> struct leda_property_map<edge_all_t> { template <class vtype, class etype> struct bind_ { typedef leda_graph_data_map<etype, etype&, leda::GRAPH<vtype, etype>*> type; typedef leda_graph_data_map<etype, const etype&, const leda::GRAPH<vtype, etype>*> const_type; }; }; template <class vtype, class etype > inline typename property_map< leda::GRAPH<vtype, etype>, edge_all_t>::type get(edge_all_t, leda::GRAPH<vtype, etype>& g) { typedef typename property_map< leda::GRAPH<vtype, etype>, edge_all_t>::type pmap_type; return pmap_type(&g); } template <class vtype, class etype > inline typename property_map< leda::GRAPH<vtype, etype>, edge_all_t>::const_type get(edge_all_t, const leda::GRAPH<vtype, etype>& g) { typedef typename property_map< leda::GRAPH<vtype, etype>, edge_all_t>::const_type pmap_type; return pmap_type(&g); } // property map interface to the LEDA node_array class template <class E, class ERef, class NodeMapPtr> class leda_node_property_map : public put_get_helper<ERef, leda_node_property_map<E, ERef, NodeMapPtr> > { public: typedef E value_type; typedef ERef reference; typedef leda::node key_type; typedef lvalue_property_map_tag category; leda_node_property_map(NodeMapPtr a) : m_array(a) { } ERef operator[](leda::node n) const { return (*m_array)[n]; } protected: NodeMapPtr m_array; }; template <class E> leda_node_property_map<E, const E&, const leda::node_array<E>*> make_leda_node_property_map(const leda::node_array<E>& a) { typedef leda_node_property_map<E, const E&, const leda::node_array<E>*> pmap_type; return pmap_type(&a); } template <class E> leda_node_property_map<E, E&, leda::node_array<E>*> make_leda_node_property_map(leda::node_array<E>& a) { typedef leda_node_property_map<E, E&, leda::node_array<E>*> pmap_type; return pmap_type(&a); } template <class E> leda_node_property_map<E, const E&, const leda::node_map<E>*> make_leda_node_property_map(const leda::node_map<E>& a) { typedef leda_node_property_map<E,const E&,const leda::node_map<E>*> pmap_type; return pmap_type(&a); } template <class E> leda_node_property_map<E, E&, leda::node_map<E>*> make_leda_node_property_map(leda::node_map<E>& a) { typedef leda_node_property_map<E, E&, leda::node_map<E>*> pmap_type; return pmap_type(&a); } // g++ 'enumeral_type' in template unification not implemented workaround template <class vtype, class etype, class Tag> struct property_map<leda::GRAPH<vtype, etype>, Tag> { typedef typename leda_property_map<Tag>::template bind_<vtype, etype> map_gen; typedef typename map_gen::type type; typedef typename map_gen::const_type const_type; }; template <class vtype, class etype, class PropertyTag, class Key> inline typename boost::property_traits< typename boost::property_map<leda::GRAPH<vtype, etype>,PropertyTag>::const_type
::value_type get(PropertyTag p, const leda::GRAPH<vtype, etype>& g, const Key& key) { return get(get(p, g), key); }
template <class vtype, class etype, class PropertyTag, class Key,class Value> inline void put(PropertyTag p, leda::GRAPH<vtype, etype>& g, const Key& key, const Value& value) { typedef typename property_map<leda::GRAPH<vtype, etype>, PropertyTag>::type Map; Map pmap = get(p, g); put(pmap, key, value); } // property map interface to the LEDA edge_array class template <class E, class ERef, class EdgeMapPtr> class leda_edge_property_map : public put_get_helper<ERef, leda_edge_property_map<E, ERef, EdgeMapPtr> > { public: typedef E value_type; typedef ERef reference; typedef leda::edge key_type; typedef lvalue_property_map_tag category; leda_edge_property_map(EdgeMapPtr a) : m_array(a) { } ERef operator[](leda::edge n) const { return (*m_array)[n]; } protected: EdgeMapPtr m_array; }; template <class E> leda_edge_property_map<E, const E&, const leda::edge_array<E>*> make_leda_node_property_map(const leda::node_array<E>& a) { typedef leda_edge_property_map<E, const E&, const leda::node_array<E>*> pmap_type; return pmap_type(&a); } template <class E> leda_edge_property_map<E, E&, leda::edge_array<E>*> make_leda_edge_property_map(leda::edge_array<E>& a) { typedef leda_edge_property_map<E, E&, leda::edge_array<E>*> pmap_type; return pmap_type(&a); } template <class E> leda_edge_property_map<E, const E&, const leda::edge_map<E>*> make_leda_edge_property_map(const leda::edge_map<E>& a) { typedef leda_edge_property_map<E,const E&,const leda::edge_map<E>*> pmap_type; return pmap_type(&a); } template <class E> leda_edge_property_map<E, E&, leda::edge_map<E>*> make_leda_edge_property_map(leda::edge_map<E>& a) { typedef leda_edge_property_map<E, E&, leda::edge_map<E>*> pmap_type; return pmap_type(&a); } } // namespace boost #endif // BOOST_GRAPH_LEDA_HPP
participants (2)
-
Doug Gregor -
Jens Müller