"Christophe" == Christophe Berger <christophe@lrde.epita.fr> writes:
| Index: ChangeLog | from Christophe Berger <christophe@lrde.epita.fr> | * oln/appli/astro/tree_coherance_checks.hh: New. | * oln/appli/astro/tree_statistics.hh: New. | * oln/canvas/tree.hh: Put the vector of sorted points in public. | This attribute is needed by checks and statistics functions. | Index: oln/appli/astro/tree_statistics.hh | --- oln/appli/astro/tree_statistics.hh (revision 0) | +++ oln/appli/astro/tree_statistics.hh (revision 0) | @@ -0,0 +1,260 @@ | +// Copyright (C) 2005 EPITA Research and Development Laboratory | +// | +// 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, 59 Temple Place - Suite 330, 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 OLENA_APPLI_ASTRO_TREE_STATISTICS | +# define OLENA_APPLI_ASTRO_TREE_STATISTICS | + | +# include <mlc/any.hh> | + | +# include <oln/core/abstract/image_entry.hh> | +# include <oln/core/ch_value_type.hh> | +# include <oln/level/fill.hh> | + | +# include <oln/core/pw/check.hh> | +# include <oln/appli/astro/clean.hh> | +# include <oln/basics.hh> | + | +# include <queue> | + | +namespace oln { | + | + namespace maxtree { | + | + namespace statistics { | + | + /** | + ** Counts the number of leafs in the tree. | + ** | + ** \param I Type of maxtree's image. | + ** | + ** \arg tree Maxtree structure to check. I agree that it is misleading, but you should use \param to document formal arguments of your functions, not \arg. As far as I known, we currently don't have any convention to document template parameters. I guess you could use \arg. | + ** | + ** \warning Maxtree should have already been computed. | + ** | + ** \code | + ** Algorithm used : | + ** | + ** Tree is traversed using breadth-first traversal with a queue. | + ** Increments count on leaf (no children). | + ** | + ** \endcode | + ** | + ** \return Number of leafs (terminal nodes). | + ** | + */ | + template<typename I> | + int leaf_count(oln::appli::astro::clean<I>& tree) | + { | + typedef oln_type_of(I, point) point_type; | + std::queue<point_type> q; | + q.push(tree.find_root(point_type(0,0))); | + int count = 0; | + while (not q.empty()) | + { | + point_type &p = q.front(); | + q.pop(); | + const std::vector<point_type> children = tree.children_get(p); | + typename std::vector<point_type>::const_iterator pchild; | + if (children.empty()) | + ++count; | + else | + for (pchild = children.begin(); | + pchild != children.end(); | + pchild++) | + q.push(*pchild); | + } | + return count; | + } | + | + /** | + ** Makes the children per node average. s/Makes/Compute/ Use imperative, not indicative. | + template<typename I> | + float children_average(oln::appli::astro::clean<I>& tree) | + { | + typedef oln_type_of(I, point) point_type; | + std::queue<point_type> q; | + q.push(tree.find_root(point_type(0,0))); | + double node_count = 0; | + double children_count = 0; | + while (not q.empty()) | + { | + point_type &p = q.front(); | + q.pop(); | + ++node_count; | + const std::vector<point_type> children = tree.children_get(p); | + typename std::vector<point_type>::const_iterator pchild; | + for (pchild = children.begin(); | + pchild != children.end(); | + pchild++) | + { | + q.push(*pchild); | + ++children_count; | + } | + } | + return children_count / node_count; | + } I think you should use float or double, but not both. | + /** | + ** Max depth of tree. | + ** | + ** \param I Type of maxtree's image. | + ** | + ** \arg tree Maxtree structure to check. | + ** | + ** \warning Maxtree should have already been computed. | + ** | + ** This algorith is not the best way to compute max depth! s/algorith/algorithm/ | + template<typename I> | + void dotty_output(oln::appli::astro::clean<I>& tree, const std::string& filename) Try to write lines that fits in the width of a standard terminal (80 colums) as much as possible. | Index: oln/appli/astro/tree_coherance_checks.hh | --- oln/appli/astro/tree_coherance_checks.hh (revision 0) | +++ oln/appli/astro/tree_coherance_checks.hh (revision 0) | @@ -0,0 +1,354 @@ | +// Copyright (C) 2005 EPITA Research and Development Laboratory | +// | +// 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, 59 Temple Place - Suite 330, 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 OLENA_APPLI_ASTRO_TREE_COHERENCE_CHECKS | +# define OLENA_APPLI_ASTRO_TREE_COHERENCE_CHECKS | + | +# include <mlc/any.hh> | + | +# include <oln/core/abstract/image_entry.hh> | +# include <oln/core/ch_value_type.hh> | +# include <oln/level/fill.hh> | + | +# include <oln/core/pw/check.hh> | +# include <oln/appli/astro/clean.hh> | +# include <oln/basics.hh> | + | +# include <queue> | + | +namespace oln { | + | + namespace maxtree { | + | + namespace coherance_check { s/coherance/coherence/ | + /** | + ** Check if children relashionship is coherent in the tree. | + ** | + ** \param I Exact type of maxtree's image. | + ** | + ** \arg tree maxtree structure to check. | + ** | + ** \warning Maxtree should have already been computed. | + ** | + ** \code | + ** Algorithm used : | + ** | + ** For all points (p) of input | + ** if (p) is not the root | + ** search for parent (par) of p | + ** ensure (p) is contained in children of (par) | + ** else | + ** // nothing, root parent of hiself s/hiself/itself/ | + /** | + ** Check if there is no recursion between parent and children. | + ** | + ** \param I Exact type of maxtree's image. | + ** | + ** \arg tree maxtree structure to check. | + ** | + ** A node cannot be children of hiself, this check if this Likewise. | + /** | + ** Check if maxtree construction was well done. | + ** | + ** \param I Exact type of maxtree's image. | + ** | + ** \arg tree maxtree structure to check. | + ** | + ** The maxtree structure is based on Tarjan's union find s/union find/Union-Find/ | + /** | + ** Check if all points of the image are contained | + ** in the maxtree. | + ** | + ** \param I Exact type of maxtree's image. | + ** | + ** \arg tree maxtree structure to check. | + ** | + ** Maxtree should cover the whole area of the base image. | + ** | + ** \warning Maxtree should have already been computed. | + ** | + ** \code | + ** Algorithm used : | + ** | + ** Tree is traversed using breadth-first traversal with a queue. | + ** Every points are marked, at the end all the points must s/Every points are marked/Every points is marked/ | + ** have been marked. | + ** | + ** \endcode | + ** | + ** \return True if all points where marked. s/where/were/ Great work!