Index: ChangeLog from Ugo Jardonnet <ugo.jardonnet@lrde.epita.fr> Fix cc_tarjan alorithms (4 versions). * oln/morpho/union_find.hh: Remove. * oln/morpho/cc_tarjan_v0.hh: New. * oln/morpho/cc_tarjan_v1.hh: New. * oln/morpho/cc_tarjan_v2.hh: New. * oln/morpho/cc_tarjan_v3.hh: New. * oln/morpho/cc_tarjan_v4.hh: New. * oln/morpho/union_find_v2.hh: Remove. * oln/morpho/union_find_procedure.hh: Remove. * oln/morpho/union_find_v3.hh: Remove. * oln/morpho/union_find_v4.hh: Remove. * oln/canvas/two_pass.hh: . canvas/two_pass.hh | 16 +++---- morpho/cc_tarjan_v1.hh | 95 +++++++++++++++++++++---------------------- morpho/cc_tarjan_v2.hh | 97 ++++++++++++++++++++------------------------ morpho/cc_tarjan_v3.hh | 16 +++---- morpho/cc_tarjan_v4.hh | 107 +++++++++++++++++++++++-------------------------- 5 files changed, 158 insertions(+), 173 deletions(-) Index: oln/morpho/cc_tarjan_v1.hh --- oln/morpho/cc_tarjan_v1.hh (revision 963) +++ oln/morpho/cc_tarjan_v1.hh (working copy) @@ -25,8 +25,8 @@ // reasons why the executable file might be covered by the GNU General // Public License. -#ifndef OLN_MORPHO_UNION_FIND_HH -# define OLN_MORPHO_UNION_FIND_HH +#ifndef OLN_MORPHO_CC_TARJAN_HH +# define OLN_MORPHO_CC_TARJAN_HH # include <oln/core/concept/image.hh> @@ -41,85 +41,82 @@ template <typename I> oln_plain_value(I, unsigned) - union_find(const Image_with_Nbh<I>& input); + cc_tarjan(const Image_with_Nbh<I>& f); # ifndef OLN_INCLUDE_ONLY namespace impl { template <typename I> - struct union_find_ + struct cc_tarjan_ { - const I& input; - oln_plain_value(I, unsigned) output; + typedef oln_point(I) point; - oln_plain(I) is_processed; - oln_plain_value(I, oln_point(I)) parent; + const I& f; - union_find_(const I& in) - : input(in) - { - prepare(is_processed, with, in); - prepare(output, with, in); - prepare(parent, with, in); - } - - oln_point(I) - find_root(const I& ima, - const oln_point(I)& x, - oln_plain_value(I, oln_point(I))& parent) - { - if (parent(x) != x) - { - parent(x) = find_root(ima, parent(x), parent); - return parent(x); - } - return x; - } + oln_plain_value(I, unsigned) output; + oln_plain(I, bool) is_processed; + oln_plain_value(I, point) parent; - void - do_union(const I& ima, - const oln_point(I)& n, - const oln_point(I)& p, - oln_plain_value(I, oln_point(I))& parent) + cc_tarjan_(const I& f) + : f(f) { - oln_point(I) r = find_root(ima, n, parent); - if (r != p) - parent(r) = p; } void init() { + prepare(is_processed, with, in); + prepare(output, with, in); + prepare(parent, with, in); level::fill(inplace(is_processed), false); } - void first_pass_body(const oln_point(I)& p) + void first_pass_body(const point& p) { parent(p) = p; - if ( input(p) ) + if ( f(p) ) { - oln_niter(I) n(input, p); + oln_niter(I) n(f, p); for_all(n) { - if ( input(n) == true and is_processed(n) ) - do_union(input, n, p, parent); + if ( f(n) == true and is_processed(n) ) + do_union(n, p); } is_processed(p) = true; } } - void second_pass_body(const oln_point(I)& p) + void second_pass_body(const point& p) { unsigned current_label = 0; - if ( input(p) == true and parent(p) == p ) + if ( f(p) == true and parent(p) == p ) output(p) = ++current_label; else output(p) = output(parent(p)); } - void final() + void final() { } + + + // auxiliary methods + + point find_root(const point& x) + { + if (parent(x) != x) + { + parent(x) = find_root(parent(x)); + return parent(x); + } + return x; + } + + void do_union(const point& n, + const point& p) { + point r = find_root(ima, n, parent); + if (r != p) + parent(r) = p; } }; @@ -130,11 +127,11 @@ template <typename I> oln_plain_value(I, unsigned) - union_find(const Image_with_Nbh<I>& input) + cc_tarjan(const Image_with_Nbh<I>& f) { - impl::union_find_<I> f(exact(input)); - canvas::v1::two_pass(f); - return f.output; + impl::cc_tarjan_<I> run(exact(f)); + canvas::v1::two_pass(run); + return run.output; } # endif // ! OLN_INCLUDE_ONLY @@ -144,4 +141,4 @@ } // end of namespace oln -#endif // ! OLN_MORPHO_UNION_FIND_HH +#endif // ! OLN_MORPHO_CC_TARJAN_HH Index: oln/morpho/cc_tarjan_v2.hh --- oln/morpho/cc_tarjan_v2.hh (revision 963) +++ oln/morpho/cc_tarjan_v2.hh (working copy) @@ -25,8 +25,8 @@ // reasons why the executable file might be covered by the GNU General // Public License. -#ifndef OLN_MORPHO_UNION_FIND_HH -# define OLN_MORPHO_UNION_FIND_HH +#ifndef OLN_MORPHO_CC_TARJAN_HH +# define OLN_MORPHO_CC_TARJAN_HH # include <oln/core/concept/image.hh> @@ -41,7 +41,7 @@ template <typename I> oln_plain_value(I, unsigned) - union_find(const Image_with_Nbh<I>& input); + cc_tarjan(const Image_with_Nbh<I>& f); # ifndef OLN_INCLUDE_ONLY @@ -49,76 +49,69 @@ { template <typename I> - struct union_find_ + struct cc_tarjan_ { - oln_plain_value(I, unsigned) output; - - oln_plain(I) is_processed; - oln_plain_value(I, oln_point(I)) parent; - - union_find_(I in) - { - prepare(is_processed, with, in); - prepare(output, with, in); - prepare(parent, with, in); - } - - oln_point(I) - find_root(const I& ima, - const oln_point(I)& x, - oln_plain_value(I, oln_point(I))& parent) - { - if (parent(x) != x) - { - parent(x) = find_root(ima, parent(x), parent); - return parent(x); - } - return x; - } + typedef oln_point(I) point; - void - do_union(const I& ima, - const oln_point(I)& n, - const oln_point(I)& p, - oln_plain_value(I, oln_point(I))& parent) - { - oln_point(I) r = find_root(ima, n, parent); - if (r != p) - parent(r) = p; - } + oln_plain_value(I, unsigned) output; + oln_plain(I, bool) is_processed; + oln_plain_value(I, point) parent; - void init() + void init(I f) { + prepare(is_processed, with, f); + prepare(output, with, f); + prepare(parent, with, f); level::fill(inplace(is_processed), false); } - void first_pass_body(const oln_point(I)& p, I input) + void first_pass_body(const point& p, I f) { parent(p) = p; - if ( input(p) ) + if ( f(p) ) { - oln_niter(I) n(input, p); + oln_niter(I) n(f, p); for_all(n) { - if ( input(n) == true and is_processed(n) ) - do_union(input, n, p, parent); + if ( f(n) == true and is_processed(n) ) + do_union(f, n, p); } is_processed(p) = true; } } - void second_pass_body(const oln_point(I)& p, I input) + void second_pass_body(const point& p, I f) { unsigned current_label = 0; - if ( input(p) == true and parent(p) == p ) + if ( f(p) == true and parent(p) == p ) output(p) = ++current_label; else output(p) = output(parent(p)); } - void final() + void final(I f) + { + } + + point find_root(const I& ima, + const point& x) + { + if (parent(x) != x) + { + parent(x) = find_root(ima, parent(x)); + return parent(x); + } + return x; + } + + void do_union(const I& ima, + const point& n) { + point r = find_root(ima, n); + if (r != p) + parent(r) = p; + } }; @@ -128,11 +121,11 @@ template <typename I> oln_plain_value(I, unsigned) - union_find(const Image_with_Nbh<I>& input) + cc_tarjan(const Image_with_Nbh<I>& f) { - impl::union_find_<I> f(exact(input)); - canvas::v2::two_pass(f, input); - return f.output; + impl::cc_tarjan_<I> run(exact(f)); + canvas::v2::two_pass(run, f); + return run.output; } # endif // ! OLN_INCLUDE_ONLY @@ -142,4 +135,4 @@ } // end of namespace oln -#endif // ! OLN_MORPHO_UNION_FIND_HH +#endif // ! OLN_MORPHO_CC_TARJAN_HH Index: oln/morpho/cc_tarjan_v3.hh --- oln/morpho/cc_tarjan_v3.hh (revision 963) +++ oln/morpho/cc_tarjan_v3.hh (working copy) @@ -25,8 +25,8 @@ // reasons why the executable file might be covered by the GNU General // Public License. -#ifndef OLN_MORPHO_UNION_FIND_HH -# define OLN_MORPHO_UNION_FIND_HH +#ifndef OLN_MORPHO_CC_TARJAN_HH +# define OLN_MORPHO_CC_TARJAN_HH # include <oln/core/concept/image.hh> @@ -41,14 +41,14 @@ template <typename I> oln_plain_value(I, unsigned) - union_find(const Image_with_Nbh<I>& input); + cc_tarjan(const Image_with_Nbh<I>& input); # ifndef OLN_INCLUDE_ONLY namespace impl { template <typename I> - struct union_find_ + struct cc_tarjan_ { const I& input; oln_plain_value(I, unsigned) output; @@ -56,7 +56,7 @@ oln_plain(I) is_processed; oln_plain_value(I, oln_point(I)) parent; - union_find_(const I& in) + cc_tarjan_(const I& in) : input(in) { prepare(is_processed, with, in); @@ -130,9 +130,9 @@ template <typename I> oln_plain_value(I, unsigned) - union_find(const Image_with_Nbh<I>& input) + cc_tarjan(const Image_with_Nbh<I>& input) { - impl::union_find_<I> f(exact(input)); + impl::cc_tarjan_<I> f(exact(input)); canvas::v1::two_pass(f); return f.output; } @@ -144,4 +144,4 @@ } // end of namespace oln -#endif // ! OLN_MORPHO_UNION_FIND_HH +#endif // ! OLN_MORPHO_CC_TARJAN_HH Index: oln/morpho/cc_tarjan_v4.hh --- oln/morpho/cc_tarjan_v4.hh (revision 963) +++ oln/morpho/cc_tarjan_v4.hh (working copy) @@ -25,10 +25,8 @@ // reasons why the executable file might be covered by the GNU General // Public License. -#ifndef OLN_MORPHO_UNION_FIND_HH -# define OLN_MORPHO_UNION_FIND_HH - -# include <oln/core/concept/image.hh> +#ifndef OLN_MORPHO_CC_TARJAN_HH +# define OLN_MORPHO_CC_TARJAN_HH # include <oln/canvas/two_pass.hh> # include <oln/level/fill.hh> @@ -39,87 +37,84 @@ namespace morpho { + // Fwd declaration. + template <typename I> oln_plain_value(I, unsigned) - union_find(const Image_with_Nbh<I>& input); + cc_tarjan(const Image_with_Nbh<I>& f); # ifndef OLN_INCLUDE_ONLY namespace impl { - template <typename I> - struct union_find_ - { - const I& input; - oln_plain_value(I, unsigned) output; - - oln_plain(I) is_processed; - oln_plain_value(I, oln_point(I)) parent; - - union_find_(const I& in) - : input(in) - { - prepare(is_processed, with, in); - prepare(output, with, in); - prepare(parent, with, in); - } - oln_point(I) - find_root(const I& ima, - const oln_point(I)& x, - oln_plain_value(I, oln_point(I))& parent) - { - if (parent(x) != x) + template <typename I> + struct cc_tarjan_ : canvas::v4::two_pass<I> { - parent(x) = find_root(ima, parent(x), parent); - return parent(x); - } - return x; - } + typedef oln_point(I) point; - void - do_union(const I& ima, - const oln_point(I)& n, - const oln_point(I)& p, - oln_plain_value(I, oln_point(I))& parent) - { - oln_point(I) r = find_root(ima, n, parent); - if (r != p) - parent(r) = p; - } + oln_plain_value(I, unsigned) output; + oln_plain_value(I, bool) is_processed; + oln_plain_value(I, point) parent; - void init() + void init(I f) { + prepare(is_processed, with, f); + prepare(output, with, f); + prepare(parent, with, f); level::fill(inplace(is_processed), false); } - void first_pass_body(const oln_point(I)& p) + void first_pass_body(const point& p, I f) { parent(p) = p; - if ( input(p) ) + if ( f(p) ) { - oln_niter(I) n(input, p); + oln_niter(I) n(f, p); for_all(n) { - if ( input(n) == true and is_processed(n) ) - do_union(input, n, p, parent); + if ( f(n) == true and is_processed(n) ) + do_union(f, n, p); } is_processed(p) = true; } } - void second_pass_body(const oln_point(I)& p) + void second_pass_body(const point& p, I f) { unsigned current_label = 0; - if ( input(p) == true and parent(p) == p ) + if ( f(p) == true and parent(p) == p ) output(p) = ++current_label; else output(p) = output(parent(p)); } - void final() + void final(I f) + { + } + + + // auxiliary methods + + point find_root(const I& ima, + const point& x) + { + if (parent(x) != x) + { + parent(x) = find_root(ima, parent(x)); + return parent(x); + } + return x; + } + + void do_union(const I& ima, + const point& n, + const point& p) { + point r = find_root(ima, n); + if (r != p) + parent(r) = p; } }; @@ -130,11 +125,11 @@ template <typename I> oln_plain_value(I, unsigned) - union_find(const Image_with_Nbh<I>& input) + cc_tarjan(const Image_with_Nbh<I>& f) { - impl::union_find_<I> f(exact(input)); - canvas::v1::two_pass(f); - return f.output; + impl::cc_tarjan_<I> f_cc_tarjan(exact(f)); + + return f_cc_tarjan.run(); } # endif // ! OLN_INCLUDE_ONLY @@ -144,4 +139,4 @@ } // end of namespace oln -#endif // ! OLN_MORPHO_UNION_FIND_HH +#endif // ! OLN_MORPHO_CC_TARJAN_HH Index: oln/canvas/two_pass.hh --- oln/canvas/two_pass.hh (revision 963) +++ oln/canvas/two_pass.hh (working copy) @@ -44,12 +44,12 @@ f.init(); // first pass - oln_fwd_piter(I) p1(f.input.points()); + oln_bkd_piter(I) p1(f.input.points()); for_all(p1) f.first_pass_body(p1); // second pass - oln_bkd_piter(I) p2(f.input.points()); + oln_fwd_piter(I) p2(f.input.points()); for_all(p2) f.second_pass_body(p2); @@ -67,12 +67,12 @@ f.init(input); // first pass - oln_fwd_piter(I) p1(input.points()); + oln_bkd_piter(I) p1(input.points()); for_all(p1) f.first_pass_body(p1, input); // second pass - oln_bkd_piter(I) p2(input.points()); + oln_fwd_piter(I) p2(input.points()); for_all(p2) f.second_pass_body(p2, input); @@ -90,12 +90,12 @@ f.init(input, aux); // first pass - oln_fwd_piter(I) p1(input.points()); + oln_bkd_piter(I) p1(input.points()); for_all(p1) f.first_pass_body(p1, input, aux); // second pass - oln_bkd_piter(I) p2(input.points()); + oln_fwd_piter(I) p2(input.points()); for_all(p2) f.second_pass_body(p2, input, aux); @@ -130,12 +130,12 @@ init(input); // first pass - oln_fwd_piter(I) p1(input.points()); + oln_bkd_piter(I) p1(input.points()); for_all(p1) first_pass_body(p1, input); // second pass - oln_bkd_piter(I) p2(input.points()); + oln_fwd_piter(I) p2(input.points()); for_all(p2) second_pass_body(p2, input);