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