* 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 <lazzara(a)lrde.epita.fr>
+ 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 <lazzara(a)lrde.epita.fr>
+
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
