[Olena-patches] 2448: Add a new util::graph implementation. The graph does not store data anymore.

--- milena/mln/core/concept/graph.hh | 150 ++++ milena/mln/core/internal/graph_iter_base.hh | 135 ++++ milena/mln/core/macros.hh | 53 ++ milena/mln/util/graph.hh | 284 ++------ milena/mln/util/internal/graph_base.hh | 742 +++++++------------- milena/mln/util/internal/graph_edge.hh | 378 ++++++++++ milena/mln/util/internal/graph_edge_iter.hh | 273 +++++++ .../mln/util/internal/graph_edge_nbh_edge_iter.hh | 335 +++++++++ milena/mln/util/internal/graph_vertex.hh | 361 ++++++++++ milena/mln/util/internal/graph_vertex_iter.hh | 266 +++++++ .../util/internal/graph_vertex_nbh_edge_iter.hh | 323 +++++++++ .../util/internal/graph_vertex_nbh_vertex_iter.hh | 320 +++++++++ milena/tests/util/graph.cc | 107 +++- 13 files changed, 3013 insertions(+), 714 deletions(-) create mode 100644 milena/mln/core/concept/graph.hh create mode 100644 milena/mln/core/internal/graph_iter_base.hh create mode 100644 milena/mln/util/internal/graph_edge.hh create mode 100644 milena/mln/util/internal/graph_edge_iter.hh create mode 100644 milena/mln/util/internal/graph_edge_nbh_edge_iter.hh create mode 100644 milena/mln/util/internal/graph_vertex.hh create mode 100644 milena/mln/util/internal/graph_vertex_iter.hh create mode 100644 milena/mln/util/internal/graph_vertex_nbh_edge_iter.hh create mode 100644 milena/mln/util/internal/graph_vertex_nbh_vertex_iter.hh diff --git a/milena/mln/core/concept/graph.hh b/milena/mln/core/concept/graph.hh new file mode 100644 index 0000000..36d94c9 --- /dev/null +++ b/milena/mln/core/concept/graph.hh @@ -0,0 +1,150 @@ +// Copyright (C) 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. + +#ifndef MLN_CORE_CONCEPT_GRAPH_HH +# define MLN_CORE_CONCEPT_GRAPH_HH + +/*! \file mln/core/concept/graph.hh + * \brief Definition of the concept of mln::Graph. + */ + +namespace mln +{ + + + // Fwd decl. + template <typename E> struct Graph; + + // Graph category flag type. + template <> + struct Graph<void> + { + typedef Object<void> super; + }; + + /*! \brief Base class for implementation of graph classes. + * + * \see mln::doc::Graph for a complete documentation of this class + * contents. + */ + template <typename E> + struct Graph : public Object<E> + { + typedef Graph<void> category; + + /* + // provided by internal::image_base: + + typedef pset; + typedef site; + typedef psite; + + typedef fwd_piter; + typedef bkd_piter; + + // Misc. + void *graph_id() const; + template<typename G2> + bool is_subgraph_of(const G2& gr) const; + + // Vertex and edges oriented. + unsigned v_other(unsigned id_e, unsigned id_v) const; + + // Vertex oriented. + size_t v_nmax() const; + bool has_v(unsigned id_v) const; + size_t v_nmax_nbh_edges(unsigned id_v) const; + unsigned v_ith_nbh_edge(unsigned id_v, unsigned i) const; + + // Edge oriented. + size_t e_nmax() const; + bool has_e(unsigned id_e) const; + unsigned v1(unsigned id_e) const; + unsigned v2(unsigned id_e) const; + size_t e_nmax_nbh_edges(unsigned id_e) const; + unsigned e_ith_nbh_edge(unsigned id_e, unsigned i) const; + + */ + + protected: + Graph(); + }; + + +# ifndef MLN_INCLUDE_ONLY + + template <typename E> + inline + Graph<E>::Graph() + { + // provided by internal::graph_base: + + //typedef mln_psite(E) psite; + + //typedef mln_fwd_piter(E) fwd_piter; + //typedef mln_bkd_piter(E) bkd_piter; + + // Check methods + const void * const(E::*m1)() const = & E::graph_id; + m1 = 0; + unsigned (E::*m2)(unsigned id_e, unsigned id_v) const = & E::v_other; + m2 = 0; + unsigned (E::*m3)() = & E::add_vertex; + m3 = 0; + size_t (E::*m4)() const = & E::v_nmax; + m4 = 0; + bool (E::*m5)(unsigned id_v) const = & E::has_v; + m5 = 0; + size_t (E::*m6)(unsigned id_v) const = & E::v_nmax_nbh_edges; + m6 = 0; + unsigned (E::*m7)(unsigned id_v, unsigned i) const = & E::v_ith_nbh_edge; + m7 = 0; + size_t (E::*m8)() const = & E::e_nmax; + m8 = 0; + bool (E::*m9)(unsigned id_e) const = & E::has_e; + m9 = 0; + unsigned (E::*m10)(unsigned id_e) const = & E::v1; + m10 = 0; + unsigned (E::*m11)(unsigned id_e) const = & E::v2; + m11 = 0; + size_t (E::*m12)(unsigned id_e) const = & E::e_nmax_nbh_edges; + m12 = 0; + unsigned (E::*m13)(unsigned id_e, unsigned i) const = & E::e_ith_nbh_edge; + m13 = 0; + + //FIXME: enable this test. Currently does not work because this is + // a templated method. + //bool (E::*m14)(...) = & E::is_subgraph_of; + //m14 = 0; +} + +# endif // ! MLN_INCLUDE_ONLY + +} // end of namespace mln + +#endif // ! MLN_CORE_CONCEPT_GRAPH_HH + diff --git a/milena/mln/core/internal/graph_iter_base.hh b/milena/mln/core/internal/graph_iter_base.hh new file mode 100644 index 0000000..2d7297c --- /dev/null +++ b/milena/mln/core/internal/graph_iter_base.hh @@ -0,0 +1,135 @@ +// Copyright (C) 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. This exception does not however invalidate any other +// reasons why the executable file might be covered by the GNU General +// Public License. + +#ifndef MLN_CORE_INTERNAL_GRAPH_ITER_BASE_HH +# define MLN_CORE_INTERNAL_GRAPH_ITER_BASE_HH + +# include <mln/core/concept/iterator.hh> +# include <mln/core/concept/proxy.hh> + +/// \file mln/core/internal/graph_iter_base.hh +/// \brief Base class for graph iterators. + +namespace mln +{ + + namespace internal + { + + /// Base class for graph iterators + /// \p G graph type. + /// \p S the type of the data pointed by the iterator. + /// For instance : edge, vertex.... + template<typename G, typename S> + class graph_iterator_base + : public Iterator< graph_iterator_base<G> >, + public internal::proxy_impl< const S&, graph_iterator_base<G> > + { + public: + /// Constructors. + /// \{ + graph_iterator_base(); + graph_iterator_base(const G& g); + /// \} + + /// Iterator interface. + /// \{ + /// Test if the iterator is valid. + bool is_valid() const; + /// Invalidate the iterator. + void invalidate(); + + /// Start an iteration. + void start(); + + /// Go to the next value. + void next_(); + + /// Return current index + unsigned index() const; + /// \} + + /// Proxy. + /// \{ + /// Proxy subject + const S& subj_(); + /// \} + + protected: + const G *g_; + unsigned i_; + }; + + + template<typename G, typename S> + class graph_fwd_iterator_base + : public Iterator< graph_fwd_iterator_base<G> >, + public internal::proxy_impl< const S&, graph_fwd_iterator_base<G> > + { + public: + /// Construction and assignment. + /// \{ + graph_fwd_iterator_base(); + graph_fwd_iterator_base(const G& g); + /// \} + + /// Manipulation. + /// \{ + /// Test if the iterator is valid. + bool is_valid() const; + /// Invalidate the iterator. + void invalidate(); + /// \} + + /// Start an iteration. + void start(); + + /// Go to the next value. + void next_(); + + /// Return current index + unsigned index() const; + + /// Proxy. + /// \{ + /// Proxy Subject type + typedef const mln_vertex(G)& q_subject; + + /// Proxy subject + q_subject subj_(); + /// \} + + protected: + const G *g_; + unsigned i_; + }; + + } // End of namespace mln::internal. + +} // End of namespace mln. + +#endif // !MLN_CORE_INTERNAL_GRAPH_ITER_BASE_HH diff --git a/milena/mln/core/macros.hh b/milena/mln/core/macros.hh index 3b0b88c..3dc9036 100644 --- a/milena/mln/core/macros.hh +++ b/milena/mln/core/macros.hh @@ -418,5 +418,58 @@ # define mln_nixter(I, N) mln_fwd_nixter(I, N) # define mln_nixter_(I, N) mln_fwd_nixter_(I, N) +/// Shortcuts to access the vertex iterator type associated to a graph G. +/// \{ +# define mln_vertex_iter(G) typename G::vertex_iter +# define mln_vertex_iter_(G) G::vertex_iter +# define mln_vertex_fwd_iter(G) typename G::vertex_fwd_iter +# define mln_vertex_fwd_iter_(G) G::vertex_fwd_iter +# define mln_vertex_bkd_iter(G) typename G::vertex_bkd_iter +# define mln_vertex_bkd_iter_(G) G::vertex_bkd_iter +/// \} + +/// Shortcuts to access the edge iterator type associated to a graph G. +/// \{ +# define mln_edge_iter(G) typename G::edge_iter +# define mln_edge_iter_(G) G::edge_iter +# define mln_edge_fwd_iter(G) typename G::edge_fwd_iter +# define mln_edge_fwd_iter_(G) G::edge_fwd_iter +# define mln_edge_bkd_iter(G) typename G::edge_bkd_iter +# define mln_edge_bkd_iter_(G) G::edge_bkd_iter +/// \} + +/// Shortcuts to access the vertex centered edge neighbors iterator type +/// associated to a graph G. +/// \{ +# define mln_vertex_nbh_vertex_iter(G) typename G::vertex_nbh_vertex_iter +# define mln_vertex_nbh_vertex_iter_(G) G::vertex_nbh_vertex_iter +# define mln_vertex_nbh_vertex_fwd_iter(G) typename G::vertex_nbh_vertex_fwd_iter +# define mln_vertex_nbh_vertex_fwd_iter_(G) G::vertex_nbh_vertex_fwd_iter +# define mln_vertex_nbh_vertex_bkd_iter(G) typename G::vertex_nbh_vertex_bkd_iter +# define mln_vertex_nbh_vertex_bkd_iter_(G) G::vertex_nbh_vertex_bkd_iter +/// \} + +/// Shortcuts to access the vertex centered edge neighbors iterator type +/// associated to a graph G. +/// \{ +# define mln_vertex_nbh_edge_iter(G) typename G::vertex_nbh_edge_iter +# define mln_vertex_nbh_edge_iter_(G) G::vertex_nbh_edge_iter +# define mln_vertex_nbh_edge_fwd_iter(G) typename G::vertex_nbh_edge_fwd_iter +# define mln_vertex_nbh_edge_fwd_iter_(G) G::vertex_nbh_edge_fwd_iter +# define mln_vertex_nbh_edge_bkd_iter(G) typename G::vertex_nbh_edge_bkd_iter +# define mln_vertex_nbh_edge_bkd_iter_(G) G::vertex_nbh_edge_bkd_iter +/// \} + +/// Shortcuts to access the edge centered edge neighbors iterator type +/// associated to a graph G. +/// \{ +# define mln_edge_nbh_edge_iter(G) typename G::edge_nbh_edge_iter +# define mln_edge_nbh_edge_iter_(G) G::edge_nbh_edge_iter +# define mln_edge_nbh_edge_fwd_iter(G) typename G::edge_nbh_edge_fwd_iter +# define mln_edge_nbh_edge_fwd_iter_(G) G::edge_nbh_edge_fwd_iter +# define mln_edge_nbh_edge_bkd_iter(G) typename G::edge_nbh_edge_bkd_iter +# define mln_edge_nbh_edge_bkd_iter_(G) G::edge_nbh_edge_bkd_iter +/// \} #endif // ! MLN_CORE_MACROS_HH + diff --git a/milena/mln/util/graph.hh b/milena/mln/util/graph.hh index 0273bd8..ba148d3 100644 --- a/milena/mln/util/graph.hh +++ b/milena/mln/util/graph.hh @@ -32,281 +32,97 @@ /// \brief Definitions of undirected graphs. # include <mln/util/internal/graph_base.hh> +# include <mln/util/internal/graph_vertex_iter.hh> +# include <mln/util/internal/graph_edge_iter.hh> +# include <mln/util/internal/graph_vertex_nbh_vertex_iter.hh> +# include <mln/util/internal/graph_vertex_nbh_edge_iter.hh> +# include <mln/util/internal/graph_edge_nbh_edge_iter.hh> namespace mln { namespace util { - /*-----------. - | Fwd decl. | - `-----------*/ /// \brief Undirected graph. - template<typename V = void, typename E = void> - class graph; - - /*--------------------. - | graph<void, void>. | - `--------------------*/ - - /// Specialization for undirected graphs with no data on vertices nor - /// on edges. - template <> - class graph<void, void> : public internal::graph_base<void, void> + class graph : public internal::graph_base<graph> { public: /// The super class. - typedef internal::graph_base<void, void> super; - - /// \brief Add a vertex. - /// - /// \return The id of the new vertex. - vertex_id add_vertex(); - /// \brief Add an edge between vertices with ids \p v1 and \p v2. - /// - /// \return The id of the new edge if it does not exist yet; - /// otherwise, return <tt>mln_max(edge_id)</tt>. - edge_id add_edge(vertex_id v1, vertex_id v2); - }; - - /*-----------------. - | graph<V, void>. | - `-----------------*/ + typedef internal::graph_base<graph> super; - /// Specialization for undirected graphs with data on vertices. - template <typename V> - class graph<V, void> : public internal::graph_base<V, void> - { - public: - /// The super class. - typedef internal::graph_base<V, void> super; - - /// \brief Add a vertex. - /// - /// \return The id of the new vertex. - vertex_id add_vertex(const V& data); - /// \brief Add an edge between vertices with ids \p v1 and \p v2. - /// - /// \return The id of the new edge if it does not exist yet; - /// otherwise, return <tt>mln_max(edge_id)</tt>. - edge_id add_edge(vertex_id v1, vertex_id v2); + /// Iterator types + /// \{ - /// Return the data associated to vertex with id \a v. + /// Vertex iterators /// \{ - V& vertex_data(vertex_id v); - const V& vertex_data(vertex_id v) const; + typedef mln::internal::vertex_fwd_iterator<graph> vertex_fwd_iter; + typedef mln::internal::vertex_bkd_iterator<graph> vertex_bkd_iter; + typedef vertex_fwd_iter vertex_iter; /// \} - }; - /*--------------. - | graph<V, E>. | - `--------------*/ - - /// Specialization for undirected graphs with data on vertices and - /// edges. - template <typename V, typename E> - class graph : public internal::graph_base<V, E> - { - public: - /// The super class. - typedef internal::graph_base<V, E> super; - - /// \brief Add a vertex. - /// - /// \return The id of the new vertex. - vertex_id add_vertex(const V& data); - /// \brief Add an edge between vertices with ids \p v1 and \p v2. - /// - /// \return The id of the new edge if it does not exist yet; - /// otherwise, return <tt>mln_max(edge_id)</tt>. - edge_id add_edge(vertex_id v1, vertex_id v2, const E& data); - - /// Return the data associated to vertex with id \a v. + /// Vertex centered edge iterators /// \{ - V& vertex_data(vertex_id v); - const V& vertex_data(vertex_id v) const; + typedef mln::internal::vertex_nbh_edge_fwd_iterator<graph> vertex_nbh_edge_fwd_iter; + typedef mln::internal::vertex_nbh_edge_bkd_iterator<graph> vertex_nbh_edge_bkd_iter; + typedef vertex_nbh_edge_fwd_iter vertex_nbh_edge_iter; /// \} - /// Return the data associated to the edge with id \a e. + /// Vertex centered vertex iterators /// \{ - E& edge_data(edge_id e); - const E& edge_data(edge_id e) const; + typedef mln::internal::vertex_nbh_vertex_fwd_iterator<graph> vertex_nbh_vertex_fwd_iter; + typedef mln::internal::vertex_nbh_vertex_bkd_iterator<graph> vertex_nbh_vertex_bkd_iter; + typedef vertex_nbh_vertex_fwd_iter vertex_nbh_vertex_iter; /// \} - /// Return the data associated to the edge between vertices with - /// ids \a v1 and \a v2. + /// Edge iterators /// \{ - E& edge_data(vertex_id v1, vertex_id v2); - const E& edge_data(vertex_id v1, vertex_id v2) const; + typedef mln::internal::edge_fwd_iterator<graph> edge_fwd_iter; + typedef mln::internal::edge_bkd_iterator<graph> edge_bkd_iter; + typedef edge_fwd_iter edge_iter; /// \} - }; - - - -# ifndef MLN_INCLUDE_ONLY - - /*--------------------. - | graph<void, void>. | - `--------------------*/ - - /* Note that definition of members from fully specialized - template classes are not preceded by `template<>'. */ - inline - vertex_id - graph<void, void>::add_vertex() - { - return super::add_vertex_(new util::vertex<void>); - } - - /* Note that ddefinition of members from fully specialized - template classes are not preceded by `template<>'. */ - inline - edge_id - graph<void, void>::add_edge(vertex_id v1, vertex_id v2) - { - mln_assertion(v1 < this->nvertices()); - mln_assertion(v2 < this->nvertices()); - return super::add_edge_(new util::edge<void>(v1, v2)); - } - - /*-----------------. - | graph<V, void>. | - `-----------------*/ - template<typename V> - inline - vertex_id - graph<V, void>::add_vertex(const V& data) - { - return super::add_vertex_(new util::vertex<V>(data)); - } - - template<typename V> - inline - edge_id - graph<V, void>::add_edge(vertex_id v1, vertex_id v2) - { - mln_assertion(v1 < this->nvertices()); - mln_assertion(v2 < this->nvertices()); - return super::add_edge_(new util::edge<void>(v1, v2)); - } - - template <class V> - inline - V& - graph<V, void>::vertex_data(vertex_id v) - { - mln_assertion(v < this->nvertices()); - return this->vertices_[v]->data; - } + /// Edge centered edge iterators. + /// \{ + typedef mln::internal::edge_nbh_edge_fwd_iterator<graph> edge_nbh_edge_fwd_iter; + typedef mln::internal::edge_nbh_edge_bkd_iterator<graph> edge_nbh_edge_bkd_iter; + typedef edge_nbh_edge_fwd_iter edge_nbh_edge_iter; + /// \} - template<typename V> - inline - const V& - graph<V, void>::vertex_data(vertex_id v) const - { - mln_assertion(v < this->nvertices()); - return this->vertices_[v]->data; - } + /// \} + /// Return whether this graph is a subgraph + /// Return always false here. + template <typename G2> + bool is_subgraph_of(const G2& g); + }; - /*--------------. - | graph<V, E>. | - `--------------*/ + } // end of namespace mln::util - template<typename V, typename E> - inline - vertex_id - graph<V, E>::add_vertex(const V& data) - { - return super::add_vertex_(new util::vertex<V>(data)); - } +} // end of namespace mln - template<typename V, typename E> - inline - edge_id - graph<V, E>::add_edge(vertex_id v1, vertex_id v2, const E& data) - { - mln_assertion(v1 < this->nvertices()); - mln_assertion(v2 < this->nvertices()); - return super::add_edge_(new util::edge<E>(v1, v2, data)); - } - template<typename V, typename E> - inline - V& - graph<V, E>::vertex_data(vertex_id v) - { - mln_assertion(v < this->nvertices()); - return this->vertices_[v]->data; - } +# ifndef MLN_INCLUDE_ONLY - template<typename V, typename E> - inline - const V& - graph<V, E>::vertex_data(vertex_id v) const - { - mln_assertion(v < this->nvertices()); - return this->vertices_[v]->data; - } +namespace mln +{ - template<typename V, typename E> - inline - E& - graph<V, E>::edge_data(edge_id e) - { - mln_assertion(e < this->nedges()); - return this->edges_[e]->data; - } + namespace util + { - template<typename V, typename E> + template <typename G2> inline - const E& - graph<V, E>::edge_data(edge_id e) const + bool + graph::is_subgraph_of(const G2& g) { - mln_assertion(e < this->nedges()); - return this->edges_[e]->data; + return false; } - template<typename V, typename E> - inline - E& - graph<V, E>::edge_data(vertex_id v1, vertex_id v2) - { - mln_assertion(v1 < this->nvertices()); - mln_assertion(v2 < this->nvertices()); - ord_pair<vertex_id> vertex_pair (v1, v2); - std::vector<edge_id>& edges_ids = this->vertices_[v1]->edges; - for (std::vector<edge_id>::iterator e = edges_ids.begin(); - e != edges_ids.end(); ++e) - if (this->edges_[*e] == vertex_pair) - return this->edges_[*e]->data; - // If no edge between V1 and V2 was found, abort. - abort(); - } + } // end of namespace mln::util - template<typename V, typename E> - inline - const E& - graph<V, E>::edge_data(vertex_id v1, vertex_id v2) const - { - mln_assertion(v1 < this->nvertices()); - mln_assertion(v2 < this->nvertices()); - ord_pair<vertex_id> vertex_pair (v1, v2); - const std::vector<edge_id>& edges_ids = this->vertices_[v1]->edges; - for (std::vector<edge_id>::const_iterator e = edges_ids.begin(); - e != edges_ids.end(); ++e) - if (this->edges_[*e] == vertex_pair) - return this->edges_[*e]->data; - // If no edge between V1 and V2 was found, abort. - abort(); - } +} // end of namespace mln # endif // ! MLN_INCLUDE_ONLY - } // end of namespace mln::util - -} // end of namespace mln #endif // ! MLN_UTIL_GRAPH_HH diff --git a/milena/mln/util/internal/graph_base.hh b/milena/mln/util/internal/graph_base.hh index d6fb437..17143c5 100644 --- a/milena/mln/util/internal/graph_base.hh +++ b/milena/mln/util/internal/graph_base.hh @@ -39,14 +39,15 @@ # include <set> # include <ostream> -// For gen_id. -# include <mln/value/builtin/all.hh> - # include <mln/core/concept/object.hh> +# include <mln/core/concept/graph.hh> +# include <mln/core/concept/proxy.hh> # include <mln/util/ord_pair.hh> # include <mln/value/builtin/integers.hh> +# include <mln/util/internal/graph_edge.hh> +# include <mln/util/internal/graph_vertex.hh> namespace mln { @@ -54,391 +55,151 @@ namespace mln namespace util { - /*--------------. - | Identifiers. | - `--------------*/ - - /// \brief Generic identifier/handler. - /// - /// Inspired by Vaucansons's handlers for automata. - /// - /// https://svn.lrde.epita.fr/svn/vaucanson/trunk/include/vaucanson/automata/con... - /// https://svn.lrde.epita.fr/svn/vaucanson/trunk/include/vaucanson/automata/con... - /// - /// \todo We /might/ want to integrate this into Milena's value system. - /// - /// \todo Move this class elsewhere? - - template <typename Tag, typename Equiv> - class gen_id : public Object< gen_id < Tag, Equiv > > - { - typedef gen_id<Tag, Equiv> self_t; - - public: - typedef Equiv equiv; - - gen_id(); - gen_id(const Equiv& e); - self_t& operator=(const Equiv& e); - - const equiv& to_equiv() const; - equiv& to_equiv(); - operator const equiv() const; - operator equiv(); - - private: - equiv e_; - }; - - - /// Compare two identifiers. - /// \{ - template <typename Tag, typename Equiv> - bool - operator==(const gen_id<Tag, Equiv>& i, const gen_id<Tag, Equiv>& j); - - template <typename Tag, typename Equiv> - bool - operator==(const Equiv& i, const gen_id<Tag, Equiv>& j); - - template <typename Tag, typename Equiv> - bool - operator==(const gen_id<Tag, Equiv>& i, const Equiv j); - - - template <typename Tag, typename Equiv> - bool - ord_strict(const gen_id<Tag, Equiv>& i, const gen_id<Tag, Equiv>& j); - - template <typename Tag, typename Equiv> - bool - ord_weak(const gen_id<Tag, Equiv>& i, const gen_id<Tag, Equiv>& j); - /// \} - - - /// Tags. - /// \{ - struct vertex_tag; - struct edge_tag; - /// \} - - - /// \brief The type used to identify vertices. - /// - /// Used internally as a key to manipulate vertices. - typedef gen_id<vertex_tag, unsigned> vertex_id; - - /// \brief The type used to identify edges. - /// - /// Used internally as a key to manipulate edges. - typedef gen_id<edge_tag, unsigned> edge_id; - - - /*---------. - | Vertex. | - `---------*/ - - /// \brief Vertex of a graph, holding a value of type \p T. - template<typename T> - struct vertex - { - vertex(T data) - : data(data) - {} - - T data; - std::vector<edge_id> edges; - }; - - /// \brief Specialization of mln::util::vertex for vertices with no - /// associated value. - template <> - struct vertex<void> - { - std::vector<edge_id> edges; - }; - - - /*-------. - | Edge. | - `-------*/ - - /// \brief Edge of a graph, holding a value of type \p T. - template<typename T> - struct edge - { - edge(vertex_id v1, vertex_id v2) - : pair_vertex_(v1, v2) - {} - - /// Return the lowest vertex id adjacent to this edge. - vertex_id v1() const { return pair_vertex_.first(); } - /// Return the highest vertex id adjacent to this edge. - vertex_id v2() const { return pair_vertex_.second(); } - - T data; - ord_pair<vertex_id> pair_vertex_; - }; - - /// \brief Specialization of mln::util::vertex for edges with no - /// associated value. - template <> - struct edge<void> - { - edge(vertex_id v1, vertex_id v2) - : pair_vertex_(v1, v2) - {} - - /// Return the lowest vertex id adjacent to this edge. - vertex_id v1() const { return pair_vertex_.first(); } - /// Return the highest vertex id adjacent to this edge. - vertex_id v2() const { return pair_vertex_.second(); } - - ord_pair<vertex_id> pair_vertex_; - }; - - // FIXME: Document this. In particular, we should state that edges are - // only compared w.r.t. their adjacent vertices, not the data they - // possibly hold! - template <typename E> - bool - operator==(const edge<E>& lhs, const edge<E>& rhs); - - template <typename E> - bool - operator< (const edge<E>& lhs, const edge<E>& rhs); - - /*-------------. | Graph base. | `-------------*/ namespace internal { - // FIXME: This should be no longer useful once vertices and edges - // are handled without pointers and dynamic allocation. - template <typename T> - struct less_ptr - { - bool - operator()(const T& a, const T& b) - { - mln_assertion(a); - mln_assertion(b); - return (*a < *b); - } - }; - - /// \brief Base class for undirected graphs. - template<typename V, typename E> - class graph_base + template<typename E> + class graph_base : public Graph<E> { - typedef graph_base<V, E> self_t; - - public: - /* FIXME: Do we really want handle vertices and edges through - pointers? In my (Roland) opinion, this is just a drawback, - here. */ + /// The type of a vertex. + typedef util::vertex<E> vertex_t; + /// Internal vertex data type + typedef std::vector<unsigned> vertex_data_t; /// The type of the set of vertices. - typedef std::vector< util::vertex<V>* > vertices_t; + typedef std::vector<vertex_data_t> vertices_t; + + /// The type of an edge. + typedef util::edge<E> edge_t; + /// Internal edge data type. + typedef ord_pair<unsigned> edge_data_t; /// The type of the set of edges. - typedef std::vector< util::edge<E>* > edges_t; + typedef std::vector<edge_data_t> edges_t; /// A set to test the presence of a given edge. - typedef std::set< util::edge<E>*, - less_ptr< util::edge<E>* > > edges_set_t; + typedef std::set<edge_data_t> edges_set_t; - /// Construction, assignments and destruction. + public: + /// Misc. methods /// \{ - graph_base(); - graph_base(const self_t& rhs); - self_t& operator=(const self_t& rhs); - ~graph_base(); + /// Returns the graph id, the "this" pointer. + const void * const graph_id() const; /// \} - /// Return the vertex whose id is \a v. + /// Vertex and edge oriented methods. /// \{ - util::vertex<V>& vertex(vertex_id v); - const util::vertex<V>& vertex(vertex_id v) const; + /// Returns the other adjacent vertex id of a given edge id \p id_e. + unsigned v_other(unsigned id_e, unsigned id_v) const; /// \} - /// Return the edge whose id is \a e. - /// \{ - util::edge<E>& edge(edge_id e); - const util::edge<E>& edge(edge_id e) const; - /// \} - /// Return the whole vertices of the graph. + /// Vertex oriented. + /// \{ + + /// Shortcuts factoring the insertion of vertices and edges. /// \{ - vertices_t& vertices(); - const vertices_t& vertices() const; - /// \} + /// \brief Add a vertex. + /// + /// \return The id of the new vertex. + unsigned add_vertex(); - /// Return the whole edges of the graph. + /// Return the vertex whose id is \a v. /// \{ - edges_t& edges(); - const edges_t& edges() const; + vertex_t vertex(unsigned id_v) const; /// \} /// \brief Return the number of vertices in the graph. - size_t nvertices() const; - /// \brief Return the number of edges in the graph. - size_t nedges() const; + size_t v_nmax() const; - // FIXME: We might want to externalize this in routine of - // namespace mln::debug. - /** \brief Print on \p ostr the graph. + /// Check whether a vertex id \p id_v is valid in the graph. + bool has_v(unsigned id_v) const; - \param[in] ostr The output stream. */ - void print_debug(std::ostream& ostr) const; + /// Return the number of adjacent edges of vertex \p id_v. + size_t v_nmax_nbh_edges(unsigned id_v) const; - protected: - /// Shortcuts factoring the insertion of vertices and edges. + /// Returns the \p i th edge adjacent to the vertex \p id_v. + unsigned v_ith_nbh_edge(unsigned id_v, unsigned i) const; + + /// Return the number of adjacent vertices of vertex \p id_v. + size_t v_nmax_nbh_vertices(unsigned id_v) const; + + /// Returns the \p i th vertex adjacent to the vertex \p id_v. + unsigned v_ith_nbh_vertex(unsigned id_v, unsigned i) const; + + /// \} + + + /// Edge oriented. /// \{ - /// \brief Add a vertex. - /// - /// \return The id of the new vertex. - vertex_id add_vertex_(util::vertex<V>* vertex); /// \brief Add an edge. /// /// \return The id of the new edge if it does not exist yet; - /// otherwise, return <tt>mln_max(edge_id)</tt>. - edge_id add_edge_(util::edge<E>* edge); + /// otherwise, return <tt>mln_max(unsigned)</tt>. + unsigned add_edge(unsigned id_v1, unsigned id_v2); /// \} - protected: - /// The vertices. - vertices_t vertices_; - /// The edges. - edges_t edges_; - /// An index of the set of edges, for fast-access purpose. - edges_set_t edges_set_; - }; - - } // end of namespace mln::util::internal - - - -# ifndef MLN_INCLUDE_ONLY + /// Return the edge whose id is \a e. + /// \{ + const edge_t& edge(unsigned e) const; + /// \} - /*--------------. - | Identifiers. | - `--------------*/ + /// \brief Return the number of edges in the graph. + size_t e_nmax() const; - template <typename Tag, typename Equiv> - inline - gen_id<Tag, Equiv>::gen_id() - { - } + /// Return whether \p id_e is in the graph. + bool has_e(unsigned id_e) const; - template <typename Tag, typename Equiv> - inline - gen_id<Tag, Equiv>::gen_id(const Equiv& e) - : e_ (e) - { - } + /// Return the first vertex associated to the edge \p id_e. + unsigned v1(unsigned id_e) const; - template <typename Tag, typename Equiv> - inline - gen_id<Tag, Equiv>& - gen_id<Tag, Equiv>::operator=(const Equiv& e) - { - e_ = e; - return *this; - } - - template <typename Tag, typename Equiv> - inline - const Equiv& - gen_id<Tag, Equiv>::to_equiv() const - { - return e_; - } + /// Return the second vertex associated to edge \p id_e + unsigned v2(unsigned id_e) const; - template <typename Tag, typename Equiv> - inline - Equiv& - gen_id<Tag, Equiv>::to_equiv() - { - return e_; - } + /// Return the number max of adjacent edge, given an edge \p id_e. + size_t e_nmax_nbh_edges(unsigned id_e) const; - template <typename Tag, typename Equiv> - inline - gen_id<Tag, Equiv>::operator const Equiv() const - { - return to_equiv(); - } + /// Return the \p i th edge adjacent to the edge \p id_e. + unsigned e_ith_nbh_edge(unsigned id_e, unsigned i) const; - template <typename Tag, typename Equiv> - inline - gen_id<Tag, Equiv>::operator Equiv() - { - return to_equiv(); - } + /// \} + // FIXME: We might want to externalize this in routine of + // namespace mln::debug. + /** \brief Print on \p ostr the graph. - template <typename Tag, typename Equiv> - inline - bool - operator==(const gen_id<Tag, Equiv>& i, const gen_id<Tag, Equiv>& j) - { - return i.to_equiv() == j.to_equiv(); - } + \param[in] ostr The output stream. */ + void print_debug(std::ostream& ostr) const; - template <typename Tag, typename Equiv> - inline - bool - operator==(const Equiv& i, const gen_id<Tag, Equiv>& j) - { - return i == j.to_equiv(); - } - template <typename Tag, typename Equiv> - inline - bool - operator==(const gen_id<Tag, Equiv>& i, const Equiv j) - { - return i.to_equiv() == j; - } + protected: - template <typename Tag, typename Equiv> - inline - bool - ord_strict (const gen_id<Tag, Equiv>& i, const gen_id<Tag, Equiv>& j) - { - return i.to_equiv() < j.to_equiv(); - } + /// The vertices. + vertices_t vertices_; + /// The edges. + edges_t edges_; + /// An index of the set of edges, for fast-access purpose. + edges_set_t edges_set_; - template <typename Tag, typename Equiv> - inline - bool - ord_weak (const gen_id<Tag, Equiv>& i, const gen_id<Tag, Equiv>& j) - { - return i.to_equiv() <= j.to_equiv(); - } + /// Construction, assignments and destruction. + /// \{ + graph_base<E>(); + //graph_base<E>(const self_t& rhs); + //self_t& operator=(const self_t& rhs); + //~graph_base<E>(); + /// \} + }; - /*---------------------. - | Operators on edges. | - `---------------------*/ + } // end of namespace mln::util::internal + } // End of namespace mln::util - template <typename E> - inline - bool - operator==(const edge<E>& lhs, const edge<E>& rhs) - { - return lhs.pair_vertex_ == rhs.pair_vertex_; - } +# ifndef MLN_INCLUDE_ONLY - template <typename E> - inline - bool - operator< (const edge<E>& lhs, const edge<E>& rhs) - { - return lhs.pair_vertex_ < rhs.pair_vertex_; - } + namespace util + { namespace internal { @@ -447,194 +208,145 @@ namespace mln | Construction, assignments and destruction. | `--------------------------------------------*/ - template<typename V, typename E> + template<typename E> inline - graph_base<V, E>::graph_base() + graph_base<E>::graph_base() : vertices_(), edges_(), edges_set_() { } - template<typename V, typename E> - inline - graph_base<V, E>::graph_base(const graph_base<V, E>& rhs) - : vertices_(), edges_(), edges_set_() - { - vertices_.reserve(rhs.vertices_.size()); - edges_.reserve(rhs.edges_.size()); - for (typename vertices_t::const_iterator v = rhs.vertices_.begin(); - v != rhs.vertices_.end(); ++v) - vertices_.push_back(new util::vertex<V>(**v)); - for (typename edges_t::const_iterator e = rhs.edges_.begin(); - e != rhs.edges_.end(); ++e) - edges_.push_back(new util::edge<E>(**e)); - std::copy(edges_.begin(), edges_.end(), - std::insert_iterator<edges_set_t>(edges_set_, - edges_set_.begin())); - } + /*-------------. + | Misc methods | + `-------------*/ - template<typename V, typename E> + template<typename E> inline - graph_base<V, E>& - graph_base<V, E>::operator=(const graph_base<V, E>& rhs) + const void * const + graph_base<E>::graph_id() const { - if (this != &rhs) - { - /// Free previous vertices and edges. - for (typename vertices_t::iterator v = vertices_.begin(); - v != vertices_.end(); ++v) - delete *v; - for (typename edges_t::iterator e = edges_.begin(); - e != edges_.end(); ++e) - delete *e; - edges_set_.clear(); - /// Assign values from RHS. - vertices_.reserve(rhs.vertices_.size()); - edges_.reserve(rhs.edges_.size()); - for (typename vertices_t::const_iterator v = rhs.vertices_.begin(); - v != rhs.vertices_.end(); ++v) - vertices_.push_back(new util::vertex<V>(**v)); - for (typename edges_t::const_iterator e = rhs.edges_.begin(); - e != rhs.edges_.end(); ++e) - edges_.push_back(new util::edge<E>(**e)); - std::copy(edges_.begin(), edges_.end(), - std::insert_iterator<edges_set_t>(edges_set_, - edges_set_.begin())); - } - return *this; + return this; } - template<typename V, typename E> + /*-------------------------. + | Vertex and edges related | + `-------------------------*/ + + template<typename E> inline - graph_base<V, E>::~graph_base() + unsigned + graph_base<E>::v_other(unsigned id_e, unsigned id_v) const { - for (typename vertices_t::iterator v = vertices_.begin(); - v != vertices_.end(); ++v) - delete *v; - for (typename edges_t::iterator e = edges_.begin(); e != edges_.end(); - ++e) - delete *e; - edges_set_.clear(); + mln_precondition(has_e(id_e)); + mln_precondition(has_v(id_v)); + mln_precondition(edges_[id_e].first() == id_v + || edges_[id_e].second() == id_v); + + const edge_data_t& e = edges_[id_e]; + if (e.first() == id_v) + return e.second(); + return e.first(); } - /*------------. - | Accessors. | - `------------*/ + /*---------------. + | Vertex related | + `---------------*/ - template<typename V, typename E> + template<typename E> inline - util::vertex<V>& - graph_base<V, E>::vertex(vertex_id v) + unsigned + graph_base<E>::add_vertex() { - mln_assertion(v < this->nvertices()); - return *vertices_[v]; - } + /* FIXME: This is not thread-proof (these two lines should + form an atomic section). */ + vertices_.resize(vertices_.size() + 1); - template<typename V, typename E> - inline - const util::vertex<V>& - graph_base<V, E>::vertex(vertex_id v) const - { - mln_assertion(v < this->nvertices()); - return *vertices_[v]; + return vertices_.size() - 1; } - template<typename V, typename E> + template<typename E> inline - util::edge<E>& - graph_base<V, E>::edge(edge_id e) + typename graph_base<E>::vertex_t + graph_base<E>::vertex(unsigned id_v) const { - mln_assertion(e < this->nedges()); - return *edges_[e]; - } + mln_assertion(has_v(id_v)); - template<typename V, typename E> - inline - const util::edge<E>& - graph_base<V, E>::edge(edge_id e) const - { - mln_assertion(e < this->nedges()); - return *edges_[e]; + return vertex_t(this, id_v); } - template<typename V, typename E> + template<typename E> inline - typename graph_base<V, E>::vertices_t& - graph_base<V, E>::vertices() + size_t + graph_base<E>::v_nmax() const { - return vertices_; + return vertices_.size(); } - template<typename V, typename E> + template<typename E> inline - const typename graph_base<V, E>::vertices_t& - graph_base<V, E>::vertices() const + bool + graph_base<E>::has_v(unsigned id_v) const { - return vertices_; + return id_v < vertices_.size(); } - template<typename V, typename E> + template<typename E> inline - typename graph_base<V, E>::edges_t& - graph_base<V, E>::edges() + size_t + graph_base<E>::v_nmax_nbh_edges(unsigned id_v) const { - return edges_; + mln_precondition(has_v(id_v)); + + return vertices_[id_v].size(); } - template<typename V, typename E> + template<typename E> inline - const typename graph_base<V, E>::edges_t& - graph_base<V, E>::edges() const + unsigned + graph_base<E>::v_ith_nbh_edge(unsigned id_v, unsigned i) const { - return edges_; + mln_precondition(has_v(id_v)); + if (i >= v_nmax_nbh_edges(id_v)) + return v_nmax(); + + return vertices_[id_v][i]; } - template<typename V, typename E> + template<typename E> inline size_t - graph_base<V, E>::nvertices() const + graph_base<E>::v_nmax_nbh_vertices(unsigned id_v) const { - return vertices_.size(); + mln_precondition(has_v(id_v)); + return v_nmax_nbh_edges(id_v); } - template<typename V, typename E> + template<typename E> inline - size_t - graph_base<V, E>::nedges() const + unsigned + graph_base<E>::v_ith_nbh_vertex(unsigned id_v, unsigned i) const { - return edges_.size(); + mln_precondition(has_v(id_v)); + + unsigned id_e = v_ith_nbh_edge(id_v, i); + return v_other(id_e, id_v); } - /*---------------. - | Manipulators. | - `---------------*/ - template<typename V, typename E> - inline - vertex_id - graph_base<V, E>::add_vertex_(util::vertex<V>* vertex) - { - /* FIXME: This is not thread-proof (these two lines should - form an atomic section). */ - vertices_.push_back (vertex); - return vertices_.size() - 1; - } + /*--------------. + | Edges related | + `---------------*/ - template<typename V, typename E> + template<typename E> inline - edge_id - graph_base<V, E>::add_edge_(util::edge<E>* edge) + unsigned + graph_base<E>::add_edge(unsigned id_v1, unsigned id_v2) { // Does this edge already exist in the graph? + edge_data_t edge(id_v1, id_v2); if (edges_set_.find(edge) != edges_set_.end ()) { - // Remove the previously allocated data for EDGE. - delete edge; - edge = 0; // Return the erroneous value. - /* FIXME: We have to explicitly extract the numerical - equivalent type here, because mln::util::gen_id<T, E> - is not compatible with Milena's value system (yet). */ - return mln_max(edge_id::equiv); + return mln_max(unsigned); } else { @@ -642,49 +354,121 @@ namespace mln /* FIXME: This is not thread-proof (these two lines should form an atomic section). */ edges_.push_back(edge); - edge_id id = edges_.size() - 1; + unsigned id = edges_.size() - 1; // Update the set of edges. edges_set_.insert(edge); - vertices_[edge->v1()]->edges.push_back(id); - vertices_[edge->v2()]->edges.push_back(id); + vertices_[edge.first()].push_back(id); + vertices_[edge.second()].push_back(id); return id; } } + template<typename E> + inline + const typename graph_base<E>::edge_t& + graph_base<E>::edge(unsigned e) const + { + mln_assertion(e < this->nedges()); + return edge_t(this, edges_[e].first(), edges_[e].second()); + } + + template<typename E> + inline + size_t + graph_base<E>::e_nmax() const + { + return edges_.size(); + } + + template<typename E> + inline + bool + graph_base<E>::has_e(unsigned id_e) const + { + return id_e < edges_.size(); + } + + template<typename E> + inline + unsigned + graph_base<E>::v1(unsigned id_e) const + { + mln_precondition(has_e(id_e)); + return edges_[id_e].first(); + } + + template<typename E> + inline + unsigned + graph_base<E>::v2(unsigned id_e) const + { + mln_precondition(has_e(id_e)); + return edges_[id_e].second(); + } + + template<typename E> + inline + size_t + graph_base<E>::e_nmax_nbh_edges(unsigned id_e) const + { + mln_precondition(has_e(id_e)); + return v_nmax_nbh_edges(v1(id_e)) + v_nmax_nbh_edges(v2(id_e)); + } + + template<typename E> + inline + unsigned + graph_base<E>::e_ith_nbh_edge(unsigned id_e, unsigned i) const + { + mln_precondition(has_e(id_e)); + if (i >= e_nmax_nbh_edges(id_e)) + return e_nmax(); + + unsigned v1_nmax = v_nmax_nbh_edges(v1(id_e)); + if (i < v1_nmax) + return v_ith_nbh_edge(v1(id_e), i); + return v_ith_nbh_edge(v2(id_e), i - v1_nmax); + } + /*--------. | Debug. | `--------*/ - template<typename V, typename E> + template<typename E> inline void - graph_base<V, E>::print_debug (std::ostream& ostr) const + graph_base<E>::print_debug (std::ostream& ostr) const { ostr << "graph: " << std::endl; for (unsigned v = 0; v < vertices_.size(); ++v) { ostr << "vertex: " << v << std::endl << " -- adjacent vertices: "; - /* FIXME: We shouldn't manipulate std::vector<edge_id> - directly, but use a typedef instead. */ - for (typename std::vector<util::edge_id>::const_iterator e = - vertices_[v]->edges.begin(); e != vertices_[v]->edges.end(); + for (vertex_data_t::const_iterator e = + vertices_[v].begin(); e != vertices_[v].end(); ++e) - if (v == edges_[*e]->v1()) - ostr << edges_[*e]->v2() << " "; + if (v == edges_[*e].first()) + ostr << edges_[*e].second() << " "; else - ostr << edges_[*e]->v1() << " "; + ostr << edges_[*e].first() << " "; ostr << std::endl; } ostr << std::endl; + + ostr << "edges:" << std::endl; + unsigned ei = 0; + for (edges_t::const_iterator e = edges_.begin(); e != edges_.end(); + ++e, ++ei) + ostr << "edge " << ei << ": (" << e->first() << ", " << e->second() << " )" << std::endl; } } // end of namespace mln::util::internal + } // end of namespace mln::util + # endif // ! MLN_INCLUDE_ONLY - } // end of namespace mln::util } // end of namespace mln diff --git a/milena/mln/util/internal/graph_edge.hh b/milena/mln/util/internal/graph_edge.hh new file mode 100644 index 0000000..78a00c2 --- /dev/null +++ b/milena/mln/util/internal/graph_edge.hh @@ -0,0 +1,378 @@ +// Copyright (C) 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_INTERNAL_GRAPH_EDGE_HH +# define MLN_UTIL_INTERNAL_GRAPH_EDGE_HH + +/*! \file mln/util/internal/graph_edge.hh + * \brief Definition of a graph edge. + */ + +namespace mln +{ + + namespace util + { + + /*-------. + | Edge. | + `-------*/ + + /// \brief Edge of a graph \p G. + template <typename G> + class edge + { + typedef mlc_const(G) graph_t; + + public: + /// Constructors + /// \{ + edge(); + explicit edge(graph_t *g); + edge(graph_t *g, unsigned id); + /// \} + + + + /// Misc. + /// \{ + /// Return the edge id. + unsigned id() const; + + /// Set \att id_ with \p id; + void update_id(unsigned id); + + /// Return pointer of the graph holding this edge. + const graph_t * const g() const; + /// \} + + + + /// Vertex and edges oriented. + /// \{ + /// Return the vertex id of this edge which is different from \p id_v. + unsigned v_other(unsigned id_v) const; + /// \} + + + /// Edge oriented. + /// \{ + bool is_valid() const; + + /// Return the lowest vertex id adjacent to this edge. + unsigned v1() const; + + /// Return the highest vertex id adjacent to this edge. + unsigned v2() const; + + /// Return the number max of adjacent edges. + size_t nmax_nbh_edges() const; + + /// Return the \p i th adjacent edge. + unsigned ith_nbh_edge(unsigned i) const; + /// \} + + private: + graph_t * const g_; + unsigned id_; + }; + + template <typename G> + bool + operator==(const util::edge<G>& lhs, const util::edge<G>& rhs); + + template <typename G> + bool + operator< (const util::edge<G>& lhs, const util::edge<G>& rhs); + + } // End of namespace mln::util + + + /// subject_impl specialization (Proxy) + /// \{ + namespace internal + { + + template <typename G, typename E> + struct subject_impl< const util::edge<G>, E > + { + unsigned id() const; + const mlc_const(G) * const g() const; + unsigned v_other(unsigned id_v) const; + bool is_valid() const; + unsigned v1() const; + unsigned v2() const; + size_t nmax_nbh_edges() const; + unsigned ith_nbh_edge(unsigned i) const; + + + private: + const E& exact_() const; + }; + + template <typename G, typename E> + struct subject_impl< util::edge<G>, E > : + subject_impl< const util::edge<G>, E > + { + void update_id(unsigned id); + + private: + E& exact_(); + }; + + } // end of namespace mln::internal + /// \} + + +# ifndef MLN_INCLUDE_ONLY + + /*---------------------. + | Operators on edges. | + `---------------------*/ + + namespace util + { + + template <typename G> + inline + edge<G>::edge() + : g_(0), id_(0) + { + } + + template <typename G> + inline + edge<G>::edge(graph_t *g) + : g_(g), id_(g->e_nmax()) + { + } + + template <typename G> + inline + edge<G>::edge(graph_t *g, unsigned id) + : g_(g), id_(id) + { + mln_precondition(g->has_e(id)); + } + + template <typename G> + inline + unsigned + edge<G>::id() const + { + return id_; + } + + template <typename G> + inline + void + edge<G>::update_id(unsigned id) + { + id_ = id; + } + + template <typename G> + inline + const typename edge<G>::graph_t * const + edge<G>::g() const + { + return g_; + } + + template <typename G> + inline + unsigned + edge<G>::v_other(unsigned id_v) const + { + mln_precondition(v1() == id_v || v2() == id_v); + return g_->v_other(id_, id_v); + } + + template <typename G> + inline + bool + edge<G>::is_valid() const + { + return g_ != 0 && g_->has_e(id_); + } + + template <typename G> + inline + unsigned + edge<G>::v1() const + { + mln_precondition(g_->has_e(id_)); + return g_->v1(id_); + } + + template <typename G> + inline + unsigned + edge<G>::v2() const + { + mln_precondition(g_->has_e(id_)); + return g_->v2(id_); + } + + template <typename G> + inline + size_t + edge<G>::nmax_nbh_edges() const + { + mln_precondition(g_->has_e(id_)); + return g_->e_nmax_nbh_edges(id_); + } + + template <typename G> + inline + unsigned + edge<G>::ith_nbh_edge(unsigned i) const + { + mln_precondition(g_->has_e(id_)); + return g_->e_ith_nbh_edge(id_, i); + } + + + + template <typename G> + inline + bool + operator==(const util::edge<G>& lhs, const util::edge<G>& rhs) + { + return lhs.pair_vertex_ == rhs.pair_vertex_; + } + + template <typename G> + inline + bool + operator< (const util::edge<G>& lhs, const util::edge<G>& rhs) + { + return lhs.pair_vertex_ < rhs.pair_vertex_; + } + + } // end of namespace mln::util + + namespace internal + { + + /*----------------------------------` + | subject_impl< const util::edge<G> | + \----------------------------------*/ + + template <typename G, typename E> + inline + const E& + subject_impl< const util::edge<G>, E >::exact_() const + { + return internal::force_exact<const E>(*this); + } + + template <typename G, typename E> + inline + unsigned + subject_impl< const util::edge<G>, E >::id() const + { + return exact_().get_subject().id(); + } + + template <typename G, typename E> + inline + const mlc_const(G) * const + subject_impl< const util::edge<G>, E >::g() const + { + return exact_().get_subject().g(); + } + + template <typename G, typename E> + inline + unsigned + subject_impl< const util::edge<G>, E >::v_other(unsigned id_v) const + { + return exact_().get_subject().v_other(id_v); + } + + template <typename G, typename E> + inline + bool + subject_impl< const util::edge<G>, E >::is_valid() const + { + return exact_().get_subject().is_valid(); + } + + template <typename G, typename E> + inline + unsigned + subject_impl< const util::edge<G>, E >::v1() const + { + return exact_().get_subject().v1(); + } + + template <typename G, typename E> + inline + unsigned + subject_impl< const util::edge<G>, E >::v2() const + { + return exact_().get_subject().v2(); + } + + template <typename G, typename E> + inline + size_t + subject_impl< const util::edge<G>, E >::nmax_nbh_edges() const + { + return exact_().get_subject().nmax_nbh_edges(); + } + + template <typename G, typename E> + inline + unsigned + subject_impl< const util::edge<G>, E >::ith_nbh_edge(unsigned i) const + { + return exact_().get_subject().ith_nbh_edge(i); + } + + + /*----------------------------------` + | subject_impl< util::edge<G> | + \----------------------------------*/ + + template <typename G, typename E> + inline + void + subject_impl< util::edge<G>, E >::update_id(unsigned id) + { + return exact_().get_subject().update_id(id); + } + + } // End of namespace mln::internal + +# endif // !MLN_INCLUDE_ONLY + +} // End of namespace mln + +#endif // !MLN_UTIL_INTERNAL_GRAPH_EDGE_HH + diff --git a/milena/mln/util/internal/graph_edge_iter.hh b/milena/mln/util/internal/graph_edge_iter.hh new file mode 100644 index 0000000..9bcf9ff --- /dev/null +++ b/milena/mln/util/internal/graph_edge_iter.hh @@ -0,0 +1,273 @@ +// Copyright (C) 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. This exception does not however invalidate any other +// reasons why the executable file might be covered by the GNU General +// Public License. + +#ifndef MLN_UTIL_INTERNAL_GRAPH_EDGE_ITER_HH +# define MLN_UTIL_INTERNAL_GRAPH_EDGE_ITER_HH + +# include <mln/core/concept/iterator.hh> +# include <mln/core/concept/proxy.hh> +# include <mln/util/internal/graph_edge.hh> + +/// \file mln/util/internal/graph_edge_iter.hh +/// \brief Implementation for graph edge iterators. + +namespace mln +{ + + namespace internal + { + + /// Forward edge iterator. + template <typename G> + class edge_fwd_iterator + : public Proxy< edge_fwd_iterator<G> >, + public internal::proxy_impl< const util::edge<G>&, edge_fwd_iterator<G> > + { + public: + /// Constructors. + /// \{ + edge_fwd_iterator(); + edge_fwd_iterator(const G& g); + /// \} + + /// Iterator interface + /// \{ + /// Test if the iterator is valid. + bool is_valid() const; + /// Invalidate the iterator. + void invalidate(); + + /// Start an iteration. + void start(); + + /// Go to the next value. + void next(); + + /// Return current index + unsigned index() const; + /// \} + + /// Proxy. + /// \{ + /// Proxy subject + const util::edge<G>& subj_(); + /// \} + + protected: + util::edge<G> e_; + }; + + template <typename G> + class edge_bkd_iterator + : public Proxy< edge_bkd_iterator<G> >, + public proxy_impl< const util::edge<G>&, edge_bkd_iterator<G> > + { + public: + /// Constructors. + /// \{ + edge_bkd_iterator(); + edge_bkd_iterator(const G& g); + /// \} + + /// Iterator interface. + /// \{ + /// Test if the iterator is valid. + bool is_valid() const; + /// Invalidate the iterator. + void invalidate(); + + /// Start an iteration. + void start(); + + /// Go to the next value. + void next(); + + /// Return current index + unsigned index() const; + /// \} + + /// Proxy. + /// \{ + /// Proxy subject + const util::edge<G>& subj_(); + /// \} + + protected: + util::edge<G> e_; + }; + + } // End of namespace mln::internal + +} // End of namespace mln + + +# ifndef MLN_INCLUDE_ONLY + +namespace mln +{ + + namespace internal + { + + template <typename G> + inline + edge_fwd_iterator<G>::edge_fwd_iterator() + { + } + + template <typename G> + inline + edge_fwd_iterator<G>::edge_fwd_iterator(const G& g) + : e_(util::edge<G>(&g)) + { + invalidate(); + } + + template <typename G> + inline + bool + edge_fwd_iterator<G>::is_valid() const + { + return e_.is_valid(); + } + + template <typename G> + inline + void + edge_fwd_iterator<G>::invalidate() + { + e_.update_id(e_.g()->e_nmax()); + } + + template <typename G> + inline + void + edge_fwd_iterator<G>::start() + { + e_.update_id(0); + } + + template <typename G> + inline + void + edge_fwd_iterator<G>::next() + { + e_.update_id(e_.id() + 1); + } + + template <typename G> + inline + unsigned + edge_fwd_iterator<G>::index() const + { + return e_.id(); + } + + template <typename G> + inline + const util::edge<G>& + edge_fwd_iterator<G>::subj_() + { + return e_; + } + + + + /*------------------` + | edge_bkd_iterator | + \------------------*/ + + template <typename G> + inline + edge_bkd_iterator<G>::edge_bkd_iterator() + { + } + + template <typename G> + inline + edge_bkd_iterator<G>::edge_bkd_iterator(const G& g) + : e_(util::edge<G>(&g)) + { + invalidate(); + } + + template <typename G> + inline + bool + edge_bkd_iterator<G>::is_valid() const + { + return e_.is_valid(); + } + + template <typename G> + inline + void + edge_bkd_iterator<G>::invalidate() + { + e_.update_id(e_.g()->e_nmax()); + } + + template <typename G> + inline + void + edge_bkd_iterator<G>::start() + { + e_.update_id(e_.g()->e_nmax() - 1); + } + + template <typename G> + inline + void + edge_bkd_iterator<G>::next() + { + e_.update_id(e_.id() - 1); + } + + template <typename G> + inline + unsigned + edge_bkd_iterator<G>::index() const + { + return e_.id(); + } + + template <typename G> + inline + const util::edge<G>& + edge_bkd_iterator<G>::subj_() + { + return e_; + } + + } // End of namespace mln::internal + +} // End of namespace mln + +# endif // !MLN_INCLUDE_ONLY + +#endif // !MLN_UTIL_INTERNAL_GRAPH_EDGE_ITER_HH + diff --git a/milena/mln/util/internal/graph_edge_nbh_edge_iter.hh b/milena/mln/util/internal/graph_edge_nbh_edge_iter.hh new file mode 100644 index 0000000..084ad23 --- /dev/null +++ b/milena/mln/util/internal/graph_edge_nbh_edge_iter.hh @@ -0,0 +1,335 @@ +// Copyright (C) 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. This exception does not however invalidate any other +// reasons why the executable file might be covered by the GNU General +// Public License. + +#ifndef MLN_UTIL_INTERNAL_GRAPH_EDGE_NBH_EDGE_ITER_HH +# define MLN_UTIL_INTERNAL_GRAPH_EDGE_NBH_EDGE_ITER_HH + +# include <mln/core/concept/proxy.hh> + +/// \file mln/util/internal/graph_edge_nbh_edge_iter.hh +/// \brief Implementation for graph edge iterators centered to an edge. + +namespace mln +{ + + namespace internal + { + + template <typename G> + class edge_nbh_edge_fwd_iterator + : public Proxy< edge_nbh_edge_fwd_iterator<G> >, + public internal::proxy_impl< const util::edge<G>&, edge_nbh_edge_fwd_iterator<G> > + { + public: + /// Construction and assignment. + /// \{ + template <typename C> + edge_nbh_edge_fwd_iterator(const C& c); + /// \} + + /// Iterator interface. + /// \{ + /// Test if the iterator is valid. + bool is_valid() const; + /// Invalidate the iterator. + void invalidate(); + + /// Start an iteration. + void start(); + + /// Go to the next value. + void next(); + + /// Return current index + unsigned index() const; + /// \} + + /// Proxy. + /// \{ + /// Proxy subject + const util::edge<G>& subj_(); + /// \} + + protected: + void update_(); + + template <typename C> + void center_at(const C& c); + + + const util::edge<G>* c_; //Center + util::edge<G> e_; + unsigned i_; + }; + + template <typename G> + class edge_nbh_edge_bkd_iterator + : public Proxy< edge_nbh_edge_bkd_iterator<G> >, + public proxy_impl< const util::edge<G>&, edge_nbh_edge_bkd_iterator<G> > + { + public: + /// Construction and assignment. + /// \{ + template <typename C> + edge_nbh_edge_bkd_iterator(const C& e); + /// \} + + /// Iterator interface. + /// \{ + /// Test if the iterator is valid. + bool is_valid() const; + /// Invalidate the iterator. + void invalidate(); + + /// Start an iteration. + void start(); + + /// Go to the next value. + void next(); + + /// Return current index + unsigned index() const; + /// \} + + /// Proxy. + /// \{ + /// Proxy subject + const util::edge<G>& subj_(); + /// \} + + protected: + void update_(); + + template <typename C> + void center_at(const C& c); + + const util::edge<G>* c_; //Center + util::edge<G> e_; + unsigned i_; + }; + + +# ifndef MLN_INCLUDE_ONLY + + template <typename G> + template <typename C> + inline + edge_nbh_edge_fwd_iterator<G>::edge_nbh_edge_fwd_iterator(const C& c) + : e_(c.g()), i_(0) + { + //FIXME: Check if typeof(e.g()) == G + center_at(c); + } + + template <typename G> + inline + bool + edge_nbh_edge_fwd_iterator<G>::is_valid() const + { + return i_ < c_->nmax_nbh_edges(); + } + + template <typename G> + inline + void + edge_nbh_edge_fwd_iterator<G>::invalidate() + { + i_ = e_.g()->e_nmax(); + } + + template <typename G> + inline + void + edge_nbh_edge_fwd_iterator<G>::start() + { + i_ = 0; + if (is_valid()) + update_(); + } + + template <typename G> + inline + void + edge_nbh_edge_fwd_iterator<G>::next() + { + ++i_; + if (is_valid()) + update_(); + } + + template <typename G> + inline + unsigned + edge_nbh_edge_fwd_iterator<G>::index() const + { + return i_; + } + + template <typename G> + inline + const util::edge<G>& + edge_nbh_edge_fwd_iterator<G>::subj_() + { + return e_; + } + + template <typename G> + inline + void + edge_nbh_edge_fwd_iterator<G>::update_() + { + mln_precondition(is_valid()); + mln_precondition(c_->is_valid()); + + // We shall encounter vertices which are part of the + // current edge. + // We do not want them to be part of the edge neighbors. + unsigned e_id = c_->ith_nbh_edge(i_); + while (e_id == c_->id()) + e_id = c_->ith_nbh_edge(++i_); + + e_.update_id(e_id); + } + + template <typename G> + template <typename E> + inline + void + edge_nbh_edge_fwd_iterator<G>::center_at(const E& c) + { + internal::get_adr(c_, c); + mln_precondition(c_ != 0); + + invalidate(); + } + + + + /*---------------------------` + | edge_nbh_edge_bkd_iterator | + \---------------------------*/ + + template <typename G> + template <typename C> + inline + edge_nbh_edge_bkd_iterator<G>::edge_nbh_edge_bkd_iterator(const C& c) + : e_(c.g()), i_(0) + { + //FIXME: Check if typeof(e.g()) == G + center_at(c); + } + + template <typename G> + inline + bool + edge_nbh_edge_bkd_iterator<G>::is_valid() const + { + return i_ < c_->nmax_nbh_edges(); + } + + template <typename G> + inline + void + edge_nbh_edge_bkd_iterator<G>::invalidate() + { + i_ = e_.g()->e_nmax(); + } + + template <typename G> + inline + void + edge_nbh_edge_bkd_iterator<G>::start() + { + i_ = c_->nmax_nbh_edges() - 1; + if (is_valid()) + update_(); + } + + template <typename G> + inline + void + edge_nbh_edge_bkd_iterator<G>::next() + { + --i_; + if (is_valid()) + update_(); + } + + template <typename G> + inline + unsigned + edge_nbh_edge_bkd_iterator<G>::index() const + { + return i_; + } + + template <typename G> + inline + const util::edge<G>& + edge_nbh_edge_bkd_iterator<G>::subj_() + { + return e_; + } + + template <typename G> + inline + void + edge_nbh_edge_bkd_iterator<G>::update_() + { + mln_precondition(is_valid()); + mln_precondition(c_->is_valid()); + + // We shall encounter vertices which are part of the + // current edge. + // We do not want them to be part of the edge neighbors. + unsigned e_id = c_->ith_nbh_edge(i_); + while (e_id == c_->id()) + e_id = c_->ith_nbh_edge(--i_); + + e_.update_id(e_id); + } + + template <typename G> + template <typename E> + inline + void + edge_nbh_edge_bkd_iterator<G>::center_at(const E& c) + { + internal::get_adr(c_, c); + mln_precondition(c_ != 0); + + invalidate(); + } +# endif // !MLN_INCLUDE_ONLY + + } // End of namespace mln::internal + +} // End of namespace mln + + +#endif // !MLN_UTIL_INTERNAL_GRAPH_EDGE_NBH_EDGE_ITER_HH + diff --git a/milena/mln/util/internal/graph_vertex.hh b/milena/mln/util/internal/graph_vertex.hh new file mode 100644 index 0000000..c40bf0f --- /dev/null +++ b/milena/mln/util/internal/graph_vertex.hh @@ -0,0 +1,361 @@ +// Copyright (C) 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_INTERNAL_GRAPH_VERTEX_HH +# define MLN_UTIL_INTERNAL_GRAPH_VERTEX_HH + +/// \file mln/util/internal/graph_vertex.hh +/// \brief Implementation of a graph vertex. + +namespace mln +{ + + namespace util + { + + /// \brief Vertex of a graph \p G. + template<typename G> + class vertex + { + typedef mlc_const(G) graph_t; + + public: + + /// Constructors. + /// \{ + vertex(); + explicit vertex(graph_t *g); + vertex(graph_t *g, unsigned id); + /// \} + + /// Check whether the vertex is still part of the graph. + bool is_valid() const; + + unsigned other(unsigned id_e) const; + + /// Returns the ith edge starting from this vertex. + unsigned ith_nbh_edge(unsigned i) const; + + /// Returns the number max of edges starting from this vertex. + /// If g_ is a sub graph of another graph, nmax will be retrived from + /// the initial graph. + unsigned nmax_nbh_edges() const; + + /// Returns the ith vertex adjacent to this vertex. + unsigned ith_nbh_vertex(unsigned i) const; + + /// Returns the number max of vertices adjacent to this vertex. + unsigned nmax_nbh_vertices() const; + + /// Change the parent graph of that vertex. + void change_graph(const G& g); + + /// Update vertex id. + void update_id(unsigned id); + + /// Returns the graph pointer this vertex belongs to. + const graph_t * const g() const; + + /// Returns vertex id. + unsigned id() const; + + private: + graph_t * const g_; + unsigned id_; + }; + + } // End of namespace mln::util + + +/// subject_impl specialization (Proxy) +/// \{ + namespace internal + { + template <typename G, typename E> + struct subject_impl< const util::vertex<G>, E > + { + bool is_valid() const; + const mlc_const(G) * const g() const; + unsigned id() const; + + unsigned other(unsigned id_e) const; + unsigned ith_nbh_edge(unsigned i) const; + unsigned nmax_nbh_edges() const; + unsigned ith_nbh_vertex(unsigned i) const; + unsigned nmax_nbh_vertices() const; + + private: + const E& exact_() const; + }; + + template <typename G, typename E> + struct subject_impl< util::vertex<G>, E > : + subject_impl< const util::vertex<G>, E > + { + void change_graph(const G& g); + void update_id(unsigned id); + + private: + E& exact_(); + }; + + } // end of namespace mln::internal + +} // End of namespace mln +/// \} + + +# ifndef MLN_INCLUDE_ONLY + +namespace mln +{ + + namespace util + { + + template <typename G> + inline + vertex<G>::vertex() + : g_(0), id_(0) + { + } + + template <typename G> + inline + vertex<G>::vertex(graph_t *g) + : g_(g), id_(g_->v_nmax()) + { + } + + template<typename G> + inline + vertex<G>::vertex(graph_t *g, unsigned id) + : g_(g), id_(id) + { + mln_precondition(g_->has_v(id)); + } + + template<typename G> + inline + bool + vertex<G>::is_valid() const + { + return g_ != 0 && g_->has_v(id_); + } + + template<typename G> + inline + unsigned + vertex<G>::other(unsigned id_e) const + { + mln_precondition(g_->has_v(id_)); + mln_precondition(g_->has_e(id_e)); + mln_precondition(g_->v1(id_e) == id_ || g_->v2(id_e) == id_); + return g_->v_other(id_e, id_); + } + + template<typename G> + inline + unsigned + vertex<G>::ith_nbh_edge(unsigned i) const + { + mln_precondition(g_->has_v(id_)); + return g_->v_ith_nbh_edge(id_, i); + } + + template<typename G> + inline + unsigned + vertex<G>::nmax_nbh_edges() const + { + mln_precondition(g_->has_v(id_)); + return g_->v_nmax_nbh_edges(id_); + } + + template<typename G> + inline + unsigned + vertex<G>::ith_nbh_vertex(unsigned i) const + { + mln_precondition(g_->has_v(id_)); + return g_->v_ith_nbh_vertex(id_, i); + } + + template<typename G> + inline + unsigned + vertex<G>::nmax_nbh_vertices() const + { + mln_precondition(g_->has_v(id_)); + return g_->v_nmax_nbh_vertices(id_); + } + + template<typename G> + inline + void + vertex<G>::change_graph(const G& g) + { + mln_precondition(g_->has_v(id_)); + g_ = &g; + } + + template<typename G> + inline + void + vertex<G>::update_id(unsigned id) + { + id_ = id; + } + + template<typename G> + inline + const typename vertex<G>::graph_t * const + vertex<G>::g() const + { + return g_; + } + + template<typename G> + inline + unsigned + vertex<G>::id() const + { + return id_; + } + + } // end of namespace mln::util + + namespace internal + { + + template <typename G, typename E> + inline + const E& + subject_impl< const util::vertex<G>, E >::exact_() const + { + return internal::force_exact<const E>(*this); + } + + template <typename G, typename E> + inline + bool + subject_impl< const util::vertex<G>, E >::is_valid() const + { + return exact_().get_subject().is_valid(); + } + + template <typename G, typename E> + inline + const mlc_const(G)* const + subject_impl< const util::vertex<G>, E >::g() const + { + return exact_().get_subject().g(); + } + + template <typename G, typename E> + inline + unsigned + subject_impl< const util::vertex<G>, E >::id() const + { + return exact_().get_subject().id(); + }; + + + + template <typename G, typename E> + inline + unsigned + subject_impl< const util::vertex<G>, E >::other(unsigned id_e) const + { + return exact_().get_subject().other(id_e); + } + + template <typename G, typename E> + inline + unsigned + subject_impl< const util::vertex<G>, E >::ith_nbh_edge(unsigned i) const + { + return exact_().get_subject().ith_nbh_edge(i); + } + + template <typename G, typename E> + inline + unsigned + subject_impl< const util::vertex<G>, E >::nmax_nbh_edges() const + { + return exact_().get_subject().nmax_nbh_edges(); + } + + template <typename G, typename E> + inline + unsigned + subject_impl< const util::vertex<G>, E >::ith_nbh_vertex(unsigned i) const + { + return exact_().get_subject().ith_nbh_vertex(i); + } + + template <typename G, typename E> + inline + unsigned + subject_impl< const util::vertex<G>, E >::nmax_nbh_vertices() const + { + return exact_().get_subject().nmax_nbh_vertices(); + } + + template <typename G, typename E> + inline + E& + subject_impl< util::vertex<G>, E >::exact_() + { + return internal::force_exact<E>(*this); + } + + template <typename G, typename E> + inline + void + subject_impl< util::vertex<G>, E >::change_graph(const G& g) + { + exact_().get_subject().change_graph(g); + } + + template <typename G, typename E> + inline + void + subject_impl< util::vertex<G>, E >::update_id(unsigned id) + { + exact_().get_subject().update_id(id); + }; + + } // end of namespace mln::internal + +} // End of namespace mln + +# endif // !MLN_INCLUDE_ONLY + + +#endif // !MLN_UTIL_INTERNAL_GRAPH_VERTEX_HH + diff --git a/milena/mln/util/internal/graph_vertex_iter.hh b/milena/mln/util/internal/graph_vertex_iter.hh new file mode 100644 index 0000000..9d2f3df --- /dev/null +++ b/milena/mln/util/internal/graph_vertex_iter.hh @@ -0,0 +1,266 @@ +// Copyright (C) 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. This exception does not however invalidate any other +// reasons why the executable file might be covered by the GNU General +// Public License. + +#ifndef MLN_UTIL_INTERNAL_GRAPH_VERTEX_ITER_HH +# define MLN_UTIL_INTERNAL_GRAPH_VERTEX_ITER_HH + +# include <mln/metal/const.hh> +# include <mln/core/concept/iterator.hh> +# include <mln/core/concept/proxy.hh> +# include <mln/util/internal/graph_base.hh> + +/// \file mln/util/internal/graph_vertex_iter.hh +/// \brief Implementation for graph vertex iterators. + +namespace mln +{ + + namespace internal + { + + template<typename G> + class vertex_fwd_iterator + : public Proxy< vertex_fwd_iterator<G> >, + public proxy_impl< const util::vertex<G>&, vertex_fwd_iterator<G> > + { + public: + /// Constructors. + /// \{ + vertex_fwd_iterator(); + vertex_fwd_iterator(const G& g); + /// \} + + /// Iterator interface. + /// \{ + /// Test if the iterator is valid. + bool is_valid() const; + /// Invalidate the iterator. + void invalidate(); + + /// Start an iteration. + void start(); + + /// Go to the next value. + void next(); + + /// Return current index + unsigned index() const; + /// \} + + /// Proxy. + /// \{ + /// Proxy subject + const util::vertex<G>& subj_(); + /// \} + + protected: + util::vertex<G> v_; + }; + + template<typename G> + class vertex_bkd_iterator + : public Proxy< vertex_bkd_iterator<G> >, + public proxy_impl< const util::vertex<G>&, vertex_fwd_iterator<G> > + { + public: + /// Constructors. + /// \{ + vertex_bkd_iterator(); + vertex_bkd_iterator(const G& g); + /// \} + + /// Iterator interface. + /// \{ + /// Test if the iterator is valid. + bool is_valid() const; + /// Invalidate the iterator. + void invalidate(); + + /// Start an iteration. + void start(); + + /// Go to the next value. + void next(); + + /// Return current index + unsigned index() const; + /// \} + + /// Proxy. + /// \{ + /// Proxy subject + const util::vertex<G>& subj_(); + /// \} + + protected: + util::vertex<G> v_; + }; + + +# ifndef MLN_INCLUDE_ONLY + + /*--------------------` + | vertex_fwd_iterator | + \--------------------*/ + + template<typename G> + inline + vertex_fwd_iterator<G>::vertex_fwd_iterator() + { + } + + template<typename G> + inline + vertex_fwd_iterator<G>::vertex_fwd_iterator(const G& g) + : v_(util::vertex<G>(&g)) + { + invalidate(); + } + + template<typename G> + inline + bool + vertex_fwd_iterator<G>::is_valid() const + { + return v_.is_valid(); + } + + template<typename G> + inline + void + vertex_fwd_iterator<G>::invalidate() + { + v_.update_id(v_.g()->v_nmax()); + } + + template<typename G> + inline + void + vertex_fwd_iterator<G>::start() + { + v_.update_id(0); + } + + template<typename G> + inline + void + vertex_fwd_iterator<G>::next() + { + v_.update_id(v_.id() + 1); + } + + template<typename G> + inline + unsigned + vertex_fwd_iterator<G>::index() const + { + return v_.id(); + } + + template<typename G> + inline + const util::vertex<G>& + vertex_fwd_iterator<G>::subj_() + { + return v_; + } + + + /*--------------------` + | vertex_bkd_iterator | + \--------------------*/ + + template<typename G> + inline + vertex_bkd_iterator<G>::vertex_bkd_iterator() + { + } + + template<typename G> + inline + vertex_bkd_iterator<G>::vertex_bkd_iterator(const G& g) + : v_(util::vertex<G>(&g)) + { + invalidate(); + } + + template<typename G> + inline + bool + vertex_bkd_iterator<G>::is_valid() const + { + return v_.is_valid(); + } + + template<typename G> + inline + void + vertex_bkd_iterator<G>::invalidate() + { + v_.update_id(v_.g()->v_nmax()); + } + + template<typename G> + inline + void + vertex_bkd_iterator<G>::start() + { + v_.update_id(v_.g()->v_nmax() - 1); + } + + template<typename G> + inline + void + vertex_bkd_iterator<G>::next() + { + v_.update_id(v_.id() - 1); + } + + template<typename G> + inline + unsigned + vertex_bkd_iterator<G>::index() const + { + return v_.id(); + } + + template<typename G> + inline + const util::vertex<G>& + vertex_bkd_iterator<G>::subj_() + { + return v_; + } +# endif // !MLN_INCLUDE_ONLY + + } // End of namespace mln::internal + +} // End of namespace mln + + +#endif // !MLN_UTIL_INTERNAL_GRAPH_VERTEX_ITER_HH + diff --git a/milena/mln/util/internal/graph_vertex_nbh_edge_iter.hh b/milena/mln/util/internal/graph_vertex_nbh_edge_iter.hh new file mode 100644 index 0000000..4edc652 --- /dev/null +++ b/milena/mln/util/internal/graph_vertex_nbh_edge_iter.hh @@ -0,0 +1,323 @@ +// Copyright (C) 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. This exception does not however invalidate any other +// reasons why the executable file might be covered by the GNU General +// Public License. + +#ifndef MLN_UTIL_INTERNAL_GRAPH_VERTEX_NBH_EDGE_ITER_HH +# define MLN_UTIL_INTERNAL_GRAPH_VERTEX_NBH_EDGE_ITER_HH + +# include <mln/core/concept/proxy.hh> + +/// \file mln/util/internal/graph_vertex_nbh_edge_iter.hh +/// \brief Implementation for graph edge iterators centered to a vertex. + +namespace mln +{ + + namespace internal + { + + template <typename G> + class vertex_nbh_edge_fwd_iterator + : public Proxy< vertex_nbh_edge_fwd_iterator<G> >, + public internal::proxy_impl< const util::edge<G>&, vertex_nbh_edge_fwd_iterator<G> > + { + public: + /// Construction and assignment. + /// \{ + template <typename C> + vertex_nbh_edge_fwd_iterator(const C& c); + /// \} + + /// Iterator interface. + /// \{ + /// Test if the iterator is valid. + bool is_valid() const; + /// Invalidate the iterator. + void invalidate(); + + /// Start an iteration. + void start(); + + /// Go to the next value. + void next(); + + /// Return current index + unsigned index() const; + /// \} + + /// Proxy. + /// \{ + /// Proxy subject + const util::edge<G>& subj_(); + /// \} + + protected: + void update_(); + + template <typename C> + void center_at(const C& c); + + const util::vertex<G>* c_; // Center + util::edge<G> e_; + unsigned i_; + }; + + template <typename G> + class vertex_nbh_edge_bkd_iterator + : public Proxy< vertex_nbh_edge_bkd_iterator<G> >, + public proxy_impl< const util::edge<G>&, vertex_nbh_edge_bkd_iterator<G> > + { + public: + /// Constructors. + /// \{ + template <typename C> + vertex_nbh_edge_bkd_iterator(const C& c); + /// \} + + /// Iterator interface. + /// \{ + /// Test if the iterator is valid. + bool is_valid() const; + /// Invalidate the iterator. + void invalidate(); + + /// Start an iteration. + void start(); + + /// Go to the next value. + void next(); + + /// Return current index + unsigned index() const; + /// \} + + /// Proxy. + /// \{ + /// Proxy subject + const util::edge<G>& subj_(); + /// \} + + protected: + void update_(); + + template <typename C> + void center_at(const C& c); + + const util::vertex<G>* c_; //Center + util::edge<G> e_; + unsigned i_; + }; + + +# ifndef MLN_INCLUDE_ONLY + + template <typename G> + template <typename C> + inline + vertex_nbh_edge_fwd_iterator<G>::vertex_nbh_edge_fwd_iterator(const C& c) + : e_(c.g()), i_(0) + { + //FIXME: Check if typeof(v.g()) == G + center_at(c); + } + + template <typename G> + inline + bool + vertex_nbh_edge_fwd_iterator<G>::is_valid() const + { + return i_ < c_->nmax_nbh_edges(); + } + + template <typename G> + inline + void + vertex_nbh_edge_fwd_iterator<G>::invalidate() + { + i_ = e_.g()->e_nmax(); + } + + template <typename G> + inline + void + vertex_nbh_edge_fwd_iterator<G>::start() + { + i_ = 0; + if (is_valid()) + update_(); + } + + template <typename G> + inline + void + vertex_nbh_edge_fwd_iterator<G>::next() + { + ++i_; + if (is_valid()) + update_(); + } + + template <typename G> + inline + unsigned + vertex_nbh_edge_fwd_iterator<G>::index() const + { + return i_; + } + + template <typename G> + inline + const util::edge<G>& + vertex_nbh_edge_fwd_iterator<G>::subj_() + { + return e_; + } + + template <typename G> + inline + void + vertex_nbh_edge_fwd_iterator<G>::update_() + { + mln_precondition(is_valid()); + mln_precondition(c_->is_valid()); + e_.update_id(c_->ith_nbh_edge(i_)); + } + + template <typename G> + template <typename C> + inline + void + vertex_nbh_edge_fwd_iterator<G>::center_at(const C& c) + { + internal::get_adr(c_, c); + mln_precondition(c_ != 0); + + invalidate(); + } + + + + + /*-----------------------------` + | vertex_nbh_edge_bkd_iterator | + \-----------------------------*/ + + + template <typename G> + template <typename C> + inline + vertex_nbh_edge_bkd_iterator<G>::vertex_nbh_edge_bkd_iterator(const C& c) + : e_(c.g()), i_(0) + { + //FIXME: Check if typeof(v.g()) == G + center_at(c); + } + + template <typename G> + inline + bool + vertex_nbh_edge_bkd_iterator<G>::is_valid() const + { + return i_ < c_->nmax_nbh_edges(); + } + + template <typename G> + inline + void + vertex_nbh_edge_bkd_iterator<G>::invalidate() + { + e_.update_id(e_.g()->e_nmax()); + } + + template <typename G> + inline + void + vertex_nbh_edge_bkd_iterator<G>::start() + { + i_ = c_->nmax_nbh_edges() - 1; + if (is_valid()) + update_(); + } + + template <typename G> + inline + void + vertex_nbh_edge_bkd_iterator<G>::next() + { + --i_; + if (is_valid()) + update_(); + } + + template <typename G> + inline + unsigned + vertex_nbh_edge_bkd_iterator<G>::index() const + { + return i_; + } + + template <typename G> + inline + const util::edge<G>& + vertex_nbh_edge_bkd_iterator<G>::subj_() + { + return e_; + } + + template <typename G> + inline + void + vertex_nbh_edge_bkd_iterator<G>::update_() + { + mln_precondition(is_valid()); + mln_precondition(c_->is_valid()); + e_.update_id(c_->ith_nbh_edge(i_)); + } + + template <typename G> + template <typename C> + inline + void + vertex_nbh_edge_bkd_iterator<G>::center_at(const C& c) + { + internal::get_adr(c_, c); + mln_precondition(c_ != 0); + + invalidate(); + } + + + +# endif // !MLN_INCLUDE_ONLY + + } // End of namespace mln::internal + +} // End of namespace mln + + +#endif // !MLN_UTIL_INTERNAL_GRAPH_NBH_EDGE_ITER_HH + diff --git a/milena/mln/util/internal/graph_vertex_nbh_vertex_iter.hh b/milena/mln/util/internal/graph_vertex_nbh_vertex_iter.hh new file mode 100644 index 0000000..d51bc29 --- /dev/null +++ b/milena/mln/util/internal/graph_vertex_nbh_vertex_iter.hh @@ -0,0 +1,320 @@ +// Copyright (C) 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. This exception does not however invalidate any other +// reasons why the executable file might be covered by the GNU General +// Public License. + +#ifndef MLN_UTIL_INTERNAL_GRAPH_VERTEX_NBH_VERTEX_ITER_HH +# define MLN_UTIL_INTERNAL_GRAPH_VERTEX_NBH_VERTEX_ITER_HH + +# include <mln/core/concept/proxy.hh> + +/// \file mln/util/internal/graph_vertex_nbh_vertex_iter.hh +/// \brief Implementation for graph vertex iterators centered to a vertex. + +namespace mln +{ + + namespace internal + { + + template <typename G> + class vertex_nbh_vertex_fwd_iterator + : public Proxy< vertex_nbh_vertex_fwd_iterator<G> >, + public internal::proxy_impl< const util::vertex<G>&, vertex_nbh_vertex_fwd_iterator<G> > + { + public: + /// Construction and assignment. + /// \{ + template <typename C> + vertex_nbh_vertex_fwd_iterator(const C& c); + /// \} + + /// Manipulation. + /// \{ + /// Test if the iterator is valid. + bool is_valid() const; + /// Invalidate the iterator. + void invalidate(); + /// \} + + /// Start an iteration. + void start(); + + /// Go to the next value. + void next(); + + /// Return current index + unsigned index() const; + + /// Proxy. + /// \{ + /// Proxy subject + const util::vertex<G>& subj_(); + /// \} + + protected: + void update_(); + + template <typename C> + void center_at(const C& c); + + const util::vertex<G>* c_; + util::vertex<G> v_; + unsigned i_; + }; + + template <typename G> + class vertex_nbh_vertex_bkd_iterator + : public Proxy< vertex_nbh_vertex_bkd_iterator<G> >, + public proxy_impl< const util::vertex<G>&, vertex_nbh_vertex_fwd_iterator<G> > + { + public: + /// Constructors. + /// \{ + template <typename C> + vertex_nbh_vertex_bkd_iterator(const C& v); + /// \} + + /// Manipulation. + /// \{ + /// Test if the iterator is valid. + bool is_valid() const; + /// Invalidate the iterator. + void invalidate(); + + /// Start an iteration. + void start(); + + /// Go to the next value. + void next(); + + /// Return current index + unsigned index() const; + /// \} + + /// Proxy. + /// \{ + /// Proxy subject + const util::vertex<G>& subj_(); + /// \} + + protected: + void update_(); + + template <typename C> + void center_at(const C& c); + + const util::vertex<G>* c_; //Center + util::vertex<G> v_; + unsigned i_; + }; + + +# ifndef MLN_INCLUDE_ONLY + + + template <typename G> + template <typename C> + inline + vertex_nbh_vertex_fwd_iterator<G>::vertex_nbh_vertex_fwd_iterator(const C& c) + : v_(c.g()), i_(0) + { + //FIXME: Check if typeof(v.g()) == G + center_at(c); + } + + template <typename G> + inline + bool + vertex_nbh_vertex_fwd_iterator<G>::is_valid() const + { + return i_ < c_->nmax_nbh_vertices(); + } + + template <typename G> + inline + void + vertex_nbh_vertex_fwd_iterator<G>::invalidate() + { + i_ = v_.g()->v_nmax(); + } + + template <typename G> + inline + void + vertex_nbh_vertex_fwd_iterator<G>::start() + { + i_ = 0; + if (is_valid()) + update_(); + } + + template <typename G> + inline + void + vertex_nbh_vertex_fwd_iterator<G>::next() + { + ++i_; + if (is_valid()) + update_(); + } + + template <typename G> + inline + unsigned + vertex_nbh_vertex_fwd_iterator<G>::index() const + { + return i_; + } + + template <typename G> + inline + const util::vertex<G>& + vertex_nbh_vertex_fwd_iterator<G>::subj_() + { + return v_; + } + + template <typename G> + inline + void + vertex_nbh_vertex_fwd_iterator<G>::update_() + { + mln_precondition(is_valid()); + mln_precondition(c_->is_valid()); + v_.update_id(c_->ith_nbh_vertex(i_)); + } + + template <typename G> + template <typename C> + inline + void + vertex_nbh_vertex_fwd_iterator<G>::center_at(const C& c) + { + internal::get_adr(c_, c); + mln_precondition(c_ != 0); + + invalidate(); + } + + + /*-------------------------------` + | vertex_nbh_vertex_bkd_iterator | + \-------------------------------*/ + + + template <typename G> + template <typename C> + inline + vertex_nbh_vertex_bkd_iterator<G>::vertex_nbh_vertex_bkd_iterator(const C& c) + : v_(c.g()), i_(0) + { + //FIXME: Check if typeof(v.g()) == G + center_at(c); + } + + template <typename G> + inline + bool + vertex_nbh_vertex_bkd_iterator<G>::is_valid() const + { + return i_ < c_->nmax_nbh_vertices(); + } + + template <typename G> + inline + void + vertex_nbh_vertex_bkd_iterator<G>::invalidate() + { + v_.update_id(v_.g()->e_nmax()); + } + + template <typename G> + inline + void + vertex_nbh_vertex_bkd_iterator<G>::start() + { + i_ = c_->nmax_nbh_edges() - 1; + if (is_valid()) + update_(); + } + + template <typename G> + inline + void + vertex_nbh_vertex_bkd_iterator<G>::next() + { + --i_; + if (is_valid()) + update_(); + } + + template <typename G> + inline + unsigned + vertex_nbh_vertex_bkd_iterator<G>::index() const + { + return i_; + } + + template <typename G> + inline + const util::vertex<G>& + vertex_nbh_vertex_bkd_iterator<G>::subj_() + { + return v_; + } + + template <typename G> + inline + void + vertex_nbh_vertex_bkd_iterator<G>::update_() + { + mln_precondition(is_valid()); + mln_precondition(c_->is_valid()); + v_.update_id(c_->ith_nbh_vertex(i_)); + } + + template <typename G> + template <typename C> + inline + void + vertex_nbh_vertex_bkd_iterator<G>::center_at(const C& c) + { + internal::get_adr(c_, c); + mln_precondition(c_ != 0); + + invalidate(); + } + +# endif // !MLN_INCLUDE_ONLY + + } // End of namespace mln::internal + +} // End of namespace mln + + +#endif // !MLN_UTIL_INTERNAL_GRAPH_VERTEX_NBH_VERTEX_ITER_HH + diff --git a/milena/tests/util/graph.cc b/milena/tests/util/graph.cc index d20b02d..60a609a 100644 --- a/milena/tests/util/graph.cc +++ b/milena/tests/util/graph.cc @@ -35,7 +35,7 @@ int main () { using namespace mln; - util::graph<void> g; + util::graph g; g.add_vertex (); // 0 g.add_vertex (); // 1 @@ -51,4 +51,109 @@ int main () g.add_edge (1, 0); g.add_edge (5, 3); g.add_edge (2, 1); + + + // Vertex iter and edge iter + { + unsigned i = 0; + mln_vertex_fwd_iter_(util::graph) v(g); + for_all(v) + mln_assertion(i++ == v.index()); + mln_assertion(i != 0); + + i = 0; + mln_edge_fwd_iter_(util::graph) e(g); + for_all(e) + mln_assertion(i++ == e.index()); + mln_assertion(i != 0); + } + { + unsigned i = g.v_nmax() - 1; + mln_vertex_bkd_iter_(util::graph) v(g); + for_all(v) + mln_assertion(i-- == v.index()); + mln_assertion(i != g.v_nmax() - 1); + + i = g.e_nmax() - 1; + mln_edge_bkd_iter_(util::graph) e(g); + for_all(e) + mln_assertion(i-- == e.index()); + mln_assertion(i != g.e_nmax() - 1); + } + + // vertex iter + Edge nbh iter + { + mln_vertex_fwd_iter_(util::graph) v(g); + mln_vertex_nbh_edge_fwd_iter_(util::graph) n(v); + for_all(v) + { + unsigned i = 0; + for_all(n) + mln_assertion(i++ == n.index()); + mln_assertion(i != 0); + } + } + { + mln_vertex_bkd_iter_(util::graph) v(g); + mln_vertex_nbh_edge_bkd_iter_(util::graph) e(v); + for_all(v) + { + unsigned i = v.nmax_nbh_edges(); + for_all(e) + mln_assertion(--i == e.index()); + mln_assertion((v.nmax_nbh_edges() == 0 && i == 0) || i != v.nmax_nbh_edges()); + } + } + + { + mln_edge_fwd_iter_(util::graph) e(g); + mln_edge_nbh_edge_fwd_iter_(util::graph) n(e); + for_all(e) + { + unsigned i = 0; + for_all(n) + ++i; + // we check i == e.nmax_nbh_edges() - 2 since e is it's own neighboor and the + // iterator skip it. + mln_assertion((i == 0 && e.nmax_nbh_edges() < 2) || i == e.nmax_nbh_edges() - 2); + } + } + { + mln_edge_bkd_iter_(util::graph) e(g); + mln_edge_nbh_edge_bkd_iter_(util::graph) n(e); + for_all(e) + { + //std::cout << "== e.id() = " << e.id() << std::endl; + unsigned i = e.nmax_nbh_edges(); + for_all(n) + --i; + // we check i == e.nmax_nbh_edges() - 2 since e is it's own neighboor and the + // iterator skip it. + mln_assertion((i == e.nmax_nbh_edges() && e.nmax_nbh_edges() < 2) || i == 2); + + } + } + + { + mln_vertex_fwd_iter_(util::graph) v(g); + mln_vertex_nbh_vertex_fwd_iter_(util::graph) n(v); + for_all(v) + { + unsigned i = 0; + for_all(n) + ++i; + mln_assertion(i == v.nmax_nbh_vertices()); + } + } + { + mln_vertex_bkd_iter_(util::graph) v(g); + mln_vertex_nbh_vertex_bkd_iter_(util::graph) n(v); + for_all(v) + { + unsigned i = v.nmax_nbh_vertices(); + for_all(n) + --i; + mln_assertion(i == 0); + } + } } -- 1.5.6.5