| //======================================================================= |
| // 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 (boost::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 (boost::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 (boost::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 (boost::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 |