* mln/accu/center.hh: New accu. * mln/accu/all.hh, * mln/accu/essential.hh: add center.hh. * mln/make/all.hh, * mln/make/essential.hh, * mln/debug/essential.hh, * mln/debug/all.hh: update includes. * mln/debug/graph.hh: Rename as... * mln/debug/draw_graph.hh: ...this. * mln/make/graph.hh: Add make::graph(). * mln/util/array.hh: cleanup. * mln/util/edge.hh: cleanup comments. * mln/util/graph.hh: add new constructors. --- milena/ChangeLog | 25 ++++ milena/mln/accu/all.hh | 1 + milena/mln/accu/center.hh | 154 +++++++++++++++++++++++++ milena/mln/accu/essential.hh | 1 + milena/mln/debug/all.hh | 10 +- milena/mln/debug/{graph.hh => draw_graph.hh} | 80 +++++--------- milena/mln/debug/essential.hh | 9 +- milena/mln/make/all.hh | 1 + milena/mln/make/essential.hh | 7 +- milena/mln/make/graph.hh | 159 ++++++++++++++++++++++++++ milena/mln/util/array.hh | 35 +++---- milena/mln/util/edge.hh | 2 +- milena/mln/util/graph.hh | 37 ++++++ 13 files changed, 434 insertions(+), 87 deletions(-) create mode 100644 milena/mln/accu/center.hh rename milena/mln/debug/{graph.hh => draw_graph.hh} (53%) create mode 100644 milena/mln/make/graph.hh diff --git a/milena/ChangeLog b/milena/ChangeLog index f6f62e5..813df7d 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,3 +1,28 @@ +2008-11-18 Guillaume Lazzara <z@lrde.epita.fr> + + Update graph related classes. + + * mln/accu/center.hh: New accu. + + * mln/accu/all.hh, + * mln/accu/essential.hh: add center.hh. + + * mln/make/all.hh, + * mln/make/essential.hh, + * mln/debug/essential.hh, + * mln/debug/all.hh: update includes. + + * mln/debug/graph.hh: Rename as... + * mln/debug/draw_graph.hh: ...this. + + * mln/make/graph.hh: Add make::graph(). + + * mln/util/array.hh: cleanup. + + * mln/util/edge.hh: cleanup comments. + + * mln/util/graph.hh: add new constructors. + 2008-11-19 Thierry Geraud <thierry.geraud@lrde.epita.fr> Update canvas labelingand labeling level. diff --git a/milena/mln/accu/all.hh b/milena/mln/accu/all.hh index cda8581..1d8b9bc 100644 --- a/milena/mln/accu/all.hh +++ b/milena/mln/accu/all.hh @@ -58,6 +58,7 @@ namespace mln # include <mln/accu/bbox.hh> # include <mln/accu/count.hh> +# include <mln/accu/center.hh> //# include <mln/accu/count_adjacent_vertices.hh> # include <mln/accu/height.hh> # include <mln/accu/histo.hh> diff --git a/milena/mln/accu/center.hh b/milena/mln/accu/center.hh new file mode 100644 index 0000000..2aacfce --- /dev/null +++ b/milena/mln/accu/center.hh @@ -0,0 +1,154 @@ +// 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_ACCU_CENTER_HH +# define MLN_ACCU_CENTER_HH + +/// \file mln/accu/center.hh +/// +/// Define an accumulator that computes the center of a site set. + +# include <mln/accu/internal/base.hh> +# include <mln/accu/bbox.hh> + +namespace mln +{ + + namespace accu + { + + + /// Generic center accumulator class. + template <typename P> + struct center : public mln::accu::internal::base< P , center<P> > + { + typedef P argument; + typedef P result; + + center(); + + /// Manipulators. + /// \{ + void init(); + void take(const argument& t); + void take(const center<P>& other); + /// \} + + /// Get the value of the accumulator. + P to_result() const; + operator P () const; + + /// Check whether this accu is able to return a result. + bool is_valid() const; + + protected: + accu::bbox<P> bbox_; + }; + + namespace meta + { + + /// Meta accumulator for center. + struct center : public Meta_Accumulator< center > + { + + template <typename P> + struct with + { + typedef accu::center<P> ret; + }; + + }; + + } // end of namespace mln::accu::meta + + + +# ifndef MLN_INCLUDE_ONLY + + template <typename P> + inline + center<P>::center() + { + init(); + } + + template <typename P> + inline + void + center<P>::init() + { + bbox_.init(); + } + + template <typename P> + inline + void center<P>::take(const argument& t) + { + bbox_.take(t); + } + + template <typename P> + inline + void + center<P>::take(const center<P>& other) + { + bbox_.take(other.bbox_); + } + + template <typename P> + inline + P + center<P>::to_result() const + { + return bbox_.to_result().center(); + } + + template <typename P> + inline + center<P>::operator P() const + { + return P(bbox_.to_result().center()); + } + + template <typename P> + inline + bool + center<P>::is_valid() const + { + return bbox_.is_valid(); + } + +# endif // ! MLN_INCLUDE_ONLY + + + } // end of namespace mln::accu + +} // end of namespace mln + + +#endif // ! MLN_ACCU_CENTER_HH diff --git a/milena/mln/accu/essential.hh b/milena/mln/accu/essential.hh index 18498f2..e8c57cc 100644 --- a/milena/mln/accu/essential.hh +++ b/milena/mln/accu/essential.hh @@ -33,6 +33,7 @@ /// File that includes the most useful accumulator types. # include <mln/accu/bbox.hh> +# include <mln/accu/center.hh> # include <mln/accu/count.hh> # include <mln/accu/histo.hh> # include <mln/accu/max.hh> diff --git a/milena/mln/debug/all.hh b/milena/mln/debug/all.hh index a17fb37..a0a27c6 100644 --- a/milena/mln/debug/all.hh +++ b/milena/mln/debug/all.hh @@ -1,4 +1,5 @@ // 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_DEBUG_ALL_HH # define MLN_DEBUG_ALL_HH -/*! \file mln/debug/all.hh - * - * \brief File that includes all debug-related routines. - */ +/// \file mln/debug/all.hh +/// +/// File that includes all debug-related routines. namespace mln @@ -48,7 +48,7 @@ namespace mln # include <mln/debug/colorize.hh> # include <mln/debug/format.hh> -//# include <mln/debug/graph.hh> +# include <mln/debug/draw_graph.hh> # include <mln/debug/iota.hh> # include <mln/debug/println.hh> # include <mln/debug/println_with_border.hh> diff --git a/milena/mln/debug/graph.hh b/milena/mln/debug/draw_graph.hh similarity index 53% rename from milena/mln/debug/graph.hh rename to milena/mln/debug/draw_graph.hh index e92b802..159b974 100644 --- a/milena/mln/debug/graph.hh +++ b/milena/mln/debug/draw_graph.hh @@ -30,7 +30,10 @@ # define MLN_DEBUG_DRAW_GRAPH_HH /// \file mln/debug/graph.hh +/// /// \brief Draw an (classical) image from a mln::graph_image. +/// +/// \todo write a version for graph images. # include <mln/pw/image.hh> # include <mln/level/fill.hh> @@ -43,83 +46,56 @@ namespace mln namespace debug { - /*! \brief Draw an image \p ima from a mln::p_graph \p pg, with - * value \p vertex_v for vertices, value \p edge_v for edges and 0 for - * the background. - * - * \param[in,out] ima The image to be drawn. - * \param[in] pv The p_vertices which contains vertices positions. - * \param[in] vertex_v The value to assign to pixels which contains - * vertices. - * \param[in] edge_v The value to assign to pixels which contains - * edges. - */ + /// Draw an image \p ima from a mln::p_graph \p pg, with + /// value \p vertex_v for vertices, value \p edge_v for edges and 0 for + /// the background. + /// + /// \param[in,out] ima The image to be drawn. + /// \param[in] pv The p_vertices which contains vertices positions. + /// \param[in] vertex_v The value to assign to pixels which contains + /// vertices. + /// \param[in] edge_v The value to assign to pixels which contains + /// edges. template <typename I, typename G, typename F> void draw_graph(Image<I>& ima, const p_vertices<G, F>& pv, mln_value(I) vertex_v, mln_value(I) edge_v); - /*! \brief Draw an image \p ima from a mln::graph_image \p gi. - * - * The background is filled with value 0. - * - * \param[in,out] ima The image to be drawn. - * \param[in] gi The graph_image which contains the vertices, - * edges positions and the values of it. - * \param[in] edge_v The value to assign to pixels which contains - * edges, defaulting to 1. - */ - // FIXME: The type of the last argument cannot always been - // constructed from `int'! We should remove this last argument. -// template <typename I, typename P, typename V> -// void -// draw_graph(Image<I>& ima, const graph_image<P, V>& gi, -// mln_value(I) edge_v = 1); + # ifndef MLN_INCLUDE_ONLY + + // FIXME: Add assertions on the size of the image: it must be large // enough to hold the representation of the graph/graph_image. template <typename I, typename G, typename F> inline void - draw_graph(Image<I>& ima, const p_vertices<G, F>& pv, - mln_value(I) vertex_v, mln_value(I) edge_v) + draw_graph(Image<I>& ima, + const p_vertices<G, F>& pv, + mln_value(I) vertex_v, + mln_value(I) edge_v) { - // Debug the background. - level::fill(ima, 0); + // Fill the background. + level::fill(ima, literal::black); - // Debug the lines (edges). + // Draw edges. const G& g = pv.graph(); typedef p_vertices<G, F> pv_t; mln_edge_iter(G) ei(g); for_all(ei) draw::line(exact(ima), pv(ei.v1()), pv(ei.v2()), edge_v); - // Debug the points (vertices). + // Draw vertices. mln_piter(pv_t) p(pv); for_all(p) - exact(ima)(p) = vertex_v; + if (exact(ima).has(p)) + exact(ima)(p) = vertex_v; } -/* - template <typename I, typename P, typename V> - inline - void - draw_graph(Image<I>& ima, const graph_image<P, V>& gi, - mln_value(I) edge_v) - { - // Debug the background. - level::fill(ima, 0); - // Debug the lines (edges). - for (unsigned l = 0; l < gi.domain().nedges(); ++l) - line (exact(ima), gi.vertex1(l), gi.vertex2(l), edge_v); - // Debug the points (vertices). - for (unsigned p = 0; p < gi.domain().nvertices(); ++p) - exact(ima)(gi.domain().point_from_id(p)) = gi.vertex_values()[p]; - } -*/ + # endif // ! MLN_INCLUDE_ONLY @@ -127,4 +103,4 @@ namespace mln } // end of namespace mln -#endif // MLN_DEBUG_DRAW_GRAPH_HH +#endif // ! MLN_DEBUG_DRAW_GRAPH_HH diff --git a/milena/mln/debug/essential.hh b/milena/mln/debug/essential.hh index 122a6c0..a28563b 100644 --- a/milena/mln/debug/essential.hh +++ b/milena/mln/debug/essential.hh @@ -1,4 +1,4 @@ -// Copyright (C) 2008 EPITA Research and Development Laboratory +// 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 @@ -28,10 +28,9 @@ #ifndef MLN_DEBUG_ESSENTIAL_HH # define MLN_DEBUG_ESSENTIAL_HH -/*! \file mln/debug/essential.hh - * - * \brief File that includes essential debug-related routines. - */ +/// \file mln/debug/essential.hh +/// +/// File that includes essential debug-related routines. # include <mln/debug/all.hh> diff --git a/milena/mln/make/all.hh b/milena/mln/make/all.hh index 910d943..5dc232c 100644 --- a/milena/mln/make/all.hh +++ b/milena/mln/make/all.hh @@ -48,6 +48,7 @@ namespace mln # include <mln/make/box3d.hh> # include <mln/make/dpoint2d_h.hh> # include <mln/make/dual_neighb.hh> +# include <mln/make/graph.hh> # include <mln/make/image.hh> # include <mln/make/image2d.hh> # include <mln/make/mat.hh> diff --git a/milena/mln/make/essential.hh b/milena/mln/make/essential.hh index 856e75a..33aa0e7 100644 --- a/milena/mln/make/essential.hh +++ b/milena/mln/make/essential.hh @@ -29,10 +29,9 @@ #ifndef MLN_MAKE_ESSENTIAL_HH # define MLN_MAKE_ESSENTIAL_HH -/*! \file mln/make/essential.hh - * - * \brief File that includes essential make routines. - */ +/// \file mln/make/essential.hh +/// +/// File that includes essential make routines. # include <mln/make/dual_neighb.hh> # include <mln/make/image.hh> diff --git a/milena/mln/make/graph.hh b/milena/mln/make/graph.hh new file mode 100644 index 0000000..c3ae618 --- /dev/null +++ b/milena/mln/make/graph.hh @@ -0,0 +1,159 @@ +// 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_MAKE_GRAPH_HH +# define MLN_MAKE_GRAPH_HH + +/// \file mln/make/graph.hh +/// +/// Create a graph from an influence zone image. +/// +/// \sa transform::influence_zone_geodesic. + +# include <mln/util/graph.hh> + +namespace mln +{ + + namespace make + { + + /// Create a graph from an influence zone image. + /// + /// \param[in] iz influence zone image. + /// \param[in] nlabels number of influence zone in \p iz. + /// + /// \return util::graph Graph based on the adjacency of the influence zones. + template <typename I> + util::graph graph(const Image<I>& iz, mln_value(I) nlabels); + + + +# ifndef MLN_INCLUDE_ONLY + + + namespace internal + { + + template <typename I> + void + graph_tests(const Image<I>& iz, mln_value(I)) + { + mln_precondition(exact(iz).has_data()); + + (void) iz; + } + + } // end of namespace mln::make::internal + + + + namespace impl + { + + namespace generic + { + + template <typename I> + util::graph + graph(const Image<I>& iz_, mln_value(I) nlabels) + { + trace::entering("make::impl::generic::graph"); + + internal::graph_tests(iz_, nlabels); + const I& iz = exact(iz_); + + util::graph g; + g.add_vertices(nlabels + 1); + + mln_piter(I) p(iz.domain()); + for_all(p) + { + // Checking 'forward' neighboors and create an edge if necessary. + for (unsigned dim = 0; dim < mln_site_(I)::dim; ++dim) + { + mln_site(I) n = p; + ++n[dim]; + + // FIXME: check that calling iz.domain().has() is correct + // and that we don't prefer iz.has(). + if (iz.domain().has(n) && iz(p) != iz(n)) + g.add_edge(iz(p), iz(n)); + } + } + + trace::exiting("make::impl::generic::graph"); + return g; + } + + } // end of namespace mln::make::impl::generic + + } // end of namespace mln::make::impl + + + + namespace internal + { + + template <typename I> + util::graph + graph_dispatch(const Image<I>& iz, mln_value(I) nlabels) + { + return make::impl::generic::graph(iz, nlabels); + } + + } // end of namespace mln::make::internal + + + + // Facade + + template <typename I> + inline + util::graph + graph(const Image<I>& iz, mln_value(I) nlabels) + { + trace::entering("make::graph"); + + internal::graph_tests(iz, nlabels); + + util::graph g = internal::graph_dispatch(iz, nlabels); + + trace::exiting("make::graph"); + return g; + } + + +# endif // ! MLN_INCLUDE_ONLY + + + } // end of namespace mln::make + +} // end of namespace mln + + +#endif // ! MLN_MAKE_GRAPH_HH diff --git a/milena/mln/util/array.hh b/milena/mln/util/array.hh index 66b41a8..5f49839 100644 --- a/milena/mln/util/array.hh +++ b/milena/mln/util/array.hh @@ -1,4 +1,4 @@ -// Copyright (C) 2008 EPITA Research and Development Laboratory +// 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 @@ -28,13 +28,12 @@ #ifndef MLN_UTIL_ARRAY_HH # define MLN_UTIL_ARRAY_HH -/*! \file mln/util/array.hh - * - * \brief Definition of mln::util::array. - * - * \todo Zed: Add a lazy removal method (based on an extra attribute - * std::vector<bool> has_). Then add a purge/compress method. - */ +/// \file mln/util/array.hh +/// +/// Definition of mln::util::array. +/// +/// \todo Zed: Add a lazy removal method (based on an extra attribute +/// std::vector<bool> has_). Then add a purge/compress method. # include <vector> # include <iostream> @@ -55,15 +54,12 @@ namespace mln template <typename T> class array_bkd_iter; - /*! \brief A dynamic array class. - * - * - * - * Elements are stored by copy. Implementation is lazy. - * - * The parameter \c T is the element type, which shall not be - * const-qualified. - */ + /// A dynamic array class. + /// + /// Elements are stored by copy. Implementation is lazy. + /// + /// The parameter \c T is the element type, which shall not be + /// const-qualified. template <typename T> class array : public Object< mln::util::array<T> > { @@ -141,7 +137,7 @@ namespace mln /// Operator<<. template <typename T> std::ostream& operator<<(std::ostream& ostr, - const mln::util::array<T>& a); + const mln::util::array<T>& a); @@ -240,7 +236,6 @@ namespace mln # ifndef MLN_INCLUDE_ONLY - // util::array<T> @@ -546,7 +541,7 @@ namespace mln template <typename T> std::ostream& operator<<(std::ostream& ostr, - const mln::util::array<T>& a) + const mln::util::array<T>& a) { ostr << '['; const unsigned n = a.nelements(); diff --git a/milena/mln/util/edge.hh b/milena/mln/util/edge.hh index a6ce803..ba34a12 100644 --- a/milena/mln/util/edge.hh +++ b/milena/mln/util/edge.hh @@ -299,7 +299,7 @@ namespace mln std::ostream& operator<<(std::ostream& ostr, const edge<G>& p) { - return ostr << p.id(); + return ostr << "(" << p.v1() << "," << p.v2() << ")"; } template <typename G> diff --git a/milena/mln/util/graph.hh b/milena/mln/util/graph.hh index 1b22c43..7c003a2 100644 --- a/milena/mln/util/graph.hh +++ b/milena/mln/util/graph.hh @@ -62,6 +62,9 @@ namespace mln typedef std::set<util::ord_pair<unsigned> > edges_set_t; data(); + /// Constructor. + /// Allocate enough space in order to support \p nvertices vertices. + data(unsigned nvertices); ~data(); /// The vertices. @@ -134,19 +137,29 @@ namespace mln /// \} /// \} + /// Constructor. graph(); + /// Construct a graph with \p nvertices vertices. + graph(unsigned nvertices); /// Vertex oriented. /// \{ + /// Shortcuts factoring the insertion of vertices and edges. /// \{ + /// Add a vertex. /// /// \return The id of the new vertex. unsigned add_vertex(); + /// Add \p n vertices to the graph. + /// + /// \return A range of vertex ids. + std::pair<unsigned, unsigned> add_vertices(unsigned n); + /// Return the vertex whose id is \a v. /// \{ vertex_t vertex(unsigned id_v) const; @@ -239,6 +252,12 @@ namespace mln } inline + data<util::graph>::data(unsigned nvertices) + { + vertices_.resize(nvertices); + } + + inline data<util::graph>::~data() { } @@ -254,6 +273,12 @@ namespace mln this->data_ = new mln::internal::data<util::graph>(); } + inline + graph::graph(unsigned nvertices) + { + this->data_ = new mln::internal::data<util::graph>(nvertices); + } + /*---------------. | Vertex related | `---------------*/ @@ -270,6 +295,18 @@ namespace mln } inline + std::pair<unsigned, unsigned> + graph::add_vertices(unsigned n) + { + /* FIXME: This is not thread-proof (these two lines should + form an atomic section). */ + data_->vertices_.resize(data_->vertices_.size() + n); + + return std::make_pair(v_nmax() - n, + v_nmax() - 1); + } + + inline graph::vertex_t graph::vertex(unsigned id_v) const { -- 1.5.6.5