|
|
Boost : |
From: Jens Müller (jens.mueller_at_[hidden])
Date: 2007-01-15 10:06:24
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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk