[Olena-patches] 3024: 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. --- 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 &lt;z(a)lrde.epita.fr&gt; + + 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 &lt;thierry.geraud(a)lrde.epita.fr&gt; 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