cc_tarjan : ---------------------------------------/code #include <oln/core/2d/image2d.hh> #include <oln/core/2d/neighb2d.hh> #include <oln/morpho/cc_tarjan_v4.hh> int main() { using namespace oln; unsigned N = 128; image2d<bool> img(N, N); float tmp; for (unsigned i = 0; i < N; i++) for (unsigned j = 0; j < N; j++) { tmp = 5 * cos(i) * cos(j); img.at(i, j) = (tmp > 0) ? tmp : 0; } morpho::cc_tarjan(img + c4); } ---------------------------------------code/ - v0 // Procedure. Compile: 15,76s Execution: 1,22s +OPTIM-> Compile: 67,67s Execution: 0,03s 1024 iter : 1,75s - v1 // Data owned by f. Compile: 16,39s Execution: 1,16s Execution(optim): +OPTIM-> Compile: 71,90s Execution: 0,03s 1024 iter : 1,78s - v2 // Data owned by f but not input. Compile: 16,35s Execution: 1,35s Execution(optim): +OPTIM-> Compile: 71,96s Execution: 0,06s 1024 iter : 4,03s Index: ChangeLog from Ugo Jardonnet &lt;ugo.jardonnet(a)lrde.epita.fr&gt; cc-tarjan(two_pass) : Fix + Comparative statement : v0, v1, v2. * tests/algorithms/cc_tarjan_v2.cc: New. * tests/algorithms/Makefile.am: . * tests/algorithms/cc_tarjan_v0.cc: New. * tests/algorithms/cc_tarjan_v1.cc: New. * oln/core/concept/point.hh: . * oln/morpho/cc_tarjan_v1.hh: . * oln/morpho/cc_tarjan_v2.hh: . * oln/morpho/cc_tarjan_v4.hh: . * oln/canvas/two_pass.hh: . oln/canvas/two_pass.hh | 79 +++++++++++++++++++-------------------- oln/core/concept/point.hh | 1 oln/morpho/cc_tarjan_v1.hh | 11 ++--- oln/morpho/cc_tarjan_v2.hh | 14 ++++-- oln/morpho/cc_tarjan_v4.hh | 35 ++++++++++------- tests/algorithms/Makefile.am | 8 +++ tests/algorithms/cc_tarjan_v0.cc | 24 +++++++++++ tests/algorithms/cc_tarjan_v1.cc | 24 +++++++++++ tests/algorithms/cc_tarjan_v2.cc | 24 +++++++++++ 9 files changed, 157 insertions(+), 63 deletions(-) Index: tests/algorithms/cc_tarjan_v2.cc --- tests/algorithms/cc_tarjan_v2.cc (revision 0) +++ tests/algorithms/cc_tarjan_v2.cc (revision 0) @@ -0,0 +1,24 @@ +#include <oln/core/2d/image2d.hh> +#include <oln/core/2d/neighb2d.hh> + +#include <oln/morpho/cc_tarjan_v0.hh> + +int main() +{ + using namespace oln; + + unsigned N = 128; + + image2d<bool> img(N, N); + + float tmp; + + for (unsigned i = 0; i < N; i++) + for (unsigned j = 0; j < N; j++) + { + tmp = 5 * cos(i) * cos(j); + img.at(i, j) = (tmp > 0) ? tmp : 0; + } + + morpho::cc_tarjan(img + c4); +} Index: tests/algorithms/Makefile.am --- tests/algorithms/Makefile.am (revision 969) +++ tests/algorithms/Makefile.am (working copy) @@ -25,11 +25,17 @@ check_PROGRAMS = \ fill \ basic_morpho \ - cc_tarjan + cc_tarjan \ + cc_tarjan_v0 \ + cc_tarjan_v1 \ + cc_tarjan_v2 # Algorithms. fill_SOURCES = fill.cc basic_morpho_SOURCES = basic_morpho.cc cc_tarjan_SOURCES = cc_tarjan.cc +cc_tarjan_v0_SOURCES = cc_tarjan_v0.cc +cc_tarjan_v1_SOURCES = cc_tarjan_v1.cc +cc_tarjan_v2_SOURCES = cc_tarjan_v2..cc TESTS = $(check_PROGRAMS) Index: tests/algorithms/cc_tarjan_v0.cc --- tests/algorithms/cc_tarjan_v0.cc (revision 0) +++ tests/algorithms/cc_tarjan_v0.cc (revision 0) @@ -0,0 +1,24 @@ +#include <oln/core/2d/image2d.hh> +#include <oln/core/2d/neighb2d.hh> + +#include <oln/morpho/cc_tarjan_v0.hh> + +int main() +{ + using namespace oln; + + unsigned N = 128; + + image2d<bool> img(N, N); + + float tmp; + + for (unsigned i = 0; i < N; i++) + for (unsigned j = 0; j < N; j++) + { + tmp = 5 * cos(i) * cos(j); + img.at(i, j) = (tmp > 0) ? tmp : 0; + } + + morpho::cc_tarjan(img + c4); +} Index: tests/algorithms/cc_tarjan_v1.cc --- tests/algorithms/cc_tarjan_v1.cc (revision 0) +++ tests/algorithms/cc_tarjan_v1.cc (revision 0) @@ -0,0 +1,24 @@ +#include <oln/core/2d/image2d.hh> +#include <oln/core/2d/neighb2d.hh> + +#include <oln/morpho/cc_tarjan_v0.hh> + +int main() +{ + using namespace oln; + + unsigned N = 128; + + image2d<bool> img(N, N); + + float tmp; + + for (unsigned i = 0; i < N; i++) + for (unsigned j = 0; j < N; j++) + { + tmp = 5 * cos(i) * cos(j); + img.at(i, j) = (tmp > 0) ? tmp : 0; + } + + morpho::cc_tarjan(img + c4); +} Index: oln/core/concept/point.hh --- oln/core/concept/point.hh (revision 969) +++ oln/core/concept/point.hh (working copy) @@ -30,6 +30,7 @@ # define OLN_CORE_CONCEPT_POINT_HH # include <mlc/value.hh> +# include <xtd/vec.hh> # include <oln/core/concept/grid.hh> # include <oln/core/concept/operators.hh> Index: oln/morpho/cc_tarjan_v1.hh --- oln/morpho/cc_tarjan_v1.hh (revision 969) +++ oln/morpho/cc_tarjan_v1.hh (working copy) @@ -32,6 +32,7 @@ # include <oln/canvas/two_pass.hh> # include <oln/level/fill.hh> +# include <oln/core/internal/f_ch_value.hh> namespace oln { @@ -55,7 +56,7 @@ const I& f; oln_plain_value(I, unsigned) output; - oln_plain(I, bool) is_processed; + oln_plain_value(I, bool) is_processed; oln_plain_value(I, point) parent; cc_tarjan_(const I& f) @@ -65,9 +66,9 @@ void init() { - prepare(is_processed, with, in); - prepare(output, with, in); - prepare(parent, with, in); + prepare(is_processed, with, f); + prepare(output, with, f); + prepare(parent, with, f); level::fill(inplace(is_processed), false); } @@ -114,7 +115,7 @@ void do_union(const point& n, const point& p) { - point r = find_root(ima, n, parent); + point r = find_root(n); if (r != p) parent(r) = p; } Index: oln/morpho/cc_tarjan_v2.hh --- oln/morpho/cc_tarjan_v2.hh (revision 969) +++ oln/morpho/cc_tarjan_v2.hh (working copy) @@ -29,6 +29,7 @@ # define OLN_MORPHO_CC_TARJAN_HH # include <oln/core/concept/image.hh> +# include <oln/core/internal/f_ch_value.hh> # include <oln/canvas/two_pass.hh> # include <oln/level/fill.hh> @@ -54,9 +55,11 @@ typedef oln_point(I) point; oln_plain_value(I, unsigned) output; - oln_plain(I, bool) is_processed; + oln_plain_value(I, bool) is_processed; oln_plain_value(I, point) parent; + cc_tarjan_() {} + void init(I f) { prepare(is_processed, with, f); @@ -92,6 +95,7 @@ void final(I f) { + f = f; } point find_root(const I& ima, @@ -106,7 +110,9 @@ } void do_union(const I& ima, - const point& n) + const point& n, + const point& p) + { point r = find_root(ima, n); if (r != p) @@ -123,8 +129,8 @@ oln_plain_value(I, unsigned) cc_tarjan(const Image_with_Nbh<I>& f) { - impl::cc_tarjan_<I> run(exact(f)); - canvas::v2::two_pass(run, f); + impl::cc_tarjan_<I> run; + canvas::v2::two_pass(run, exact(f)); return run.output; } Index: oln/morpho/cc_tarjan_v4.hh --- oln/morpho/cc_tarjan_v4.hh (revision 969) +++ oln/morpho/cc_tarjan_v4.hh (working copy) @@ -28,6 +28,9 @@ #ifndef OLN_MORPHO_CC_TARJAN_HH # define OLN_MORPHO_CC_TARJAN_HH +# include <oln/core/concept/image.hh> +# include <oln/core/internal/f_ch_value.hh> + # include <oln/canvas/two_pass.hh> # include <oln/level/fill.hh> @@ -49,7 +52,7 @@ { template <typename I> - struct cc_tarjan_ : canvas::v4::two_pass<I> + struct cc_tarjan_ : public canvas::v4::two_pass<I> { typedef oln_point(I) point; @@ -57,40 +60,44 @@ oln_plain_value(I, bool) is_processed; oln_plain_value(I, point) parent; - void init(I f) + cc_tarjan_(const I& img) { - prepare(is_processed, with, f); - prepare(output, with, f); - prepare(parent, with, f); + } + + void init() + { + prepare(is_processed, with, this.f); + prepare(output, with, this.f); + prepare(parent, with, this.f); level::fill(inplace(is_processed), false); } - void first_pass_body(const point& p, I f) + void first_pass_body(const point& p) { parent(p) = p; if ( f(p) ) { - oln_niter(I) n(f, p); + oln_niter(I) n(this.f, p); for_all(n) { - if ( f(n) == true and is_processed(n) ) - do_union(f, n, p); + if ( this.f(n) == true and is_processed(n) ) + do_union(this.f, n, p); } is_processed(p) = true; } } - void second_pass_body(const point& p, I f) + void second_pass_body(const point& p) { unsigned current_label = 0; - if ( f(p) == true and parent(p) == p ) + if ( this.f(p) == true and parent(p) == p ) output(p) = ++current_label; else output(p) = output(parent(p)); } - void final(I f) + void final() { } @@ -129,7 +136,9 @@ { impl::cc_tarjan_<I> f_cc_tarjan(exact(f)); - return f_cc_tarjan.run(); + f_cc_tarjan.run(); + + return f_cc_tarjan.output; } # endif // ! OLN_INCLUDE_ONLY Index: oln/canvas/two_pass.hh --- oln/canvas/two_pass.hh (revision 969) +++ oln/canvas/two_pass.hh (working copy) @@ -37,69 +37,69 @@ { template <template <class> class F, typename I> // Data owned by f. - void two_pass(F<I> f) + void two_pass(F<I> fun) { // mlc::assert_< mlc_is_a(I, Image) >::check(); - f.init(); + fun.init(); // first pass - oln_bkd_piter(I) p1(f.input.points()); + oln_bkd_piter(I) p1(fun.f.points()); for_all(p1) - f.first_pass_body(p1); + fun.first_pass_body(p1); // second pass - oln_fwd_piter(I) p2(f.input.points()); + oln_fwd_piter(I) p2(fun.f.points()); for_all(p2) - f.second_pass_body(p2); + fun.second_pass_body(p2); - f.final(); + fun.final(); } } - namespace v2 // Data owned by f but not input + namespace v2 // Data owned by f but not input. { template <typename F, typename I> - void two_pass(F f, I input) + void two_pass(F fun, I f) { // mlc::assert_< mlc_is_a(I, Image) >::check(); - f.init(input); + fun.init(f); // first pass - oln_bkd_piter(I) p1(input.points()); + oln_bkd_piter(I) p1(f.points()); for_all(p1) - f.first_pass_body(p1, input); + fun.first_pass_body(p1, f); // second pass - oln_fwd_piter(I) p2(input.points()); + oln_fwd_piter(I) p2(f.points()); for_all(p2) - f.second_pass_body(p2, input); + fun.second_pass_body(p2, f); - f.final(input); + fun.final(f); } } namespace v3 // Auxiliar data given as argument. { template <typename F, typename I, typename A> - void two_pass(F f, I input, A aux) + void two_pass(F fun, I f, A aux) { // mlc::assert_< mlc_is_a(I, Image) >::check(); - f.init(input, aux); + f.init(f, aux); // first pass - oln_bkd_piter(I) p1(input.points()); + oln_bkd_piter(I) p1(f.points()); for_all(p1) - f.first_pass_body(p1, input, aux); + f.first_pass_body(p1, f, aux); // second pass - oln_fwd_piter(I) p2(input.points()); + oln_fwd_piter(I) p2(f.points()); for_all(p2) - f.second_pass_body(p2, input, aux); + f.second_pass_body(p2, f, aux); - f.final(input, aux); + f.final(f, aux); } } @@ -108,38 +108,37 @@ { template <typename I> - class two_pass + struct two_pass { - void init(I input) { } + const I& f; - void final(I input) { } - void first_pass_body(const oln_point(I)& p) - { - assert (0 && "two_pass canvas : procedure 'void first_pass_body(const oln_point(I)& p)' must be defined"); - } - void second_pass_body(const oln_point(I)& p) - { - assert (0 && "two_pass canvas : procedure 'void second_pass_body(const oln_point(I)& p)' must be defined"); - } + void init(); - void run(I input) + void final(); + + void first_pass_body(const oln_point(I)& p); + + void second_pass_body(const oln_point(I)& p); + + void run() { - init(input); + init(f); // first pass - oln_bkd_piter(I) p1(input.points()); + oln_bkd_piter(I) p1(f.points()); for_all(p1) - first_pass_body(p1, input); + first_pass_body(p1); // second pass - oln_fwd_piter(I) p2(input.points()); + oln_fwd_piter(I) p2(f.points()); for_all(p2) - second_pass_body(p2, input); + second_pass_body(p2); + + final(f); - final(input); } };