[Olena-patches] 2484: Add p_edges.

--- ChangeLog | 81 ++++++++ milena/mln/core/site_set/p_edges.hh | 262 ++++++++++++++++++++++++++ milena/mln/util/internal/graph_edge_psite.hh | 126 ++++++++++++ milena/tests/core/site_set/Makefile.am | 2 + milena/tests/core/site_set/p_edges.cc | 93 +++++++++ 5 files changed, 564 insertions(+), 0 deletions(-) create mode 100644 milena/mln/core/site_set/p_edges.hh create mode 100644 milena/mln/util/internal/graph_edge_psite.hh create mode 100644 milena/tests/core/site_set/p_edges.cc diff --git a/ChangeLog b/ChangeLog index 0353d7e..e4e58c0 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,84 @@ +2008-10-03 Guillaume Lazzara &lt;z(a)lrde.epita.fr&gt; + + Add p_edges. + + * milena/mln/core/site_set/p_edges.hh: + The site set p_edges. + + * milena/mln/util/internal/graph_edge_psite.hh: + The associated psite. + + * milena/tests/core/site_set/Makefile.am, + * milena/tests/core/site_set/p_edges.cc: + Add a basic test. + +2008-10-03 Guillaume Lazzara &lt;z(a)lrde.epita.fr&gt; + + Refactor graph_vertex_psite. + + * milena/mln/util/internal/graph_vertex_psite.hh: + Refactor this class... + * milena/mln/util/internal/graph_psite_base.hh: + ... here. + +2008-10-03 Guillaume Lazzara &lt;z(a)lrde.epita.fr&gt; + + Fix util::graph<G>::is_subgraph_of(). + + * milena/mln/util/graph.hh: here. + +2008-10-03 Guillaume Lazzara &lt;z(a)lrde.epita.fr&gt; + + Add missing methods to vertex and edge. + + * milena/mln/util/internal/graph_edge.hh: + Add change_graph(). + * milena/mln/util/internal/graph_vertex.hh: + Add invalidate(). + + +2008-10-03 Guillaume Lazzara &lt;z(a)lrde.epita.fr&gt; + + Add p_vertices. + + * milena/mln/core/site_set/p_vertices.hh: + The site set p_vertices. + + * milena/mln/util/internal/graph_vertex_psite.hh: + The psite associated to p_vertices. + + * milena/tests/core/site_set/p_vertices.cc, + * milena/tests/core/site_set/Makefile.am: + Add a small test. + +2008-10-03 Guillaume Lazzara &lt;z(a)lrde.epita.fr&gt; + + Add a missing method to graph_vertex_iter. + + * milena/mln/util/internal/graph_vertex_iter.hh: + Add a missing update_graph() method. + +2008-10-03 Guillaume Lazzara &lt;z(a)lrde.epita.fr&gt; + + Fix invalid compilation of graph_vertex. + + * milena/mln/util/internal/graph_vertex.hh: + Remove useless const and a wrong precondition. + +2008-10-03 Guillaume Lazzara &lt;z(a)lrde.epita.fr&gt; + + Fix missing methods in graph_base. + + * milena/mln/util/internal/graph_base.hh: + Add new has() overload for convenience. + +2008-10-03 Guillaume Lazzara &lt;z(a)lrde.epita.fr&gt; + + Update p_graph_piter. + + * milena/mln/core/site_set/p_graph_piter.hh: + update in order to make it work with the new graph structure. + 2008-09-30 Thierry Geraud &lt;thierry.geraud(a)lrde.epita.fr&gt; Update reconstruction algorithms in theo's sandbox. diff --git a/milena/mln/core/site_set/p_edges.hh b/milena/mln/core/site_set/p_edges.hh new file mode 100644 index 0000000..3c94998 --- /dev/null +++ b/milena/mln/core/site_set/p_edges.hh @@ -0,0 +1,262 @@ + // 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_CORE_SITE_SET_P_EDGES_HH +# define MLN_CORE_SITE_SET_P_EDGES_HH + + /// \file mln/core/site_set/p_edges.hh + /// \brief Definition of a site set based on graph edges. + +# include <mln/core/internal/site_set_base.hh> +# include <mln/core/site_set/p_graph_piter.hh> +# include <mln/util/internal/graph_edge_psite.hh> +# include <mln/util/graph.hh> + + +namespace mln +{ + // Forward declaration. + template <typename G, typename F> struct p_edges; + + namespace trait + { + template <typename G, typename F> + struct site_set_< p_edges<G, F> > + { + // FIXME: I don't know what to use yet! + typedef trait::site_set::nsites::known nsites; + typedef trait::site_set::bbox::unknown bbox; + typedef trait::site_set::contents::fixed contents; + typedef trait::site_set::arity::unique arity; + }; + } // end of namespace mln::trait + + + template <typename G, typename F> + class p_edges + : public internal::site_set_base_< typename F::result, p_edges<G, F> > + { + typedef util::edge<G> edge_t; + + typedef p_edges<G, F> self_; + typedef internal::site_set_base_< typename F::result, self_ > super_; + + typedef G graph_t; + + public: + /// \brief Construct a graph edge psite set from a graph and a function. + /// + /// \param gr The graph upon which the graph edge psite set is built. + /// \param f the function mapping edges and sites. + p_edges(const graph_t& gr, const F& f); + + /// Associated types. + /// \{ + /// Element associated type. + typedef mln_site(super_) element; + /// Point_Site associated type. + typedef internal::edge_psite<G, F> psite; + + /// Forward Site_Iterator associated type. + typedef p_graph_piter< self_, mln_edge_fwd_iter(G) > fwd_piter; + + /// Backward Site_Iterator associated type. + typedef p_graph_piter< self_, mln_edge_bkd_iter(G) > bkd_piter; + + /// Site_Iterator associated type. + typedef fwd_piter piter; + /// \} + + /// \brief Return The number of points (sites) of the set, i.e., + /// the number of \em edges. + size_t nsites() const; + + /// Return The number of edges in the graph. + std::size_t nedges() const; + + /// Is this site set valid? + bool is_valid() const; + /// Invalidate this site set. + void invalidate(); + + /// Does this site set has site \a p? + bool has(const psite& p) const; + + /// Does this site set has edge \a e? + template <typename G2> + bool has(const util::edge<G2>& e) const; + + // FIXME: Dummy. + std::size_t memory_size() const; + + /// Accessors. + /// \{ + /// Return the graph associated to this site set + const graph_t& g() const; + /// Return the mapping function. + F function() const; + /// \} + + private: + mlc_const(graph_t)* g_; + F f_; + }; + + + /// \brief Comparison between two mln::p_edges's. + /// + /// Two mln::p_edges's are considered equal if they share the + /// same graph. + template <typename G, typename F> + bool + operator==(const p_edges<G, F>& lhs, const p_edges<G, F>& rhs); + + + /// \brief Inclusion of a mln::p_edges in another one. + /// + /// \todo Refine this later, when we are able to express subgraph + /// relations. + template <typename G, typename F> + bool + operator<=(const p_edges<G, F>& lhs, const p_edges<G, F>& rhs); + +} // end of mln + + +# ifndef MLN_INCLUDE_ONLY + +namespace mln +{ + + template <typename G, typename F> + inline + p_edges<G, F>::p_edges(const graph_t& g, const F& f) + : g_ (&g), f_(f) + { + } + + template <typename G, typename F> + inline + size_t + p_edges<G, F>::nsites() const + { + return nedges(); + } + + template <typename G, typename F> + inline + std::size_t + p_edges<G, F>::nedges() const + { + return this->g_->e_nmax(); + } + + template <typename G, typename F> + inline + bool + p_edges<G, F>::is_valid() const + { + return g_ != 0; + } + + template <typename G, typename F> + inline + void + p_edges<G, F>::invalidate() + { + g_ = 0; + } + + template <typename G, typename F> + inline + bool + p_edges<G, F>::has(const psite& p) const + { + mln_precondition(is_valid()); + return has(p.e()); + } + + template <typename G, typename F> + template <typename G2> + inline + bool + p_edges<G, F>::has(const util::edge<G2>& e) const + { + mln_precondition(is_valid()); + return e.g()->is_subgraph_of(*g_) && g_->has(e) && e.is_valid(); + } + + template <typename G, typename F> + inline + std::size_t + p_edges<G, F>::memory_size() const + { + // FIXME: Dummy; implement (see other site sets). + abort(); + return 0; + } + + template <typename G, typename F> + inline + const typename p_edges<G, F>::graph_t& + p_edges<G, F>::g() const + { + mln_precondition(is_valid()); + return *g_; + } + + template <typename G, typename F> + inline + F + p_edges<G, F>::function() const + { + return f_; + } + + template <typename G, typename F> + bool + operator==(const p_edges<G, F>& lhs, const p_edges<G, F>& rhs) + { + /* FIXME: We should not rely on pointer equality here, as graph + will soon become shells using (shared) tracked pointers to + actual data. So, delegate the equality test to the graphs + themselves. */ + return (*lhs.g_) == (*rhs.g_); + } + + template <typename G, typename F> + bool + operator<=(const p_edges<G, F>& lhs, const p_edges<G, F>& rhs) + { + return lhs == rhs; + } + +} // end of mln + +# endif // ! MLN_INCLUDE_ONLY + +#endif // MLN_CORE_SITE_SET_P_EDGES_HH diff --git a/milena/mln/util/internal/graph_edge_psite.hh b/milena/mln/util/internal/graph_edge_psite.hh new file mode 100644 index 0000000..5e00d18 --- /dev/null +++ b/milena/mln/util/internal/graph_edge_psite.hh @@ -0,0 +1,126 @@ +// 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_PSITE_HH +# define MLN_UTIL_INTERNAL_GRAPH_EDGE_PSITE_HH + +# include <mln/core/concept/pseudo_site.hh> +# include <mln/util/internal/graph_psite_base.hh> + +namespace mln +{ + + template <typename G, typename F> class p_edges; + +} // end of namespace mln + +/// \file mln/util/internal/edge_psite.hh +/// \brief Implementation of p_edges psite. + +namespace mln +{ + + namespace internal + { + + template <typename G, typename F> + class edge_psite : + public graph_psite_base<util::edge<G>, typename F::result, + p_edges<G, F>, + edge_psite<G, F> > + { + typedef edge_psite<G, F> self_; + typedef p_edges<G, F> target_t; + typedef graph_psite_base<util::edge<G>, typename F::result, target_t, self_> super_; + typedef util::edge<G> edge_t; + + public: + /// Associated Types + /// \{ + /// Site type, the return type of the mapping function \p F here. + typedef typename F::result site; + /// \} + + /// Constructors + /// \{ + edge_psite(); + edge_psite(const target_t& t); + /// \} + + /// Accessors + /// \{ + /// Return the underlying edge. + const edge_t& e() const; + /// \} + + protected: + /// The underlying edge (inherited). + using super_::v_; + }; + + } // end of namespace internal + +} // end of namespace mln + + +# ifndef MLN_INCLUDE_ONLY + +namespace mln +{ + + namespace internal + { + + template <typename G, typename F> + inline + edge_psite<G, F>::edge_psite() + { + } + + template <typename G, typename F> + inline + edge_psite<G, F>::edge_psite(const target_t& t) + { + this->change_target(t); + } + + template <typename G, typename F> + inline + const typename edge_psite<G, F>::edge_t& + edge_psite<G, F>::e() const + { + return v_; + } + + } // end of namespace internal + +} // end of namespace mln + +# endif // !MLN_INCLUDE_ONLY + +#endif // !MLN_UTIL_INTERNAL_GRAPH_EDGE_PSITE_HH + diff --git a/milena/tests/core/site_set/Makefile.am b/milena/tests/core/site_set/Makefile.am index d1b2cf6..1b23c79 100644 --- a/milena/tests/core/site_set/Makefile.am +++ b/milena/tests/core/site_set/Makefile.am @@ -5,6 +5,7 @@ include $(top_srcdir)/milena/tests/tests.mk check_PROGRAMS = \ p_array \ ## p_bgraph \ + p_edges \ p_image \ p_priority_queue \ p_queue \ @@ -22,5 +23,6 @@ p_queue_fast_SOURCES = p_queue_fast.cc p_set_SOURCES = p_set.cc pset_if_SOURCES = pset_if.cc p_vertices_SOURCES = p_vertices.cc +p_edges_SOURCES = p_edges.cc TESTS = $(check_PROGRAMS) diff --git a/milena/tests/core/site_set/p_edges.cc b/milena/tests/core/site_set/p_edges.cc new file mode 100644 index 0000000..9ab01a1 --- /dev/null +++ b/milena/tests/core/site_set/p_edges.cc @@ -0,0 +1,93 @@ +// 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. + +/*! \file tests/core/site_set/p_edges.cc + * + * \brief Tests on mln::p_edges. + */ + +#include <mln/util/graph.hh> +#include <mln/core/alias/point2d.hh> +#include <mln/core/site_set/p_edges.hh> + +// Function mapping an edge to a specific site. +template <typename G> +struct my_fun +{ + typedef mln::point2d result; + + const result& operator()(const mln::util::edge<G>& v) const + { + static mln::point2d res(0, 0); + res.row() = v.id(); + return res; + } +}; + +int main() +{ + using namespace mln; + + // Create a graph. + 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 (0, 2); + g.add_edge (3, 4); + g.add_edge (4, 5); + g.add_edge (5, 4); + g.add_edge (1, 0); + g.add_edge (5, 3); + g.add_edge (2, 1); + + typedef p_edges<util::graph, my_fun<util::graph> > p_edges; + p_edges pv(g, my_fun<util::graph>()); + + // Forward iterator + { + mln_fwd_piter_(p_edges) p(pv); + unsigned i = 0; + for_all(p) + mln_assertion(p.p_hook_().e().id() == i++); + mln_assertion(i == g.e_nmax()); + } + // Backward iterator + { + mln_bkd_piter_(p_edges) p(pv); + unsigned i = g.e_nmax() - 1; + for_all(p) + mln_assertion(p.p_hook_().e().id() == i--); + mln_assertion(i == UINT_MAX); + } + + return 0; +} -- 1.5.6.5