[Olena-patches] 2885: Introduce a dual graph class.

* mln/core/concept/graph.hh: does not force add_* methods. * mln/util/dual_graph.hh: new class. * mln/util/graph.hh: cleanup comments * mln/util/internal/graph_edge.hh: add missing operator<<. * mln/util/internal/graph_nbh_iter_base.hh, * mln/util/internal/graph_iter_base.hh: add operator unsigned(). * tests/util/Makefile.am, * tests/util/dual_graph.cc: Add a new test. --- milena/ChangeLog | 18 ++ milena/mln/core/concept/graph.hh | 2 - milena/mln/util/{graph.hh => dual_graph.hh} | 243 +++++++++++------------ milena/mln/util/graph.hh | 14 +- milena/mln/util/internal/graph_edge.hh | 19 ++- milena/mln/util/internal/graph_iter_base.hh | 11 + milena/mln/util/internal/graph_nbh_iter_base.hh | 10 + milena/tests/util/Makefile.am | 2 + milena/tests/util/dual_graph.cc | 164 +++++++++++++++ 9 files changed, 338 insertions(+), 145 deletions(-) copy milena/mln/util/{graph.hh => dual_graph.hh} (58%) create mode 100644 milena/tests/util/dual_graph.cc diff --git a/milena/ChangeLog b/milena/ChangeLog index c947990..809f727 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,3 +1,21 @@ +2008-11-17 Guillaume Lazzara &lt;guillaume.lazzara(a)lrde.epita.fr&gt; + + Introduce a dual graph class. + + * mln/core/concept/graph.hh: does not force add_* methods. + + * mln/util/dual_graph.hh: new class. + + * mln/util/graph.hh: cleanup comments + + * mln/util/internal/graph_edge.hh: add missing operator<<. + + * mln/util/internal/graph_nbh_iter_base.hh, + * mln/util/internal/graph_iter_base.hh: add operator unsigned(). + + * tests/util/Makefile.am, + * tests/util/dual_graph.cc: Add a new test. + 2008-11-14 Thierry Geraud &lt;thierry.geraud(a)lrde.epita.fr&gt; Factor code for erosion on lines. diff --git a/milena/mln/core/concept/graph.hh b/milena/mln/core/concept/graph.hh index c98d9e5..e89acc2 100644 --- a/milena/mln/core/concept/graph.hh +++ b/milena/mln/core/concept/graph.hh @@ -113,8 +113,6 @@ namespace mln 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; diff --git a/milena/mln/util/graph.hh b/milena/mln/util/dual_graph.hh similarity index 58% copy from milena/mln/util/graph.hh copy to milena/mln/util/dual_graph.hh index dfcbc23..3533e7c 100644 --- a/milena/mln/util/graph.hh +++ b/milena/mln/util/dual_graph.hh @@ -1,4 +1,4 @@ -// Copyright (C) 2007, 2008 EPITA Research and Development Laboratory +// Copyright (C) 2008 EPITA Research and Development Laboratory // (LRDE) // // This file is part of the Olena Library. This library is free @@ -26,10 +26,10 @@ // reasons why the executable file might be covered by the GNU General // Public License. -#ifndef MLN_UTIL_GRAPH_HH -# define MLN_UTIL_GRAPH_HH +#ifndef MLN_UTIL_DUAL_GRAPH_HH +# define MLN_UTIL_DUAL_GRAPH_HH -/// \file mln/util/graph.hh +/// \file mln/util/dual_graph.hh /// Definitions of undirected graphs. # include <mln/util/internal/graph_base.hh> @@ -43,7 +43,8 @@ namespace mln namespace util { /// Fwd declaration. - class graph; + template <typename G> + class dual_graph; } @@ -51,23 +52,22 @@ namespace mln { /// Data structure for \c mln::image2d<T>. - template <> - struct data<util::graph> + template <typename G> + struct data< util::dual_graph<G> > { - typedef util::graph G; + typedef std::vector<std::vector<unsigned> > vertices_t; typedef std::vector<util::ord_pair<unsigned> > edges_t; - typedef std::set<util::ord_pair<unsigned> > edges_set_t; data(); + data(const G& g); ~data(); + G g_; /// 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::internal @@ -76,14 +76,18 @@ namespace mln namespace util { - /// \brief Undirected graph. - class graph : public internal::graph_base<graph> + /// Undirected dual graph of a graph of type \tparam G. + template <typename G> + class dual_graph : public internal::graph_base< dual_graph<G> > { /// The super class. - typedef internal::graph_base<graph> super; + typedef internal::graph_base< dual_graph<G> > super; - using super::vertex_data_t; - using super::edge_data_t; + typedef typename super::vertex_t vertex_t; + typedef typename super::edge_t edge_t; + + typedef typename super::vertex_data_t vertex_data_t; + typedef typename super::edge_data_t edge_data_t; public: /// The type of the set of vertices. @@ -91,71 +95,46 @@ namespace mln /// The type of the set of edges. typedef std::vector<edge_data_t> edges_t; - /// A set to test the presence of a given edge. - typedef std::set<edge_data_t> edges_set_t; /// Iterator types /// \{ /// Vertex iterators /// \{ - typedef mln::internal::vertex_fwd_iterator<graph> vertex_fwd_iter; - typedef mln::internal::vertex_bkd_iterator<graph> vertex_bkd_iter; + typedef mln::internal::vertex_fwd_iterator< dual_graph<G> > + vertex_fwd_iter; + typedef mln::internal::vertex_bkd_iterator< dual_graph<G> > + vertex_bkd_iter; typedef vertex_fwd_iter vertex_iter; - /// \} - /// Vertex centered edge iterators - /// \{ - 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; - /// \} - - /// Vertex centered vertex iterators - /// \{ - 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; - /// \} - - /// Edge iterators - /// \{ - typedef mln::internal::edge_fwd_iterator<graph> edge_fwd_iter; - typedef mln::internal::edge_bkd_iterator<graph> edge_bkd_iter; + typedef mln::internal::edge_fwd_iterator< dual_graph<G> > + edge_fwd_iter; + typedef mln::internal::edge_bkd_iterator< dual_graph<G> > + edge_bkd_iter; typedef edge_fwd_iter edge_iter; - /// \} - /// 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; /// \} /// \} - graph(); + dual_graph(); + dual_graph(const G& g); /// Vertex oriented. /// \{ /// Shortcuts factoring the insertion of vertices and edges. /// \{ - /// \brief Add a vertex. - /// - /// \return The id of the new vertex. - unsigned add_vertex(); - /// Return the vertex whose id is \a v. /// \{ vertex_t vertex(unsigned id_v) const; /// \} - /// \brief Return the number of vertices in the graph. + /// Return the number of vertices in the graph. size_t v_nmax() const; /// Check whether a vertex id \p id_v exists in the graph. bool has_v(unsigned id_v) const; /// Check whether an edge \p v exists in the graph. - template <typename G> - bool has_v(const util::vertex<G>& v) const; + template <typename G2> + bool has_v(const util::vertex<G2>& v) const; /// Return the number of adjacent edges of vertex \p id_v. @@ -176,23 +155,17 @@ namespace mln /// Edge oriented. /// \{ - /// \brief Add an edge. - /// - /// \return The id of the new edge if it does not exist yet; - /// otherwise, return <tt>mln_max(unsigned)</tt>. - unsigned add_edge(unsigned id_v1, unsigned id_v2); - /// Return the edge whose id is \a e. edge_t edge(unsigned e) const; - /// \brief Return the number of edges in the graph. + /// Return the number of edges in the graph. size_t e_nmax() const; /// Return whether \p id_e is in the graph. bool has_e(unsigned id_e) const; /// Return whether \p e is in the graph. - template <typename G> - bool has_e(const util::edge<G>& e) const; + template <typename G2> + bool has_e(const util::edge<G2>& e) const; /// Return the first vertex associated to the edge \p id_e. @@ -213,6 +186,8 @@ namespace mln bool is_subgraph_of(const G2& g) const; /// \} + protected: + using super::data_; }; } // end of namespace mln::util @@ -227,13 +202,32 @@ namespace mln namespace internal { + template <typename G> inline - data<util::graph>::data() + data< util::dual_graph<G> >::data() { } + template <typename G> inline - data<util::graph>::~data() + data< util::dual_graph<G> >::data(const G& g) + { + g_ = g; + vertices_.resize(g.e_nmax()); + mln_edge_iter(G) e(g); + mln_edge_nbh_edge_iter(G) ne(e); + + for_all(e) + for_all(ne) + { + vertices_[e].push_back(edges_.size()); + edges_.push_back(util::ord_pair<unsigned>(e, ne)); + } + } + + template <typename G> + inline + data< util::dual_graph<G> >::~data() { } @@ -242,69 +236,73 @@ namespace mln namespace util { + template <typename G> inline - graph::graph() + dual_graph<G>::dual_graph() { - this->data_ = new mln::internal::data<util::graph>(); + this->data_ = new mln::internal::data< util::dual_graph<G> >(); } - /*---------------. - | Vertex related | - `---------------*/ - + template <typename G> inline - unsigned - graph::add_vertex() + dual_graph<G>::dual_graph(const G& g) { - /* FIXME: This is not thread-proof (these two lines should - form an atomic section). */ - data_->vertices_.resize(data_->vertices_.size() + 1); - - return v_nmax() - 1; + this->data_ = new mln::internal::data< util::dual_graph<G> >(g); } + /*---------------. + | Vertex related | + `---------------*/ + + template <typename G> inline - graph::vertex_t - graph::vertex(unsigned id_v) const + typename dual_graph<G>::vertex_t + dual_graph<G>::vertex(unsigned id_v) const { mln_assertion(has_v(id_v)); return vertex_t(*this, id_v); } + template <typename G> inline size_t - graph::v_nmax() const + dual_graph<G>::v_nmax() const { - return data_->vertices_.size(); + return data_->g_.e_nmax(); } + template <typename G> inline bool - graph::has_v(unsigned id_v) const + dual_graph<G>::has_v(unsigned id_v) const { - return id_v < data_->vertices_.size(); + return data_->g_.has_e(id_v); } template <typename G> + template <typename G2> inline bool - graph::has_v(const util::vertex<G>& v) const + dual_graph<G>::has_v(const util::vertex<G2>& v) const { + //FIXME: not sure... return v.graph().is_subgraph_of(*this) && has_v(v.id()); } + template <typename G> inline size_t - graph::v_nmax_nbh_edges(unsigned id_v) const + dual_graph<G>::v_nmax_nbh_edges(unsigned id_v) const { mln_precondition(has_v(id_v)); - return data_->vertices_[id_v].size(); + return data_->g_.e_nmax_nbh_edges(id_v); } + template <typename G> inline unsigned - graph::v_ith_nbh_edge(unsigned id_v, unsigned i) const + dual_graph<G>::v_ith_nbh_edge(unsigned id_v, unsigned i) const { mln_precondition(has_v(id_v)); if (i >= v_nmax_nbh_edges(id_v)) @@ -312,22 +310,24 @@ namespace mln return data_->vertices_[id_v][i]; } + template <typename G> inline size_t - graph::v_nmax_nbh_vertices(unsigned id_v) const + dual_graph<G>::v_nmax_nbh_vertices(unsigned id_v) const { mln_precondition(has_v(id_v)); return v_nmax_nbh_edges(id_v); } + template <typename G> inline unsigned - graph::v_ith_nbh_vertex(unsigned id_v, unsigned i) const + dual_graph<G>::v_ith_nbh_vertex(unsigned id_v, unsigned i) const { mln_precondition(has_v(id_v)); - unsigned id_e = v_ith_nbh_edge(id_v, i); - return v_other(id_e, id_v); + unsigned id_e = this->v_ith_nbh_edge(id_v, i); + return this->v_other(id_e, id_v); } @@ -335,91 +335,71 @@ namespace mln | Edges related | `---------------*/ + template <typename G> inline - unsigned - graph::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 (data_->edges_set_.find(edge) != data_->edges_set_.end ()) - { - // Return the erroneous value. - return mln_max(unsigned); - } - else - { - // Otherwise insert it into the graph. - /* FIXME: This is not thread-proof (these two lines should - form an atomic section). */ - data_->edges_.push_back(edge); - unsigned id = data_->edges_.size() - 1; - - // Update the set of edges. - data_->edges_set_.insert(edge); - data_->vertices_[edge.first()].push_back(id); - data_->vertices_[edge.second()].push_back(id); - - return id; - } - } - - inline - graph::edge_t - graph::edge(unsigned e) const + typename dual_graph<G>::edge_t + dual_graph<G>::edge(unsigned e) const { mln_assertion(e < e_nmax()); return edge_t(*this, e); } + template <typename G> inline size_t - graph::e_nmax() const + dual_graph<G>::e_nmax() const { return data_->edges_.size(); } + template <typename G> inline bool - graph::has_e(unsigned id_e) const + dual_graph<G>::has_e(unsigned id_e) const { return id_e < data_->edges_.size(); } template <typename G> + template <typename G2> inline bool - graph::has_e(const util::edge<G>& e) const + dual_graph<G>::has_e(const util::edge<G2>& e) const { return e.graph().is_subgraph_of(*this) && has_e(e.id()); } + template <typename G> inline unsigned - graph::v1(unsigned id_e) const + dual_graph<G>::v1(unsigned id_e) const { mln_precondition(has_e(id_e)); return data_->edges_[id_e].first(); } + template <typename G> inline unsigned - graph::v2(unsigned id_e) const + dual_graph<G>::v2(unsigned id_e) const { mln_precondition(has_e(id_e)); return data_->edges_[id_e].second(); } + template <typename G> inline size_t - graph::e_nmax_nbh_edges(unsigned id_e) const + dual_graph<G>::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 G> inline unsigned - graph::e_ith_nbh_edge(unsigned id_e, unsigned i) const + dual_graph<G>::e_ith_nbh_edge(unsigned id_e, unsigned i) const { mln_precondition(has_e(id_e)); if (i >= e_nmax_nbh_edges(id_e)) @@ -432,10 +412,11 @@ namespace mln } + template <typename G> template <typename G2> inline bool - graph::is_subgraph_of(const G2& g) const + dual_graph<G>::is_subgraph_of(const G2& g) const { return g.graph_id() == this->graph_id(); } @@ -447,4 +428,4 @@ namespace mln # endif // ! MLN_INCLUDE_ONLY -#endif // ! MLN_UTIL_GRAPH_HH +#endif // ! MLN_UTIL_DUAL_GRAPH_HH diff --git a/milena/mln/util/graph.hh b/milena/mln/util/graph.hh index dfcbc23..30b19bd 100644 --- a/milena/mln/util/graph.hh +++ b/milena/mln/util/graph.hh @@ -76,14 +76,14 @@ namespace mln namespace util { - /// \brief Undirected graph. + /// Undirected graph. class graph : public internal::graph_base<graph> { /// The super class. typedef internal::graph_base<graph> super; - using super::vertex_data_t; - using super::edge_data_t; + typedef super::vertex_data_t vertex_data_t; + typedef super::edge_data_t edge_data_t; public: /// The type of the set of vertices. @@ -138,7 +138,7 @@ namespace mln /// \{ /// Shortcuts factoring the insertion of vertices and edges. /// \{ - /// \brief Add a vertex. + /// Add a vertex. /// /// \return The id of the new vertex. unsigned add_vertex(); @@ -148,7 +148,7 @@ namespace mln vertex_t vertex(unsigned id_v) const; /// \} - /// \brief Return the number of vertices in the graph. + /// Return the number of vertices in the graph. size_t v_nmax() const; /// Check whether a vertex id \p id_v exists in the graph. @@ -176,7 +176,7 @@ namespace mln /// Edge oriented. /// \{ - /// \brief Add an edge. + /// Add an edge. /// /// \return The id of the new edge if it does not exist yet; /// otherwise, return <tt>mln_max(unsigned)</tt>. @@ -185,7 +185,7 @@ namespace mln /// Return the edge whose id is \a e. edge_t edge(unsigned e) const; - /// \brief Return the number of edges in the graph. + /// Return the number of edges in the graph. size_t e_nmax() const; /// Return whether \p id_e is in the graph. diff --git a/milena/mln/util/internal/graph_edge.hh b/milena/mln/util/internal/graph_edge.hh index 06e39d4..bab22d8 100644 --- a/milena/mln/util/internal/graph_edge.hh +++ b/milena/mln/util/internal/graph_edge.hh @@ -110,12 +110,16 @@ namespace mln }; template <typename G> + std::ostream& + operator<<(std::ostream& ostr, edge<G>& p); + + template <typename G> bool - operator==(const util::edge<G>& lhs, const util::edge<G>& rhs); + operator==(const edge<G>& lhs, const edge<G>& rhs); template <typename G> bool - operator< (const util::edge<G>& lhs, const util::edge<G>& rhs); + operator< (const edge<G>& lhs, const edge<G>& rhs); } // End of namespace mln::util @@ -283,12 +287,17 @@ namespace mln return g_.e_ith_nbh_edge(id_, i); } - + template <typename G> + std::ostream& + operator<<(std::ostream& ostr, edge<G>& p) + { + return ostr << p.id(); + } template <typename G> inline bool - operator==(const util::edge<G>& lhs, const util::edge<G>& rhs) + operator==(const edge<G>& lhs, const edge<G>& rhs) { return lhs.pair_vertex_ == rhs.pair_vertex_; } @@ -296,7 +305,7 @@ namespace mln template <typename G> inline bool - operator< (const util::edge<G>& lhs, const util::edge<G>& rhs) + operator< (const edge<G>& lhs, const edge<G>& rhs) { return lhs.pair_vertex_ < rhs.pair_vertex_; } diff --git a/milena/mln/util/internal/graph_iter_base.hh b/milena/mln/util/internal/graph_iter_base.hh index a901192..96777af 100644 --- a/milena/mln/util/internal/graph_iter_base.hh +++ b/milena/mln/util/internal/graph_iter_base.hh @@ -62,6 +62,9 @@ namespace mln /// Return current index unsigned index() const; + + /// Conversion operator. Returns the element id. + operator unsigned() const; /// \} /// Proxy. @@ -76,6 +79,7 @@ namespace mln P p_; }; + # ifndef MLN_INCLUDE_ONLY template <typename G, typename P, typename E> @@ -128,6 +132,13 @@ namespace mln template <typename G, typename P, typename E> inline + graph_iter_base<G, P, E>::operator unsigned() const + { + return p_.id(); + } + + template <typename G, typename P, typename E> + inline const P& graph_iter_base<G, P, E>::subj_() { diff --git a/milena/mln/util/internal/graph_nbh_iter_base.hh b/milena/mln/util/internal/graph_nbh_iter_base.hh index 14950a1..f6f02ea 100644 --- a/milena/mln/util/internal/graph_nbh_iter_base.hh +++ b/milena/mln/util/internal/graph_nbh_iter_base.hh @@ -61,6 +61,9 @@ namespace mln /// Return current index unsigned index() const; + + /// Conversion operator. Returns the element ID. + operator unsigned() const; /// \} /// Proxy. @@ -145,6 +148,13 @@ namespace mln template <typename G, typename C, typename P, typename E> inline + nbh_iterator_base<G, C, P, E>::operator unsigned() const + { + return p_.id(); + } + + template <typename G, typename C, typename P, typename E> + inline const P& nbh_iterator_base<G, C, P, E>::subj_() { diff --git a/milena/tests/util/Makefile.am b/milena/tests/util/Makefile.am index d0fe4be..fcfb902 100644 --- a/milena/tests/util/Makefile.am +++ b/milena/tests/util/Makefile.am @@ -6,6 +6,7 @@ include $(top_srcdir)/milena/tests/tests.mk check_PROGRAMS = \ branch_iter \ branch_iter_ind \ + dual_graph \ eat \ graph \ lazy_set \ @@ -19,6 +20,7 @@ check_PROGRAMS = \ branch_iter_SOURCES = branch_iter.cc branch_iter_ind_SOURCES = branch_iter_ind.cc +dual_graph_SOURCES = dual_graph.cc eat_SOURCES = eat.cc graph_SOURCES = graph.cc lazy_set_SOURCES = lazy_set.cc diff --git a/milena/tests/util/dual_graph.cc b/milena/tests/util/dual_graph.cc new file mode 100644 index 0000000..ff8c8ad --- /dev/null +++ b/milena/tests/util/dual_graph.cc @@ -0,0 +1,164 @@ +// 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. + +/// \file tests/util/dual_graph.cc +/// test of mln::util::dual_graph + +#include <mln/util/graph.hh> +#include <mln/util/dual_graph.hh> +#include <iostream> + +int main () +{ + using namespace mln; + + util::graph g; + + g.add_vertex (); // 0 + g.add_vertex (); // 1 + g.add_vertex (); // 2 + g.add_vertex (); // 3 + g.add_vertex (); // 4 + g.add_vertex (); // 5 + g.add_edge (0, 1); + g.add_edge (1, 0); // Not inserted twice + g.add_edge (0, 2); + g.add_edge (3, 4); + g.add_edge (4, 5); + g.add_edge (5, 4); // Not inserted twice + g.add_edge (5, 3); + g.add_edge (2, 1); + + typedef util::dual_graph<util::graph> DG; + DG dg(g); + + // Vertex iter and edge iter + { + unsigned i = 0; + mln_vertex_fwd_iter_(DG) v(dg); + for_all(v) + std::cout << v.index() << std::endl; +// mln_assertion(i++ == v.index()); + //mln_assertion(i != 0); + + i = 0; + mln_edge_fwd_iter_(util::graph) e(g); + for_all(e) + std::cout << e << std::endl; +// 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