* mln/canvas/browsing/depth_first_search.hh: new canvas.
* mln/util/array.hh,
* mln/fun/internal/array_base.hh: add new resize() overload.
* mln/fun/x2x/rotation.hh: update doc.
* tests/fun/x2x/rotation.cc: fix wrong namespace.
* milena/tests/unit_test/Makefile.am,
* milena/tests/unit_test/mln_canvas_browsing_depth_first_search.cc:
add a new unit test.
* milena/headers.mk: update distributed headers.
---
milena/ChangeLog | 19 +++
milena/headers.mk | 2 +-
milena/mln/canvas/browsing/depth_first_search.hh | 134 ++++++++++++++++++++
milena/mln/fun/internal/array_base.hh | 9 ++
milena/mln/fun/x2x/rotation.hh | 14 +--
milena/mln/util/array.hh | 11 ++
milena/tests/fun/x2x/rotation.cc | 4 +-
milena/tests/unit_test/Makefile.am | 2 +
.../mln_canvas_browsing_depth_first_search.cc | 8 ++
9 files changed, 192 insertions(+), 11 deletions(-)
create mode 100644 milena/mln/canvas/browsing/depth_first_search.hh
create mode 100644 milena/tests/unit_test/mln_canvas_browsing_depth_first_search.cc
diff --git a/milena/ChangeLog b/milena/ChangeLog
index 2fd50e0..64c3fd7 100644
--- a/milena/ChangeLog
+++ b/milena/ChangeLog
@@ -1,3 +1,22 @@
+2008-12-10 Guillaume Lazzara <z(a)lrde.epita.fr>
+
+ Add depth first search canvas for graphes.
+
+ * mln/canvas/browsing/depth_first_search.hh: new canvas.
+
+ * mln/util/array.hh,
+ * mln/fun/internal/array_base.hh: add new resize() overload.
+
+ * mln/fun/x2x/rotation.hh: update doc.
+
+ * tests/fun/x2x/rotation.cc: fix wrong namespace.
+
+ * milena/tests/unit_test/Makefile.am,
+ * milena/tests/unit_test/mln_canvas_browsing_depth_first_search.cc:
+ add a new unit test.
+
+ * milena/headers.mk: update distributed headers.
+
2008-12-10 Thierry Geraud <thierry.geraud(a)lrde.epita.fr>
Fix 'implies' test and doc tutorial examples.
diff --git a/milena/headers.mk b/milena/headers.mk
index f88845e..25f239c 100644
--- a/milena/headers.mk
+++ b/milena/headers.mk
@@ -237,7 +237,6 @@ mln/convert/to_p_array.hh \
mln/convert/from_to.hxx \
mln/convert/to_rgb.hh \
mln/convert/essential.hh \
-mln/value/label.hh.bak \
mln/value/float01_f.hh \
mln/value/float01_16.hh \
mln/value/lut_vec.hh \
@@ -464,6 +463,7 @@ mln/canvas/browsing/all.hh \
mln/canvas/browsing/diagonal2d.hh \
mln/canvas/browsing/fwd.hh \
mln/canvas/browsing/dir_struct_elt_incr_update.hh \
+mln/canvas/browsing/depth_first_search.hh \
mln/canvas/browsing/directional.hh \
mln/canvas/browsing/essential.hh \
mln/canvas/chamfer.hh \
diff --git a/milena/mln/canvas/browsing/depth_first_search.hh b/milena/mln/canvas/browsing/depth_first_search.hh
new file mode 100644
index 0000000..716be86
--- /dev/null
+++ b/milena/mln/canvas/browsing/depth_first_search.hh
@@ -0,0 +1,134 @@
+// 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_CANVAS_BROWSING_DEPTH_FIRST_SEARCH_HH
+# define MLN_CANVAS_BROWSING_DEPTH_FIRST_SEARCH_HH
+
+/// \file mln/canvas/browsing/depth_first_search.hh
+///
+/// Depth-limited search algorithm for graph.
+/// Browse over all vertices for each component.
+
+/*!
+** The functor should provide the following methods:
+**
+** - template <typename G> void init(const Graph<G>& g)
+** Will be called at the beginning.
+**
+** - void next()
+** Will be called after all vertices from a component have been treated.
+**
+** - void update_treated(unsigned id)
+** will be called for the first vertex encountered for each component.
+**
+** - void update_queued(unsigned id)
+** Will be called for every vertex encountered in each component, except
+** the first one.
+**
+** - bool to_be_treated(unsigned id)
+** Return whether this vertex has already been marked or if it may be a
+** a component representative.
+**
+** - bool to_be_queued(unsigned id)
+** Return whether this vertex has already been marked or if it can be added
+** to the current component.
+**
+** - void final()
+** Will be called at the end;
+**
+*/
+
+# include <mln/core/concept/graph.hh>
+
+namespace mln
+{
+
+ namespace canvas
+ {
+
+ namespace browsing
+ {
+
+ struct depth_first_search_t : public Browsing< depth_first_search_t >
+ {
+ template <typename G, typename F>
+ void operator()(const Graph<G>&, F& f) const;
+ };
+
+ extern const depth_first_search_t depth_first_search;
+
+# ifndef MLN_INCLUDE_ONLY
+
+ const depth_first_search_t depth_first_search;
+
+ template <typename G, typename F>
+ inline
+ void
+ depth_first_search_t::operator()(const Graph<G>& g_, F& f) const
+ {
+ trace::entering("canvas::browsing::depth_first_search");
+
+ const G& g = exact(g_);
+
+ f.init(g);
+
+ mln_vertex_iter(util::graph) v(g);
+ for_all(v)
+ if (f.to_be_treated(v.id()))
+ {
+ std::queue<unsigned> queue;
+ queue.push(v.id());
+ f.update_treated(v.id());
+ while (!queue.empty())
+ {
+ util::vertex<util::graph> current_v = g.vertex(queue.front());
+ queue.pop();
+ for (unsigned nv = 0; nv < current_v.nmax_nbh_vertices(); ++nv)
+ if (f.to_be_queued(current_v.ith_nbh_vertex(nv)))
+ {
+ f.update_queued(current_v.ith_nbh_vertex(nv));
+ queue.push(current_v.ith_nbh_vertex(nv));
+ }
+ }
+ f.next();
+ }
+
+ f.final();
+
+ trace::exiting("canvas::browsing::depth_first_search");
+ }
+
+# endif // ! MLN_INCLUDE_ONLY
+
+ } // end of namespace mln::canvas::browsing
+
+ } // end of namespace mln::canvas
+
+} // end of namespace mln
+
+
+#endif // ! MLN_CANVAS_BROWSING_DEPTH_FIRST_SEARCH_HH
diff --git a/milena/mln/fun/internal/array_base.hh b/milena/mln/fun/internal/array_base.hh
index 32abb8a..62486fb 100644
--- a/milena/mln/fun/internal/array_base.hh
+++ b/milena/mln/fun/internal/array_base.hh
@@ -55,6 +55,7 @@ namespace mln
typedef T result;
void resize(unsigned n);
+ void resize(unsigned n, const T& val);
unsigned size() const;
const T& operator()(unsigned i) const;
@@ -150,6 +151,14 @@ namespace mln
template <typename T>
inline
+ void
+ array_base<T>::resize(unsigned n, const T& val)
+ {
+ v_.resize(n, val);
+ }
+
+ template <typename T>
+ inline
unsigned
array_base<T>::size() const
{
diff --git a/milena/mln/fun/x2x/rotation.hh b/milena/mln/fun/x2x/rotation.hh
index 9364cda..6ebe9b2 100644
--- a/milena/mln/fun/x2x/rotation.hh
+++ b/milena/mln/fun/x2x/rotation.hh
@@ -1,4 +1,5 @@
-// Copyright (C) 2007 EPITA Research and Development Laboratory
+// Copyright (C) 2007, 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
@@ -28,10 +29,9 @@
#ifndef MLN_FUN_X2X_ROTATION_HH
# define MLN_FUN_X2X_ROTATION_HH
-/*! \file mln/fun/x2x/rotation.hh
- *
- * \brief Define a rotation function.
- */
+/// \file mln/fun/x2x/rotation.hh
+///
+/// Define a rotation function.
# include <mln/core/concept/function.hh>
# include <mln/fun/internal/x2x_linear_impl.hh>
@@ -116,9 +116,7 @@ namespace mln
} // end of namespace internal
- /*! \brief Represent a rotation function.
- *
- */
+ /// Represent a rotation function.
template <unsigned n, typename C>
struct rotation
: fun::internal::x2x_linear_impl_< algebra::vec<n,C>, rotation<n,C> >
diff --git a/milena/mln/util/array.hh b/milena/mln/util/array.hh
index b5e2534..822a513 100644
--- a/milena/mln/util/array.hh
+++ b/milena/mln/util/array.hh
@@ -118,6 +118,9 @@ namespace mln
/// Resize this array to \p n elements.
void resize(unsigned n);
+ /// Resize this array to \p n elements with \p value as value.
+ void resize(unsigned n, const T& value);
+
/// Add the element \p elt at the end of this array.
array<T>& append(const T& elt);
@@ -329,6 +332,14 @@ namespace mln
template <typename T>
inline
+ void
+ array<T>::resize(unsigned n, const T& value)
+ {
+ v_.resize(n, value);
+ }
+
+ template <typename T>
+ inline
array<T>&
array<T>::append(const T& elt)
{
diff --git a/milena/tests/fun/x2x/rotation.cc b/milena/tests/fun/x2x/rotation.cc
index 85b9619..bce3137 100644
--- a/milena/tests/fun/x2x/rotation.cc
+++ b/milena/tests/fun/x2x/rotation.cc
@@ -31,7 +31,7 @@
///
#include <iostream>
-#include <mln/fun/x2x/rotation.hh>
+#include <mln/fun/x2v/rotation.hh>
#include <mln/core/image/image2d.hh>
#include <mln/value/int_u8.hh>
#include <mln/io/pgm/load.hh>
@@ -56,7 +56,7 @@ int main()
io::pgm::load(lena, MLN_IMG_DIR "/lena.pgm");
image2d<int_u8> out(lena.domain());
- interpolated<image2d<int_u8>, fun::x2x::bilinear> inter(lena);
+ interpolated<image2d<int_u8>, fun::x2v::bilinear> inter(lena);
fun::x2x::rotation<2,float> rot1(0.1, axis);
diff --git a/milena/tests/unit_test/Makefile.am b/milena/tests/unit_test/Makefile.am
index 893238e..953077f 100644
--- a/milena/tests/unit_test/Makefile.am
+++ b/milena/tests/unit_test/Makefile.am
@@ -459,6 +459,7 @@ mln_canvas_browsing_all \
mln_canvas_browsing_diagonal2d \
mln_canvas_browsing_fwd \
mln_canvas_browsing_dir_struct_elt_incr_update \
+mln_canvas_browsing_depth_first_search \
mln_canvas_browsing_directional \
mln_canvas_browsing_essential \
mln_canvas_chamfer \
@@ -1454,6 +1455,7 @@ mln_canvas_browsing_all_SOURCES = mln_canvas_browsing_all.cc
mln_canvas_browsing_diagonal2d_SOURCES = mln_canvas_browsing_diagonal2d.cc
mln_canvas_browsing_fwd_SOURCES = mln_canvas_browsing_fwd.cc
mln_canvas_browsing_dir_struct_elt_incr_update_SOURCES = mln_canvas_browsing_dir_struct_elt_incr_update.cc
+mln_canvas_browsing_depth_first_search_SOURCES = mln_canvas_browsing_depth_first_search.cc
mln_canvas_browsing_directional_SOURCES = mln_canvas_browsing_directional.cc
mln_canvas_browsing_essential_SOURCES = mln_canvas_browsing_essential.cc
mln_canvas_chamfer_SOURCES = mln_canvas_chamfer.cc
diff --git a/milena/tests/unit_test/mln_canvas_browsing_depth_first_search.cc b/milena/tests/unit_test/mln_canvas_browsing_depth_first_search.cc
new file mode 100644
index 0000000..5073125
--- /dev/null
+++ b/milena/tests/unit_test/mln_canvas_browsing_depth_first_search.cc
@@ -0,0 +1,8 @@
+// Unit test for mln/canvas/browsing/depth_first_search.hh.
+// Generated file, do not modify.
+#include <mln/canvas/browsing/depth_first_search.hh>
+
+int main()
+{
+ // Nothing.
+}
--
1.5.6.5