https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Nicolas Ballas <ballas@lrde.epita.fr> Add base decorator for boost graph. * tests/util/boost_graph.cc: New. * mln/util/internal/boost_graph.hh: New, boost graph base decorator. * mln/util/internal/boost_graph_structure.hh, * mln/util/internal/boost_graph_access.hh, * mln/util/internal/boost_graph_property.hh: boost graph operations. mln/util/internal/boost_graph.hh | 189 ++++++++++++++++++ mln/util/internal/boost_graph_access.hh | 293 +++++++++++++++++++++++++++++ mln/util/internal/boost_graph_property.hh | 171 ++++++++++++++++ mln/util/internal/boost_graph_structure.hh | 281 +++++++++++++++++++++++++++ tests/util/boost_graph.cc | 116 +++++++++++ 5 files changed, 1050 insertions(+) Index: tests/util/boost_graph.cc --- tests/util/boost_graph.cc (revision 0) +++ tests/util/boost_graph.cc (revision 0) @@ -0,0 +1,116 @@ +// Copyright (C) 2007, 2008 EPITA Research and Development Laboratory +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to +// produce an executable, this file does not by itself cause the +// resulting executable to be covered by the GNU General Public +// License. This exception does not however invalidate any other +// reasons why the executable file might be covered by the GNU General +// Public License. + +/// \file tests/util/graph.cc +/// \brief test of mln::util::graph +/// This test is a copy of the BGL quick tours example. + +#include <mln/util/internal/boost_graph.hh> +#include <iostream> + +using namespace mln::util::internal; +using namespace boost; + +struct empty {}; + +template <class Graph> +struct exercise_vertex +{ + typedef typename graph_traits<Graph>::vertex_descriptor Vertex; + exercise_vertex(Graph& g_) : g(g_) {} + + void operator()(const Vertex& v) const + { + typedef graph_traits<Graph> GraphTraits; + typename property_map<Graph, vertex_index_t>::type + index = get(vertex_index, g); + + std::cout << "out-edges: "; + typename GraphTraits::out_edge_iterator out_i, out_end; + typename GraphTraits::edge_descriptor e; + for (tie(out_i, out_end) = out_edges(v, g); out_i != out_end; ++out_i) + { + e = *out_i; + Vertex src = source(e, g), targ = target(e, g); + std::cout << "(" << index[src] << "," << index[targ] << ") "; + } + std::cout << std::endl; + + std::cout << "adjacent vertices: "; + typename graph_traits<Graph>::adjacency_iterator ai; + typename graph_traits<Graph>::adjacency_iterator ai_end; + for (tie(ai, ai_end) = adjacent_vertices(v, g); ai != ai_end; ++ai) + std::cout << index[*ai] << " "; + std::cout << std::endl; + } + + Graph& g; +}; + +int main () +{ + + typedef boost_graph<empty, empty> Graph; + + // Make convenient labels for the vertices + const int num_vertices = 5; + + // writing out the edges in the graph + typedef std::pair<int, int> Edge; + Edge edge_array[] = { + Edge(0, 1), Edge(0, 3), Edge(2, 0), Edge(3, 2), + Edge(2, 4), Edge(1, 3), Edge(3, 4) + }; + const int num_edges = sizeof(edge_array)/sizeof(edge_array[0]); + + // declare a graph object + Graph g(num_vertices); + typedef property_map<Graph, vertex_index_t>::type IndexMap; + IndexMap index = get(vertex_index, g); + + // add the edges to the graph object + for (int i = 0; i < num_edges; ++i) + add_edge(edge_array[i].first, edge_array[i].second, g); + + std::cout << "vertices(g) = "; + typedef graph_traits<Graph>::vertex_iterator vertex_iter; + std::pair<vertex_iter, vertex_iter> vp; + for (vp = vertices(g); vp.first != vp.second; ++vp.first) + std::cout << index[*vp.first] << " "; + std::cout << std::endl; + + std::cout << "edges(g) = "; + graph_traits<Graph>::edge_iterator ei, ei_end; + for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) + std::cout << "(" << index[source(*ei, g)] + << "," << index[target(*ei, g)] << ") "; + std::cout << std::endl; + + std::for_each(vertices(g).first, vertices(g).second, + exercise_vertex<Graph>(g)); + return 0; +} Index: mln/util/internal/boost_graph.hh --- mln/util/internal/boost_graph.hh (revision 0) +++ mln/util/internal/boost_graph.hh (revision 0) @@ -0,0 +1,189 @@ +// Copyright (C) 2007, 2008 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to +// produce an executable, this file does not by itself cause the +// resulting executable to be covered by the GNU General Public +// License. +// reasons why the executable file might be covered by the GNU General +// Public License. + +#ifndef MLN_UTIL_BOOST_GRAPH_HH +# define MLN_UTIL_BOOST_GRAPH_HH + +/// \file mln/util/internal/boost_graph.hh +/// \brief Definition of the boost::adjacenly_list decorator. + +# include <boost/graph/adjacency_list.hpp> + +namespace mln +{ + + namespace util + { + + namespace internal + { + + /// \brief Boost graph decorator base + /// Graph class which rests on boost::adjacency_list class. + template <typename VertexProperty, typename EdgeProperty> + class boost_graph + { + typedef boost_graph<VertexProperty, EdgeProperty> self_type; + + public: + /// Types declartation. + typedef boost::adjacency_list<boost::setS, boost::vecS, + boost::undirectedS, + VertexProperty, EdgeProperty> decorated; + + /// Descriptors. + typedef typename decorated::vertex_descriptor vertex_descriptor; + typedef typename decorated::edge_descriptor edge_descriptor; + + /// Iterators. + typedef typename decorated::vertex_iterator vertex_iterator; + typedef typename decorated::edge_iterator edge_iterator; + typedef typename decorated::out_edge_iterator out_edge_iterator; + typedef typename decorated::in_edge_iterator in_edge_iterator; + typedef typename decorated::adjacency_iterator adjacency_iterator; + typedef typename decorated::inv_adjacency_iterator + inv_adjacency_iterator; + + /// Categories. + typedef typename decorated::directed_category directed_category; + typedef typename decorated::traversal_category traversal_category; + typedef typename decorated::edge_parallel_category + edge_parallel_category; + typedef typename decorated::vertex_property_type vertex_property_type; + typedef typename decorated::graph_tag graph_tag; + + /// Sizes. + typedef typename decorated::vertices_size_type vertices_size_type; + typedef typename decorated::edges_size_type edges_size_type; + typedef typename decorated::degree_size_type degree_size_type; + + + /// Constructor(s). + boost_graph(); + boost_graph(const boost_graph& lhs); + boost_graph(vertices_size_type n); + + /// Assignment operator. + boost_graph& + operator=(const boost_graph& lhs); + + /// Remove all of the edges and vertices from the graph. + void clear(); + + /// Swap the vertices, edges, and properties of this graph with + /// the vertices, edges, and properties of graph x. + void swap(boost_graph& rhs); + + /// Internal methods: + + /// Return the boost decorated graph. + decorated& + graph(); + + /// Return the boost decorated graph (const version). + const decorated& + graph() const; + + + protected: + decorated graph_; + /// add index on need + }; + + /// Graph method declaration + + /// Implementation + +# ifndef MLN_INCLUDE_ONLY + + template <typename VertexProp, typename EdgeProp> + boost_graph<VertexProp, EdgeProp>::boost_graph() + { + } + + template <typename VertexProp, typename EdgeProp> + boost_graph<VertexProp, EdgeProp>::boost_graph(const boost_graph& lhs) : + graph_(lhs.graph_) + { + } + + template <typename VertexProp, typename EdgeProp> + boost_graph<VertexProp, EdgeProp>::boost_graph(vertices_size_type n) : + graph_(n) + { + } + + template <typename VertexProp, typename EdgeProp> + boost_graph<VertexProp, EdgeProp>& + boost_graph<VertexProp, EdgeProp>::operator=(const boost_graph& lhs) + { + if (&lhs == this) + return *this; + this->graph_ = lhs.graph_; + } + + template <typename VertexProp, typename EdgeProp> + void + boost_graph<VertexProp, EdgeProp>::clear() + { + this->graph_.clear(); + } + + template <typename VertexProp, typename EdgeProp> + void + boost_graph<VertexProp, EdgeProp>::swap(boost_graph& rhs) + { + this->graph_.swap(rhs.graph_); + } + + template <typename VertexProp, typename EdgeProp> + inline typename boost_graph<VertexProp, EdgeProp>::decorated& + boost_graph<VertexProp, EdgeProp>::graph() + { + return this->graph_; + } + + template <typename VertexProp, typename EdgeProp> + inline const typename boost_graph<VertexProp, EdgeProp>::decorated& + boost_graph<VertexProp, EdgeProp>::graph() const + { + return this->graph_; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::util::internal + + } // end of namespace mln::util + +} // end of namespace mln + +# include "boost_graph_access.hh" +# include "boost_graph_structure.hh" +# include "boost_graph_property.hh" + +#endif // ! MLN_UTIL_BOOST_GRAPH_HH Index: mln/util/internal/boost_graph_structure.hh --- mln/util/internal/boost_graph_structure.hh (revision 0) +++ mln/util/internal/boost_graph_structure.hh (revision 0) @@ -0,0 +1,281 @@ +// Copyright (C) 2007, 2008 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to +// produce an executable, this file does not by itself cause the +// resulting executable to be covered by the GNU General Public +// License. +// reasons why the executable file might be covered by the GNU General +// Public License. + + +/// \file mln/util/internal/boost_graph_struture.hh +/// \brief Operations that interract with the boost_graph structure. + +#ifndef MLN_UTIL_INTERNAL_BOOST_GRAPH_STRUCTURE_HH_ +# define MLN_UTIL_INTERNAL_BOOST_GRAPH_STRUCTURE_HH_ + +/// fwd declaration +namespace mln +{ + namespace util + { + namespace internal + { + template <typename VertexProperty, typename EdgeProperty> + class boost_graph; + } + } +} + +namespace boost +{ + namespace mlnu = mln::util::internal; + + /// \brief Adds edge (u,v) to the graph and returns the edge descriptor for + /// the new edge. + template <typename VProp, typename EProp> + std::pair<typename mlnu::boost_graph<VProp, EProp>::edge_descriptor, bool> + add_edge(typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor u, + typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor v, + typename mlnu::boost_graph<VProp, EProp>& g); + + + /// \brief Adds edge (u,v) to the graph and attaches p as the value of the + /// edge's internal property storage. + template <typename VProp, typename EProp> + std::pair<typename mlnu::boost_graph<VProp, EProp>::edge_descriptor, bool> + add_edge(typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor u, + typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor v, + const typename mlnu::boost_graph<VProp, EProp>::EdgeProperties& p, + typename mlnu::boost_graph<VProp, EProp>& g); + + /// \brief Removes the edge (u,v) from the graph. + template <typename VProp, typename EProp> + void + remove_edge(typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor u, + typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor v, + typename mlnu::boost_graph<VProp, EProp>& g); + + /// \brief Removes the edge e from the graph. + /// This differs from the remove_edge(u, v, g) function in the case of + /// a multigraph. This remove_edge(e, g) function removes a single edge, + /// whereas the remove_edge(u, v, g) function removes all edges (u,v). + template <typename VProp, typename EProp> + void + remove_edge(typename mlnu::boost_graph<VProp, EProp>::edge_descriptor e, + typename mlnu::boost_graph<VProp, EProp>& g); + + + /// \brief Same as remove_edge(*iter, g) + template <typename VProp, typename EProp> + void + remove_edge(typename mlnu::boost_graph<VProp, EProp>::out_edge_iterator iter, + typename mlnu::boost_graph<VProp, EProp>& g); + + + /// \brief Removes all out-edges of vertex u from the graph that + /// satisfy the predicate. + template <typename VProp, typename EProp, class Predicate> + void + remove_out_edge_if(typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor u, + Predicate predicate, + typename mlnu::boost_graph<VProp, EProp>& g); + + /// FIXME only available on directed graph + template <typename VProp, typename EProp, class Predicate> + void + remove_in_edge_if(typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor v, + Predicate predicate, + typename mlnu::boost_graph<VProp, EProp>& g); + + /// \brief Removes all edges of vertex u from the graph that + /// satisfy the predicate. + template <typename VProp, typename EProp, class Predicate> + void remove_edge_if(Predicate predicate, + typename mlnu::boost_graph<VProp, EProp>& g); + + /// \brief Adds a vertex to the graph. + /// Returns the vertex descriptor for the new vertex. + template <typename VProp, typename EProp> + typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor + add_vertex(typename mlnu::boost_graph<VProp, EProp>& g); + + /// \brief Adds a vertex to the graph with the specified properties. + /// Returns the vertex descriptor for the new vertex. + template <typename VProp, typename EProp> + typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor + add_vertex(const typename mlnu::boost_graph<VProp, EProp>::VertexProperties& p, + typename mlnu::boost_graph<VProp, EProp>& g); + + /// \brief Removes all edges to and from vertex u. + template <typename VProp, typename EProp> + void + clear_vertex(typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor u, + typename mlnu::boost_graph<VProp, EProp>& g); + + /// \brief Removes all out-edges to and from vertex u. + template <typename VProp, typename EProp> + void + clear_out_edges(typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor u, + typename mlnu::boost_graph<VProp, EProp>& g); + + /// FIXME: only define for the directed graphs. + template <typename VProp, typename EProp> + void + clear_in_edges(typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor u, + typename mlnu::boost_graph<VProp, EProp>& g); + + + /// \brief Remove vertex u from the vertex set of the graph. + /// It is assumed that there are no edges to or from vertex u + /// when it is removed + template <typename VProp, typename EProp> + void + remove_vertex(typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor u, + typename mlnu::boost_graph<VProp, EProp>& g); + +# ifndef MLN_INCLUDE_ONLY + + template <typename VProp, typename EProp> + std::pair<typename mlnu::boost_graph<VProp, EProp>::edge_descriptor, + bool> + add_edge(typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor u, + typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor v, + typename mlnu::boost_graph<VProp, EProp>& g) + { + return add_edge(u, v, g.graph()); + } + + + template <typename VProp, typename EProp> + std::pair<typename mlnu::boost_graph<VProp, EProp>::edge_descriptor, + bool> + add_edge(typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor u, + typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor v, + const typename mlnu::boost_graph<VProp, EProp>::EdgeProperties& p, + typename mlnu::boost_graph<VProp, EProp>& g) + { + return add_edge(u, v, p, g.graph()); + } + + template <typename VProp, typename EProp> + void + remove_edge(typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor u, + typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor v, + typename mlnu::boost_graph<VProp, EProp>& g) + { + return remove_edge(u, v, g.graph()); + } + + template <typename VProp, typename EProp> + void + remove_edge(typename mlnu::boost_graph<VProp, EProp>::edge_descriptor e, + typename mlnu::boost_graph<VProp, EProp>& g) + { + return remove_edge(e, g.graph()); + } + + template <typename VProp, typename EProp> + void + remove_edge(typename mlnu::boost_graph<VProp, EProp>::out_edge_iterator iter, + typename mlnu::boost_graph<VProp, EProp>& g) + { + return remove_edge(iter, g.graph()); + } + + template <typename VProp, typename EProp, class Predicate> + void + remove_out_edge_if(typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor u, + Predicate predicate, + typename mlnu::boost_graph<VProp, EProp>& g) + { + return remove_out_edge_if(u, predicate, g.graph()); + } + + template <typename VProp, typename EProp, class Predicate> + void + remove_in_edge_if(typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor v, + Predicate predicate, + typename mlnu::boost_graph<VProp, EProp>& g) + { + return remove_in_edge_if(v, predicate, g.graph()); + } + + template <typename VProp, typename EProp, class Predicate> + void remove_edge_if(Predicate predicate, + typename mlnu::boost_graph<VProp, EProp>& g) + { + return remove_edge_if(predicate, g.graph()); + } + + template <typename VProp, typename EProp> + typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor + add_vertex(typename mlnu::boost_graph<VProp, EProp>& g) + { + return add_vertex(g.graph()); + } + + template <typename VProp, typename EProp> + typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor + add_vertex(const typename mlnu::boost_graph<VProp, EProp>::VertexProperties& p, + typename mlnu::boost_graph<VProp, EProp>& g) + { + return add_vertex(p, g.graph()); + } + + template <typename VProp, typename EProp> + void + clear_vertex(typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor u, + typename mlnu::boost_graph<VProp, EProp>& g) + { + return clear_vertex(u, g.graph()); + } + + template <typename VProp, typename EProp> + void + clear_out_edges(typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor u, + typename mlnu::boost_graph<VProp, EProp>& g) + { + return clear_out_edges(u, g.graph()); + } + + template <typename VProp, typename EProp> + void + clear_in_edges(typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor u, + typename mlnu::boost_graph<VProp, EProp>& g) + { + return clear_in_edges(u, g.graph()); + } + + + template <typename VProp, typename EProp> + void + remove_vertex(typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor u, + typename mlnu::boost_graph<VProp, EProp>& g) + { + return remove_vertex(u, g); + } + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace boost + +#endif // ! MLN_UTIL_INTERNAL_BOOST_GRAPH_STRUCTURE_HH_ Index: mln/util/internal/boost_graph_access.hh --- mln/util/internal/boost_graph_access.hh (revision 0) +++ mln/util/internal/boost_graph_access.hh (revision 0) @@ -0,0 +1,293 @@ +// Copyright (C) 2007, 2008 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to +// produce an executable, this file does not by itself cause the +// resulting executable to be covered by the GNU General Public +// License. +// reasons why the executable file might be covered by the GNU General +// Public License. + +/// \file mln/util/internal/boost_graph_access.hh +/// \brief boost_graph access operations. + +#ifndef MLN_UTIL_INTERNAL_BOOST_GRAPH_ACCESS_HH_ +# define MLN_UTIL_INTERNAL_BOOST_GRAPH_ACCESS_HH_ + + +# include <utility> + +/// fwd declaration +namespace mln +{ + namespace util + { + namespace internal + { + template <typename VertexProperty, typename EdgeProperty> + class boost_graph; + } + } +} + +namespace boost +{ + namespace mlnu = mln::util::internal; + + /// \brief Returns an iterator-range providing access to the vertex + /// set of graph g. + template <typename VProp, typename EProp> + std::pair<typename mlnu::boost_graph<VProp, EProp>::vertex_iterator, + typename mlnu::boost_graph<VProp, EProp>::vertex_iterator> + vertices(const mlnu::boost_graph<VProp, EProp>& g); + + + /// \brief Returns an iterator-range providing access to + /// the edge set of graph g. + template <typename VProp, typename EProp> + std::pair<typename mlnu::boost_graph<VProp, EProp>::edge_iterator, + typename mlnu::boost_graph<VProp, EProp>::edge_iterator> + edges(const mlnu::boost_graph<VProp, EProp>& g); + + + /// \brief Returns an iterator-range providing access to the vertices + /// adjacent to vertex u in graph g. + template <typename VProp, typename EProp> + std::pair<typename mlnu::boost_graph<VProp, EProp>::adjacency_iterator, + typename mlnu::boost_graph<VProp, EProp>::adjacency_iterator> + adjacent_vertices(typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor u, + const mlnu::boost_graph<VProp, EProp>& g); + + + /// \brief Returns an iterator-range providing access to the vertices in + /// graph g to which u is adjacent. (inv is for inverse.) + template <typename VProp, typename EProp> + std::pair<typename mlnu::boost_graph<VProp, EProp>::inv_adjacency_iterator, + typename mlnu::boost_graph<VProp, EProp>::inv_adjacency_iterator> + inv_adjacent_vertices(typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor u, + const mlnu::boost_graph<VProp, EProp>& g); + + /// \brief Returns an iterator-range providing access access to + /// all edges incident on vertex u. + template <typename VProp, typename EProp> + std::pair<typename mlnu::boost_graph<VProp, EProp>::out_edge_iterator, + typename mlnu::boost_graph<VProp, EProp>::out_edge_iterator> + out_edges(typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor u, + const mlnu::boost_graph<VProp, EProp>& g); + + /// FIXME: this operation is undefined for undirected graph + template <typename VProp, typename EProp> + std::pair<typename mlnu::boost_graph<VProp, EProp>::in_edge_iterator, + typename mlnu::boost_graph<VProp, EProp>::in_edge_iterator> + in_edges(typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor v, + const mlnu::boost_graph<VProp, EProp>& g); + + + /// \brief Returns the source vertex of edge e. + template <typename VProp, typename EProp> + typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor + source(typename mlnu::boost_graph<VProp, EProp>::edge_descriptor e, + const mlnu::boost_graph<VProp, EProp>& g); + + /// \brief Returns the target vertex of edge e. + template <typename VProp, typename EProp> + typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor + target(typename mlnu::boost_graph<VProp, EProp>::edge_descriptor e, + const mlnu::boost_graph<VProp, EProp>& g); + + /// \brief Returns the number of edges leaving vertex u. + template <typename V, typename E> + typename mlnu::boost_graph<V, E>::degree_size_type + out_degree(typename mlnu::boost_graph<V, E>::vertex_descriptor u, + const mlnu::boost_graph<V, E>& g); + + /// FIXME this operation is unavalaible for undirected graph. + template <typename VProp, typename EProp> + typename mlnu::boost_graph<VProp, EProp>::degree_size_type + in_degree(typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor u, + const mlnu::boost_graph<VProp, EProp>& g); + + /// \brief Returns the number of vertices in the graph g. + template <typename VProp, typename EProp> + typename mlnu::boost_graph<VProp, EProp>::vertices_size_type + num_vertices(const mlnu::boost_graph<VProp, EProp>& g); + + /// \brief Returns the number of edges in the graph g. + template <typename VProp, typename EProp> + typename mlnu::boost_graph<VProp, EProp>::edges_size_type + num_edges(const mlnu::boost_graph<VProp, EProp>& g); + + + /// \brief Returns the nth vertex in the graph's vertex list. + template <typename VProp, typename EProp> + typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor + vertex(typename mlnu::boost_graph<VProp, EProp>::vertices_size_type n, + const typename mlnu::boost_graph<VProp, EProp>& g); + + + /// \brief Returns an edge connecting vertex u to vertex v in graph g. + template <typename VProp, typename EProp> + std::pair<typename mlnu::boost_graph<VProp, EProp>::edge_descriptor, bool> + edge(typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor u, + typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor v, + const mlnu::boost_graph<VProp, EProp>& g); + + /// \brief Returns a pair of out-edge iterators that give the range for all + /// the parallel edges from u to v. + template <typename VProp, typename EProp> + std::pair<typename mlnu::boost_graph<VProp, EProp>::out_edge_iterator, + typename mlnu::boost_graph<VProp, EProp>::out_edge_iterator> + edge_range(typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor u, + typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor v, + const mlnu::boost_graph<VProp, EProp>& g); + +# ifndef MLN_INCLUDE_ONLY + + template <typename VProp, typename EProp> + std::pair<typename mlnu::boost_graph<VProp, EProp>::vertex_iterator, + typename mlnu::boost_graph<VProp, EProp>::vertex_iterator> + vertices(const mlnu::boost_graph<VProp, EProp>& g) + { + return vertices(g.graph()); + } + + template <typename VProp, typename EProp> + std::pair<typename mlnu::boost_graph<VProp, EProp>::edge_iterator, + typename mlnu::boost_graph<VProp, EProp>::edge_iterator> + edges(const mlnu::boost_graph<VProp, EProp>& g) + { + return edges(g.graph()); + } + + template <typename VProp, typename EProp> + std::pair<typename mlnu::boost_graph<VProp, EProp>::adjacency_iterator, + typename mlnu::boost_graph<VProp, EProp>::adjacency_iterator> + adjacent_vertices(typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor u, + const mlnu::boost_graph<VProp, EProp>& g) + { + return adjacent_vertices(u, g.graph()); + } + + template <typename VProp, typename EProp> + std::pair<typename mlnu::boost_graph<VProp, EProp>::inv_adjacency_iterator, + typename mlnu::boost_graph<VProp, EProp>::inv_adjacency_iterator> + inv_adjacent_vertices(typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor u, + const mlnu::boost_graph<VProp, EProp>& g) + { + return inv_adjacent_vertices(u, g.graph()); + } + + template <typename VProp, typename EProp> + std::pair<typename mlnu::boost_graph<VProp, EProp>::out_edge_iterator, + typename mlnu::boost_graph<VProp, EProp>::out_edge_iterator> + out_edges(typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor u, + const mlnu::boost_graph<VProp, EProp>& g) + { + return out_edges(u, g.graph()); + } + + template <typename VProp, typename EProp> + std::pair<typename mlnu::boost_graph<VProp, EProp>::in_edge_iterator, + typename mlnu::boost_graph<VProp, EProp>::in_edge_iterator> + in_edges(typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor v, + const mlnu::boost_graph<VProp, EProp>& g) + { + return in_edges(v, g.graph()); + } + + template <typename VProp, typename EProp> + typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor + source(typename mlnu::boost_graph<VProp, EProp>::edge_descriptor e, + const mlnu::boost_graph<VProp, EProp>& g) + { + return source(e, g.graph()); + } + + template <typename VProp, typename EProp> + typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor + target(typename mlnu::boost_graph<VProp, EProp>::edge_descriptor e, + const mlnu::boost_graph<VProp, EProp>& g) + { + return target(e, g.graph()); + } + + template <typename VProp, typename EProp> + typename mlnu::boost_graph<VProp, EProp>::degree_size_type + out_degree(typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor u, + const mlnu::boost_graph<VProp, EProp>& g) + { + return out_degree(u, g.graph()); + } + + template <typename VProp, typename EProp> + typename mlnu::boost_graph<VProp, EProp>::degree_size_type + in_degree(typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor u, + const mlnu::boost_graph<VProp, EProp>& g) + { + return in_degree(u, g.graph()); + } + + template <typename VProp, typename EProp> + typename mlnu::boost_graph<VProp, EProp>::vertices_size_type + num_vertices(const mlnu::boost_graph<VProp, EProp>& g) + { + return num_vertices(g.graph()); + } + + template <typename VProp, typename EProp> + typename mlnu::boost_graph<VProp, EProp>::edges_size_type + num_edges(const mlnu::boost_graph<VProp, EProp>& g) + { + return num_edges(g.graph()); + } + + template <typename VProp, typename EProp> + typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor + vertex(typename mlnu::boost_graph<VProp, EProp>::vertices_size_type n, + const typename mlnu::boost_graph<VProp, EProp>& g) + { + return vertex(n, g.graph()); + } + + template <typename VProp, typename EProp> + std::pair<typename mlnu::boost_graph<VProp, EProp>::edge_descriptor, + bool> + edge(typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor u, + typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor v, + const mlnu::boost_graph<VProp, EProp>& g) + { + return edge(u, v, g.graph()); + } + + template <typename VProp, typename EProp> + std::pair<typename mlnu::boost_graph<VProp, EProp>::out_edge_iterator, + typename mlnu::boost_graph<VProp, EProp>::out_edge_iterator> + edge_range(typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor u, + typename mlnu::boost_graph<VProp, EProp>::vertex_descriptor v, + const mlnu::boost_graph<VProp, EProp>& g) + { + return edge_range(u, v, g.graph()); + } + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace boost + +#endif // ! MLN_UTIL_INTERNAL_BOOST_GRAPH_ACCESS_HH_ Index: mln/util/internal/boost_graph_property.hh --- mln/util/internal/boost_graph_property.hh (revision 0) +++ mln/util/internal/boost_graph_property.hh (revision 0) @@ -0,0 +1,171 @@ +// Copyright (C) 2007, 2008 EPITA Research and Development Laboratory (LRDE) +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to +// produce an executable, this file does not by itself cause the +// resulting executable to be covered by the GNU General Public +// License. +// reasons why the executable file might be covered by the GNU General +// Public License. + +/// \file mln/util/internal/boost_graph_property.hh +/// \brief boost_graph properties access operations. + +#ifndef MLN_UTIL_INTERNAL_BOOST_GRAPH_PROPERTY_HH_ +# define MLN_UTIL_INTERNAL_BOOST_GRAPH_PROPERTY_HH_ + +# include <utility> +# include <boost/graph/adjacency_list.hpp> + +/// fwd declaration +namespace mln +{ + namespace util + { + namespace internal + { + template <typename VertexProperty, typename EdgeProperty> + class boost_graph; + } + } +} + +namespace boost +{ + namespace mlnu = mln::util::internal; + + + /// \brief Returns the property map object for the vertex property + /// specified by PropertyTag. + template <typename VProp, typename EProp, typename PropertyTag> + typename property_map<typename mlnu::boost_graph<EProp, VProp>::decorated, + PropertyTag>::type + get(PropertyTag, typename mlnu::boost_graph<VProp, EProp>& g); + + + /// \brief Returns the property map object for the vertex property + /// specified by PropertyTag (const version). + template <typename VProp, typename EProp, typename PropertyTag> + typename property_map<typename mlnu::boost_graph<EProp, VProp>::decorated, + PropertyTag>::const_type + get(PropertyTag, const mlnu::boost_graph<VProp, EProp>& g); + + + /// \brief This returns the property value for x. + /// x is either a vertex or edge descriptor. + template <typename VProp, typename EProp, typename PropertyTag, typename X> + typename property_traits< + typename property_map<typename mlnu::boost_graph<EProp, VProp>::decorated, + PropertyTag>::const_type >::value_type + get(PropertyTag, const mlnu::boost_graph<VProp, EProp>& g, X x); + + + /// \brief This sets the property value for x to value. + /// x is either a vertex or edge descriptor. + template <typename VProp, typename EProp, + typename PropertyTag, typename X, typename Value> + void + put(PropertyTag, const mlnu::boost_graph<VProp, EProp>& g, + X x, const Value& value); + + + /// \brief Return the property specified by GraphPropertyTag. + template <typename EProp, typename VProp, typename GraphProperties, + typename GraphPropertyTag> + typename graph_property<typename mlnu::boost_graph<EProp, VProp>::decorated, + GraphPropertyTag>::type& + get_property(mlnu::boost_graph<VProp, EProp>& g, GraphPropertyTag); + + + /// \brief Return the property specified by GraphPropertyTag. + template <typename VProp, typename EProp, + typename GraphProperties, typename GraphPropertyTag> + const typename graph_property< + typename mlnu::boost_graph<EProp, VProp>::decorated, + GraphPropertyTag>::type& + get_property(const mlnu::boost_graph<VProp, EProp>& g, + GraphPropertyTag); + +# ifndef MLN_INCLUDE_ONLY + + template <typename VProp, typename EProp, typename PropertyTag> + typename property_map<typename mlnu::boost_graph<EProp, VProp>::decorated, + PropertyTag>::type + get(PropertyTag property_tag, + typename mlnu::boost_graph<VProp, EProp>& g) + { + return get(property_tag, g.graph()); + } + + template <typename VProp, typename EProp, typename PropertyTag> + typename property_map<typename mlnu::boost_graph<EProp, VProp>::decorated, + PropertyTag>::const_type + get(PropertyTag property_tag, + const mlnu::boost_graph<VProp, EProp>& g) + { + return get(property_tag, g.graph()); + } + + template <typename VProp, typename EProp, + typename PropertyTag, typename X> + typename property_traits< + typename property_map< + typename mlnu::boost_graph<EProp, VProp>::decorated, + PropertyTag>::const_type>::value_type + get(PropertyTag property_tag, const mlnu::boost_graph<VProp, EProp>& g, X x) + { + return get(property_tag, g.graph(), x); + } + + template <typename VProp, typename EProp, + typename PropertyTag, typename X, typename Value> + void + put(PropertyTag property_tag, const mlnu::boost_graph<VProp, EProp>& g, + X x, const Value& value) + { + put(property_tag, g.graph(), x, value); + } + + template <typename EProp, typename VProp, + typename GraphProperties, typename GraphPropertyTag> + typename graph_property<typename mlnu::boost_graph<EProp, VProp>::decorated, + GraphPropertyTag>::type& + get_property(mlnu::boost_graph<VProp, EProp>& g, + GraphPropertyTag property_tag) + { + return get_property(g.graph(), property_tag); + } + + template <typename VProp, typename EProp, + typename GraphProperties, typename GraphPropertyTag> + const typename graph_property< + typename mlnu::boost_graph<EProp, VProp>::decorated, + GraphPropertyTag>::type& + get_property(const mlnu::boost_graph<VProp, EProp>& g, + GraphPropertyTag property_tag) + { + return get_property(g.graph(), property_tag); + } + +# endif // ! MLN_INCLUDE_ONLY + +} + +#endif // ! MLN_UTIL_INTERNAL_BOOST_GRAPH_PROPERTY_HH_