//======================================================================= | |
// 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 |