June 2008 - Olena-patches

2002: Fix mln/algebra/vec.hh (to_point).
by Ugo Jardonnet 06 Jun '08

06 Jun '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Ugo Jardonnet <jardonnet(a)lrde.epita.fr> Fix mln/algebra/vec.hh (to_point). * mln/algebra/vec.hh (to_point): Fix. Coord conversions now use cast operator (It wasn't the case! argg). vec.hh | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) Index: mln/algebra/vec.hh --- mln/algebra/vec.hh (revision 2001) +++ mln/algebra/vec.hh (working copy) @@ -557,7 +557,7 @@ { P tmp; for (unsigned i = 0; i < P::dim; ++i) - tmp[i] = round(v[i]); + tmp[i] = typename P::coord(v[i]);//round(v[i]); return tmp; }

1 0

2001 (space odyssey): Sandbox: ICP: Make icp stop if error e_k < error d_k.
by Ugo Jardonnet 06 Jun '08

06 Jun '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox Index: ChangeLog from Ugo Jardonnet <jardonnet(a)lrde.epita.fr> Sandbox: ICP: Make icp stop if e_k < d_k (errors). * jardonnet/test/icp_ref.cc: Fix p_array initialisation. * jardonnet/registration/icp_ref.hh (impl::icp) : Update : Stop if e_k < d_k. registration/icp_ref.hh | 11 ++++++----- registration/tools.hh | 1 + test/icp_ref.cc | 33 ++++++++++++++++++++++++++------- 3 files changed, 33 insertions(+), 12 deletions(-) Index: jardonnet/test/icp_ref.cc --- jardonnet/test/icp_ref.cc (revision 2000) +++ jardonnet/test/icp_ref.cc (working copy) @@ -22,9 +22,8 @@ if (argc != 5) usage(argv); - float q = std::atof(argv[3]); - int e = std::atoi(argv[4]); - + float q = 1;//std::atof(argv[3]); + int e = 1;//std::atoi(argv[4]); if (q < 1 or e < 1) usage(argv); @@ -44,14 +43,34 @@ I3d surface = convert::to_image3d(img2); //build p_arrays. - p_array<mln_point_(I3d)> c = convert::to_p_array(cloud); - p_array<mln_point_(I3d)> x = convert::to_p_array(surface); + p_array< point_<grid::cube, float> > c; + { + mln_piter_(I3d) p(cloud.domain()); + for_all(p) + if (cloud(p)) + { + point_<grid::cube,float> p_; + p_[0] = p[0]; p_[1] = p[1]; p_[2] = p[2]; + c.append(p_); + } + } + p_array< point_<grid::cube, float> > x; + { + mln_piter_(I3d) p(surface.domain()); + for_all(p) + if (surface(p)) + { + point_<grid::cube,float> p_; + p_[0] = p[0]; p_[1] = p[1]; p_[2] = p[2]; + x.append(p_); + } + } //working box - const box_<mln_point_(I3d)> working_box = enlarge(bigger(c.bbox(),x.bbox()),100); + const box_< point_<grid::cube, float> > working_box = enlarge(bigger(c.bbox(),x.bbox()),100); // FIXME : TODO : map : vec<3,float> -> point - closest_point<mln_point_(I3d)> map(x, working_box); + closest_point< point_<grid::cube, float> > map(x, working_box); quat7<3> qk = registration::icp(c, map, q, e, x); Index: jardonnet/registration/tools.hh --- jardonnet/registration/tools.hh (revision 2000) +++ jardonnet/registration/tools.hh (working copy) @@ -200,6 +200,7 @@ return a; } + template < typename P > inline box_<point2d> Index: jardonnet/registration/icp_ref.hh --- jardonnet/registration/icp_ref.hh (revision 2000) +++ jardonnet/registration/icp_ref.hh (working copy) @@ -103,7 +103,7 @@ buffer<4,quat7<P::dim> > buf_qk; p_array Ck(C), Xk(C); - float d_k = 1000, d_k_1 = 1000; + float d_k = 1000, d_k_1 = 1000, e_k = 1000; algebra::vec<P::dim,float> mu_C = center(C, c_length), mu_Xk; @@ -127,10 +127,10 @@ // = d(closest(qk-1(P)), qk(P)) d_k = rms(C, map, c_length, buf_qk[1], qk); -#ifndef NDEBUG // e_k = d(closest(qk-1(P)), qk-1(P)) - float e_k = rms(C, map, c_length, buf_qk[1], buf_qk[1]); + e_k = rms(C, map, c_length, buf_qk[1], buf_qk[1]); +#ifndef NDEBUG //plot file std::cout << k << '\t' << (e_k >= d_k ? ' ' : '-') << '\t' << e_k << '\t' << d_k << '\t' << ((qk - buf_qk[1]).sqr_norm() / qk.sqr_norm()) << '\t' @@ -139,7 +139,8 @@ pts += c_length; #endif k++; - } while (d_k_1 - d_k > epsilon); + } while (e_k >= d_k && d_k_1 - d_k > epsilon); + // FIXME : test (e_k >= d_k) seems to be a bad idea. trace::exiting("registration::impl::icp_"); } @@ -200,7 +201,7 @@ mln_piter(p_array) p(cloud); for_all(p) { - algebra::vec<3,float> p_ = point3d(p), qp_ = qk(p_); + algebra::vec<3,float> p_ = P(p), qp_ = qk(p_); point2d qp = make::point2d(int(qp_[0]), int(qp_[1])); if (tmp.has(qp)) tmp(qp) = c;

1 0

cleanup-2008 1997: Add a 2D simplicial complex (toy code) + a double-window type.
by Thierry Geraud 06 Jun '08

06 Jun '08

https://svn.lrde.epita.fr/svn/oln/branches/cleanup-2008/milena Index: ChangeLog from Thierry Geraud <thierry.geraud(a)lrde.epita.fr> Add a 2D simplicial complex (toy code) + a double-window type. * sandbox/geraud/cs2d: New directory. * sandbox/geraud/cs2d/cs2d.cc: New. * sandbox/geraud/cs2d/dbl_neighb.cc: New. * sandbox/geraud/cs2d/cs2d.hh: New. * sandbox/geraud/cs2d/cs2d_utils.hh: New. * sandbox/geraud/cs2d/dbl_neighb.hh: New. * sandbox/geraud/cs2d/cs2d_morpho.hh: New. cs2d.cc | 110 ++++++++++++++++ cs2d.hh | 172 ++++++++++++++++++++++++++ cs2d_morpho.hh | 372 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ cs2d_utils.hh | 251 ++++++++++++++++++++++++++++++++++++++ dbl_neighb.cc | 112 +++++++++++++++++ dbl_neighb.hh | 167 +++++++++++++++++++++++++ 6 files changed, 1184 insertions(+) Index: sandbox/geraud/cs2d/cs2d.cc --- sandbox/geraud/cs2d/cs2d.cc (revision 0) +++ sandbox/geraud/cs2d/cs2d.cc (revision 0) @@ -0,0 +1,110 @@ +# include "cs2d.hh" +# include "cs2d_morpho.hh" +# include "dbl_neighb.hh" + +# include <mln/debug/println.hh> + +# include <mln/io/pgm/load.hh> +# include <mln/io/pgm/save.hh> +# include <mln/io/ppm/save.hh> + +# include <mln/level/paste.hh> +# include <mln/level/fill.hh> + +# include <mln/morpho/dilation.hh> +# include <mln/morpho/meyer_wst.hh> +# include <mln/morpho/closing_area.hh> + +# include <mln/logical/not.hh> +# include <mln/labeling/blobs.hh> +# include <mln/accu/mean.hh> + + + +void usage(char* argv[]) +{ + std::cerr << "usage: " << argv[0] << " input.pgm lambda output.pgm" << std::endl; + abort(); +} + + +struct is_row_odd_t +{ + bool operator()(const mln::point2d& p) const + { + return p.row() % 2; + } +} is_row_odd; + + + +int main(int argc, char* argv[]) +{ + if (argc != 4) + usage(argv); + + + using namespace mln; + using value::int_u8; + + // trace::quiet = false; + + cmorpho::dbl_neighb2d nbh_e; + nbh_e + .insert_even(dpoint2d(-1,-1)) + .insert_even(dpoint2d(-1,+1)) + .insert_even(dpoint2d( 0,-2)) + .insert_odd(dpoint2d(-2, 0)) + .insert_odd(dpoint2d(-1,-1)) + .insert_odd(dpoint2d(-1,+1)); + + // display_masks(make::box2d(2,3)); + + image2d<int_u8> lena; + io::pgm::load(lena, argv[1]); + + cs2d<int_u8, int_u8, int_u8> cs(lena.domain()); + + fill_cells_with(cs, lena); + level::fill(cs.vertex, 0); + + cmorpho::dbl_neighb2d nbh_g; + nbh_g.insert_odd(up).insert_even(left); + level::paste(cmorpho::gradient(cs.edge, nbh_g), + cs.edge); + // io::pgm::save(cs.impl, "grad.pgm"); + + int lambda = atoi(argv[2]); + if (lambda < 0) + usage(argv); + + if (lambda != 0) + level::paste(morpho::closing_area(cs.edge, nbh_e, lambda), cs.edge); + + cs2d<int_u8, bool, bool> cs_(lena.domain()); + level::fill(cs_.impl, false); + fill_cells_with(cs_, lena); + + unsigned l; + level::fill(cs_.edge, + pw::value(cmorpho::meyer_wst(cs.edge, nbh_e, l)) == pw::cst(0)); + std::cout << "l = " << l << std::endl; + + level::paste(morpho::dilation(cs_.vertex, + convert::to_window(c4())), + cs_.vertex); + + unsigned L; + // debug::println(cs_.impl); + image2d<unsigned> label = labeling::blobs(logical::not_(cs_.impl), c4(), L); + // debug::println(label); + mln_invariant(L == l); + + std::vector<int_u8> v(l + 1); + accu::compute<accu::mean>(cs_.cell, label, v); + + level::fill(cs_.cell, level::transform(label, v)); + io::pgm::save(cell_image(cs_), argv[3]); + +// io::ppm::save(pack(cs_, colorize, 7), "log.ppm"); +} Index: sandbox/geraud/cs2d/dbl_neighb.cc --- sandbox/geraud/cs2d/dbl_neighb.cc (revision 0) +++ sandbox/geraud/cs2d/dbl_neighb.cc (revision 0) @@ -0,0 +1,112 @@ +# include <cstdlib> + +# include <mln/value/int_u8.hh> +# include <mln/value/rgb8.hh> + +# include <mln/core/image2d.hh> +# include <mln/core/neighb2d.hh> +# include <mln/core/window2d.hh> + +# include <mln/convert/to_p_set.hh> +# include <mln/convert/to_image.hh> +# include <mln/debug/println.hh> + +# include "dbl_neighb.hh" + +# include <mln/io/pgm/load.hh> +# include <mln/io/pgm/save.hh> +# include <mln/io/pbm/save.hh> +# include <mln/io/ppm/save.hh> + +# include <mln/level/transform.hh> +# include <mln/literal/black.hh> +# include <mln/pw/all.hh> + +# include <mln/morpho/closing_area.hh> +# include <mln/morpho/gradient.hh> +# include <mln/morpho/meyer_wst.hh> + + + + +struct is_chess_t +{ + bool operator()(const mln::point2d& p) const + { + return p.col() % 2 == p.row() % 2; + } +}; + + +struct colorize : mln::Function_v2v< colorize > +{ + typedef mln::value::rgb8 result; + colorize(unsigned max) + : lut(max + 1) + { + lut[0] = mln::literal::black; + for (unsigned i = 1; i <= max; ++i) + lut[i] = result(100 + std::rand() % 150, + 100 + std::rand() % 150, + 100 + std::rand() % 150); + } + result operator()(unsigned i) const + { + return lut[i]; + } + std::vector<result> lut; +}; + + +void usage(char* argv[]) +{ + std::cerr << "usage: " << argv[0] << " input.pgm lambda output.ppm" << std::endl; + abort(); +} + + +int main(int argc, char* argv[]) +{ + using namespace mln; + using value::int_u8; + + if (argc != 4) + usage(argv); + + image2d<int_u8> lena; + io::pgm::load(lena, argv[1]); + + bool vert[] = { 1, 1, 0, + 1, 0, 1, + 0, 1, 1 }; + + bool hori[] = { 0, 1, 1, + 1, 0, 1, + 1, 1, 0 }; + + dbl_neighb_<dpoint2d, is_chess_t> nbh; + nbh + .when_true (make::neighb2d(vert)) + .when_false(make::neighb2d(hori)); + + image2d<int_u8> clo, grad = morpho::gradient(lena, nbh); + // io::pgm::save(grad, "grad.pgm"); + + int lambda = atoi(argv[2]); + if (lambda > 1) + { + clo = morpho::closing_area(grad, nbh, lambda); + // io::pgm::save(clo, "clo.pgm"); + } + else + clo = grad; + + unsigned l; + image2d<unsigned> wst = morpho::meyer_wst(clo, nbh, l); + std::cout << "l = " << l << std::endl; + + io::ppm::save(level::transform(wst, colorize(l)), argv[3]); + +// io::pbm::save((pw::value(wst) == pw::cst(0)) | lena.domain(), +// argv[3]); +} Index: sandbox/geraud/cs2d/cs2d.hh --- sandbox/geraud/cs2d/cs2d.hh (revision 0) +++ sandbox/geraud/cs2d/cs2d.hh (revision 0) @@ -0,0 +1,172 @@ +# include <mln/core/image2d.hh> +# include <mln/core/neighb2d.hh> +# include <mln/core/window2d.hh> +# include <mln/convert/to_window.hh> + +# include <mln/core/image_if.hh> +# include <mln/debug/println.hh> + + +# include "cs2d_utils.hh" + + +namespace mln +{ + + + template <typename C, typename E, typename X> + struct cs2d + { + typedef C cell_value; + typedef E edge_value; + typedef X vertex_value; + + cs2d(unsigned nrows, unsigned ncols) + { + init(nrows, ncols); + } + + cs2d(const box2d& b) + { + init(b.nrows(), b.ncols()); + } + + void init(unsigned nrows, unsigned ncols) + { + mln_precondition(nrows && ncols); + + // Raw data (impl). + b = make::box2d(2 * nrows - 1, 2 * ncols - 1); + cimpl = image2d<C>(b, 0); + eimpl = image2d<E>(b, 0); + ximpl = image2d<X>(b, 0); + + // Images. + cell = cimpl | is_cell; + edge = eimpl | is_edge; + vertex = ximpl | is_vertex; + } + + unsigned nrows() const { return (b.nrows() + 1) / 2; } + unsigned ncols() const { return (b.ncols() + 1) / 2; } + + box2d b; + image2d<C> cimpl; + image2d<E> eimpl; + image2d<X> ximpl; + + typedef image_if< image2d<C>, is_cell_t > cell_t; + cell_t cell; + + typedef image_if< image2d<E>, is_edge_t > edge_t; + edge_t edge; + + typedef image_if< image2d<X>, is_vertex_t > vertex_t; + vertex_t vertex; + }; + + + + + template <typename T> + struct cs2d< T, T, T> + { + typedef T cell_value; + typedef T edge_value; + typedef T vertex_value; + + cs2d(unsigned nrows, unsigned ncols) + { + init(nrows, ncols); + } + + cs2d(const box2d& b) + { + init(b.nrows(), b.ncols()); + } + + void init(unsigned nrows, unsigned ncols) + { + mln_precondition(nrows && ncols); + + // Raw data (impl). + b = make::box2d(2 * nrows - 1, 2 * ncols - 1); + impl = image2d<T>(b, 0); + + // Images. + cell = impl | is_cell; + edge = impl | is_edge; + vertex = impl | is_vertex; + } + + unsigned nrows() const { return (b.nrows() + 1) / 2; } + unsigned ncols() const { return (b.ncols() + 1) / 2; } + + box2d b; + image2d<T> impl; + + typedef image_if< image2d<T>, is_cell_t > cell_t; + cell_t cell; + + typedef image_if< image2d<T>, is_edge_t > edge_t; + edge_t edge; + + typedef image_if< image2d<T>, is_vertex_t > vertex_t; + vertex_t vertex; + }; + + + + + + template <typename C, typename T> + struct cs2d< C, T, T> + { + typedef C cell_value; + typedef T edge_value; + typedef T vertex_value; + + cs2d(unsigned nrows, unsigned ncols) + { + init(nrows, ncols); + } + + cs2d(const box2d& b) + { + init(b.nrows(), b.ncols()); + } + + void init(unsigned nrows, unsigned ncols) + { + mln_precondition(nrows && ncols); + + // Raw data (impl). + b = make::box2d(2 * nrows - 1, 2 * ncols - 1); + cimpl = image2d<C>(b, 0); + impl = image2d<T>(b, 0); + + // Images. + cell = cimpl | is_cell; + edge = impl | is_edge; + vertex = impl | is_vertex; + } + + unsigned nrows() const { return (b.nrows() + 1) / 2; } + unsigned ncols() const { return (b.ncols() + 1) / 2; } + + box2d b; + image2d<C> cimpl; + image2d<T> impl; + + typedef image_if< image2d<C>, is_cell_t > cell_t; + cell_t cell; + + typedef image_if< image2d<T>, is_edge_t > edge_t; + edge_t edge; + + typedef image_if< image2d<T>, is_vertex_t > vertex_t; + vertex_t vertex; + }; + + +} // mln Index: sandbox/geraud/cs2d/cs2d_utils.hh --- sandbox/geraud/cs2d/cs2d_utils.hh (revision 0) +++ sandbox/geraud/cs2d/cs2d_utils.hh (revision 0) @@ -0,0 +1,251 @@ +# include <mln/value/rgb8.hh> +# include <mln/value/int_u8.hh> +# include <mln/literal/black.hh> +# include <mln/literal/white.hh> +# include <mln/literal/colors.hh> +# include <mln/win/rectangle2d.hh> +# include <mln/level/fill.hh> + + +namespace mln +{ + + // 0 1 2 + // 0 c c c + // 1 c c c + + // 0 1 2 3 4 + // 0 c e c e c + // 1 e x e x e + // 2 c e c e c + + + struct is_cell_t : Function_p2b<is_cell_t> + { + typedef bool result; + bool operator()(const point2d& p) const + { + return p.row() % 2 == 0 && p.col() % 2 == 0; + } + } + is_cell; + + + struct is_edge_t : Function_p2b<is_edge_t> + { + typedef bool result; + bool operator()(const point2d& p) const + { + return p.row() % 2 + p.col() % 2 == 1; + } + } + is_edge; + + + struct is_vertex_t : Function_p2b<is_vertex_t> + { + typedef bool result; + bool operator()(const point2d& p) const + { + return p.row() % 2 && p.col() % 2; + } + } + is_vertex; + + + + void display_masks(box2d b) + { + box2d b_(2 * b.nrows() - 1, 2 * b.ncols() - 1); + image2d<char> tmp(b_); + mln_piter_(box2d) p(b_); + for_all(p) + if (is_cell(p)) + { + mln_invariant(! is_edge(p) && ! is_vertex(p)); + tmp(p) = 'O'; + } + else if (is_edge(p)) + { + mln_invariant(! is_cell(p) && ! is_vertex(p)); + tmp(p) = p.to_point().row() % 2 ? '-' : '|'; + } + else if (is_vertex(p)) + { + mln_invariant(! is_edge(p) && ! is_cell(p)); + tmp(p) = '+'; + } + else + mln_invariant(0); + debug::println(tmp); + } + + + struct colorize_t + { + typedef value::rgb8 result; + result operator()(value::int_u8 i) const + { + return result(i,i,i); + } + result operator()(bool b) const + { + if (b) + return literal::red; + else + return literal::black; + } + } + colorize; + + + template <typename Cs, typename F> + image2d<mln_result(F)> pack(const Cs& cs, F f) + { + image2d<mln_result(F)> output(cs.b); + mln_piter(box2d) p(cs.b); + for_all(p) + if (is_cell(p)) + output(p) = f(cs.cell(p)); + else if (is_edge(p)) + output(p) = f(cs.edge(p)); + else + output(p) = f(cs.vertex(p)); + return output; + } + + + template <typename Cs, typename F> + image2d<mln_result(F)> pack(const Cs& cs, F f, unsigned clen) + { + typedef mln_result(F) R; + + mln_precondition(clen % 2); // oddity + + typedef win::rectangle2d Sqr; + Sqr sqr(clen, clen); + + typedef win::hline2d H; + H hline(clen); + + typedef win::vline2d V; + V vline(clen); + + // 0 1 2 3 4 + // 0 c e c e c + // 1 e x e x e + // 2 c e c e c + + // 0 1 2 3 4 5 6 7 8 9 10 + + // 0 c c c . e . c c c . e . c c c + // 1 c c c . e . c c c . e . c c c + // 2 c c c . e . c c c . e . c c c + // 3 . . . . . . . . . . . . . . . + // 4 e e e . x . e e e . x . e e e + // 5 . . . . . . . . . . . . . . . + // 6 c c c . e . c c c . e . c c c + // 7 c c c . e . c c c . e . c c c + // 8 c c c . e . c c c . e . c c c + + box2d b(cs.nrows() * clen + 3 * (cs.nrows() - 1), + cs.ncols() * clen + 3 * (cs.ncols() - 1)); + image2d<R> output(b); + level::fill(output, literal::black); + + // Cells. + mln_piter(Cs::cell_t) c(cs.cell.domain()); + for_all(c) + { + R v = f(cs.cell(c)); + point2d c_ = c.to_point(), p_; + p_.row() = clen / 2 + (clen + 3) * (c_.row() / 2); + p_.col() = clen / 2 + (clen + 3) * (c_.col() / 2); + mln_qiter(Sqr) q(sqr, p_); + for_all(q) + output(q) = v; + } + + // Points. + mln_piter(Cs::vertex_t) x(cs.vertex.domain()); + for_all(x) + { + point2d x_ = x, q; + q.row() = clen + 1 + (clen + 3) * (x_.row() / 2); + q.col() = clen + 1 + (clen + 3) * (x_.col() / 2); + output(q) = f(cs.vertex(x)); + } + + + // 0 1 2 3 4 + // 0 c e c e c + // 1 e x e x e + // 2 c e c e c + + // 0 1 2 3 4 5 6 7 8 9 10 + + // 0 c c c . e . c c c . e . c c c + // 1 c c c . e . c c c . e . c c c + // 2 c c c . e . c c c . e . c c c + // 3 . . . . . . . . . . . . . . . + // 4 e e e . x . e e e . x . e e e + // 5 . . . . . . . . . . . . . . . + // 6 c c c . e . c c c . e . c c c + // 7 c c c . e . c c c . e . c c c + // 8 c c c . e . c c c . e . c c c + + + // Edges. + mln_piter(Cs::edge_t) e(cs.edge.domain()); + for_all(e) + { + R v = f(cs.edge(e)); + point2d e_ = e, p_; + if (e_.row() % 2) // Odd => horizontal. + { + p_.row() = clen + 1 + (clen + 3) * (e_.row() / 2); // vertex-like + p_.col() = clen / 2 + (clen + 3) * (e_.col() / 2); // cell-like + mln_qiter(V) q(hline, p_); + for_all(q) if (output.has(q)) + output(q) = v; + } + else // Even => vertical. + { + p_.row() = clen / 2 + (clen + 3) * (e_.row() / 2); // cell-like + p_.col() = clen + 1 + (clen + 3) * (e_.col() / 2); // vertex-like + mln_qiter(H) q(vline, p_); + for_all(q) if (output.has(q)) + output(q) = v; + } + } + + return output; + } + + + + template <typename Cs, typename T> + void fill_cells_with(Cs& cs, const image2d<T>& input) + { + mlc_equal(T, typename Cs::cell_value)::check(); + mln_piter(box2d) p(input.domain()); + mln_piter(Cs::cell_t) c(cs.cell.domain()); + for_all_2(p, c) + cs.cell(c) = input(p); + } + + template <typename Cs> + image2d<typename Cs::cell_value> + cell_image(const Cs& cs) + { + image2d<typename Cs::cell_value> output(cs.nrows(), cs.ncols()); + mln_piter(box2d) p(output.domain()); + mln_piter(Cs::cell_t) c(cs.cell.domain()); + for_all_2(p, c) + output(p) = cs.cell(c); + return output; + } + +} // mln + + Index: sandbox/geraud/cs2d/dbl_neighb.hh --- sandbox/geraud/cs2d/dbl_neighb.hh (revision 0) +++ sandbox/geraud/cs2d/dbl_neighb.hh (revision 0) @@ -0,0 +1,167 @@ +# include <mln/core/concept/neighborhood.hh> + + +namespace mln +{ + + + // Fwd decl. + template <typename D, typename F> class dbl_niter_; + + + template <typename D, typename F> + struct dbl_neighb_ : public Neighborhood< dbl_neighb_<D,F> > + { + typedef D dpoint; + typedef mln_point(D) point; + + typedef dbl_niter_<D,F> fwd_niter; + typedef dbl_niter_<D,F> bkd_niter; + typedef dbl_niter_<D,F> niter; + + dbl_neighb_(F f) + : f(f) + { + } + + dbl_neighb_() + : f() + { + } + + bool is_empty() const + { + return trues.size() == 0 && falses.size() == 0; + } + + dbl_neighb_& insert_true(const D& dp) + { + trues.push_back(dp); + trues.push_back(-dp); + return *this; + } + + dbl_neighb_& insert_false(const D& dp) + { + falses.push_back(dp); + falses.push_back(-dp); + return *this; + } + + template <typename N> + dbl_neighb_& when_true(const Neighborhood<N>& nbh_) + { + const N& nbh = exact(nbh_); + for (unsigned i = 0; i < nbh.ndpoints(); ++i) + trues.push_back(nbh.dp(i)); + return *this; + } + + template <typename N> + dbl_neighb_& when_false(const Neighborhood<N>& nbh_) + { + const N& nbh = exact(nbh_); + for (unsigned i = 0; i < nbh.ndpoints(); ++i) + falses.push_back(nbh.dp(i)); + return *this; + } + + std::vector<D> trues, falses; + F f; + }; + + + + template <typename D, typename F> + class dbl_niter_ + : public internal::point_iterator_base_< mln_point(D), dbl_niter_<D,F> > + { + public: + + typedef mln_point(D) point; + + template <typename Pref> + dbl_niter_(const Neighborhood< dbl_neighb_<D,F> >& nbh, + const Point_Site<Pref>& p_ref) : + dps_true(exact(nbh).trues), + dps_false(exact(nbh).falses), + p_ref_(exact(p_ref).to_point()), + f(exact(nbh).f) + { + invalidate(); + } + + /// Convertion to point. + operator point () const + { + mln_precondition(is_valid()); + return p_; + } + + /// Reference to the corresponding point. + const point& to_point() const + { + return p_; + } + + /// Test the iterator validity. + bool is_valid() const + { + return i_ != dps_true.size(); + } + + /// Invalidate the iterator. + void invalidate() + { + i_ = dps_true.size(); + } + + /// Start an iteration. + void start() + { + i_ = 0; + update(); + } + + /// Go to the next point. + void next_() + { + ++i_; + update(); + } + + /// Give the i-th coordinate. + int operator[](unsigned i) const + { + mln_precondition(is_valid()); + return p_[i]; + } + + /// The point around which this iterator moves. + const point& center_point() const + { + return p_ref_; + } + + /// Force this iterator to update its location to take into + /// account that its center point may have moved. + void update() + { + if (is_valid()) + p_ = p_ref_ + (f(p_ref_) ? dps_true[i_] : dps_false[i_]); + } + + protected: + + const std::vector<D>& dps_true, dps_false; + const point& p_ref_; // reference point (or "center point") + F f; + + unsigned i_; + point p_; // location of this iterator; p_ makes this iterator be + // itself a potential center point. + }; + + + +} // mln Index: sandbox/geraud/cs2d/cs2d_morpho.hh --- sandbox/geraud/cs2d/cs2d_morpho.hh (revision 0) +++ sandbox/geraud/cs2d/cs2d_morpho.hh (revision 0) @@ -0,0 +1,372 @@ +# include <mln/accu/max.hh> +# include <mln/accu/min_max.hh> +# include <mln/labeling/regional_minima.hh> + +# include <mln/core/p_queue_fast.hh> + + +namespace mln +{ + + namespace cmorpho + { + + template <typename T> + T abs_diff(T t1, T t2) + { + return t1 > t2 ? t1 - t2 : t2 - t1; + } + + template <typename I> + void gradient(I& input) + { + mln_piter(I) p(input.domain()); + for_all(p) + { + mln_point(I) p_ = p; + input(p) = + p_.row() % 2 ? + // Odd so horizontal edge and vertical cells. + abs_diff(input(p_ + left), input(p_ + right)) : + // Otherwise + abs_diff(input(p_ + up), input(p_ + down)); + } + } + + + template <typename I, typename N> + inline + mln_concrete(I) gradient(const Image& input_, + const Neighborhood<N>& nbh_) + { + const I& input = exact(input_); + const N& nbh = exact(nbh_); + + mln_concrete(I) output; + initialize(output, input); + + accu::min_max_<mln_value(I)> m; + + mln_piter(I) p(input.domain()); + mln_niter(N) n(nbh, p); + for_all(p) + { + m.init(); + for_all(n) if (input.owns_(n)) + m.take(input(n)); + output(p) = m.second() - m.first(); + } + return output; + } + + + class dbl_niter; + + struct dbl_neighb2d : public Neighborhood< dbl_neighb2d > + { + typedef dpoint2d dpoint; + typedef point2d point; + + typedef dbl_niter fwd_niter; + typedef dbl_niter bkd_niter; + typedef dbl_niter niter; + + dbl_neighb2d() + { + } + + dbl_neighb2d& insert_odd(const dpoint2d& dp) + { + odds.push_back(dp); + odds.push_back(-dp); + return *this; + } + dbl_neighb2d& insert_even(const dpoint2d& dp) + { + evens.push_back(dp); + evens.push_back(-dp); + return *this; + } + + std::vector<dpoint2d> odds, evens; + }; + + + class dbl_niter + : public internal::point_iterator_base_< point2d, dbl_niter > + { + public: + + typedef dpoint2d D; + + template <typename N, typename Pref> + dbl_niter(const N& nbh, const Point_Site<Pref>& p_ref) : + dps_odd(exact(nbh).odds), + dps_even(exact(nbh).evens), + p_ref_(exact(p_ref).to_point()) + { + + invalidate(); + } + + /// Convertion to point. + operator point2d () const + { + mln_precondition(is_valid()); + return p_; + } + + /// Reference to the corresponding point. + const point2d& to_point() const + { + return p_; + } + + /// Test the iterator validity. + bool is_valid() const + { + return i_ != dps_odd.size(); + } + + /// Invalidate the iterator. + void invalidate() + { + i_ = dps_odd.size(); + } + + /// Start an iteration. + void start() + { + i_ = 0; + update(); + } + + /// Go to the next point. + void next_() + { + ++i_; + update(); + } + + /// Give the i-th coordinate. + int operator[](unsigned i) const + { + mln_precondition(is_valid()); + return p_[i]; + } + + /// The point around which this iterator moves. + const point2d& center_point() const + { + return p_ref_; + } + + /// Force this iterator to update its location to take into + /// account that its center point may have moved. + void update() + { + if (is_valid()) + p_ = p_ref_ + (p_ref_.row() % 2 ? dps_odd[i_] : dps_even[i_]); + } + + protected: + + const std::vector<dpoint2d>& dps_odd, dps_even; + const point2d& p_ref_; // reference point (or "center point") + + unsigned i_; + point2d p_; // location of this iterator; p_ makes this iterator be + // itself a potential center point. + }; + + + template <typename L, typename I, typename N> + mln_ch_value(I, L) + meyer_wst(const Image& input_, const Neighborhood<N>& nbh_, + L& nbasins) + { + trace::entering("morpho::meyer_wst"); + + const I& input = exact(input_); + const N& nbh = exact(nbh_); + + /* FIXME: Ensure the input image has scalar values. */ + + const L unmarked = 0; + + // Initialize the output with the markers (minima components). + mln_ch_value(I, L) output; + output = labeling::regional_minima(input, nbh, nbasins); + + // Ordered queue. + std::vector< p_queue_fast<mln_psite(I)> > qu(256); + unsigned qu_size = 0; + + // Insert every neighbor P of every marked area in a + // hierarchical queue, with a priority level corresponding to + // the grey level input(P). + { + mln_piter(I) p(output.domain()); + mln_niter(N) n(nbh, p); + for_all(p) + if (output(p) == unmarked) + for_all(n) + if (output.has(n) && output(n) != unmarked) + { + qu[input(p)].push_force(p); + ++qu_size; + break; + } + } + + /* Until the queue is empty, extract a psite p from the + hierarchical queue, at the highest priority level, that is, + the lowest level. */ + mln_psite(I) p; + mln_niter(N) n(nbh, p); + + while (qu_size != 0) + { + + for (unsigned l = 0; l < 256; ++l) + if (! qu[l].is_empty()) + { + p = qu[l].pop_front(); + // qu[l].pop(); + break; + } + --qu_size; + + // Last seen marker adjacent to P. + L adjacent_marker = unmarked; + // Has P a single adjacent marker? + bool single_adjacent_marker_p = true; + for_all(n) + if (output.has(n) && output(n) != unmarked) + { + if (adjacent_marker == unmarked) + { + adjacent_marker = output(n); + single_adjacent_marker_p = true; + } + else + if (adjacent_marker != output(n)) + { + single_adjacent_marker_p = false; + break; + } + } + + /* If the neighborhood of P contains only psites with the + same label, then P is marked with this label, and its + neighbors that are not yet marked are put into the + hierarchical queue. */ + if (single_adjacent_marker_p) + { + output(p) = adjacent_marker; + for_all(n) + if (output.has(n) && output(n) == unmarked) + { + qu[input(n)].push_force(n); + ++qu_size; + } + } + } + + trace::exiting("morpho::meyer_wst"); + return output; + } + + } // mln::cmorpho + + + namespace accu + { + + template <typename A_, typename I, typename L> + inline + std::vector<mln_accu_with(A_, mln_value(I))::result> + compute(const Image& input_, + const Image<L>& label_, + mln_value(L) n) + { + mlc_is_a(A_, Meta_Accumulator)::check(); + + trace::entering("accu::compute"); + + const I& input = exact(input_); + const L& label = exact(label_); + + typedef mln_accu_with(A_, mln_value(I)) A; + std::vector<A> a(n + 1); + + mln_piter(I) p(input.domain()); + for_all(p) + a[label(p)].take(input(p)); + + typedef typename A::result R; + std::vector<R> v(n + 1); + for (unsigned l = 1; l <= n; ++l) + v[l] = a[l].to_result(); + + trace::exiting("accu::compute"); + return v; + } + + + template <typename A_, typename I, typename L, typename R> + inline + void + compute(const Image& input_, + const Image<L>& label_, + std::vector<R>& v) + { + mlc_is_a(A_, Meta_Accumulator)::check(); + + trace::entering("accu::compute"); + + const I& input = exact(input_); + const L& label = exact(label_); + + typedef mln_accu_with(A_, mln_value(I)) A; + const unsigned n = v.size(); + std::vector<A> a(n); + + mln_piter(I) p(input.domain()); + for_all(p) + a[label(p)].take(input(p)); + + for (unsigned l = 1; l < n; ++l) + v[l] = a[l].to_result(); + + trace::exiting("accu::compute"); + } + + } // mln::accu + + + namespace level + { + + template<typename I, typename R> + mln_ch_value(I, R) + transform(const Image& input_, const std::vector<R>& v) + { + trace::entering("level::transform"); + const I& input = exact(input_); + + mln_ch_value(I, R) output; + initialize(output, input); + + mln_piter(I) p(input.domain()); + for_all(p) + output(p) = v[input(p)]; + + trace::exiting("level::transform"); + return output; + } + + } // mln::level + + +} // mln

2 1

Re: [Olena-patches] 2000: Fix tests/util/graph.
by Warren Seine 06 Jun '08

06 Jun '08

Roland Levillain wrote: > https://svn.lrde.epita.fr/svn/oln/trunk/milena > > > Index: ChangeLog > from Roland Levillain <roland(a)lrde.epita.fr> > > Fix tests/util/graph. > > * tests/util/graph.cc: Catch up with the new interface of > mln::util::graph<V, E>. > s/add_node/add_vertex/. > > graph.cc | 12 ++++++------ > 1 file changed, 6 insertions(+), 6 deletions(-) > > Index: tests/util/graph.cc > --- tests/util/graph.cc (revision 1999) > +++ tests/util/graph.cc (working copy) > @@ -37,12 +37,12 @@ > > util::graph<void> g; > > - g.add_node (); // 0 > - g.add_node (); // 1 > - g.add_node (); // 2 > - g.add_node (); // 3 > - g.add_node (); // 4 > - g.add_node (); // 5 > + g.add_vertex (); // 0 > + g.add_vertex (); // 1 > + g.add_vertex (); // 2 > + g.add_vertex (); // 3 > + g.add_vertex (); // 4 > + g.add_vertex (); // 5 > g.add_edge (0, 1); > g.add_edge (0, 2); > g.add_edge (3, 4); Congratulations for this 2000th patch ! Transformers will be next ! -- :: Warren Seine // SooW :: :: warren.seine @ gmail.com :: :: EPITA CSI 2010 ::

1 0

2000: Fix tests/util/graph.
by Roland Levillain 06 Jun '08

06 Jun '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Roland Levillain <roland(a)lrde.epita.fr> Fix tests/util/graph. * tests/util/graph.cc: Catch up with the new interface of mln::util::graph<V, E>. s/add_node/add_vertex/. graph.cc | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) Index: tests/util/graph.cc --- tests/util/graph.cc (revision 1999) +++ tests/util/graph.cc (working copy) @@ -37,12 +37,12 @@ util::graph<void> g; - g.add_node (); // 0 - g.add_node (); // 1 - g.add_node (); // 2 - g.add_node (); // 3 - g.add_node (); // 4 - g.add_node (); // 5 + g.add_vertex (); // 0 + g.add_vertex (); // 1 + g.add_vertex (); // 2 + g.add_vertex (); // 3 + g.add_vertex (); // 4 + g.add_vertex (); // 5 g.add_edge (0, 1); g.add_edge (0, 2); g.add_edge (3, 4);

1 0

***SPAM*** L3 1999: Have mln:p_set be able to erase its elements.
by Roland Levillain 06 Jun '08

06 Jun '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Th�o, si tu veux faire la r�vision 2000, c'est le moment ! ;-) Index: ChangeLog from Roland Levillain <roland(a)lrde.epita.fr> Have mln:p_set be able to erase its elements. * mln/core/p_set.hh (mln::p_set::remove): Enable this method. * mln/core/internal/set_of.hh (mln::internal::set_of_<E>::s_): Make it protected. (mln::internal::set_of_<E>::remove): Use std::set::erase instead of std::remove. * tests/core/p_set.cc: Exercise mln::p_set::remove. mln/core/internal/set_of.hh | 6 +++--- mln/core/p_set.hh | 29 +++++++++++++++-------------- tests/core/p_set.cc | 7 +++++++ 3 files changed, 25 insertions(+), 17 deletions(-) Index: tests/core/p_set.cc --- tests/core/p_set.cc (revision 1998) +++ tests/core/p_set.cc (working copy) @@ -50,7 +50,14 @@ mln_assertion(ps.npoints() == 3); std::cout << ps.bbox() << std::endl; + std::copy(ps.vect().begin(), ps.vect().end(), + std::ostream_iterator<point2d>(std::cout, " ")); + std::cout << std::endl; + ps.remove(make::point2d(4, 2)); + mln_assertion(ps.npoints() == 2); + + std::cout << ps.bbox() << std::endl; std::copy(ps.vect().begin(), ps.vect().end(), std::ostream_iterator<point2d>(std::cout, " ")); std::cout << std::endl; Index: mln/core/internal/set_of.hh --- mln/core/internal/set_of.hh (revision 1998) +++ mln/core/internal/set_of.hh (working copy) @@ -147,13 +147,14 @@ */ mutable std::vector<E> v_; + protected: /*! \brief Set of elements. * * This structure is always up-to-date w.r.t. the set contents. */ std::set<E> s_; - + private: /*! \brief Update \a v_ from \a s_. * * FIXME: explain. @@ -206,8 +207,7 @@ set_of_<E>& set_of_<E>::remove(const E& elt) { - // FIXME : doesn't compile - std::remove(s_.begin(), s_.end(), elt); + s_.erase(elt); if (needs_update_ == false) needs_update_ = true; return internal::force_exact< set_of_<E> >(*this); Index: mln/core/p_set.hh --- mln/core/p_set.hh (revision 1998) +++ mln/core/p_set.hh (working copy) @@ -78,9 +78,8 @@ /// Insert a point \p p. p_set& insert(const P& p); - // FIXME : doesn't compile - // /// Remove a point \p p. - // p_set& remove(P& p); + /// Remove a point \p p. + p_set& remove(const P& p); /// Return the \p i-th point. const P& operator[](unsigned i) const; @@ -132,17 +131,19 @@ return *this; } - - // FIXME : finish it. - // template <typename P> - // p_set& - // p_set::remove(P& p) - // { - // this->super_::remove(p); - // // FIXME: need to rebuild bb_ ? - // //bb_.untake(p); - // return *this; - // } + template <typename P> + inline + p_set& + p_set::remove(const P& p) + { + this->super_::remove(p); + // Rebuild the bounding box. + bb_.init(); + for (typename std::set::const_iterator i = this->s_.begin(); + i != this->s_.end(); ++i) + bb_.take(*i); + return *this; + } template <typename P> inline

1 0

1998: https://svn.lrde.epita.fr/svn/oln/trunk/milena
by Roland Levillain 06 Jun '08

06 Jun '08

Like Mac OS X, Ubuntu is too far ahead of its time! ;-) URL: https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog =================================================================== --- ChangeLog (revision 1997) +++ ChangeLog (revision 1998) @@ -1,4 +1,4 @@ -2008-06-04 GÃraud BÃguin <geraud.beguin(a)lrde.epita.fr> +2008-06-04 Géraud Béguin <geraud.beguin(a)lrde.epita.fr> * mln/util/graph.hh: Typo.

1 1

1996: Finish the computation of the fusion graph test.
by Roland Levillain 04 Jun '08

04 Jun '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena/sandbox The code is probably finished (and compiles!), but is buggy: the program gets a SIGSEGV at run time... Index: ChangeLog from Roland Levillain <roland(a)lrde.epita.fr> Finish the computation of the fusion graph test. * beguin/irm.cc: s/node/vertex/. (my_mln::mk2_graph): Disable. (my_mln::region_data, my_mln::abs_diff_threshold): New structs. (my_mln::make_fg, my_mln::merge_fg): New routines. (my_mln::main): Adjust. Compute the fusion graphs and output a result. * beguin/+irm6.pgm: Rename image as... * beguin/irm6.pgm: ...this. irm.cc | 307 +++++++++++++++++++++++++++++++++++++++++++++++++++++------------ 1 file changed, 253 insertions(+), 54 deletions(-) Index: beguin/irm.cc --- beguin/irm.cc (revision 1995) +++ beguin/irm.cc (working copy) @@ -1,6 +1,11 @@ +// g++ -Wall -Wextra -DNDEBUG -O3 -I../.. -o irm irm.cc +// g++ -Wall -Wextra -ggdb -I../.. -o irm irm.cc + #include <iterator> #include <iostream> #include <algorithm> + +#include <set> #include <map> #include <mln/core/image2d.hh> @@ -12,8 +17,12 @@ #include <mln/io/pgm/load.hh> #include <mln/io/pgm/save.hh> +#include <mln/io/ppm/save.hh> #include <mln/value/int_u8.hh> +#include <mln/value/rgb8.hh> +#include <mln/literal/colors.hh> + #include <mln/level/transform.hh> #include <mln/convert/to_window.hh> @@ -32,7 +41,7 @@ #include <mln/debug/println.hh> //#include <segm_to_pregraph.hh> -#include <fusion_graph2.hh> +// #include <fusion_graph2.hh> mln::value::int_u8 foo(unsigned u) { @@ -42,9 +51,10 @@ } -namespace mln - +namespace my_mln { + using namespace mln; + template <typename I> void region_10(const I& lbl) @@ -163,12 +173,12 @@ // // // Graph. // util::graph<float> g; -// // Nodes. +// // Vertices. // for (unsigned i = 0; i <= nlabels; ++i) // { // accu::mean_<unsigned> m; // level::take(irm | (pw::value(lbl) == pw::cst(i)), m); -// g.add_node(m.to_result()); +// g.add_vertex(m.to_result()); // } // // Edges. // for (unsigned l1 = 1; l1 <= nlabels; ++l1) @@ -176,11 +186,16 @@ // if (adja[l1][l2]) // g.add_edge(l1, l2); // //g.print_debug (std::cout); -// for( int i = 0 ; i < g.nnodes() ; ++i) -// std::cout << "[" << i << " : " << g.node_data(i) << " ] "; +// for( int i = 0 ; i < g.nvertices() ; ++i) +// std::cout << "[" << i << " : " << g.vertex_data(i) << " ] "; // std::cout << std::endl; // } + + /*------------------------. + | Region adjacent graph. | + `------------------------*/ + /// Build a region adjacency graph. template <typename I, typename J, typename N> util::graph< accu::mean_<mln_value(J)> > @@ -190,19 +205,19 @@ for (unsigned l = 0; l <= nlabels; ++l) adja[l].resize(nlabels + 1, false); - mln_piter(I) p(lbl.domain()); + mln_piter(I) p(label.domain()); mln_niter(N) n(nbh, p); // We compute the adjacency matrix of the RAG. for_all(p) - if (lbl(p) == 0) // wshed + if (label(p) == 0) // wshed { std::set<unsigned> s; - for_all(n) if (lbl.has(n)) + for_all(n) if (label.has(n)) { - if (lbl(n) == 0) + if (label(n) == 0) continue; - s.insert(lbl(n)); + s.insert(label(n)); } if (s.size() < 2) { @@ -227,12 +242,12 @@ // Graph. util::graph< accu::mean_<mln_value(J)> > g; - // Nodes. + // Vertices. for (unsigned i = 0; i <= nlabels; ++i) { accu::mean_<mln_value(J)> m; - level::take(irm | (pw::value(lbl) == pw::cst(i)), m); - g.add_node(m); + level::take(input | (pw::value(label) == pw::cst(i)), m); + g.add_vertex(m); } // Edges. for (unsigned l1 = 1; l1 <= nlabels; ++l1) @@ -240,57 +255,210 @@ if (adja[l1][l2]) g.add_edge(l1, l2); //g.print_debug (std::cout); - for( int i = 0 ; i < g.nnodes() ; ++i) - std::cout << "[" << i << " : " << g.node_data(i) << " ] "; + for( unsigned i = 0 ; i < g.nvertices() ; ++i) + std::cout << "[" < - void mk2_graph(const I& lbl , const J& irm , const N& - nbh, int nbasins) +// template <typename I, typename J, typename N> +// void mk2_graph(const I& label , const J& input , const N& +// nbh, int nbasins) +// { +// typedef mln::p_set<mln_point(I)> R; +// std::map<int, R > regions; + +// mln_piter(I) p(label.domain()); +// for_all(p) +// { +// if (unsigned int i = label(p)) +// regions[i].insert(p); +// } + +// std::cout << "Boite englobante de la r�gion 10 : " << regions[10].bbox() << std::endl; + +// /* +// for (unsigned i = 0 ; i<nbasins ; ++i) +// { + +// } +// for (unsigned i = 0 ; i<regions.size() ; ++i) +// g.add_vertex(regions[]); +// */ +// } + + + /*---------------. + | Fusion graph. | + `---------------*/ + + /// The data associated to the vertex of a fusion graph. + template <typename A> + struct region_data { - typedef mln::p_set<mln_point(I)> R; - std::map<int, R > regions; + // The subregions composing the region. + std::set<util::vertex_id> subregions; + // An accumulator. + A accumulator; + }; - mln_piter(I) p(lbl.domain()); - for_all(p) + + /// Build a fusion graph from a RAG. + template <typename A> + util::graph< region_data<A> > + make_fg(const util::graph<A>& rag) + { + typedef util::graph<A> region_adjacency_graph; + typedef util::graph< region_data<A> > fusion_graph; + + fusion_graph fg; + + // Vertices. + for (util::vertex_id i = 0; i < rag.nvertices(); ++i) + { + // The singleton subregion: { I }. + std::set<util::vertex_id> sr; + sr.insert(i); + // The accumulator. + A a = rag.vertex_data(i); + // The region data + region_data<A> data = { sr, a }; + + // Add the vertex at index I. + fg.add_vertex(data); + } + + // Edges. + for (typename region_adjacency_graph::edges_t::const_iterator e = + rag.edges().begin(); e != rag.edges().end(); ++e) + { + util::vertex_id v1 = (*e)->v1(); + util::vertex_id v2 = (*e)->v2(); + fg.add_edge(v1, v2); + } + + return fg; + } + + /// Merge regions of the fusion graph. + template <typename A, typename C> + util::graph< region_data<A> > + merge_fg(const util::graph< region_data<A> >& input, const C& criterion) + { + typedef util::graph< region_data<A> > fusion_graph; + + // A disjoint set of vertices represented as a forest of rooted + // trees (disjoint set forest). + std::vector<util::vertex_id> parent(input.nvertices()); + for (util::vertex_id i = 0; i < parent.size(); ++i) + // � make_set �. + parent[i] = i; + + // Parent. + for (typename fusion_graph::edges_t::const_iterator e = + input.edges().begin(); e != input.edges().end(); ++e) { - if (unsigned int i = lbl(p)) - regions[i].insert(p); + util::vertex_id v1 = (*e)->v1(); + util::vertex_id v2 = (*e)->v2(); + A accu1 = input.vertex_data(v1).accumulator; + A accu2 = input.vertex_data(v2).accumulator; + if (criterion(accu1.to_result(), accu2.to_result())) + // � union �. + parent[v1] = v2; } - std::cout << "Boite englobante de la région 10 : " << regions[10].bbox() << std::endl; + // Children. + typedef std::multimap<util::vertex_id, util::vertex_id> children_t; + children_t children; + for (typename util::vertex_id i = 0; i < parent.size(); ++i) + { + // � find �. + util::vertex_id r = i; + while (r != parent[r]) + r = parent[r]; + children.insert(std::make_pair(r, i)); + } + + /// Data associated to merged regions. + typedef std::map< util::vertex_id, region_data<A> > merged_region_data_t; + merged_region_data_t merged_region_data; + for (typename children_t::const_iterator i = children.begin(); + i != children.end(); ++i) + { + util::vertex_id root = i->first; + util::vertex_id child = i->second; + + region_data<A>& root_data = merged_region_data[root]; + const region_data<A>& child_data = input.vertex_data(child); + + root_data.subregions.insert(child_data.subregions.begin(), + child_data.subregions.end()); + root_data.accumulator.take(child_data.accumulator); + } - /* - for (unsigned i = 0 ; i<nbasins ; ++i) + // Fusion graph. + fusion_graph output; + std::map<util::vertex_id, util::vertex_id> old_to_new_root; + // Vertices. + for (typename merged_region_data_t::const_iterator i = + merged_region_data.begin(); i != merged_region_data.end(); ++i) + { + util::vertex_id v = output.add_vertex(i->second); + old_to_new_root[i->first] = v; + } + // Edges. + for (typename fusion_graph::edges_t::const_iterator e = + input.edges().begin(); e != input.edges().end(); ++e) { + // The root of the first vertex connected to E. + util::vertex_id r1 = (*e)->v1(); + while (r1 != parent[r1]) + r1 = parent[r1]; + // The root of the second vertex connected to E. + util::vertex_id r2 = (*e)->v2(); + while (r2 != parent[r2]) + r2 = parent[r2]; + if (r1 != r2) + { + // The regions represented by R1 and R2 are connected. + output.add_edge(old_to_new_root[r1], old_to_new_root[r2]); + } } - for (unsigned i = 0 ; i<regions.size() ; ++i) - g.add_node(regions[]); - */ + return output; } +} // end of namespace my_mln -} // end of namespace mln -template <typename A> -struct region_data +struct abs_diff_threshold { - // The subregions composing the region. - std::set<util::vertex_id> subregions; - // An accumulator. - A a; + abs_diff_threshold(int threshold) + : threshold_(threshold) + { + } + + template <typename T> + bool operator() (const T& a, const T& b) const + { + return std::abs(a - b) < threshold_; } +private: + int threshold_; +}; + + + int main() { using namespace mln; + using namespace my_mln; using value::int_u8; + using value::rgb8; image2d<int_u8> irm; - io::pgm::load(irm, "./+irm6.pgm"); + io::pgm::load(irm, "./irm6.pgm"); // io::pgm::save( morpho::gradient(irm, win::rectangle2d(3,3)), // "tmp_grad_3x3.pgm" ); @@ -316,22 +484,53 @@ //typedef fusion_graph<unsigned int, void> _fg; //_fg fg(wshed , irm , c8() , nbasins); -// fusion_graph fg(lbl&, irm&, c4(), nbasins); -// std::cout << "nnodes = " << fg.nnodes() << std::endl +// fusion_graph fg(label&, irm&, c4(), nbasins); +// std::cout << "nvertices = " << fg.nvertices() << std::endl // << "nregions = " << fg.nn() << std::endl; - // Region adjacency graph. - util::graph< accu::mean_<int_u8> > rag = make_rag(wshed, irm, c4(), nbasins); - - // Fusion graph. - - typedef util::graph< region_data< accu::mean<int_u8> > fusion_graph; - - fusion_graph output; + // Region adjacency graph (RAG). + typedef util::graph< accu::mean_<int_u8> > region_adjacency_graph; + region_adjacency_graph rag = make_rag(wshed, irm, c4(), nbasins); + + // Fusion graph (FG). + typedef util::graph< region_data< accu::mean_<int_u8> > > fusion_graph; + fusion_graph fg = make_fg(rag); fusion_graph work; do - work = output; - output = merge(work); - while (work.nvertices() != output.nvertices()); - + { + work = fg; + fg = merge_fg (work, abs_diff_threshold(20)); + std::cerr << "work.nvertices() = " << work.nvertices() << std::endl; + std::cerr << "fg.nvertices() = " << fg.nvertices() << std::endl; + } + while (work.nvertices() != fg.nvertices()); + + // Compute the values (means) for the output image. + std::map<util::vertex_id, int_u8> region_value; + for (util::vertex_id v = 0; v < fg.nvertices(); ++v) + { + // FIXME: Implicit cast. We should rather change the type of + // the accumulator instead. + int_u8 mean = fg.vertex_data(v).accumulator.to_result(); + for (std::set<util::vertex_id>::const_iterator sr = + fg.vertex_data(v).subregions.begin(); + sr != fg.vertex_data(v).subregions.end(); + ++sr) + region_value[*sr] = mean; + } + + // Output. + image2d<rgb8> output(wshed.domain()); + mln_piter_(image2d<rgb8>) p(output.domain()); + for_all (p) + { + if (wshed(p) == 0) + output(p) = literal::red; + else + { + int_u8 mean = region_value[wshed(p)]; + output(p) = rgb8(mean, mean, mean); + } + } + io::ppm::save(output, "out.ppm"); }

1 0

1993: Rename graphs' � nodes � as � vertices �.
by Roland Levillain 03 Jun '08

03 Jun '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Roland Levillain <roland(a)lrde.epita.fr> Rename graphs' � nodes � as � vertices �. * mln/util/graph.hh, * mln/util/internal/graph_base.hh, * mln/accu/count_adjacent_vertices.hh, * mln/core/graph_elt_neighborhood.hh, * mln/core/graph_elt_window.hh, * mln/core/graph_image.hh, * mln/core/graph_psite.hh, * mln/core/internal/graph_vicinity_piter.hh, * mln/core/line_graph_elt_neighborhood.hh, * mln/core/line_graph_elt_window.hh, * mln/core/line_graph_image.hh, * mln/core/line_graph_psite.hh, * mln/core/p_graph.hh, * mln/core/p_graph_piter.hh, * mln/core/p_line_graph.hh, * mln/draw/graph.hh, * mln/morpho/line_gradient.hh, * tests/core/graph_elt_neighborhood.cc, * tests/core/graph_elt_window.cc, * tests/core/graph_image.cc, * tests/core/line_graph_elt_neighborhood.cc, * tests/core/line_graph_elt_window.cc, * tests/core/line_graph_image.cc, * tests/core/line_graph_image_wst.cc, * tests/core/point_set_compatibility.cc, * tests/morpho/artificial_line_graph_image_wst.cc, * tests/morpho/lena_line_graph_image_wst1.cc, * tests/morpho/lena_line_graph_image_wst2.cc: s/nodes/vertices/. s/node/vertex/. s/link/edge/. mln/accu/count_adjacent_vertices.hh | 2 mln/core/graph_elt_neighborhood.hh | 27 +- mln/core/graph_elt_window.hh | 34 +-- mln/core/graph_image.hh | 26 +- mln/core/graph_psite.hh | 14 - mln/core/internal/graph_vicinity_piter.hh | 8 mln/core/line_graph_elt_neighborhood.hh | 16 - mln/core/line_graph_elt_window.hh | 18 - mln/core/line_graph_image.hh | 60 ++--- mln/core/line_graph_psite.hh | 20 - mln/core/p_graph.hh | 72 +++--- mln/core/p_graph_piter.hh | 10 mln/core/p_line_graph.hh | 20 - mln/draw/graph.hh | 46 ++-- mln/morpho/line_gradient.hh | 14 - mln/util/graph.hh | 210 +++++++++---------- mln/util/internal/graph_base.hh | 258 +++++++++++------------- tests/core/graph_elt_neighborhood.cc | 16 - tests/core/graph_elt_window.cc | 16 - tests/core/graph_image.cc | 20 - tests/core/line_graph_elt_neighborhood.cc | 16 - tests/core/line_graph_elt_window.cc | 16 - tests/core/line_graph_image.cc | 24 +- tests/core/line_graph_image_wst.cc | 30 +- tests/core/point_set_compatibility.cc | 16 - tests/morpho/artificial_line_graph_image_wst.cc | 4 tests/morpho/lena_line_graph_image_wst1.cc | 22 +- tests/morpho/lena_line_graph_image_wst2.cc | 4 28 files changed, 519 insertions(+), 520 deletions(-) Index: tests/core/graph_elt_neighborhood.cc --- tests/core/graph_elt_neighborhood.cc (revision 1992) +++ tests/core/graph_elt_neighborhood.cc (working copy) @@ -62,19 +62,19 @@ */ - // Points associated to nodes. + // Points associated to vertices. std::vector<p_t> points; - points.push_back(make::point2d(0,0)); // Point associated to node 0. - points.push_back(make::point2d(2,2)); // Point associated to node 1. - points.push_back(make::point2d(0,4)); // Point associated to node 2. - points.push_back(make::point2d(4,3)); // Point associated to node 3. - points.push_back(make::point2d(4,4)); // Point associated to node 4. + points.push_back(make::point2d(0,0)); // Point associated to vertex 0. + points.push_back(make::point2d(2,2)); // Point associated to vertex 1. + points.push_back(make::point2d(0,4)); // Point associated to vertex 2. + points.push_back(make::point2d(4,3)); // Point associated to vertex 3. + points.push_back(make::point2d(4,4)); // Point associated to vertex 4. // Edges. mln::util::graph<p_t> g; - // Populate the graph with nodes. + // Populate the graph with vertices. for (unsigned i = 0; i < points.size(); ++i) - g.add_node (points[i]); + g.add_vertex (points[i]); // Populate the graph with edges. g.add_edge(0, 1); g.add_edge(1, 2); Index: tests/core/point_set_compatibility.cc --- tests/core/point_set_compatibility.cc (revision 1992) +++ tests/core/point_set_compatibility.cc (working copy) @@ -47,19 +47,19 @@ // Graph. - // Points associated to nodes. + // Points associated to vertices. std::vector<point2d> points; - points.push_back(make::point2d(0,0)); // Point associated to node 0. - points.push_back(make::point2d(2,2)); // Point associated to node 1. - points.push_back(make::point2d(0,4)); // Point associated to node 2. - points.push_back(make::point2d(4,3)); // Point associated to node 3. - points.push_back(make::point2d(4,4)); // Point associated to node 4. + points.push_back(make::point2d(0,0)); // Point associated to vertex 0. + points.push_back(make::point2d(2,2)); // Point associated to vertex 1. + points.push_back(make::point2d(0,4)); // Point associated to vertex 2. + points.push_back(make::point2d(4,3)); // Point associated to vertex 3. + points.push_back(make::point2d(4,4)); // Point associated to vertex 4. // Edges. util::graph<point2d> g; - // Populate the graph with nodes. + // Populate the graph with vertices. for (unsigned i = 0; i < points.size(); ++i) - g.add_node (points[i]); + g.add_vertex (points[i]); // Populate the graph with edges. g.add_edge(0, 1); g.add_edge(1, 2); Index: tests/core/graph_image.cc --- tests/core/graph_image.cc (revision 1992) +++ tests/core/graph_image.cc (working copy) @@ -63,19 +63,19 @@ */ - // Points associated to nodes. + // Points associated to vertices. std::vector<point2d> points; - points.push_back(make::point2d(0,0)); // Point associated to node 0. - points.push_back(make::point2d(2,2)); // Point associated to node 1. - points.push_back(make::point2d(0,4)); // Point associated to node 2. - points.push_back(make::point2d(4,3)); // Point associated to node 3. - points.push_back(make::point2d(4,4)); // Point associated to node 4. + points.push_back(make::point2d(0,0)); // Point associated to vertex 0. + points.push_back(make::point2d(2,2)); // Point associated to vertex 1. + points.push_back(make::point2d(0,4)); // Point associated to vertex 2. + points.push_back(make::point2d(4,3)); // Point associated to vertex 3. + points.push_back(make::point2d(4,4)); // Point associated to vertex 4. // Edges. util::graph<point2d> g; - // Populate the graph with nodes. + // Populate the graph with vertices. for (unsigned i = 0; i < points.size(); ++i) - g.add_node (points[i]); + g.add_vertex (points[i]); // Populate the graph with edges. g.add_edge(0, 1); g.add_edge(1, 2); @@ -122,14 +122,14 @@ itslef. An alternative is to use draw::graph (which, again, is misnamed), - but it doesn't show the values, only the nodes and edges of the + but it doesn't show the values, only the vertices and edges of the graph. The current solution is a mix between draw::graph and hand-made iterations. */ image2d<int> ima_rep(ima.bbox()); // We use the value 9 in draw::graph instead of the default (which is - // 1) to represent edges to distinguish it from nodes holding a + // 1) to represent edges to distinguish it from vertices holding a // value of 1. draw::graph (ima_rep, ima, 9); debug::println (ima_rep); Index: tests/core/graph_elt_window.cc --- tests/core/graph_elt_window.cc (revision 1992) +++ tests/core/graph_elt_window.cc (working copy) @@ -62,19 +62,19 @@ */ - // Points associated to nodes. + // Points associated to vertices. std::vector<p_t> points; - points.push_back(make::point2d(0,0)); // Point associated to node 0. - points.push_back(make::point2d(2,2)); // Point associated to node 1. - points.push_back(make::point2d(0,4)); // Point associated to node 2. - points.push_back(make::point2d(4,3)); // Point associated to node 3. - points.push_back(make::point2d(4,4)); // Point associated to node 4. + points.push_back(make::point2d(0,0)); // Point associated to vertex 0. + points.push_back(make::point2d(2,2)); // Point associated to vertex 1. + points.push_back(make::point2d(0,4)); // Point associated to vertex 2. + points.push_back(make::point2d(4,3)); // Point associated to vertex 3. + points.push_back(make::point2d(4,4)); // Point associated to vertex 4. // Edges. mln::util::graph<p_t> g; - // Populate the graph with nodes. + // Populate the graph with vertices. for (unsigned i = 0; i < points.size(); ++i) - g.add_node (points[i]); + g.add_vertex (points[i]); // Populate the graph with edges. g.add_edge(0, 1); g.add_edge(1, 2); Index: tests/core/line_graph_image_wst.cc --- tests/core/line_graph_image_wst.cc (revision 1992) +++ tests/core/line_graph_image_wst.cc (working copy) @@ -50,7 +50,7 @@ | Line graph. | `-------------*/ - /* Actually this graph is from Jean Cousty's PhD dissertation, page 76. + /* Actually this graph is from Jean Cousty's PhD thesis, page 76. 0 1 2 3 (rows) ,------------------------ @@ -63,23 +63,23 @@ 3 5 2 (cols) - In G, nodes and egdes are numbered following in the classical + In G, vertices and egdes are numbered following in the classical foward order. */ util::graph<point2d> g; - // Nodes. - std::vector<int> node_values; - // We don't really care about values on nodes, because the algorithm + // Vertices. + std::vector<int> vertex_values; + // We don't really care about values on vertices, because the algorithm // won't see them. So all are set to 0. - g.add_node (make::point2d(0, 0)); node_values.push_back (0); // Node 0. - g.add_node (make::point2d(0, 1)); node_values.push_back (0); // Node 1. - g.add_node (make::point2d(0, 2)); node_values.push_back (0); // Node 2. - g.add_node (make::point2d(0, 3)); node_values.push_back (0); // Node 3. - - g.add_node (make::point2d(1, 0)); node_values.push_back (0); // Node 4. - g.add_node (make::point2d(1, 1)); node_values.push_back (0); // Node 5. - g.add_node (make::point2d(1, 2)); node_values.push_back (0); // Node 6. - g.add_node (make::point2d(1, 3)); node_values.push_back (0); // Node 7. + g.add_vertex (make::point2d(0, 0)); vertex_values.push_back (0); // Vertex 0. + g.add_vertex (make::point2d(0, 1)); vertex_values.push_back (0); // Vertex 1. + g.add_vertex (make::point2d(0, 2)); vertex_values.push_back (0); // Vertex 2. + g.add_vertex (make::point2d(0, 3)); vertex_values.push_back (0); // Vertex 3. + + g.add_vertex (make::point2d(1, 0)); vertex_values.push_back (0); // Vertex 4. + g.add_vertex (make::point2d(1, 1)); vertex_values.push_back (0); // Vertex 5. + g.add_vertex (make::point2d(1, 2)); vertex_values.push_back (0); // Vertex 6. + g.add_vertex (make::point2d(1, 3)); vertex_values.push_back (0); // Vertex 7. // Edges. std::vector<int> edge_values; @@ -103,7 +103,7 @@ /* FIXME: We probably don't want to build line_graph_images by hand; provide helpers and/or conversion functions. */ typedef line_graph_image<point2d, int> ima_t; - ima_t ima(plg, node_values, edge_values); + ima_t ima(plg, vertex_values, edge_values); /*------------. | Iterators. | Index: tests/core/line_graph_elt_window.cc --- tests/core/line_graph_elt_window.cc (revision 1992) +++ tests/core/line_graph_elt_window.cc (working copy) @@ -60,19 +60,19 @@ */ - // Points associated to nodes. + // Points associated to vertices. std::vector<p_t> points; - points.push_back(make::point2d(0,0)); // Point associated to node 0. - points.push_back(make::point2d(2,2)); // Point associated to node 1. - points.push_back(make::point2d(0,4)); // Point associated to node 2. - points.push_back(make::point2d(4,3)); // Point associated to node 3. - points.push_back(make::point2d(4,4)); // Point associated to node 4. + points.push_back(make::point2d(0,0)); // Point associated to vertex 0. + points.push_back(make::point2d(2,2)); // Point associated to vertex 1. + points.push_back(make::point2d(0,4)); // Point associated to vertex 2. + points.push_back(make::point2d(4,3)); // Point associated to vertex 3. + points.push_back(make::point2d(4,4)); // Point associated to vertex 4. // Edges. mln::util::graph<p_t> g; - // Populate the graph with nodes. + // Populate the graph with vertices. for (unsigned i = 0; i < points.size(); ++i) - g.add_node (points[i]); + g.add_vertex (points[i]); // Populate the graph with edges. g.add_edge(0, 1); g.add_edge(1, 2); Index: tests/core/line_graph_elt_neighborhood.cc --- tests/core/line_graph_elt_neighborhood.cc (revision 1992) +++ tests/core/line_graph_elt_neighborhood.cc (working copy) @@ -60,19 +60,19 @@ */ - // Points associated to nodes. + // Points associated to vertices. std::vector<p_t> points; - points.push_back(make::point2d(0,0)); // Point associated to node 0. - points.push_back(make::point2d(2,2)); // Point associated to node 1. - points.push_back(make::point2d(0,4)); // Point associated to node 2. - points.push_back(make::point2d(4,3)); // Point associated to node 3. - points.push_back(make::point2d(4,4)); // Point associated to node 4. + points.push_back(make::point2d(0,0)); // Point associated to vertex 0. + points.push_back(make::point2d(2,2)); // Point associated to vertex 1. + points.push_back(make::point2d(0,4)); // Point associated to vertex 2. + points.push_back(make::point2d(4,3)); // Point associated to vertex 3. + points.push_back(make::point2d(4,4)); // Point associated to vertex 4. // Edges. mln::util::graph<p_t> g; - // Populate the graph with nodes. + // Populate the graph with vertices. for (unsigned i = 0; i < points.size(); ++i) - g.add_node (points[i]); + g.add_vertex (points[i]); // Populate the graph with edges. g.add_edge(0, 1); g.add_edge(1, 2); Index: tests/core/line_graph_image.cc --- tests/core/line_graph_image.cc (revision 1992) +++ tests/core/line_graph_image.cc (working copy) @@ -63,19 +63,19 @@ */ - // Points associated to nodes. + // Points associated to vertices. std::vector<point2d> points; - points.push_back(make::point2d(0,0)); // Point associated to node 0. - points.push_back(make::point2d(2,2)); // Point associated to node 1. - points.push_back(make::point2d(0,4)); // Point associated to node 2. - points.push_back(make::point2d(4,3)); // Point associated to node 3. - points.push_back(make::point2d(4,4)); // Point associated to node 4. + points.push_back(make::point2d(0,0)); // Point associated to vertex 0. + points.push_back(make::point2d(2,2)); // Point associated to vertex 1. + points.push_back(make::point2d(0,4)); // Point associated to vertex 2. + points.push_back(make::point2d(4,3)); // Point associated to vertex 3. + points.push_back(make::point2d(4,4)); // Point associated to vertex 4. // Edges. util::graph<point2d> g; - // Populate the graph with nodes. + // Populate the graph with vertices. for (unsigned i = 0; i < points.size(); ++i) - g.add_node (points[i]); + g.add_vertex (points[i]); // Populate the graph with edges. g.add_edge(0, 1); g.add_edge(1, 2); @@ -101,11 +101,11 @@ `-------------------*/ // Values ("empty" vectors). - std::vector<int> node_values(5); + std::vector<int> vertex_values(5); std::vector<int> edge_values(5); // FIXME: hand-made iota's. - for (unsigned i = 0; i < node_values.size(); ++i) - node_values[i] = i; + for (unsigned i = 0; i < vertex_values.size(); ++i) + vertex_values[i] = i; for (unsigned i = 0; i < edge_values.size(); ++i) edge_values[i] = i; @@ -113,7 +113,7 @@ /* FIXME: We probably don't want to build line_graph_images by hand; provide helpers and/or conversion functions. */ typedef line_graph_image<point2d, int> ima_t; - ima_t ima(plg, node_values, edge_values); + ima_t ima(plg, vertex_values, edge_values); /*------------. | Iterators. | Index: tests/morpho/artificial_line_graph_image_wst.cc --- tests/morpho/artificial_line_graph_image_wst.cc (revision 1992) +++ tests/morpho/artificial_line_graph_image_wst.cc (working copy) @@ -38,7 +38,7 @@ \li create an artificial (checkboard) 2-D image ; \li convert this 2-D image into a line graph-based one, where values on edges are computed as the absolute value of the difference - between the values on the nodes adjacent to the edge, so as to + between the values on the vertices adjacent to the edge, so as to create a (norm of the) gradient ``between the pixels'' of the input image; \li perform a WST on this line graph image; @@ -198,7 +198,7 @@ We should probably solve this when we ``paint'' the watershed over the ``doubled'' image. - A better approach is probably to iterate over the set of nodes, + A better approach is probably to iterate over the set of vertices, and ``connect'' edges according to patterns (vertically or horizontally connected egdes member of the watershed, etc.). */ // Reuse the piter on OUTPUT. Index: tests/morpho/lena_line_graph_image_wst1.cc --- tests/morpho/lena_line_graph_image_wst1.cc (revision 1992) +++ tests/morpho/lena_line_graph_image_wst1.cc (working copy) @@ -38,7 +38,7 @@ \li compute a morphological gradient of this image; \li simplify the image to reduce the number of local minima; \li convert this 2-D image into a line graph-based one, where values - on edges are computed as the maxmimum of the values on the nodes + on edges are computed as the maxmimum of the values on the vertices adjacent to the edge; \li perform a WST on the line graph image; \li create an 2-D, color output image with height and width double @@ -110,20 +110,20 @@ // Points. /* FIXME: The need for such a structure during the conversion exhibits the lack of a service from util::graph (or a another, - missing tool) regarding the retrieval of node ids from + missing tool) regarding the retrieval of vertex ids from points. */ - std::map<point2d, util::node_id> points; - util::node_id id = 0; + std::map<point2d, util::vertex_id> points; + util::vertex_id id = 0; - // Nodes. - std::vector<int> node_values; + // Vertices. + std::vector<int> vertex_values; mln_fwd_piter_(image2d<input_val_t>) p(work.domain()); for_all (p) { - g.add_node (p); - node_values.push_back (work(p)); + g.add_vertex (p); + vertex_values.push_back (work(p)); /* FIXME: ``Guessing'' the id of the point just being inserted - is bad. util:graph<N,E>::add_node should return this + is bad. util:graph<N,E>::add_vertex should return this id. */ points[p] = id; ++id; @@ -149,7 +149,7 @@ /* FIXME: Shouldn't we use `input_val_t' instead of plain `int' as value type here? */ typedef line_graph_image<point2d, int> ima_t; - ima_t lg_ima(plg, node_values, edge_values); + ima_t lg_ima(plg, vertex_values, edge_values); /*------. | WST. | @@ -234,7 +234,7 @@ We should probably solve this when we ``paint'' the watershed over the ``doubled'' image. - A better approach is probably to iterate over the set of nodes, + A better approach is probably to iterate over the set of vertices, and ``connect'' edges according to patterns (vertically or horizontally connected egdes member of the watershed, etc.). */ // Reuse the piter on OUTPUT. Index: tests/morpho/lena_line_graph_image_wst2.cc --- tests/morpho/lena_line_graph_image_wst2.cc (revision 1992) +++ tests/morpho/lena_line_graph_image_wst2.cc (working copy) @@ -38,7 +38,7 @@ \li load a 2-D, gray-level image from a PGM file; \li convert this 2-D image into a line graph-based one, where values on edges are computed as the absolute value of the difference - between the values on the nodes adjacent to the edge, so as to + between the values on the vertices adjacent to the edge, so as to create a (norm of the) gradient ``between the pixels'' of the input image; \li reduce the number of minima using an area opening (counting the @@ -194,7 +194,7 @@ We should probably solve this when we ``paint'' the watershed over the ``doubled'' image. - A better approach is probably to iterate over the set of nodes, + A better approach is probably to iterate over the set of vertices, and ``connect'' edges according to patterns (vertically or horizontally connected egdes member of the watershed, etc.). */ // Reuse the piter on OUTPUT. Index: mln/core/line_graph_elt_neighborhood.hh --- mln/core/line_graph_elt_neighborhood.hh (revision 1992) +++ mln/core/line_graph_elt_neighborhood.hh (working copy) @@ -116,20 +116,20 @@ /* FIXME: Move this computation out of the neighborhood. In fact, this should be a service of the graph, also proposed by the p_line_graph. */ - // Ajacent edges connected through node 1. - util::node_id id1 = piter.p_ref().first_id(); - const util::node& node1 = piter.plg().gr_->node(id1); + // Ajacent edges connected through vertex 1. + util::vertex_id id1 = piter.p_ref().first_id(); + const util::vertex& vertex1 = piter.plg().gr_->vertex(id1); for (std::vector<util::edge_id>::const_iterator e = - node1.edges.begin(); e != node1.edges.end(); ++e) + vertex1.edges.begin(); e != vertex1.edges.end(); ++e) // We explicitly enforce that the reference piter edge id is // *not* inserted into SITES. if (*e != ref_edge_id) sites.insert(*e); - // Ajacent edges connected through node 2. - util::node_id id2 = piter.p_ref().second_id(); - const util::node& node2 = piter.plg().gr_->node(id2); + // Ajacent edges connected through vertex 2. + util::vertex_id id2 = piter.p_ref().second_id(); + const util::vertex& vertex2 = piter.plg().gr_->vertex(id2); for (std::vector<util::edge_id>::const_iterator e = - node2.edges.begin(); e != node2.edges.end(); ++e) + vertex2.edges.begin(); e != vertex2.edges.end(); ++e) // Same remark as above. if (*e != ref_edge_id) sites.insert(*e); Index: mln/core/line_graph_image.hh --- mln/core/line_graph_image.hh (revision 1992) +++ mln/core/line_graph_image.hh (working copy) @@ -44,14 +44,14 @@ possible. */ /* FIXME: This is only a very naive prototype. For instance, this - image associates values to both the nodes and the edges of the + image associates values to both the vertices and the edges of the graph, but only values on edges are accessible. We probably want to fork this class to have a pure image of line graph (with no data - on nodes) and one having data on both nodes and edges. + on vertices) and one having data on both vertices and edges. Moreover, in the current implementation, the type of values on - nodes and edges is necessarily the same (V). We should allow - different data types for nodes and edges. */ + vertices and edges is necessarily the same (V). We should allow + different data types for vertices and edges. */ namespace mln @@ -68,9 +68,9 @@ struct data_< line_graph_image<P, V> > { data_(const p_line_graph& g, - const std::vector<V>& node_val, const std::vector<V>& edge_val); + const std::vector<V>& vertex_val, const std::vector<V>& edge_val); - std::vector<V> node_val_; + std::vector<V> vertex_val_; std::vector<V> edge_val_; const p_line_graph plg_; }; @@ -139,13 +139,13 @@ line_graph_image(); line_graph_image(const p_line_graph& g); line_graph_image(const p_line_graph& g, - const std::vector<V>& node_val, + const std::vector<V>& vertex_val, const std::vector<V>& edge_val); /// \} /// Initialize an empty image. void init_(const p_line_graph& g, - const std::vector<V>& node_val, + const std::vector<V>& vertex_val, const std::vector<V>& edge_val); /// Read-only access of pixel value at point site \p p. @@ -163,19 +163,19 @@ /// Return the array of values associated to the edges. const std::vector<V>& edge_values() const; - /// Return the array of values associated to the nodes. - const std::vector<V>& node_values() const; + /// Return the array of values associated to the vertices. + const std::vector<V>& vertex_values() const; /// \} /* FIXME: Do we want to provide these two methods? (at least, in the interface of the class? */ - /// Return the point of the first node adjacent to the edge with + /// Return the point of the first vertex adjacent to the edge with /// id \a e. - const P& node1(const util::edge_id& e) const; - /// Return the point of the second node adjacent to the edge with + const P& vertex1(const util::edge_id& e) const; + /// Return the point of the second vertex adjacent to the edge with /// id \a e. - const P& node2(const util::edge_id& e) const; + const P& vertex2(const util::edge_id& e) const; }; // Fwd decl. @@ -198,7 +198,7 @@ const line_graph_image<P, W>& model) { target.init_(model.domain(), - std::vector<V>(model.node_values().size()), + std::vector<V>(model.vertex_values().size()), std::vector<V>(model.edge_values().size())); } @@ -211,9 +211,9 @@ template <typename P, typename V> inline data_< line_graph_image<P, V> >::data_(const p_line_graph& g, - const std::vector<V>& node_val, + const std::vector<V>& vertex_val, const std::vector<V>& edge_val) - : node_val_(node_val), + : vertex_val_(vertex_val), edge_val_(edge_val), plg_(g) { @@ -235,28 +235,28 @@ inline line_graph_image<P, V>::line_graph_image(const p_line_graph& g) { - init_(g, std::vector<V>(g.nnodes()), std::vector<V>(g.nedges())); + init_(g, std::vector<V>(g.nvertices()), std::vector<V>(g.nedges())); } template <typename P, typename V> inline line_graph_image<P, V>::line_graph_image(const p_line_graph& g, - const std::vector<V>& node_val, + const std::vector<V>& vertex_val, const std::vector<V>& edge_val) { - init_(g, node_val, edge_val); + init_(g, vertex_val, edge_val); } template <typename P, typename V> inline void line_graph_image<P, V>::init_(const p_line_graph& g, - const std::vector<V>& node_val, + const std::vector<V>& vertex_val, const std::vector<V>& edge_val) { mln_precondition(! this->has_data()); this->data_ = - new internal::data_< line_graph_image<P, V> >(g, node_val, edge_val); + new internal::data_< line_graph_image<P, V> >(g, vertex_val, edge_val); } /*---------------. @@ -302,9 +302,9 @@ template <typename P, typename V> inline const std::vector<V>& - line_graph_image<P, V>::node_values() const + line_graph_image<P, V>::vertex_values() const { - return this->data_->node_val_; + return this->data_->vertex_val_; } template <typename P, typename V> @@ -319,23 +319,23 @@ template <typename P, typename V> inline const P& - line_graph_image<P, V>::node1(const util::edge_id& e) const + line_graph_image<P, V>::vertex1(const util::edge_id& e) const { // FIXME: Improve the interface of graph to avoid these low-level // manipulations. - util::node_id n1 = this->domain().gr_.edge(e).n1(); - return this->domain().gr_.node_data(n1); + util::vertex_id v1 = this->domain().gr_.edge(e).v1(); + return this->domain().gr_.vertex_data(v1); } template <typename P, typename V> inline const P& - line_graph_image<P, V>::node2(const util::edge_id& e) const + line_graph_image<P, V>::vertex2(const util::edge_id& e) const { // FIXME: Improve the interface of graph to avoid these low-level // manipulations. - util::node_id n2 = this->domain().gr_.edge(e).n2(); - return this->domain().gr_.node_data(n2); + util::vertex_id v2 = this->domain().gr_.edge(e).v2(); + return this->domain().gr_.vertex_data(v2); } # endif // ! MLN_INCLUDE_ONLY Index: mln/core/internal/graph_vicinity_piter.hh --- mln/core/internal/graph_vicinity_piter.hh (revision 1992) +++ mln/core/internal/graph_vicinity_piter.hh (working copy) @@ -78,7 +78,7 @@ typedef void mesh; // The type of the set of vicinity sites (adjacent vertex ids). - typedef std::set<util::node_id> sites_t; + typedef std::set<util::vertex_id> sites_t; public: /// Conversion and accessors. @@ -111,8 +111,8 @@ /// Internals, used by the vicinity. /// \{ public: - /// An internal iterator on the set of nodes of the underlying graph. - util::node_id id_; + /// An internal iterator on the set of vertices of the underlying graph. + util::vertex_id id_; /// \} protected: @@ -198,7 +198,7 @@ template <typename P, typename E> inline - std::set<util::node_id>& + std::set<util::vertex_id>& graph_vicinity_piter_<P, E>::sites() { return sites_; Index: mln/core/graph_image.hh --- mln/core/graph_image.hh (revision 1992) +++ mln/core/graph_image.hh (working copy) @@ -139,19 +139,19 @@ /// Return the domain of values of the image. const vset& values() const; - /// Return the array of values associated to the nodes. - const std::vector<V>& node_values() const; + /// Return the array of values associated to the vertices. + const std::vector<V>& vertex_values() const; /// \} /* FIXME: Do we want to provide these two methods? (at least, in the interface of the class? */ - /// Return the point of the first node adjacent to the edge with + /// Return the point of the first vertex adjacent to the edge with /// id \a e. - const P& node1(const util::edge_id& e) const; - /// Return the point of the second node adjacent to the edge with + const P& vertex1(const util::edge_id& e) const; + /// Return the point of the second vertex adjacent to the edge with /// id \a e. - const P& node2(const util::edge_id& e) const; + const P& vertex2(const util::edge_id& e) const; }; // Fwd decl. @@ -172,7 +172,7 @@ graph_image<P, V>& target, const graph_image<P, W>& model) { target.init_(model.domain(), - std::vector<V>(model.node_values().size())); + std::vector<V>(model.vertex_values().size())); } /*-------. @@ -206,7 +206,7 @@ inline graph_image<P, V>::graph_image(const p_graph& g) { - init_(g, std::vector<V>(g.nnodes())); + init_(g, std::vector<V>(g.nvertices())); } template <typename P, typename V> @@ -260,7 +260,7 @@ template <typename P, typename V> inline const std::vector<V>& - graph_image<P, V>::node_values() const + graph_image<P, V>::vertex_values() const { return this->data_->val_; } @@ -277,17 +277,17 @@ template <typename P, typename V> inline const P& - graph_image<P, V>::node1(const util::edge_id& e) const + graph_image<P, V>::vertex1(const util::edge_id& e) const { - return this->domain().node1(e); + return this->domain().vertex1(e); } template <typename P, typename V> inline const P& - graph_image<P, V>::node2(const util::edge_id& e) const + graph_image<P, V>::vertex2(const util::edge_id& e) const { - return this->domain().node2(e); + return this->domain().vertex2(e); } # endif // ! MLN_INCLUDE_ONLY Index: mln/core/line_graph_psite.hh --- mln/core/line_graph_psite.hh (revision 1992) +++ mln/core/line_graph_psite.hh (working copy) @@ -86,9 +86,9 @@ P second() const; /// Return the id of the first associated vertex. - util::node_id first_id() const; + util::vertex_id first_id() const; /// Return the id of the second associated vertex. - util::node_id second_id() const; + util::vertex_id second_id() const; /// Is this psite valid? bool is_valid() const; @@ -103,7 +103,7 @@ Contrary to mln::graph_psite, this information is actually stored in the mln::line_graph_psite. In mln::graph_psite, the point is retrieved from the data associated with the - corresponding node in the graph. We cannot do this here, + corresponding vertex in the graph. We cannot do this here, since points associated to edges are computed on the fly (storing them in the graph could be possible, but too costly in space). */ @@ -224,7 +224,7 @@ template<typename P> inline - util::node_id + util::vertex_id line_graph_psite::id() const { return id_; @@ -236,7 +236,7 @@ line_graph_psite::first() const { mln_assertion(is_valid()); - return plg().gr_->node_data(first_id()); + return plg().gr_->vertex_data(first_id()); } template<typename P> @@ -245,26 +245,26 @@ line_graph_psite::second() const { mln_assertion(is_valid()); - return plg().gr_->node_data(second_id()); + return plg().gr_->vertex_data(second_id()); } template<typename P> inline - util::node_id + util::vertex_id line_graph_psite::first_id() const { mln_assertion(is_valid()); - return plg().gr_->edge(id_).n1(); + return plg().gr_->edge(id_).v1(); } template<typename P> inline - util::node_id + util::vertex_id line_graph_psite::second_id() const { mln_assertion(is_valid()); - return plg().gr_->edge(id_).n2(); + return plg().gr_->edge(id_).v2(); } Index: mln/core/p_graph_piter.hh --- mln/core/p_graph_piter.hh (revision 1992) +++ mln/core/p_graph_piter.hh (working copy) @@ -100,7 +100,7 @@ private: /// The p_graph this point site belongs to. const p_graph* pg_; - /// The id of the node this psite is pointing towards. + /// The id of the vertex this psite is pointing towards. unsigned id_; /// The psite corresponding to this iterator. psite psite_; @@ -176,7 +176,7 @@ private: /// The p_graph this point site belongs to. const p_graph* pg_; - /// The id of the node this psite is pointing towards. + /// The id of the vertex this psite is pointing towards. unsigned id_; /// The psite corresponding to this iterator. psite psite_; @@ -249,7 +249,7 @@ bool p_graph_fwd_piter_::is_valid() const { - return pg_ && id_ < pg_->nnodes(); + return pg_ && id_ < pg_->nvertices(); } template<typename P> @@ -401,7 +401,7 @@ bool p_graph_bkd_piter_::is_valid() const { - return pg_ && id_ < pg_->nnodes(); + return pg_ && id_ < pg_->nvertices(); } template<typename P> @@ -417,7 +417,7 @@ void p_graph_bkd_piter_::start() { - id_ = pg_->nnodes() - 1; + id_ = pg_->nvertices() - 1; if (is_valid()) update_(); } Index: mln/core/graph_elt_window.hh --- mln/core/graph_elt_window.hh (revision 1992) +++ mln/core/graph_elt_window.hh (working copy) @@ -69,9 +69,9 @@ typedef P point; /// The type of psite corresponding to the window. typedef graph_psite psite; - // The type of the set of window sites (node ids adjacent to the + // The type of the set of window sites (vertex ids adjacent to the // reference psite). - typedef std::set<util::node_id> sites_t; + typedef std::set<util::vertex_id> sites_t; // FIXME: This is a dummy value. typedef void dpoint; @@ -109,7 +109,7 @@ /* FIXME: This method returns a dummy value (0), since the delta of a window on a graph - 1. is not constant (graph nodes are not necessarily aligned on + 1. is not constant (graph vertices are not necessarily aligned on a regular grid); 2. depends on the underlying graph, too. @@ -132,25 +132,27 @@ graph_elt_window::compute_sites_(Point_Iterator<Piter>& piter_) const { Piter& piter = exact(piter_); - util::node_id ref_node_id = piter.p_ref().id(); - const util::node& ref_node = piter.pg().gr_->node(ref_node_id); + util::vertex_id ref_vertex_id = piter.p_ref().id(); + const util::vertex& ref_vertex = piter.pg().gr_->vertex(ref_vertex_id); sites_t& sites = piter.sites(); sites.clear(); /* FIXME: Move this computation out of the window. In fact, this should be a service of the graph, also proposed by the p_line_graph. */ - // Adjacent vertices. - /* We don't need to explicitely insert the reference piter (node - id) itself into SITES, since it is part of the set of nodes - adjacent to NODE1 and NODE2, and will therefore be + /* Adjacent vertices. + + We don't need to explicitely insert the reference piter (vertex + id) itself into SITES, since it is part of the set of vertices + adjacent to V1 and V2, and will therefore be automatically added. */ - for (std::vector<util::edge_id>::const_iterator e = ref_node.edges.begin(); - e != ref_node.edges.end(); ++e) - { - util::node_id n1 = piter.pg().gr_->edges()[*e]->n1(); - sites.insert(n1); - util::node_id n2 = piter.pg().gr_->edges()[*e]->n2(); - sites.insert(n2); + for (std::vector<util::edge_id>::const_iterator e = + ref_vertex.edges.begin(); + e != ref_vertex.edges.end(); ++e) + { + util::vertex_id v1 = piter.pg().gr_->edges()[*e]->v1(); + sites.insert(v1); + util::vertex_id v2 = piter.pg().gr_->edges()[*e]->v2(); + sites.insert(v2); } } Index: mln/core/p_line_graph.hh --- mln/core/p_line_graph.hh (revision 1992) +++ mln/core/p_line_graph.hh (working copy) @@ -79,8 +79,8 @@ /// graph. std::size_t npoints() const; - /// Return The number of nodes (vertices) in the graph. - std::size_t nnodes() const; + /// Return The number of vertices (vertices) in the graph. + std::size_t nvertices() const; /// Return The number of edges in the graph. std::size_t nedges() const; @@ -145,8 +145,8 @@ : gr_ (new util::graph(gr)) { accu::bbox a; - for (unsigned i = 0; i < nnodes(); ++i) - a.take(gr_->node_data(i)); + for (unsigned i = 0; i < nvertices(); ++i) + a.take(gr_->vertex_data(i)); bb_ = a.to_result(); } @@ -161,9 +161,9 @@ template<typename P> inline std::size_t - p_line_graph::nnodes() const + p_line_graph::nvertices() const { - return this->gr_->nnodes(); + return this->gr_->nvertices(); } template<typename P> @@ -222,10 +222,10 @@ // RHS share a common vertex. /* FIXME: This is too low-level. Yet another service the graph should provide. */ - if (gr_->edge(lhs).n1() == gr_->edge(rhs).n1() || - gr_->edge(lhs).n1() == gr_->edge(rhs).n2() || - gr_->edge(lhs).n2() == gr_->edge(rhs).n1() || - gr_->edge(lhs).n2() == gr_->edge(rhs).n2()) + if (gr_->edge(lhs).v1() == gr_->edge(rhs).v1() || + gr_->edge(lhs).v1() == gr_->edge(rhs).v2() || + gr_->edge(lhs).v2() == gr_->edge(rhs).v1() || + gr_->edge(lhs).v2() == gr_->edge(rhs).v2()) return true; return false; Index: mln/core/line_graph_elt_window.hh --- mln/core/line_graph_elt_window.hh (revision 1992) +++ mln/core/line_graph_elt_window.hh (working copy) @@ -137,21 +137,21 @@ /* FIXME: Move this computation out of the window. In fact, this should be a service of the graph, also proposed by the p_line_graph. */ - // Ajacent edges connected through node 1. + // Ajacent edges connected through vertex 1. /* We don't need to explicitely insert the reference piter (edge id) itself into SITES, since it is part of the set of edges - adjacent to NODE1 and NODE2, and will therefore be + adjacent to VERTEX1 and VERTEX2, and will therefore be automatically added. */ - util::node_id id1 = piter.p_ref().first_id(); - const util::node& node1 = piter.plg().gr_->node(id1); + util::vertex_id id1 = piter.p_ref().first_id(); + const util::vertex& vertex1 = piter.plg().gr_->vertex(id1); for (std::vector<util::edge_id>::const_iterator e = - node1.edges.begin(); e != node1.edges.end(); ++e) + vertex1.edges.begin(); e != vertex1.edges.end(); ++e) sites.insert(*e); - // Ajacent edges connected through node 2. - util::node_id id2 = piter.p_ref().second_id(); - const util::node& node2 = piter.plg().gr_->node(id2); + // Ajacent edges connected through vertex 2. + util::vertex_id id2 = piter.p_ref().second_id(); + const util::vertex& vertex2 = piter.plg().gr_->vertex(id2); for (std::vector<util::edge_id>::const_iterator e = - node2.edges.begin(); e != node2.edges.end(); ++e) + vertex2.edges.begin(); e != vertex2.edges.end(); ++e) sites.insert(*e); } Index: mln/core/graph_psite.hh --- mln/core/graph_psite.hh (revision 1992) +++ mln/core/graph_psite.hh (working copy) @@ -74,8 +74,8 @@ /// Return the p_graph this point site belongs to. const p_graph& pg() const; - /// Return the node id of this point site. - util::node_id id() const; + /// Return the vertex id of this point site. + util::vertex_id id() const; /// Is this psite valid? bool is_valid() const; @@ -83,8 +83,8 @@ private: /// The p_graph this point site belongs to. const p_graph* pg_; - /// The id of the node this psite is pointing towards. - util::node_id id_; + /// The id of the vertex this psite is pointing towards. + util::vertex_id id_; }; /// Compare two mln::graph_psite instances. @@ -109,7 +109,7 @@ template<typename P> inline - graph_psite::graph_psite(const p_graph& g, util::node_id id) + graph_psite::graph_psite(const p_graph& g, util::vertex_id id) : super_(), pg_(&g), id_(id) @@ -142,7 +142,7 @@ bool graph_psite::is_valid() const { - return pg_ && id_ < pg_->gr_->nnodes(); + return pg_ && id_ < pg_->gr_->nvertices(); } template<typename P> @@ -181,7 +181,7 @@ template<typename P> inline - util::node_id + util::vertex_id graph_psite::id() const { return id_; Index: mln/core/p_graph.hh --- mln/core/p_graph.hh (revision 1992) +++ mln/core/p_graph.hh (working copy) @@ -72,8 +72,8 @@ /// number of \em vertices. std::size_t npoints() const; - /// Return The number of nodes (vertices) in the graph. - std::size_t nnodes() const; + /// Return The number of vertices (vertices) in the graph. + std::size_t nvertices() const; /// Return The number of edges in the graph. std::size_t nedges() const; @@ -83,31 +83,31 @@ bool has(const psite& p) const; /// Return the graph point (FIXME site?) from an index - const P& point_from_id(const util::node_id& id) const; - P& point_from_id(const util::node_id& id); + const P& point_from_id(const util::vertex_id& id) const; + P& point_from_id(const util::vertex_id& id); - /// Return the point contained in the first node adjacent + /// Return the point contained in the first vertex adjacent // to the edge id \a e. - const P& node1(const util::edge_id& e) const; - /// Return the point contained in the second node adjacent + const P& vertex1(const util::edge_id& e) const; + /// Return the point contained in the second vertex adjacent /// to the edge id \a e. - const P& node2(const util::edge_id& e) const; + const P& vertex2(const util::edge_id& e) const; /// Adjacency tests. /// \{ /// Return true if the psites \a lhs and \a rhs are adjacent. /// (If \a lhs and \a rhs are equal, return false). bool adjacent(const psite& lhs, const psite& rhs) const; - /// Return true if the nodes \a lhs and \a rhs are adjacent. + /// Return true if the vertices \a lhs and \a rhs are adjacent. /// (If \a lhs and \a rhs are equal, return false). - bool adjacent(const util::node_id& lhs, const util::node_id& rhs) const; + bool adjacent(const util::vertex_id& lhs, const util::vertex_id& rhs) const; /// Return true if the psites \a lhs and \a rhs are adjacent, or equal. bool adjacent_or_equal(const psite& lhs, const psite& rhs) const; - /// Return true if the nodes \a lhs and \a rhs are adjacent, or equal - bool adjacent_or_equal(const util::node_id& lhs, - const util::node_id& rhs) const; + /// Return true if the vertices \a lhs and \a rhs are adjacent, or equal + bool adjacent_or_equal(const util::vertex_id& lhs, + const util::vertex_id& rhs) const; /// \} /// Return the graph associated to the p_graph domain: @@ -158,7 +158,7 @@ { accu::bbox a; for (unsigned i = 0; i < npoints(); ++i) - a.take(gr_->node_data(i)); + a.take(gr_->vertex_data(i)); bb_ = a.to_result(); } @@ -167,15 +167,15 @@ std::size_t p_graph::npoints() const { - return nnodes(); + return nvertices(); } template<typename P> inline std::size_t - p_graph::nnodes() const + p_graph::nvertices() const { - return this->gr_->nnodes(); + return this->gr_->nvertices(); } template<typename P> @@ -202,38 +202,38 @@ return // Check whether P is compatible with this psite set. (&p.pg() == this) && - // Check that the node id of P belongs to the range of valid node ids. - (p.id() < gr_->nnodes()); + // Check that the vertex id of P belongs to the range of valid vertex ids. + (p.id() < gr_->nvertices()); } template <typename P> const P& - p_graph::point_from_id(const util::node_id& id) const + p_graph::point_from_id(const util::vertex_id& id) const { - return this->gr_->node_data(id); + return this->gr_->vertex_data(id); } template <typename P> P& - p_graph::point_from_id(const util::node_id& id) + p_graph::point_from_id(const util::vertex_id& id) { - return this->gr_->node_data(id); + return this->gr_->vertex_data(id); } template <typename P> const P& - p_graph::node1(const util::edge_id& e) const + p_graph::vertex1(const util::edge_id& e) const { - util::node_id n1 = this->gr_->edge(e).n1(); - return this->point_from_id(n1); + util::vertex_id v1 = this->gr_->edge(e).v1(); + return this->point_from_id(v1); } template <typename P> const P& - p_graph::node2(const util::edge_id& e) const + p_graph::vertex2(const util::edge_id& e) const { - util::node_id n2 = this->gr_->edge(e).n2(); - return this->point_from_id(n2); + util::vertex_id v2 = this->gr_->edge(e).v2(); + return this->point_from_id(v2); } template <typename P> @@ -250,8 +250,8 @@ template <typename P> inline bool - p_graph::adjacent(const util::node_id& lhs, - const util::node_id& rhs) const + p_graph::adjacent(const util::vertex_id& lhs, + const util::vertex_id& rhs) const { mln_assertion(lhs < this->npoints()); mln_assertion(rhs < this->npoints()); @@ -263,11 +263,11 @@ // Check whether LHS and RHS are adjacent (i.e., whether RHS is // among the neighbors of LHS). typedef std::vector<util::edge_id> edges_t; - const edges_t& lhs_neighbs = gr_->nodes()[lhs]->edges; + const edges_t& lhs_neighbs = gr_->vertices()[lhs]->edges; for (edges_t::const_iterator e = lhs_neighbs.begin(); e != lhs_neighbs.end(); ++e) - if (gr_->edges()[*e]->n1() == rhs || - gr_->edges()[*e]->n2() == rhs) + if (gr_->edges()[*e]->v1() == rhs || + gr_->edges()[*e]->v2() == rhs) return true; return false; @@ -285,8 +285,8 @@ template <typename P> inline bool - p_graph::adjacent_or_equal(const util::node_id& lhs, - const util::node_id& rhs) const + p_graph::adjacent_or_equal(const util::vertex_id& lhs, + const util::vertex_id& rhs) const { mln_assertion(lhs < this->npoints()); mln_assertion(rhs < this->npoints()); Index: mln/core/graph_elt_neighborhood.hh --- mln/core/graph_elt_neighborhood.hh (revision 1992) +++ mln/core/graph_elt_neighborhood.hh (working copy) @@ -70,9 +70,9 @@ typedef P point; /// The type of psite corresponding to the neighborhood. typedef graph_psite psite; - // The type of the set of neighbors (node ids adjacent to the + // The type of the set of neighbors (vertex ids adjacent to the // reference psite). - typedef std::set<util::node_id> sites_t; + typedef std::set<util::vertex_id> sites_t; // FIXME: This is a dummy value. typedef void dpoint; @@ -107,26 +107,27 @@ graph_elt_neighborhood::compute_sites_(Point_Iterator<Piter>& piter_) const { Piter& piter = exact(piter_); - util::node_id ref_node_id = piter.p_ref().id(); - const util::node& ref_node = piter.pg().gr_->node(ref_node_id); + util::vertex_id ref_vertex_id = piter.p_ref().id(); + const util::vertex& ref_vertex = piter.pg().gr_->vertex(ref_vertex_id); sites_t& sites = piter.sites(); sites.clear(); /* FIXME: Move this computation out of the neighborhood. In fact, this should be a service of the graph, also proposed by the p_line_graph. */ // Adjacent vertices. - for (std::vector<util::edge_id>::const_iterator e = ref_node.edges.begin(); - e != ref_node.edges.end(); ++e) + for (std::vector<util::edge_id>::const_iterator e = + ref_vertex.edges.begin(); + e != ref_vertex.edges.end(); ++e) { - util::node_id n1 = piter.pg().gr_->edges()[*e]->n1(); - // We explicitly enforce that the reference piter node id is + util::vertex_id v1 = piter.pg().gr_->edges()[*e]->v1(); + // We explicitly enforce that the reference piter vertex id is // *not* inserted into SITES. - if (n1 != ref_node_id) - sites.insert(n1); - util::node_id n2 = piter.pg().gr_->edges()[*e]->n2(); + if (v1 != ref_vertex_id) + sites.insert(v1); + util::vertex_id v2 = piter.pg().gr_->edges()[*e]->v2(); // Likewise. - if (n2 != ref_node_id) - sites.insert(n2); + if (v2 != ref_vertex_id) + sites.insert(v2); } } Index: mln/draw/graph.hh --- mln/draw/graph.hh (revision 1992) +++ mln/draw/graph.hh (working copy) @@ -48,38 +48,38 @@ (e.g., in debug::). */ /*! \brief Draw an image \p ima from a mln::p_graph \p pg, with - * value \p node_v for nodes, value \p link_v for links and 0 for + * 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] pg The p_graph which contains nodes and links + * \param[in] pg The p_graph which contains vertices and edges * positions. - * \param[in] node_v The value to assign to pixels which contains - * nodes. - * \param[in] link_v The value to assign to pixels which contains - * links. + * \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 P> void graph(Image& ima, const p_graph& pg, - mln_value(I) node_v, mln_value(I) link_v); + 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 nodes, links - * positions and the values of it. - * \param[in] link_v The value to assign to pixels which contains - * links, defaulting to 1. + * \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 graph(Image& ima, const graph_image<P, V>& gi, - mln_value(I) link_v = 1); + mln_value(I) edge_v = 1); # ifndef MLN_INCLUDE_ONLY @@ -90,7 +90,7 @@ inline void graph(Image& ima, const p_graph& pg, - mln_value(I) node_v, mln_value(I) link_v) + mln_value(I) vertex_v, mln_value(I) edge_v) { // Draw the background. level::fill(ima, 0); @@ -99,28 +99,28 @@ line (exact(ima), // FIXME: Too low-level. See similar remarks // in mln/core/graph_image.hh - pg.gr_->node_data(pg.gr_->edge(l).n1()), - pg.gr_->node_data(pg.gr_->edge(l).n2()), - link_v); - // Draw the points (nodes). + pg.gr_->vertex_data(pg.gr_->edge(l).n1()), + pg.gr_->vertex_data(pg.gr_->edge(l).n2()), + edge_v); + // Draw the points (vertices). for (size_t p = 0; p < pg.npoints(); ++p) - exact(ima)(pg.gr_->node_data(p)) = node_v; + exact(ima)(pg.gr_->vertex_data(p)) = vertex_v; } template <typename I, typename P, typename V> inline void graph(Image& ima, const graph_image<P, V>& gi, - mln_value(I) link_v) + mln_value(I) edge_v) { // Draw the background. level::fill(ima, 0); // Draw the lines (edges). for (size_t l = 0; l < gi.domain().nedges(); ++l) - line (exact(ima), gi.node1(l), gi.node2(l), link_v); - // Draw the points (nodes). - for (size_t p = 0; p < gi.domain().nnodes(); ++p) - exact(ima)(gi.domain().point_from_id(p)) = gi.node_values()[p]; + line (exact(ima), gi.vertex1(l), gi.vertex2(l), edge_v); + // Draw the points (vertices). + for (size_t p = 0; p < gi.domain().nvertices(); ++p) + exact(ima)(gi.domain().point_from_id(p)) = gi.vertex_values()[p]; } # endif // ! MLN_INCLUDE_ONLY Index: mln/accu/count_adjacent_vertices.hh --- mln/accu/count_adjacent_vertices.hh (revision 1992) +++ mln/accu/count_adjacent_vertices.hh (working copy) @@ -82,7 +82,7 @@ /// The value of the counter. std::size_t count__; /// The set of adjacent vertices. - std::set<util::node_id> vertices_; + std::set<util::vertex_id> vertices_; }; Index: mln/morpho/line_gradient.hh --- mln/morpho/line_gradient.hh (revision 1992) +++ mln/morpho/line_gradient.hh (working copy) @@ -72,17 +72,17 @@ // Points. /* FIXME: The need for such a structure during the conversion exhibits the lack of a service from util::graph (or a another, - missing tool) regarding the retrieval of nodes' ids from + missing tool) regarding the retrieval of vertices' ids from points. */ - std::map<mln::point2d, util::node_id> points; + std::map<mln::point2d, util::vertex_id> points; - // Nodes. - std::vector<value_t> node_values; + // Vertices. + std::vector<value_t> vertex_values; mln_fwd_piter(image2d<value_t>) p(ima.domain()); for_all (p) { - util::node_id id = g.add_node (p); - node_values.push_back (ima(p)); + util::vertex_id id = g.add_vertex (p); + vertex_values.push_back (ima(p)); points[p] = id; } @@ -113,7 +113,7 @@ // Line graph image. typedef line_graph_image<mln::point2d, value_t> ima_t; - ima_t lg_ima(plg, node_values, edge_values); + ima_t lg_ima(plg, vertex_values, edge_values); return lg_ima; } Index: mln/util/graph.hh --- mln/util/graph.hh (revision 1992) +++ mln/util/graph.hh (working copy) @@ -33,8 +33,6 @@ # include <mln/util/internal/graph_base.hh> -// FIXME: Rename node(s) as vertex (vertices). - namespace mln { @@ -45,14 +43,14 @@ `-----------*/ /// \brief Undirected graph. - template<typename N = void, typename E = void> + template<typename V = void, typename E = void> class graph; /*--------------------. | graph<void, void>. | `--------------------*/ - /// Specialization for undirected graphs with no data on nodes nor + /// Specialization for undirected graphs with no data on vertices nor /// on edges. template <> class graph<void, void> : public internal::graph_base<void, void> @@ -61,73 +59,73 @@ /// The super class. typedef internal::graph_base<void, void> super; - /// \brief Add a node. + /// \brief Add a vertex. /// - /// \return The id of the new node. - node_id add_node(); - /// \brief Add an edge between nodes with ids \p n1 and \p n2. + /// \return The id of the new vertex. + vertex_id add_vertex(); + /// \brief Add an edge between vertices with ids \p v1 and \p v2. /// /// \return The id of the new edge if it does not exist yet; /// otherwise, return <tt>mln_max(edge_id)</tt>. - edge_id add_edge(node_id n1, node_id n2); + edge_id add_edge(vertex_id v1, vertex_id v2); }; /*-----------------. - | graph<N, void>. | + | graph<V, void>. | `-----------------*/ - /// Specialization for undirected graphs with data on nodes. - template <typename N> - class graph<N, void> : public internal::graph_base<N, void> + /// Specialization for undirected graphs with data on vertices. + template <typename V> + class graph<V, void> : public internal::graph_base<V, void> { public: /// The super class. - typedef internal::graph_base<N, void> super; + typedef internal::graph_base<V, void> super; - /// \brief Add a node. + /// \brief Add a vertex. /// - /// \return The id of the new node. - node_id add_node(const N& data); - /// \brief Add an edge between nodes with ids \p n1 and \p n2. + /// \return The id of the new vertex. + vertex_id add_vertex(const V& data); + /// \brief Add an edge between vertices with ids \p v1 and \p v2. /// /// \return The id of the new edge if it does not exist yet; /// otherwise, return <tt>mln_max(edge_id)</tt>. - edge_id add_edge(node_id n1, node_id n2); + edge_id add_edge(vertex_id v1, vertex_id v2); - /// Return the data associated to node with id \a n. + /// Return the data associated to vertex with id \a v. /// \{ - N& node_data(node_id n); - const N& node_data(node_id n) const; + V& vertex_data(vertex_id v); + const V& vertex_data(vertex_id v) const; /// \} }; /*--------------. - | graph<N, E>. | + | graph<V, E>. | `--------------*/ - /// Specialization for undirected graphs with data on nodes and + /// Specialization for undirected graphs with data on vertices and /// edges. - template <typename N, typename E> - class graph : public internal::graph_base<N, E> + template <typename V, typename E> + class graph : public internal::graph_base<V, E> { public: /// The super class. - typedef internal::graph_base<N, E> super; + typedef internal::graph_base<V, E> super; - /// \brief Add a node. + /// \brief Add a vertex. /// - /// \return The id of the new node. - node_id add_node(const N& data); - /// \brief Add an edge between nodes with ids \p n1 and \p n2. + /// \return The id of the new vertex. + vertex_id add_vertex(const V& data); + /// \brief Add an edge between vertices with ids \p v1 and \p v2. /// /// \return The id of the new edge if it does not exist yet; /// otherwise, return <tt>mln_max(edge_id)</tt>. - edge_id add_edge(node_id n1, node_id n2, const E& data); + edge_id add_edge(vertex_id v1, vertex_id v2, const E& data); - /// Return the data associated to node with id \a n. + /// Return the data associated to vertex with id \a v. /// \{ - N& node_data(node_id n); - const N& node_data(node_id n) const; + V& vertex_data(vertex_id v); + const V& vertex_data(vertex_id v) const; /// \} /// Return the data associated to the edge with id \a e. @@ -136,11 +134,11 @@ const E& edge_data(edge_id e) const; /// \} - /// Return the data associated to the edge between nodes with - /// ids \a n1 and \a n2. + /// Return the data associated to the edge between vertices with + /// ids \a v1 and \a v2. /// \{ - E& edge_data(node_id n1, node_id n2); - const E& edge_data(node_id n1, node_id n2) const; + E& edge_data(vertex_id v1, vertex_id v2); + const E& edge_data(vertex_id v1, vertex_id v2) const; /// \} }; @@ -155,153 +153,153 @@ /* Note that ddefinition of members from fully specialized template classes are not preceded by `template<>'. */ inline - node_id - graph<void, void>::add_node() + vertex_id + graph<void, void>::add_vertex() { - return super::add_node_(new util::node<void>); + return super::add_vertex_(new util::vertex<void>); } /* Note that ddefinition of members from fully specialized template classes are not preceded by `template<>'. */ inline edge_id - graph<void, void>::add_edge(node_id n1, node_id n2) + graph<void, void>::add_edge(vertex_id v1, vertex_id v2) { - mln_assertion(n1 < this->nnodes()); - mln_assertion(n2 < this->nnodes()); - return super::add_edge_(new util::edge<void>(n1, n2)); + mln_assertion(v1 < this->nvertices()); + mln_assertion(v2 < this->nvertices()); + return super::add_edge_(new util::edge<void>(v1, v2)); } /*-----------------. - | graph<N, void>. | + | graph<V, void>. | `-----------------*/ - template<typename N> + template<typename V> inline - node_id - graph<N, void>::add_node(const N& data) + vertex_id + graph<V, void>::add_vertex(const V& data) { - return super::add_node_(new util::node<N>(data)); + return super::add_vertex_(new util::vertex<V>(data)); } - template<typename N> + template<typename V> inline edge_id - graph<N, void>::add_edge(node_id n1, node_id n2) + graph<V, void>::add_edge(vertex_id v1, vertex_id v2) { - mln_assertion(n1 < this->nnodes()); - mln_assertion(n2 < this->nnodes()); - return super::add_edge_(new util::edge<void>(n1, n2)); + mln_assertion(v1 < this->nvertices()); + mln_assertion(v2 < this->nvertices()); + return super::add_edge_(new util::edge<void>(v1, v2)); } - template <class N> + template <class V> inline - N& - graph<N, void>::node_data(node_id n) + V& + graph<V, void>::vertex_data(vertex_id v) { - mln_assertion(n < this->nnodes()); - return this->nodes_[n]->data; + mln_assertion(v < this->nvertices()); + return this->vertices_[v]->data; } - template<typename N> + template<typename V> inline - const N& - graph<N, void>::node_data(node_id n) const + const V& + graph<V, void>::vertex_data(vertex_id v) const { - mln_assertion(n < this->nnodes()); - return this->nodes_[n]->data; + mln_assertion(v < this->nvertices()); + return this->vertices_[v]->data; } /*--------------. - | graph<N, E>. | + | graph<V, E>. | `--------------*/ - template<typename N, typename E> + template<typename V, typename E> inline - node_id - graph<N, E>::add_node(const N& data) + vertex_id + graph<V, E>::add_vertex(const V& data) { - return super::add_node_(new util::node<N>(data)); + return super::add_vertex_(new util::vertex<V>(data)); } - template<typename N, typename E> + template<typename V, typename E> inline edge_id - graph<N, E>::add_edge(node_id n1, node_id n2, const E& data) + graph<V, E>::add_edge(vertex_id v1, vertex_id v2, const E& data) { - mln_assertion(n1 < this->nnodes()); - mln_assertion(n2 < this->nnodes()); - return super::add_edge_(new util::edge<E>(n1, n2, data)); + mln_assertion(v1 < this->nvertices()); + mln_assertion(v2 < this->nvertices()); + return super::add_edge_(new util::edge<E>(v1, v2, data)); } - template<typename N, typename E> + template<typename V, typename E> inline - N& - graph<N, E>::node_data(node_id n) + V& + graph<V, E>::vertex_data(vertex_id v) { - mln_assertion(n < this->nnodes()); - return this->nodes_[n]->data; + mln_assertion(v < this->nvertices()); + return this->vertices_[v]->data; } - template<typename N, typename E> + template<typename V, typename E> inline - const N& - graph<N, E>::node_data(node_id n) const + const V& + graph<V, E>::vertex_data(vertex_id v) const { - mln_assertion(n < this->nnodes()); - return this->nodes_[n]->data; + mln_assertion(v < this->nvertices()); + return this->vertices_[v]->data; } - template<typename N, typename E> + template<typename V, typename E> inline E& - graph<N, E>::edge_data(edge_id e) + graph<V, E>::edge_data(edge_id e) { mln_assertion(e < this->nedges()); return this->edges_[e]->data; } - template<typename N, typename E> + template<typename V, typename E> inline const E& - graph<N, E>::edge_data(edge_id e) const + graph<V, E>::edge_data(edge_id e) const { mln_assertion(e < this->nedges()); return this->edges_[e]->data; } - template<typename N, typename E> + template<typename V, typename E> inline E& - graph<N, E>::edge_data(node_id n1, node_id n2) + graph<V, E>::edge_data(vertex_id v1, vertex_id v2) { - mln_assertion(n1 < this->nnodes()); - mln_assertion(n2 < this->nnodes()); - ordpair_<node_id> node_pair (n1, n2); - std::vector<edge_id>& edges_ids = this->nodes_[n1]->edges; + mln_assertion(v1 < this->nvertices()); + mln_assertion(v2 < this->nvertices()); + ordpair_<vertex_id> vertex_pair (v1, v2); + std::vector<edge_id>& edges_ids = this->vertices_[v1]->edges; for (std::vector<edge_id>::iterator e = edges_ids.begin(); e != edges_ids.end(); ++e) - if (this->edges_[*e] == node_pair) + if (this->edges_[*e] == vertex_pair) return this->edges_[*e]->data; - // If no edge between N1 and N2 was found, abort. + // If no edge between V1 and V2 was found, abort. abort(); } - template<typename N, typename E> + template<typename V, typename E> inline const E& - graph<N, E>::edge_data(node_id n1, node_id n2) const + graph<V, E>::edge_data(vertex_id v1, vertex_id v2) const { - mln_assertion(n1 < this->nnodes()); - mln_assertion(n2 < this->nnodes()); - ordpair_<node_id> node_pair (n1, n2); - const std::vector<edge_id>& edges_ids = this->nodes_[n1]->edges; + mln_assertion(v1 < this->nvertices()); + mln_assertion(v2 < this->nvertices()); + ordpair_<vertex_id> vertex_pair (v1, v2); + const std::vector<edge_id>& edges_ids = this->vertices_[v1]->edges; for (std::vector<edge_id>::const_iterator e = edges_ids.begin(); e != edges_ids.end(); ++e) - if (this->edges_[*e] == node_pair) + if (this->edges_[*e] == vertex_pair) return this->edges_[*e]->data; - // If no edge between N1 and N2 was found, abort. + // If no edge between V1 and V2 was found, abort. abort(); } Index: mln/util/internal/graph_base.hh --- mln/util/internal/graph_base.hh (revision 1992) +++ mln/util/internal/graph_base.hh (working copy) @@ -42,16 +42,14 @@ # include <mln/core/concept/object.hh> # include <mln/util/ordpair.hh> -// FIXME: Rename node(s) as vertex (vertices). - namespace mln { namespace util { - /* FIXME: We should create actual types for node_id and edge_id, + /* FIXME: We should create actual types for vertex_id and edge_id, (not just typedefs), at least to prevent the user from using a - node_id where an edge_id is expected (and vice versa). + vertex_id where an edge_id is expected (and vice versa). Conversion to and from unsigned would still be useful, but it might be safer to turn them into explicit ones. @@ -62,10 +60,10 @@ We /might/ want to integrate this into Milena's value system. */ - /// \brief The type used to identify nodes. + /// \brief The type used to identify vertices. /// - /// Used internally as a key to manipulate nodes. - typedef unsigned node_id; + /// Used internally as a key to manipulate vertices. + typedef unsigned vertex_id; /// \brief The type used to identify edges. /// @@ -73,15 +71,15 @@ typedef unsigned edge_id; - /*-------. - | Node. | - `-------*/ + /*---------. + | Vertex. | + `---------*/ - /// \brief Node of a graph, holding a value of type \p T. + /// \brief Vertex of a graph, holding a value of type \p T. template<typename T> - struct node + struct vertex { - node(T data) + vertex(T data) : data(data) {} @@ -89,10 +87,10 @@ std::vector<edge_id> edges; }; - /// \brief Specialization of mln::util::node for nodes with no + /// \brief Specialization of mln::util::vertex for vertices with no /// associated value. template <> - struct node<void> + struct vertex<void> { std::vector<edge_id> edges; }; @@ -106,38 +104,38 @@ template<typename T> struct edge { - edge(node_id n1, node_id n2) - : pair_node_(n1, n2) + edge(vertex_id v1, vertex_id v2) + : pair_vertex_(v1, v2) {} - /// Return the lowest node id adjacent to this edge. - node_id n1() const { return pair_node_.first; } - /// Return the highest node id adjacent to this edge. - node_id n2() const { return pair_node_.second; } + /// Return the lowest vertex id adjacent to this edge. + vertex_id v1() const { return pair_vertex_.first; } + /// Return the highest vertex id adjacent to this edge. + vertex_id v2() const { return pair_vertex_.second; } T data; - ordpair_<node_id> pair_node_; + ordpair_<vertex_id> pair_vertex_; }; - /// \brief Specialization of mln::util::node for edges with no + /// \brief Specialization of mln::util::vertex for edges with no /// associated value. template <> struct edge<void> { - edge(node_id n1, node_id n2) - : pair_node_(n1, n2) + edge(vertex_id v1, vertex_id v2) + : pair_vertex_(v1, v2) {} - /// Return the lowest node id adjacent to this edge. - node_id n1() const { return pair_node_.first; } - /// Return the highest node id adjacent to this edge. - node_id n2() const { return pair_node_.second; } + /// Return the lowest vertex id adjacent to this edge. + vertex_id v1() const { return pair_vertex_.first; } + /// Return the highest vertex id adjacent to this edge. + vertex_id v2() const { return pair_vertex_.second; } - ordpair_<node_id> pair_node_; + ordpair_<vertex_id> pair_vertex_; }; // FIXME: Document this. In particular, we should state that edges are - // only compared w.r.t. their adjacent nodes, not the data they + // only compared w.r.t. their adjacent vertices, not the data they // possibly hold! template <typename E> bool @@ -148,24 +146,24 @@ operator< (const edge<E>& lhs, const edge<E>& rhs); - /*--------. - | Graph. | - `--------*/ + /*-------------. + | Graph base. | + `-------------*/ namespace internal { /// \brief Base class for undirected graphs. - template<typename N, typename E> + template<typename V, typename E> class graph_base { - typedef graph_base<N, E> self_t; + typedef graph_base<V, E> self_t; public: - /* FIXME: Do we really want handle nodes and edges through + /* FIXME: Do we really want handle vertices and edges through pointers? In my (Roland) opinion, this is just a drawback, here. */ - /// The type of the set of nodes. - typedef std::vector< util::node<N>* > nodes_t; + /// The type of the set of vertices. + typedef std::vector< util::vertex<V>* > vertices_t; /// The type of the set of edges. typedef std::vector< util::edge<E>* > edges_t; /// A set to test the presence of a given edge. @@ -179,10 +177,10 @@ ~graph_base(); /// \} - /// Return the node whose id is \a n. + /// Return the vertex whose id is \a v. /// \{ - util::node<N>& node(node_id n); - const util::node<N>& node(edge_id n) const; + util::vertex<V>& vertex(vertex_id v); + const util::vertex<V>& vertex(edge_id v) const; /// \} /// Return the edge whose id is \a e. @@ -191,10 +189,10 @@ const util::edge<E>& edge(edge_id e) const; /// \} - /// Return the whole nodes of the graph. + /// Return the whole vertices of the graph. /// \{ - nodes_t& nodes(); - const nodes_t& nodes() const; + vertices_t& vertices(); + const vertices_t& vertices() const; /// \} /// Return the whole edges of the graph. @@ -203,8 +201,8 @@ const edges_t& edges() const; /// \} - /// \brief Return the number of nodes in the graph. - size_t nnodes() const; + /// \brief Return the number of vertices in the graph. + size_t nvertices() const; /// \brief Return the number of edges in the graph. size_t nedges() const; @@ -216,12 +214,12 @@ void print_debug(std::ostream& ostr) const; protected: - /// Shortcuts factoring the insertion of nodes and edges. + /// Shortcuts factoring the insertion of vertices and edges. /// \{ - /// \brief Add a node. + /// \brief Add a vertex. /// - /// \return The id of the new node. - node_id add_node_(util::node<N>* node); + /// \return The id of the new vertex. + vertex_id add_vertex_(util::vertex<V>* vertex); /// \brief Add an edge. /// /// \return The id of the new edge if it does not exist yet; @@ -230,8 +228,8 @@ /// \} protected: - /// The nodes. - nodes_t nodes_; + /// The vertices. + vertices_t vertices_; /// The edges. edges_t edges_; /// An index of the set of edges, for fast-access purpose. @@ -248,14 +246,14 @@ bool operator==(const edge<E>& lhs, const edge<E>& rhs) { - return lhs.pair_node_ == rhs.pair_node_; + return lhs.pair_vertex_ == rhs.pair_vertex_; } template <typename E> bool operator< (const edge<E>& lhs, const edge<E>& rhs) { - return lhs.pair_node_ < rhs.pair_node_; + return lhs.pair_vertex_ < rhs.pair_vertex_; } namespace internal @@ -265,23 +263,23 @@ | Construction, assignments and destruction. | `--------------------------------------------*/ - template<typename N, typename E> + template<typename V, typename E> inline - graph_base<N, E>::graph_base() - : nodes_(), edges_(), edges_set_() + graph_base<V, E>::graph_base() + : vertices_(), edges_(), edges_set_() { } - template<typename N, typename E> + template<typename V, typename E> inline - graph_base<N, E>::graph_base(const graph_base<N, E>& rhs) - : nodes_(), edges_(), edges_set_() + graph_base<V, E>::graph_base(const graph_base<V, E>& rhs) + : vertices_(), edges_(), edges_set_() { - nodes_.reserve(rhs.nodes_.size()); + vertices_.reserve(rhs.vertices_.size()); edges_.reserve(rhs.edges_.size()); - for (typename nodes_t::const_iterator n = rhs.nodes_.begin(); - n != rhs.nodes_.end(); ++n) - nodes_.push_back(new util::node<N>(**n)); + for (typename vertices_t::const_iterator v = rhs.vertices_.begin(); + v != rhs.vertices_.end(); ++v) + vertices_.push_back(new util::vertex<V>(**v)); for (typename edges_t::const_iterator e = rhs.edges_.begin(); e != rhs.edges_.end(); ++e) edges_.push_back(new util::edge<E>(**e)); @@ -290,27 +288,27 @@ edges_set_.begin())); } - template<typename N, typename E> + template<typename V, typename E> inline - graph_base<N, E>& - graph_base<N, E>::operator=(const graph_base<N, E>& rhs) + graph_base<V, E>& + graph_base<V, E>::operator=(const graph_base<V, E>& rhs) { if (this != &rhs) { - /// Free previous nodes and edges. - for (typename nodes_t::iterator n = nodes_.begin(); - n != nodes_.end(); ++n) - delete *n; + /// Free previous vertices and edges. + for (typename vertices_t::iterator v = vertices_.begin(); + v != vertices_.end(); ++v) + delete *v; for (typename edges_t::iterator e = edges_.begin(); e != edges_.end(); ++e) delete *e; edges_set_.clear(); /// Assign values from RHS. - nodes_.reserve(rhs.nodes_.size()); + vertices_.reserve(rhs.vertices_.size()); edges_.reserve(rhs.edges_.size()); - for (typename nodes_t::const_iterator n = rhs.nodes_.begin(); - n != rhs.nodes_.end(); ++n) - nodes_.push_back(new util::node<N>(**n)); + for (typename vertices_t::const_iterator v = rhs.vertices_.begin(); + v != rhs.vertices_.end(); ++v) + vertices_.push_back(new util::vertex<V>(**v)); for (typename edges_t::const_iterator e = rhs.edges_.begin(); e != rhs.edges_.end(); ++e) edges_.push_back(new util::edge<E>(**e)); @@ -321,13 +319,13 @@ return *this; } - template<typename N, typename E> + template<typename V, typename E> inline - graph_base<N, E>::~graph_base() + graph_base<V, E>::~graph_base() { - for (typename nodes_t::iterator n = nodes_.begin(); n != nodes_.end(); - ++n) - delete *n; + for (typename vertices_t::iterator v = vertices_.begin(); + v != vertices_.end(); ++v) + delete *v; for (typename edges_t::iterator e = edges_.begin(); e != edges_.end(); ++e) delete *e; @@ -338,86 +336,86 @@ | Accessors. | `------------*/ - template<typename N, typename E> + template<typename V, typename E> inline - util::node<N>& - graph_base<N, E>::node(node_id n) + util::vertex<V>& + graph_base<V, E>::vertex(vertex_id v) { - mln_assertion(n < this->nnodes()); - return *nodes_[n]; + mln_assertion(v < this->nvertices()); + return *vertices_[v]; } - template<typename N, typename E> + template<typename V, typename E> inline - const util::node<N>& - graph_base<N, E>::node(node_id n) const + const util::vertex<V>& + graph_base<V, E>::vertex(vertex_id v) const { - mln_assertion(n < this->nnodes()); - return *nodes_[n]; + mln_assertion(v < this->nvertices()); + return *vertices_[v]; } - template<typename N, typename E> + template<typename V, typename E> inline util::edge<E>& - graph_base<N, E>::edge(edge_id e) + graph_base<V, E>::edge(edge_id e) { mln_assertion(e < this->nedges()); return *edges_[e]; } - template<typename N, typename E> + template<typename V, typename E> inline const util::edge<E>& - graph_base<N, E>::edge(edge_id e) const + graph_base<V, E>::edge(edge_id e) const { mln_assertion(e < this->nedges()); return *edges_[e]; } - template<typename N, typename E> + template<typename V, typename E> inline - typename graph_base<N, E>::nodes_t& - graph_base<N, E>::nodes() + typename graph_base<V, E>::vertices_t& + graph_base<V, E>::vertices() { - return nodes_; + return vertices_; } - template<typename N, typename E> + template<typename V, typename E> inline - const typename graph_base<N, E>::nodes_t& - graph_base<N, E>::nodes() const + const typename graph_base<V, E>::vertices_t& + graph_base<V, E>::vertices() const { - return nodes_; + return vertices_; } - template<typename N, typename E> + template<typename V, typename E> inline - typename graph_base<N, E>::edges_t& - graph_base<N, E>::edges() + typename graph_base<V, E>::edges_t& + graph_base<V, E>::edges() { return edges_; } - template<typename N, typename E> + template<typename V, typename E> inline - const typename graph_base<N, E>::edges_t& - graph_base<N, E>::edges() const + const typename graph_base<V, E>::edges_t& + graph_base<V, E>::edges() const { return edges_; } - template<typename N, typename E> + template<typename V, typename E> inline size_t - graph_base<N, E>::nnodes() const + graph_base<V, E>::nvertices() const { - return nodes_.size(); + return vertices_.size(); } - template<typename N, typename E> + template<typename V, typename E> inline size_t - graph_base<N, E>::nedges() const + graph_base<V, E>::nedges() const { return edges_.size(); } @@ -426,21 +424,21 @@ | Manipulators. | `---------------*/ - template<typename N, typename E> + template<typename V, typename E> inline - node_id - graph_base<N, E>::add_node_(util::node<N>* node) + vertex_id + graph_base<V, E>::add_vertex_(util::vertex<V>* vertex) { /* FIXME: This is not thread-proof (these two lines should form an atomic section). */ - nodes_.push_back (node); - return nodes_.size() - 1; + vertices_.push_back (vertex); + return vertices_.size() - 1; } - template<typename N, typename E> + template<typename V, typename E> inline edge_id - graph_base<N, E>::add_edge_(util::edge<E>* edge) + graph_base<V, E>::add_edge_(util::edge<E>* edge) { // Does this edge already exist in the graph? if (edges_set_.find(edge) != edges_set_.end ()) @@ -461,8 +459,8 @@ // Update the set of edges. edges_set_.insert(edge); - nodes_[edge->n1()]->edges.push_back(id); - nodes_[edge->n2()]->edges.push_back(id); + vertices_[edge->v1()]->edges.push_back(id); + vertices_[edge->v2()]->edges.push_back(id); return id; } @@ -472,22 +470,22 @@ | Debug. | `--------*/ - template<typename N, typename E> + template<typename V, typename E> inline void - graph_base<N, E>::print_debug (std::ostream& ostr) const + graph_base<V, E>::print_debug (std::ostream& ostr) const { ostr << "graph: " << std::endl; int i = 0; - for (typename nodes_t::const_iterator n = nodes_.begin (); - n != nodes_.end (); ++n, ++i) + for (typename vertices_t::const_iterator v = vertices_.begin (); + v != vertices_.end (); ++v, ++i) { - ostr << "node: " < directly, but use a typedef instead. */ for (typename std::vector<util::edge_id>::const_iterator e = - (*n)->edges.begin(); - e != (*n)->edges.end(); ++e) + (*v)->edges.begin(); + e != (*v)->edges.end(); ++e) ostr << *e << " "; ostr << std::endl; }

1 0

1992: Clean up accumulators related to connected filters.
by Roland Levillain 03 Jun '08

03 Jun '08

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Roland Levillain <roland(a)lrde.epita.fr> Clean up accumulators related to connected filters. * mln/accu/count.hh, * mln/accu/volume.hh: Add more documentation. Aesthetic changes. (mln::accu::count_<T>::result) (mln::accu::volume_::result): Remove useless typedef. * mln/accu/volume.hh: (mln::accu::volume_::height__): Rename member as... (mln::accu::volume_::ref_level__): ...this. (mln::accu::volume_::take) (mln::accu::volume_::set_value): Adjust. (mln::accu::volume_::init): Likewise. Actually initialize all members. (mln::accu::count_adjacent_vertices_<P, V>::set_value): Reset member ref_level__ and area__. * mln/accu/count_adjacent_vertices.hh (mln::accu::count_adjacent_vertices_<P, V>::set_value): Reset member vertices_. count.hh | 33 +++++++++++---------------- count_adjacent_vertices.hh | 2 + volume.hh | 54 +++++++++++++++++++++++++++++++++------------ 3 files changed, 56 insertions(+), 33 deletions(-) Index: mln/accu/count.hh --- mln/accu/count.hh (revision 1991) +++ mln/accu/count.hh (working copy) @@ -1,4 +1,4 @@ -// Copyright (C) 2007 EPITA Research and Development Laboratory +// 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,52 +28,47 @@ #ifndef MLN_ACCU_COUNT_HH # define MLN_ACCU_COUNT_HH -/*! \file mln/accu/count.hh - * - * \brief Define an accumulator that counts. - */ +/// \file mln/accu/count.hh +/// \brief Define an accumulator that counts. # include <mln/accu/internal/base.hh> # include <mln/core/concept/meta_accumulator.hh> - namespace mln { namespace accu { - - /*! - * \brief Generic counter accumulator class. - * - * The parameter \a T is the type to be count. - */ + /// \brief Generic counter accumulator class. + /// The parameter \a T is the type to be count. template <typename T> struct count_ : public mln::accu::internal::base_< std::size_t , count_<T> > { typedef T argument; - typedef std::size_t result; // FIXME: Up in Accumulator. count_(); + /// Manipulators. + /// \{ void init(); - // FIXME : should we add a take() without argument? void take(const argument&); void take(const count_<T>& other); - std::size_t to_result() const; + /// Force the value of the counter to \a c. void set_value(std::size_t c); + /// \} - protected: + /// Get the value of the accumulator. + std::size_t to_result() const; + protected: + /// The value of the counter. std::size_t count__; }; - /*! - * \brief Meta accumulator for count. - */ + /// \brief Meta accumulator for count. struct count : public Meta_Accumulator< count > { template <typename T> Index: mln/accu/volume.hh --- mln/accu/volume.hh (revision 1991) +++ mln/accu/volume.hh (working copy) @@ -33,7 +33,7 @@ component through one of its pixels. This accumulator uses an mln::util::pix (pixel) to update the - height, area and volume information of the component. + reference level, area and volume information of the component. The class mln/accu/volume_ is not a general-purpose accumulator; it is used to implement volume-based connected filters. @@ -67,20 +67,30 @@ /// mln::morpho::opening_volume for actual uses of this /// accumulator. typedef util::pix argument; - typedef std::size_t result; // FIXME: Up in Accumulator. + /// The value type associated to the pixel type. + typedef typename argument::value value; volume_(); + /// Manipulators. + /// \{ void init(); - void take(const argument&); + void take(const argument& pixel); void take(const volume_& other); + /// Force the value of the counter to \a v. + void set_value(std::size_t v); + /// \} + + /// Get the value of the accumulator. std::size_t to_result() const; - void set_value(std::size_t c); protected: - typename argument::value height__; + /// The reference level (the level of the component's root). + value ref_level__; + /// The area of the component. std::size_t area__; + /// The volume of the component. std::size_t volume__; }; @@ -110,17 +120,30 @@ void volume_::init() { - height__ = literal::zero; - volume__ = 0; + ref_level__ = literal::zero; volume__ = 0; + area__ = 0; } template <typename I> inline void - volume_::take(const argument& t) + volume_::take(const argument& pixel) { - height__ = t.v(); + /* FIXME: Growing a component using this particular `take' + routine won't work, since the update does not take care of + the reference level to compute the new volume. Maybe we + could distinguish two cases: + + 1. the empty accumulator case (which corresponds to the + following code); + 2. the non-empty accumulator case (which sohuld act as in + `take(const volume_& other)'). + + Currently, the implementation is only valid if the + accumulator was initialy empty before the call to + `take(const argument&)'. */ + ref_level__ = pixel.v(); ++area__; ++volume__; } @@ -135,8 +158,9 @@ the latter, but both the ISMM 2005 paper and Olena 0.11 use the former. */ volume__ += - other.volume__ + other.area__ * math::abs(other.height__ - height__); - // Member height__ is not touched. + other.volume__ + + other.area__ * math::abs(other.ref_level__ - ref_level__); + // Member ref_level__ is not touched. } template <typename I> @@ -150,10 +174,12 @@ template <typename I> inline void - volume_::set_value(std::size_t c) + volume_::set_value(std::size_t v) { - volume__ = c; - // FIXME: What about area__ and height__ ? + volume__ = v; + // Reset the other members. + ref_level__ = literal::zero; + area__ = 0; } # endif // ! MLN_INCLUDE_ONLY Index: mln/accu/count_adjacent_vertices.hh --- mln/accu/count_adjacent_vertices.hh (revision 1991) +++ mln/accu/count_adjacent_vertices.hh (working copy) @@ -149,6 +149,8 @@ count_adjacent_vertices_<P, V>::set_value(std::size_t c) { count__ = c; + /// Reset the other member. + vertices_.clear(); } template <typename P, typename V>

1 0