[Olena-patches] [PATCH 02/31] Add adjacency matrix.

* mln/make/influence_zone_adjacency_graph.hh, * mln/make/region_adjacency_graph.hh: make use of this new structure. * mln/util/adjacency_matrix.hh: new structure. * tests/util/Makefile.am, * tests/util/adjacency_matrix.cc: associated test. --- milena/ChangeLog | 12 + milena/mln/make/influence_zone_adjacency_graph.hh | 17 +- milena/mln/make/region_adjacency_graph.hh | 15 +- milena/mln/util/adjacency_matrix.hh | 335 +++++++++++++++++++++ milena/tests/util/Makefile.am | 3 + milena/tests/util/adjacency_matrix.cc | 76 +++++ 6 files changed, 440 insertions(+), 18 deletions(-) create mode 100644 milena/mln/util/adjacency_matrix.hh create mode 100644 milena/tests/util/adjacency_matrix.cc diff --git a/milena/ChangeLog b/milena/ChangeLog index d68a7e9..ff6c707 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,5 +1,17 @@ 2009-05-06 Guillaume Lazzara &lt;lazzara(a)lrde.epita.fr&gt; + Add adjacency matrix. + + * mln/make/influence_zone_adjacency_graph.hh, + * mln/make/region_adjacency_graph.hh: make use of this new structure. + + * mln/util/adjacency_matrix.hh: new structure. + + * tests/util/Makefile.am, + * tests/util/adjacency_matrix.cc: associated test. + +2009-05-06 Guillaume Lazzara &lt;lazzara(a)lrde.epita.fr&gt; + Small fixes. * doc/tutorial/tutorial.tex: fix compilation. diff --git a/milena/mln/make/influence_zone_adjacency_graph.hh b/milena/mln/make/influence_zone_adjacency_graph.hh index 7113962..6cbaa4c 100644 --- a/milena/mln/make/influence_zone_adjacency_graph.hh +++ b/milena/mln/make/influence_zone_adjacency_graph.hh @@ -44,6 +44,8 @@ # include <mln/core/alias/box2d.hh> # include <mln/extension/adjust_fill.hh> # include <mln/util/graph.hh> +# include <mln/util/adjacency_matrix.hh> + namespace mln { @@ -104,8 +106,7 @@ namespace mln const I& iz = exact(iz_); const N& nbh = exact(nbh_); - mln::image2d<bool> adj(mln::box2d(nlabels.next(), nlabels.next())); - data::fill(adj, false); + util::adjacency_matrix<> adj(nlabels.next()); extension::adjust_fill(iz, nbh, 0u); typedef mln_value(I) L; @@ -120,13 +121,7 @@ namespace mln { L l2 = iz(n); if (iz(n) != iz((p))) - { - // l2 is adjacent to l1 - if (l2 < l1) - adj(point2d(l1,l2)) = true; - else - adj(point2d(l2,l1)) = true; - } + adj.add(l1, l2); } } } @@ -134,9 +129,9 @@ namespace mln // Construct graph. util::graph g; g.add_vertices(nlabels.next()); - for (unsigned i = 0; i < geom::nrows(adj); ++i) + for (unsigned i = 0; i < nlabels.next(); ++i) for (unsigned j = 0; j < i; ++j) - if (adj(point2d(i,j))) + if (adj.are_adjacent(i, j)) g.add_edge(i, j); trace::exiting("make::impl::generic::influence_zone_adjacency_graph"); diff --git a/milena/mln/make/region_adjacency_graph.hh b/milena/mln/make/region_adjacency_graph.hh index 695174d..b930367 100644 --- a/milena/mln/make/region_adjacency_graph.hh +++ b/milena/mln/make/region_adjacency_graph.hh @@ -33,6 +33,8 @@ /// Create a region_adjacency_graph from a watershed image. /// /// \sa morpho::meyer_wst. +/// +/// \todo add dispatch. # include <mln/core/concept/image.hh> # include <mln/core/concept/neighborhood.hh> @@ -40,6 +42,8 @@ # include <mln/core/alias/box2d.hh> # include <mln/extension/adjust_fill.hh> # include <mln/util/graph.hh> +# include <mln/util/adjacency_matrix.hh> + namespace mln { @@ -100,8 +104,7 @@ namespace mln const I& wshd = exact(wshd_); const N& nbh = exact(nbh_); - mln::image2d<bool> adj(mln::box2d(nbasins.next(), nbasins.next())); - data::fill(adj, false); + util::adjacency_matrix<> adj(nbasins.next()); extension::adjust_fill(wshd, nbh, 0u); typedef mln_value(I) L; @@ -129,19 +132,17 @@ namespace mln } if (l2 == 0u || l1 == 0u) continue; - if (l2 < l1) - std::swap(l1, l2); // adjacency l1 l2 - adj(point2d(l2,l1)) = true; + adj.add(l2, l1); } // Construct graph. util::graph g; g.add_vertices(nbasins.next()); - for (unsigned i = 1; i < geom::nrows(adj); ++i) + for (unsigned i = 1; i < nbasins.next(); ++i) for (unsigned j = 1; j < i; ++j) - if (adj(point2d(i,j))) + if (adj.are_adjacent(i, j)) g.add_edge(i, j); diff --git a/milena/mln/util/adjacency_matrix.hh b/milena/mln/util/adjacency_matrix.hh new file mode 100644 index 0000000..dfda26f --- /dev/null +++ b/milena/mln/util/adjacency_matrix.hh @@ -0,0 +1,335 @@ +// Copyright (C) 2009 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_ADJACENCY_MATRIX_HH +# define MLN_UTIL_ADJACENCY_MATRIX_HH + +/// \file mln/util/adjacency_matrix.hh +/// +/// A class of adjacency matrix. +/// +/// FIXME: the underlying data structure is chosen according +/// to the value type quantification however we may like to make it +/// depend on the number of elements. + +# include <mln/core/image/image2d.hh> +# include <mln/util/set.hh> +# include <mln/util/ord_pair.hh> +# include <mln/trait/value_.hh> +# include <mln/metal/converts_to.hh> +# include <mln/debug/println.hh> + +namespace mln +{ + + namespace util + { + + namespace internal + { + + // Implementation for low quantification. + + template <typename V, typename Q> + struct adjacency_matrix_impl_selector + { + /// Data structure used to store adjacency information. + typedef image2d<bool> adj_t; + + /// Constructor. + adjacency_matrix_impl_selector(const V& nelements); + + /// Make \p e1 and \p e2 adjacent. + void add(const V& e1, const V& e2); + + /// Remove adjacency between \p e1 and \p e2. + void remove(const V& e1, const V& e2); + + /// Clear all adjacencies. + void clear(); + + /// Check whether \p e1 and \p e2 are adjacent. + bool are_adjacent(const V& e1, const V& e2) const; + + /// Print data to std::out. + std::ostream& print_data_(std::ostream& ostr) const; + + protected: + adj_t adj_; + }; + + + // Implementation for high quantification. + + template <typename V> + struct adjacency_matrix_impl_selector<V, metal::bool_<false> > + { + /// Data structure used to store adjacency information. + typedef util::set< util::ord_pair<V> > adj_t; + + /// Constructor. + adjacency_matrix_impl_selector(const V& nelements); + + /// Make \p e1 and \p e2 adjacent. + void add(const V& e1, const V& e2); + + /// Remove adjacency between \p e1 and \p e2. + void remove(const V& e1, const V& e2); + + /// Clear all adjacencies. + void clear(); + + /// Check whether \p e1 and \p e2 are adjacent. + bool are_adjacent(const V& e1, const V& e2) const; + + /// Print data to std::out. + std::ostream& print_data_(std::ostream& ostr) const; + + protected: + adj_t adj_; + +# ifndef NDEBUG + unsigned nelements_; +# endif // ! NDEBUG + }; + + + } // end of namespace mln::util::internal + + + /// A class of adjacency matrix. + /// + /// Support low and high quantification value types. + /// In case of low quantification value type, it uses + /// an image2d to store adjacency information. + /// In case of high quantification value type, it uses + /// a util::set to store the adjacency information. + /// + /// \ingroup modutil + // + template <typename V = def::coord> + class adjacency_matrix + : private mlc_converts_to(V,unsigned)::check_t, + public internal::adjacency_matrix_impl_selector<V, typename mlc_equal(mln_trait_value_quant(V),trait::value::quant::low)::eval> + { + typedef internal::adjacency_matrix_impl_selector<V, typename mlc_equal(mln_trait_value_quant(V),trait::value::quant::low)::eval> + impl_t; + + typedef typename impl_t::adj_t adj_t; + + public: + /// Constructors. + /// \@{ + /// + /// Default + adjacency_matrix(); + /// Construct an adjacency matrix with \p nelements elements + /// maximum. + adjacency_matrix(const V& nelements); + /// + /// \@} + + /// Hook member used to retrieve the underlying data structure. + const adj_t& hook_data_() const; + }; + + + // << + + template <typename V> + std::ostream& + operator<<(std::ostream& ostr, const adjacency_matrix<V>& adj); + + + +# ifndef MLN_INCLUDE_ONLY + + + namespace internal + { + + // Low quantification. + + template <typename V, typename Q> + adjacency_matrix_impl_selector<V, Q>::adjacency_matrix_impl_selector(const V& nelements) + : adj_(nelements, nelements) + { + clear(); + } + + template <typename V, typename Q> + void + adjacency_matrix_impl_selector<V, Q>::add(const V& e1, const V& e2) + { + mln_precondition(adj_.is_valid()); + mln_precondition(e1 < adj_.nrows()); + mln_precondition(e2 < adj_.nrows()); + + if (e1 > e2) + opt::at(adj_, e2, e1) = true; + else + opt::at(adj_, e1, e2) = true; + } + + template <typename V, typename Q> + void + adjacency_matrix_impl_selector<V, Q>::remove(const V& e1, const V& e2) + { + mln_precondition(adj_.is_valid()); + mln_precondition(e1 < adj_.nrows()); + mln_precondition(e2 < adj_.nrows()); + + if (e1 > e2) + opt::at(adj_, e2, e1) = false; + else + opt::at(adj_, e1, e2) = false; + } + + template <typename V, typename Q> + void + adjacency_matrix_impl_selector<V, Q>::clear() + { + mln_precondition(adj_.is_valid()); + data::fill(adj_, false); + } + + template <typename V, typename Q> + bool + adjacency_matrix_impl_selector<V, Q>::are_adjacent(const V& e1, + const V& e2) const + { + mln_precondition(adj_.is_valid()); + mln_precondition(e1 < adj_.nrows()); + mln_precondition(e2 < adj_.nrows()); + + if (e1 > e2) + return opt::at(adj_, e2, e1); + return opt::at(adj_, e1, e2); + } + + template <typename V, typename Q> + std::ostream& + adjacency_matrix_impl_selector<V, Q>::print_data_(std::ostream& ostr) const + { + mln_precondition(adj_.is_valid()); + debug::println(adj_); + return ostr; + } + + + + + // High quantification. + + template <typename V> + adjacency_matrix_impl_selector<V, metal::bool_<false> > + ::adjacency_matrix_impl_selector(const V& nelements) + { + (void) nelements; +# ifndef DNDEBUG + nelements_ = nelements; +# endif // ! DNDEBUG + } + + template <typename V> + void + adjacency_matrix_impl_selector<V, metal::bool_<false> > + ::add(const V& e1, const V& e2) + { + mln_precondition(e1 < nelements_); + mln_precondition(e2 < nelements_); + adj_.insert(make::ord_pair(e1, e2)); + } + + template <typename V> + void + adjacency_matrix_impl_selector<V, metal::bool_<false> > + ::remove(const V& e1, const V& e2) + { + mln_precondition(e1 < nelements_); + mln_precondition(e2 < nelements_); + mln_precondition(adj_.has(make::ord_pair(e1, e2))); + adj_.remove(make::ord_pair(e1, e2)); + } + + template <typename V> + void + adjacency_matrix_impl_selector<V, metal::bool_<false> >::clear() + { + adj_.clear(); + } + + template <typename V> + bool + adjacency_matrix_impl_selector<V, metal::bool_<false> > + ::are_adjacent(const V& e1, const V& e2) const + { + mln_precondition(e1 < nelements_); + mln_precondition(e2 < nelements_); + return adj_.has(make::ord_pair(e1, e2)); + } + + template <typename V> + std::ostream& + adjacency_matrix_impl_selector<V, metal::bool_<false> >::print_data_(std::ostream& ostr) const + { + return ostr << adj_; + } + + } // end of namespace mln::internal + + + template <typename V> + adjacency_matrix<V>::adjacency_matrix() + : impl_t() + { + } + + + template <typename V> + adjacency_matrix<V>::adjacency_matrix(const V& nelements) + : impl_t(nelements) + { + } + + + template <typename V> + std::ostream& + operator<<(std::ostream& ostr, const adjacency_matrix<V>& adj) + { + return adj.print_data_(ostr); + } + + +# endif // ! MLN_UTIL_ADJACENCY_MATRIX_HH + + } // end of namespace mln::util + +} // end of namespace mln + + +#endif // ! MLN_UTIL_ADJACENCY_MATRIX_HH diff --git a/milena/tests/util/Makefile.am b/milena/tests/util/Makefile.am index c1d6c4d..07b6018 100644 --- a/milena/tests/util/Makefile.am +++ b/milena/tests/util/Makefile.am @@ -4,6 +4,7 @@ include $(top_srcdir)/milena/tests/tests.mk check_PROGRAMS = \ + adjacency_matrix \ branch_iter \ branch_iter_ind \ eat \ @@ -21,6 +22,8 @@ check_PROGRAMS = \ tree_to_fast \ tree_to_image + +adjacency_matrix_SOURCES = adjacency_matrix.cc branch_iter_SOURCES = branch_iter.cc branch_iter_ind_SOURCES = branch_iter_ind.cc eat_SOURCES = eat.cc diff --git a/milena/tests/util/adjacency_matrix.cc b/milena/tests/util/adjacency_matrix.cc new file mode 100644 index 0000000..e67f659 --- /dev/null +++ b/milena/tests/util/adjacency_matrix.cc @@ -0,0 +1,76 @@ +// Copyright (C) 2009 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/adjacency_matrix.cc +/// +/// test of mln::util::adjacency_matrix + +#include <mln/util/adjacency_matrix.hh> +#include <mln/value/int_u8.hh> +#include <mln/value/int_u16.hh> + +int main() +{ + using namespace mln; + + // The underlying data structure is a image2d. + { + util::adjacency_matrix<value::int_u8> adj(5); + adj.add(3, 4); + adj.add(2, 3); + adj.add(1, 2); + + mln_assertion(adj.are_adjacent(2,3)); + mln_assertion(adj.are_adjacent(4,3)); + mln_assertion(adj.are_adjacent(2,1)); + mln_assertion(adj.are_adjacent(1,2)); + mln_assertion(!adj.are_adjacent(1,4)); + + adj.remove(2,3); + mln_assertion(!adj.are_adjacent(2,3)); + mln_assertion(!adj.are_adjacent(2,2)); + } + + // The underlying data structure is a util::set + { + util::adjacency_matrix<value::int_u16> adj(5); + adj.add(3, 4); + adj.add(2, 3); + adj.add(1, 2); + + mln_assertion(adj.are_adjacent(2,3)); + mln_assertion(adj.are_adjacent(4,3)); + mln_assertion(adj.are_adjacent(2,1)); + mln_assertion(adj.are_adjacent(1,2)); + mln_assertion(!adj.are_adjacent(1,4)); + + adj.remove(2,3); + mln_assertion(!adj.are_adjacent(2,3)); + mln_assertion(!adj.are_adjacent(2,2)); + } + +} -- 1.6.1.2