Ugo Jardonnet wrote (en vrai):

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 <ugo.jardonnet@lrde.epita.fr>

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); }

};