[Olena-patches] 1714: Update to new mln::util::graph and improve graph-based entities.

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Roland Levillain &lt;roland(a)lrde.epita.fr&gt; Catch up with the new interface of mln::util::graph and improve graph-based entities. * mln/core/p_graph.hh: Store points associated to nodes in the graph itself, not in an separate array. (p_graph<P>::graph): Set this typedef from `util::graph<void>' to `util::graph<P>'. (p_graph<P>::loc_): Remove. (p_graph<P>::graph): Adjust ctor. (p_graph<P>::npoints, p_graph<P>::nlines, p_graph<P>::has): Use the new interface of mln::util::graph. * mln/core/graph_psite.hh (graph_psite<P>::i_): Rename as (graph_psite<P>::id_): ...this. Make it a private argument. (graph_psite<P>::pg_): Likewise. (graph_psite<P>::id, graph_psite<P>::pg): New accessors. Adjust users. * mln/core/graph_image.hh (graph_image<P, V>::access_location_link_node1) (graph_image<P, V>::access_location_link_node2): Rename as... (graph_image<P, V>::node1) (graph_image<P, V>::node2): ...these. Use the new interface of mln::util::graph. (graph_image<P, V>::operator()) Use the new interface of mln::graph_psite. * mln/core/graph_window_piter.hh (graph_window_fwd_piter<P>::i_): Rename as... (graph_window_fwd_piter<P>::id_): ...this. Set its to type from `unsigned' to `util::node_id'. Adjust users. (graph_window_fwd_piter<P>::is_valid) (graph_window_fwd_piter<P>::invalidate) (graph_window_fwd_piter<P>::adjacent_or_equal_to_p_ref_) (graph_window_fwd_piter<P>::to_point) (graph_window_fwd_piter<P>::operator graph_psite<P>): Use the new interface of mln::util::graph. * mln/core/p_graph_piter.hh (p_graph_piter_<P>::psite_set_): Rename as... (p_graph_piter_<P>::pg_): ...this. Use the new interface of mln::p_graph. (p_graph_piter_<P>::is_valid) (p_graph_piter_<P>::invalidate) (p_graph_piter_<P>::update_): Likewise. * mln/draw/graph.hh (draw::graph): Update to the new interfaces of mln::util::graph and mln::p_graph. * mln/draw/all.hh: Adjust and complete the list of included headers. * tests/core/graph_elt_window.cc, * tests/core/graph_image.cc, * tests/draw/graph.cc: Update tests. mln/core/graph_image.hh | 39 +++++++++++++---------- mln/core/graph_psite.hh | 68 ++++++++++++++++++++++++----------------- mln/core/graph_window_piter.hh | 51 +++++++++++++----------------- mln/core/p_graph.hh | 37 +++++++++++++--------- mln/core/p_graph_piter.hh | 18 +++++----- mln/draw/all.hh | 4 +- mln/draw/graph.hh | 33 ++++++++++--------- tests/core/graph_elt_window.cc | 6 +-- tests/core/graph_image.cc | 6 +-- tests/draw/graph.cc | 8 +--- 10 files changed, 145 insertions(+), 125 deletions(-) Index: mln/core/graph_psite.hh --- mln/core/graph_psite.hh (revision 1713) +++ mln/core/graph_psite.hh (working copy) @@ -28,12 +28,8 @@ #ifndef MLN_CORE_GRAPH_PSITE_HH # define MLN_CORE_GRAPH_PSITE_HH -/*! \file mln/core/graph_psite.hh - * - * \brief Definition of a graph-based point site. - * - * \todo Clean-up! - */ +/// \file mln/core/graph_psite.hh +/// \brief Definition of a graph-based point site. # include <mln/core/p_graph.hh> @@ -45,11 +41,7 @@ template<typename P> class p_graph; - /*! - * \brief Point site associate to graph_image. - * - * \todo Fix access to member. - */ + /// \brief Point site associated to a mln::graph_image. template<typename P> class graph_psite : public Point_Site< graph_psite<P> > { @@ -64,27 +56,37 @@ /// Construction and assignment. /// \{ - graph_psite(const p_graph<P>& pg_, unsigned i); + graph_psite(const p_graph<P>& pg_, unsigned id); graph_psite(const self_& rhs); self_& operator= (const self_& rhs); /// \} + /// Access to point/psite. + /// \{ operator P() const; const point& to_point() const; - coord operator[](unsigned i) const; + coord operator[](unsigned id) const; + /// \} - // FIXME: These shouldn't be public. + /// Return the mln::p_graph this point site belongs to. + const p_graph<P>& pg() const; + /// Return the node id of this point site. + util::node_id id() const; + + private: const p_graph<P>& pg_; - unsigned i_; + util::node_id id_; }; + + # ifndef MLN_INCLUDE_ONLY template<typename P> inline - graph_psite<P>::graph_psite(const p_graph<P>& g, unsigned i) + graph_psite<P>::graph_psite(const p_graph<P>& g, util::node_id id) : pg_(g), - i_(i) + id_(id) { } @@ -92,7 +94,7 @@ inline graph_psite<P>::graph_psite(const graph_psite<P>& rhs) : pg_(rhs.pg_), - i_(rhs.i_) + id_(rhs.id_) { } @@ -105,7 +107,7 @@ return *this; // FIXME: Could we get rid of this cast? const_cast< p_graph<P>& >(pg_) = rhs.pg_; - i_ = rhs.i_; + id_ = rhs.id_; return *this; } @@ -113,9 +115,7 @@ inline graph_psite<P>::operator P() const { - // FIXME: This is quite unsafe: we should check that i_ is a valid - // index before dereferencing loc_ to ensure clear error messages. - return pg_.loc_[i_]; + return pg_.gr_.node_data(id_); } template<typename P> @@ -123,17 +123,31 @@ const P& graph_psite<P>::to_point() const { - // FIXME: This is quite unsafe: we should check that i_ is a valid - // index before dereferencing loc_ to ensure clear error messages. - return pg_.loc_[i_]; + return pg_.gr_.node_data(id_); } template<typename P> inline mln_coord(P) - graph_psite<P>::operator[](unsigned i) const + graph_psite<P>::operator[](util::node_id id) const + { + return to_point()[id]; + } + + template<typename P> + inline + const p_graph<P>& + graph_psite<P>::pg() const + { + return pg_; + } + + template<typename P> + inline + util::node_id + graph_psite<P>::id() const { - return to_point()[i]; + return id_; } # endif // ! MLN_INCLUDE_ONLY Index: mln/core/p_graph.hh --- mln/core/p_graph.hh (revision 1713) +++ mln/core/p_graph.hh (working copy) @@ -44,12 +44,13 @@ template<typename P> class p_graph_piter_; template<typename P> - struct p_graph : public internal::point_set_base_< graph_psite<P>, p_graph<P> > + struct p_graph + : public internal::point_set_base_< graph_psite<P>, p_graph<P> > { - typedef util::graph<void> graph; + typedef util::graph<P> graph; - /// Construct a graph psite set from a graph and an array of locations. - p_graph (graph& gr, std::vector<P>& loc); + /// Construct a graph psite set from a graph of points. + p_graph (graph& gr); /// Point_Site associated type. typedef graph_psite<P> psite; @@ -71,8 +72,8 @@ bool has(const psite& p) const; + // FIXME: Should be private. graph gr_; - std::vector<P> loc_; // FIXME: (Roland) Is it really useful/needed? /* 2007-12-19: It seems so, since graph_image must implement a method named bbox(). Now the question is: should each image type have a @@ -84,22 +85,25 @@ template<typename P> inline - p_graph<P>::p_graph (util::graph<void>& gr, std::vector<P>& loc) - : gr_ (gr), - loc_ (loc) + p_graph<P>::p_graph (util::graph<P>& gr) + : gr_ (gr) { + // FIXME: Warning: if the underlying graph is updated later, this + // won't be taken into account by this p_graph! accu::bbox<P> a; - for (unsigned i = 0; i < loc.size(); ++i) - a.take(loc[i]); + for (unsigned i = 0; i < npoints(); ++i) + a.take(gr_.node_data(i)); bb_ = a.to_result(); } + // FIXME: Rename to npsites? In fact, this depends on the + // interface expected from models of Point_Sets. template<typename P> inline std::size_t p_graph<P>::npoints() const { - return this->gr_.nb_node_; + return this->gr_.nnodes(); } template<typename P> @@ -107,7 +111,7 @@ std::size_t p_graph<P>::nlines() const { - return this->gr_.nb_link_; + return this->gr_.nedges(); } template<typename P> @@ -123,13 +127,16 @@ bool p_graph<P>::has(const psite& p) const { - for (unsigned i = 0; i < loc_.size(); ++i) - if (loc_[i] == p) + // FIXME: util::graph (or util::internal::graph_base) should + // provide the iteration facility (iterators, find, etc.) + const typename graph::nodes_t& nodes = gr_.nodes(); + for (typename graph::nodes_t::const_iterator n = nodes.begin(); + n != nodes.end(); ++n) + if ((*n)->data == p) return true; return false; } - # endif // ! MLN_INCLUDE_ONLY } // end of mln Index: mln/core/graph_window_piter.hh --- mln/core/graph_window_piter.hh (revision 1713) +++ mln/core/graph_window_piter.hh (working copy) @@ -82,6 +82,7 @@ // it returns a mln::graph_psite<P> object, not a P object. const point& to_point() const; operator psite () const; + /// Return the \a i th coordinate of the (iterated) point. coord operator[](unsigned i) const; private: @@ -89,7 +90,7 @@ const psite& p_ref_; /// An internal iterator on the set of nodes of the underlying graph. - unsigned i_; + util::node_id id_; }; // FIXME: Implement graph_window_bkd_piter. @@ -104,7 +105,7 @@ const Point_Site<Pref>& p_ref) : p_ref_(exact(p_ref).to_psite()) { - // Invalidate i_. + // Invalidate id_. invalidate(); } @@ -115,21 +116,21 @@ // FIXME: We depend too much on the implementation of util::graph // here. The util::graph should provide the service to abstract // these manipulations. - return i_ >= 0 && i_ < p_ref_.pg_.gr_.nb_node_; + return id_ < p_ref_.pg().gr_.nnodes(); } template <typename P> void graph_window_fwd_piter<P>::invalidate() { - i_ = p_ref_.pg_.gr_.nb_node_; + id_ = p_ref_.pg().gr_.nnodes(); } template <typename P> void graph_window_fwd_piter<P>::start() { - i_ = 0; + id_ = 0; if (!adjacent_or_equal_to_p_ref_()) next_(); } @@ -138,12 +139,14 @@ void graph_window_fwd_piter<P>::next_() { - // FIXME: This is inefficient. The graph structure should be able - // to produce the set of adjacent nodes fast. Boost Graphs - // probably provides adequates structures to fetch these - // neighbors in constant time. + /* FIXME: This is inefficient. The graph structure should be able + to produce the set of adjacent nodes fast. Boost Graphs + probably provides adequates structures to fetch these + neighbors in constant time. */ + /* FIXME: Moreover, the behavior of next shall depend on the + window, which is not the case now! */ do - ++i_; + ++id_; while (is_valid() && !adjacent_or_equal_to_p_ref_()); } @@ -154,34 +157,24 @@ // FIXME: Likewise, this is inefficient. // Check wether the iterator points to P_REF_. - if (i_ == p_ref_.i_) + if (id_ == p_ref_.id()) return true; - typedef std::list<unsigned> adjacency_type; - // Check whether the iterator is among the neighbors of P_REF_. { // Paranoid assertion. - assert (p_ref_.i_ >= 0 && - p_ref_.i_ < p_ref_.pg_.gr_.nodes_.size ()); + assert (p_ref_.id() < p_ref_.pg().gr_.nnodes()); + // FIXME: This is too low-level. Yet another service the graph + // should provide. + typedef std::vector<util::node_id> adjacency_type; const adjacency_type& p_ref_neighbs = - p_ref_.pg_.gr_.nodes_[p_ref_.i_]->links; + p_ref_.pg().gr_.nodes()[p_ref_.id()]->edges; adjacency_type::const_iterator j = - std::find (p_ref_neighbs.begin(), p_ref_neighbs.end(), i_); + std::find (p_ref_neighbs.begin(), p_ref_neighbs.end(), id_); if (j != p_ref_neighbs.end()) return true; } - // Check whether P_REF_ is among the neighbors of the iterator. - { - assert (is_valid ()); - const adjacency_type& i_neighbs = p_ref_.pg_.gr_.nodes_[i_]->links; - adjacency_type::const_iterator k = - std::find (i_neighbs.begin(), i_neighbs.end(), p_ref_.i_); - if (k != i_neighbs.end()) - return true; - } - // Otherwise, the iterator is not adjacent to P_REF_. return false; } @@ -190,13 +183,13 @@ const P& graph_window_fwd_piter<P>::to_point() const { - return p_ref_.pg_.loc_[i_]; + return p_ref_.pg().gr_.node_data(id_); } template <typename P> graph_window_fwd_piter<P>::operator graph_psite<P> () const { - return graph_psite<P>(p_ref_.pg_, i_); + return graph_psite<P>(p_ref_.pg(), id_); } template <typename P> Index: mln/core/graph_image.hh --- mln/core/graph_image.hh (revision 1713) +++ mln/core/graph_image.hh (working copy) @@ -134,11 +134,12 @@ const p_graph<P>& domain() const; - /// Return the first node of the link at i from loc - const P& access_location_link_node1 (const unsigned& i) const; - - /// Return the second node of the link at i from loc - const P& access_location_link_node2 (const unsigned& i) const; + /// Return the point of the first node 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 + /// id \a e. + const P& node2(const util::edge_id& e) const; }; // Fwd decl. @@ -225,9 +226,9 @@ const V& graph_image<P, V>::operator()(const graph_psite<P>& p) const { - mln_precondition(&p.pg_ == &this->data_->pg_); - mln_precondition(p.i_ < this->data_->val_.size()); - return this->data_->val_[p.i_]; + mln_precondition(&p.pg() == &this->data_->pg_); + mln_precondition(p.id() < this->data_->val_.size()); + return this->data_->val_[p.id()]; } template <typename P, typename V> @@ -235,9 +236,9 @@ V& graph_image<P, V>::operator()(const graph_psite<P>& p) { - mln_precondition(&p.pg_ == &this->data_->pg_); - mln_precondition(p.i_ < this->data_->val_.size()); - return this->data_->val_[p.i_]; + mln_precondition(&p.pg() == &this->data_->pg_); + mln_precondition(p.id() < this->data_->val_.size()); + return this->data_->val_[p.id()]; } template <typename P, typename V> @@ -268,19 +269,23 @@ template <typename P, typename V> inline const P& - graph_image<P, V>::access_location_link_node1 (const unsigned& i) const + graph_image<P, V>::node1(const util::edge_id& e) const { - // FIXME: This is ugly! Too much implementation details are shown here. - return this->domain().loc_[this->domain().gr_.links_[i]->pair_node_.first]; + // 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); } template <typename P, typename V> inline const P& - graph_image<P, V>::access_location_link_node2 (const unsigned& i) const + graph_image<P, V>::node2(const util::edge_id& e) const { - // FIXME: This is ugly! Too much implementation details are shown here. - return this->domain().loc_[this->domain().gr_.links_[i]->pair_node_.second]; + // 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); } # endif // ! MLN_INCLUDE_ONLY Index: mln/core/p_graph_piter.hh --- mln/core/p_graph_piter.hh (revision 1713) +++ mln/core/p_graph_piter.hh (working copy) @@ -60,7 +60,7 @@ typedef graph_psite<P> psite; typedef P point; - p_graph_piter_(const p_graph<P>& psite_set); + p_graph_piter_(const p_graph<P>& pg); /// Read-only access to the \p i-th coordinate. mln_coord(P) operator[](unsigned i) const; @@ -93,7 +93,7 @@ operator psite() const; protected: - const p_graph<P>& psite_set_; + const p_graph<P>& pg_; unsigned i_; P p_; psite psite_; @@ -105,11 +105,11 @@ template<typename P> inline - p_graph_piter_<P>::p_graph_piter_(const p_graph<P>& psite_set) - : psite_set_(psite_set), + p_graph_piter_<P>::p_graph_piter_(const p_graph<P>& pg) + : pg_(pg), p_(), // Initialize psite_ to a dummy value. - psite_(psite_set, psite_set_.loc_.size()) + psite_(pg, pg_.npoints()) { // Invalidate i_. invalidate(); @@ -128,7 +128,7 @@ bool p_graph_piter_<P>::is_valid() const { - return i_ != psite_set_.loc_.size(); + return i_ < pg_.npoints(); } template<typename P> @@ -136,7 +136,7 @@ void p_graph_piter_<P>::invalidate() { - i_ = psite_set_.loc_.size(); + i_ = pg_.npoints(); } template<typename P> @@ -165,9 +165,9 @@ p_graph_piter_<P>::update_() { // Update p_. - p_ = psite_set_.loc_[i_]; + p_ = pg_.gr_.node_data(i_); // Update psite_. - psite_ = graph_psite<P>(psite_set_, i_); + psite_ = graph_psite<P>(pg_, i_); } template<typename P> Index: mln/draw/graph.hh --- mln/draw/graph.hh (revision 1713) +++ mln/draw/graph.hh (working copy) @@ -92,16 +92,19 @@ graph(Image<I>& ima, const p_graph<P>& pg, mln_value(I) node_v, mln_value(I) link_v) { + // Draw the background. level::fill(ima, 0); - - for (unsigned i = 0; i < pg.nlines(); ++i) + // Draw the lines (edges). + for (size_t l = 0; l < pg.nlines(); ++l) line (exact(ima), - pg.loc_[pg.gr_.links_[i]->pair_node_.first], - pg.loc_[pg.gr_.links_[i]->pair_node_.second], + // 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); - - for (unsigned i = 0; i < pg.npoints(); ++i) - exact(ima)(pg.loc_[i]) = node_v; + // Draw the points (nodes). + for (size_t p = 0; p < pg.npoints(); ++p) + exact(ima)(pg.gr_.node_data(p)) = node_v; } template <typename I, typename P, typename V> @@ -110,16 +113,14 @@ graph(Image<I>& ima, const graph_image<P, V>& gi, mln_value(I) link_v) { + // Draw the background. level::fill(ima, 0); - - for (unsigned i = 0; i < gi.domain().nlines(); ++i) - line (exact(ima), - gi.access_location_link_node1 (i), - gi.access_location_link_node2 (i), - link_v); - - for (unsigned i = 0; i < gi.domain().npoints(); ++i) - exact(ima)(gi.domain().loc_[i]) = gi.data_values ()[i]; + // Draw the lines (edges). + for (size_t l = 0; l < gi.domain().nlines(); ++l) + line (exact(ima), gi.node1(l), gi.node2(l), link_v); + // Draw the points (nodes). + for (size_t p = 0; p < gi.domain().npoints(); ++p) + exact(ima)(gi.domain().gr_.node_data(p)) = gi.data_values()[p]; } # endif // ! MLN_INCLUDE_ONLY Index: mln/draw/all.hh --- mln/draw/all.hh (revision 1713) +++ mln/draw/all.hh (working copy) @@ -42,7 +42,9 @@ } +# include <mln/draw/box.hh> +# include <mln/draw/graph.hh> +# include <mln/draw/label.hh> # include <mln/draw/line.hh> -# include <mln/draw/mesh.hh> #endif // ! MLN_DRAW_ALL_HH Index: tests/core/graph_elt_window.cc --- tests/core/graph_elt_window.cc (revision 1713) +++ tests/core/graph_elt_window.cc (working copy) @@ -58,10 +58,10 @@ points.push_back(make::point2d(4,4)); // Point associated to node 4. // Edges. - mln::util::graph<void> g; + mln::util::graph<p_t> g; // Populate the graph with nodes. for (unsigned i = 0; i < points.size(); ++i) - g.add_node (); + g.add_node (points[i]); // Populate the graph with edges. g.add_edge(0, 1); g.add_edge(1, 2); @@ -74,7 +74,7 @@ `------------------*/ // Graph psite set. - p_graph<p_t> pg(g, points); + p_graph<p_t> pg(g); // Graph point site. graph_psite<p_t> psite(pg, 0); // ``Sliding'' window (in fact, neighborhood) of a psite of PG. Index: tests/core/graph_image.cc --- tests/core/graph_image.cc (revision 1713) +++ tests/core/graph_image.cc (working copy) @@ -59,10 +59,10 @@ points.push_back(make::point2d(4,4)); // Point associated to node 4. // Edges. - util::graph<void> g; + util::graph<point2d> g; // Populate the graph with nodes. for (unsigned i = 0; i < points.size(); ++i) - g.add_node (); + g.add_node (points[i]); // Populate the graph with edges. g.add_edge(0, 1); g.add_edge(1, 2); @@ -74,7 +74,7 @@ | Graph. | `-------*/ - p_graph<point2d> pg(g, points); + p_graph<point2d> pg(g); /*-------------. | Graph image. | Index: tests/draw/graph.cc --- tests/draw/graph.cc (revision 1713) +++ tests/draw/graph.cc (working copy) @@ -61,17 +61,15 @@ unsigned nrows, unsigned ncols, const mln::image2d<int>& ref) { // Graph. - util::graph<void> g; + util::graph<mln::point2d> g; // Populate the graph with nodes. for (unsigned i = 0; i < points.size(); ++i) - g.add_node (); + g.add_node (points[i]); // Populate the graph with edges. for (edges_type::const_iterator i = edges.begin(); i != edges.end(); ++i) g.add_edge (i->first, i->second); - // Check its consistency. - g.consistency (); - mln::p_graph<point2d> pg(g, points); + mln::p_graph<point2d> pg(g); image2d<int> ima(nrows, ncols); draw::graph (ima, pg, 2, 1);