[Olena-patches] 1905: Speed up iterations on graph windows and neighborhoods.

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Roland Levillain &lt;roland(a)lrde.epita.fr&gt; Speed up iterations on graph windows and neighborhoods. * mln/core/internal/graph_vicinity_piter.hh (mln::internal::graph_vicinity_piter_<P, E>::graph_vicinity_piter_): Make this ctor protected. No longer invalidate the iterator. (mln::internal::graph_vicinity_piter_<P, E>::is_valid) (mln::internal::graph_vicinity_piter_<P, E>::invalidate) (mln::internal::graph_vicinity_piter_<P, E>::adjacent_to_p_ref_) (mln::internal::graph_vicinity_piter_<P, E>::adjacent_or_equal_to_p_ref_) (mln::internal::graph_vicinity_piter_<P, E>::update_): Remove. (mln::internal::graph_vicinity_piter_<P, E>::p_ref) (mln::internal::graph_vicinity_piter_<P, E>::pg) (mln::internal::graph_vicinity_piter_<P, E>::sites): New accessors. (mln::internal::graph_vicinity_piter_<P, E>::saved_p_ref_) (mln::internal::graph_vicinity_piter_<P, E>::p_ref_): New members. * mln/core/graph_window_piter.hh (mln::graph_window_fwd_piter<P>::is_valid) (mln::graph_window_fwd_piter<P>::invalidate) (mln::graph_window_fwd_piter<P>::update) (mln::graph_window_bkd_piter<P>::is_valid) (mln::graph_window_bkd_piter<P>::invalidate) (mln::graph_window_bkd_piter<P>::update): New methods. (mln::graph_window_fwd_piter<P>::first_) (mln::graph_window_fwd_piter<P>::step_) (mln::graph_window_bkd_piter<P>::first_) (mln::graph_window_bkd_piter<P>::step_): Remove methods. (mln::graph_window_fwd_piter<P>::i_) (mln::graph_window_bkd_piter<P>::i_): New members. (mln::graph_window_fwd_piter<P>::graph_window_fwd_piter) (mln::graph_window_bkd_piter<P>::graph_window_bkd_piter): Invalidate member i_. (mln::graph_window_fwd_piter<P>::start) (mln::graph_window_fwd_piter<P>::next) (mln::graph_window_bkd_piter<P>::start) (mln::graph_window_bkd_piter<P>::next): Change the algorithms used in these routines, so that they use a list of computed sites (super member sites_) instead of iterating over the whole set of vertices. * mln/core/graph_neighborhood_piter.hh: (mln::graph_neighborhood_fwd_piter<P>::is_valid) (mln::graph_neighborhood_fwd_piter<P>::invalidate) (mln::graph_neighborhood_fwd_piter<P>::update) (mln::graph_neighborhood_bkd_piter<P>::is_valid) (mln::graph_neighborhood_bkd_piter<P>::invalidate) (mln::graph_neighborhood_bkd_piter<P>::update): New methods. (mln::graph_neighborhood_fwd_piter<P>::first_) (mln::graph_neighborhood_fwd_piter<P>::step_) (mln::graph_neighborhood_bkd_piter<P>::first_) (mln::graph_neighborhood_bkd_piter<P>::step_): Remove methods. (mln::graph_neighborhood_fwd_piter<P>::i_) (mln::graph_neighborhood_bkd_piter<P>::i_): New members. (mln::graph_neighborhood_fwd_piter<P>::graph_neighborhood_fwd_piter) (mln::graph_neighborhood_bkd_piter<P>::graph_neighborhood_bkd_piter): Invalidate member i_. (mln::graph_neighborhood_fwd_piter<P>::start) (mln::graph_neighborhood_fwd_piter<P>::next) (mln::graph_neighborhood_bkd_piter<P>::start) (mln::graph_neighborhood_bkd_piter<P>::next): Change the algorithms used in these routines, so that they use a list of computed sites (super member sites_) instead of iterating over the whole set of vertices. * mln/core/graph_elt_window.hh: Catch up with the new interface of piters on line graph windows. (mln::graph_elt_window<P>::sites_t): New typedef. (mln::graph_elt_window<P>::graph_elt_window): Remove useless ctor. (mln::graph_elt_window<P>::start) (mln::graph_elt_window<P>::next_): Remove methods. (mln::graph_elt_window<P>::compute_sites_): New method. * mln/core/graph_elt_neighborhood.hh: Catch up with the new interface of piters on line graph neighborhoods. (mln::graph_elt_neighborhood::neighbors_t): New typedef. (mln::graph_elt_neighborhood::start) (mln::graph_elt_neighborhood::next_): Remove methods. (mln::graph_elt_neighborhood<P>::compute_sites_): New method. graph_elt_neighborhood.hh | 54 +++++++------ graph_elt_window.hh | 62 +++++++-------- graph_neighborhood_piter.hh | 153 ++++++++++++++++++++++++++------------- graph_window_piter.hh | 151 +++++++++++++++++++++++++------------- internal/graph_vicinity_piter.hh | 109 +++++++++++---------------- 5 files changed, 306 insertions(+), 223 deletions(-) Index: mln/core/internal/graph_vicinity_piter.hh --- mln/core/internal/graph_vicinity_piter.hh (revision 1904) +++ mln/core/internal/graph_vicinity_piter.hh (working copy) @@ -32,6 +32,11 @@ /// \brief Factored implementation for point iterators on a graph windows /// and graph neighborhoods, called "vicinities". +/* FIXME: Factor those classes: + + - mln::internal::graph_vicinity_piter.hh + - mln::internal::line_graph_vicinity_piter.hh */ + # include <mln/core/concept/point_iterator.hh> # include <mln/core/p_graph.hh> # include <mln/core/graph_psite.hh> @@ -72,28 +77,10 @@ // FIXME: Dummy value. typedef void mesh; - public: - /// Construction. - /// \{ - template <typename Pref> - graph_vicinity_piter_(const Point_Site<Pref>& p_ref); - /// \} - - /// Manipulation. - /// \{ - /// Test if the iterator is valid. - bool is_valid() const; - /// Invalidate the iterator. - void invalidate(); - - /// Is the piter adjacent to the reference point? - bool adjacent_to_p_ref_() const; - /// Is the piter adjacent or equal to the reference point? - bool adjacent_or_equal_to_p_ref_() const; - /// Update the internal data of the iterator. - void update_(); - /// \} + // The type of the set of vicinity sites (adjacent vertex ids). + typedef std::set<util::node_id> sites_t; + public: /// Conversion and accessors. /// \{ /// Reference to the corresponding point. @@ -103,10 +90,24 @@ /// Convert the iterator into a line graph psite. operator psite() const; + /// Return the reference psite. + const psite& p_ref() const; + /// Return the mln::p_graph corresponding to this piter. + const p_graph<P>& pg() const; + /// Return the set of sites (adjacent vertex ids). + sites_t& sites(); + /// Read-only access to the \a i-th coordinate. coord operator[](unsigned i) const; /// \} + protected: + /// Construction. + /// \{ + template <typename Pref> + graph_vicinity_piter_(const Point_Site<Pref>& p_ref); + /// \} + /// Internals, used by the vicinity. /// \{ public: @@ -120,7 +121,11 @@ /// piter). const psite& p_ref_; - private: + /// The last reference psite whose ajacent psites have been computed. + psite saved_p_ref_; + /// The set of edge ids adjacent to the reference psite. + sites_t sites_; + /// The psite corresponding to this iterator. psite psite_; /// The point corresponding to this iterator. @@ -140,78 +145,54 @@ psite_(), p_() { - // Invalidate id_. - invalidate(); - } - - template <typename P, typename E> - inline - bool - graph_vicinity_piter_<P, E>::is_valid() const - { - /* FIXME: We depend too much on the implementation of - util::graph here. The util::graph should provide the service - to abstract these manipulations. */ - return p_ref_.is_valid() && id_ < p_ref_.pg().npoints(); - } - - template <typename P, typename E> - inline - void - graph_vicinity_piter_<P, E>::invalidate() - { - id_ = -1; } template <typename P, typename E> inline - bool - graph_vicinity_piter_<P, E>::adjacent_to_p_ref_() const + const P& + graph_vicinity_piter_<P, E>::to_point() const { - return p_ref_.pg().adjacent(p_ref_.id(), id_); + return p_; } template <typename P, typename E> inline - bool - graph_vicinity_piter_<P, E>::adjacent_or_equal_to_p_ref_() const + const graph_psite<P>& + graph_vicinity_piter_<P, E>::to_psite() const { - return p_ref_.pg().adjacent_or_equal(p_ref_.id(), id_); + return psite_; } template <typename P, typename E> inline - void - graph_vicinity_piter_<P, E>::update_() + graph_vicinity_piter_<P, E>::operator graph_psite<P>() const { - // Update psite_. - psite_ = graph_psite<P>(p_ref_.pg(), id_); - // Update p_. - p_ = p_ref_.pg().point_from_id(id_); + mln_precondition(exact(*this).is_valid()); + return psite_; } template <typename P, typename E> inline - const P& - graph_vicinity_piter_<P, E>::to_point() const + const graph_psite<P>& + graph_vicinity_piter_<P, E>::p_ref() const { - return p_; + return p_ref_; } template <typename P, typename E> inline - const graph_psite<P>& - graph_vicinity_piter_<P, E>::to_psite() const + const p_graph<P>& + graph_vicinity_piter_<P, E>::pg() const { - return psite_; + return p_ref_.pg(); } template <typename P, typename E> inline - graph_vicinity_piter_<P, E>::operator graph_psite<P>() const + std::set<util::node_id>& + graph_vicinity_piter_<P, E>::sites() { - mln_precondition(is_valid()); - return psite_; + return sites_; } template <typename P, typename E> Index: mln/core/graph_window_piter.hh --- mln/core/graph_window_piter.hh (revision 1904) +++ mln/core/graph_window_piter.hh (working copy) @@ -31,17 +31,6 @@ /// \file mln/core/graph_window_piter.hh /// \brief Definition of a point iterator on a graph window. -/* FIXME: Factor those classes: - - - mln::graph_window_fwd_piter - - mln::graph_neighborhood_fwd_piter - - mln::line_graph_window_fwd_piter - - mln::line_graph_neighborhood_fwd_piter. - - mln::graph_window_bkd_piter - - mln::graph_neighborhood_bkd_piter - - mln::line_graph_window_bkd_piter - - mln::line_graph_neighborhood_bkd_piter. */ - # include <mln/core/internal/graph_vicinity_piter.hh> /* FIXME: Due to the poor interface of mln::p_graph and @@ -72,23 +61,25 @@ /// Manipulation. /// \{ + /// Test if the iterator is valid. + bool is_valid() const; + /// Invalidate the iterator. + void invalidate(); /// Start an iteration. void start(); + /// Go to the next point. void next_(); - /// \} - - /// Internals, used by the window. - /// \{ - /// Set the iterator to the first site of the graph. - void first_(); - /// Advance the position of the iterator by one step. - void step_(); + /// Update the internal data of the iterator. + void update_(); /// \} private: /// The window. const W& win_; + + /// An iterator on the set of adjacent vertices. + typename super_::sites_t::const_iterator i_; }; @@ -113,23 +104,25 @@ /// Manipulation. /// \{ + /// Test if the iterator is valid. + bool is_valid() const; + /// Invalidate the iterator. + void invalidate(); /// Start an iteration. void start(); + /// Go to the next point. void next_(); - /// \} - - /// Internals, used by the window. - /// \{ - /// Set the iterator to the first site of the graph. - void first_(); - /// Advance the position of the iterator by one step. - void step_(); + /// Update the internal data of the iterator. + void update_(); /// \} private: /// The window. const W& win_; + + /// An iterator on the set of adjacent vertices. + typename super_::sites_t::const_reverse_iterator i_; }; @@ -148,42 +141,70 @@ : super_(p_ref), win_(exact(win)) { + // Invalidate i_. + invalidate(); + } + + template <typename P, typename W> + inline + bool + graph_window_fwd_piter<P, W>::is_valid() const + { + return + // The reference point must be valid... + this->p_ref_.is_valid() + // ...and must not have changed since the window has been computed... + && this->p_ref_ == this->saved_p_ref_ + // ...and the iterator i_ must point a valid value. + && i_ != this->sites_.end(); } template <typename P, typename W> inline void - graph_window_fwd_piter<P, W>::start() + graph_window_fwd_piter<P, W>::invalidate() { - this->win_.start(*this); - if (this->is_valid()) - this->update_(); + i_ = this->sites_.end(); } template <typename P, typename W> inline void - graph_window_fwd_piter<P, W>::next_() + graph_window_fwd_piter<P, W>::start() { - this->win_.next_(*this); - if (this->is_valid()) - this->update_(); + mln_precondition(this->p_ref_.is_valid()); + // Update the sites, if needed. + if (!this->saved_p_ref_.is_valid() || this->p_ref_ != this->saved_p_ref_) + { + this->saved_p_ref_ = this->p_ref_; + win_.compute_sites_(*this); + } + i_ = this->sites_.begin(); + // FIXME: We might move the is_valid condition within update_. + if (is_valid()) + update_(); } template <typename P, typename W> inline void - graph_window_fwd_piter<P, W>::first_() + graph_window_fwd_piter<P, W>::next_() { - this->id_ = 0; + // Ensure the p_ref_ has not changed. + mln_precondition(this->p_ref_ == this->saved_p_ref_); + ++i_; + // FIXME: We might move the is_valid condition within update_. + if (is_valid()) + update_(); } template <typename P, typename W> inline void - graph_window_fwd_piter<P, W>::step_() + graph_window_fwd_piter<P, W>::update_() { - ++this->id_; + // Update psite_. + this->psite_ = graph_psite<P>(this->pg(), *i_); } @@ -199,42 +220,70 @@ : super_(p_ref), win_(exact(win)) { + // Invalidate i_. + invalidate(); + } + + template <typename P, typename W> + inline + bool + graph_window_bkd_piter<P, W>::is_valid() const + { + return + // The reference point must be valid... + this->p_ref_.is_valid() + // ...and must not have changed since the window has been computed... + && this->p_ref_ == this->saved_p_ref_ + // ...and the iterator i_ must point a valid value. + && i_ != this->sites_.rend(); } template <typename P, typename W> inline void - graph_window_bkd_piter<P, W>::start() + graph_window_bkd_piter<P, W>::invalidate() { - this->win_.start(*this); - if (this->is_valid()) - this->update_(); + i_ = this->sites_.rend(); } template <typename P, typename W> inline void - graph_window_bkd_piter<P, W>::next_() + graph_window_bkd_piter<P, W>::start() + { + mln_precondition(this->p_ref_.is_valid()); + // Update the sites, if needed. + if (!this->saved_p_ref_.is_valid() || this->p_ref_ != this->saved_p_ref_) { - this->win_.next_(*this); - if (this->is_valid()) - this->update_(); + this->saved_p_ref_ = this->p_ref_; + win_.compute_sites_(*this); + } + i_ = this->sites_.rbegin(); + // FIXME: We might move the is_valid condition within update_. + if (is_valid()) + update_(); } template <typename P, typename W> inline void - graph_window_bkd_piter<P, W>::first_() + graph_window_bkd_piter<P, W>::next_() { - this->id_ = this->p_ref_.pg().gr_->nnodes() - 1; + // Ensure the p_ref_ has not changed. + mln_precondition(this->p_ref_ == this->saved_p_ref_); + ++i_; + // FIXME: We might move the is_valid condition within update_. + if (is_valid()) + update_(); } template <typename P, typename W> inline void - graph_window_bkd_piter<P, W>::step_() + graph_window_bkd_piter<P, W>::update_() { - --this->id_; + // Update psite_. + this->psite_ = graph_psite<P>(this->pg(), *i_); } # endif // ! MLN_INCLUDE_ONLY Index: mln/core/graph_neighborhood_piter.hh --- mln/core/graph_neighborhood_piter.hh (revision 1904) +++ mln/core/graph_neighborhood_piter.hh (working copy) @@ -31,17 +31,6 @@ /// \file mln/core/graph_neighborhood_piter.hh /// \brief Definition of a point iterator on a graph neighborhood. -/* FIXME: Factor those classes: - - - mln::graph_window_fwd_piter - - mln::graph_neighborhood_fwd_piter - - mln::line_graph_window_fwd_piter - - mln::line_graph_neighborhood_fwd_piter. - - mln::graph_window_bkd_piter - - mln::graph_neighborhood_bkd_piter - - mln::line_graph_window_bkd_piter - - mln::line_graph_neighborhood_bkd_piter. */ - # include <mln/core/internal/graph_vicinity_piter.hh> /* FIXME: Due to the poor interface of mln::p_graph and @@ -73,23 +62,25 @@ /// Manipulation. /// \{ + /// Test if the iterator is valid. + bool is_valid() const; + /// Invalidate the iterator. + void invalidate(); /// Start an iteration. void start(); + /// Go to the next point. void next_(); - /// \} - - /// Internals, used by the neighborhood. - /// \{ - /// Set the iterator to the first site of the graph. - void first_(); - /// Advance the position of the iterator by one step. - void step_(); + /// Update the internal data of the iterator. + void update_(); /// \} private: /// The neighborhood. const N& nbh_; + + /// An iterator on the set of adjacent edges. + typename super_::sites_t::const_iterator i_; }; @@ -115,23 +106,25 @@ /// Manipulation. /// \{ + /// Test if the iterator is valid. + bool is_valid() const; + /// Invalidate the iterator. + void invalidate(); /// Start an iteration. void start(); + /// Go to the next point. void next_(); - /// \} - - /// Internals, used by the neighborhood. - /// \{ - /// Set the iterator to the first site of the graph. - void first_(); - /// Advance the position of the iterator by one step. - void step_(); + /// Update the internal data of the iterator. + void update_(); /// \} private: /// The neighborhood. const N& nbh_; + + /// An iterator on the set of adjacent edges. + typename super_::sites_t::const_reverse_iterator i_; }; @@ -150,42 +143,71 @@ : super_(p_ref), nbh_(exact(nbh)) { + // Invalidate i_. + invalidate(); + } + + template <typename P, typename N> + inline + bool + graph_neighborhood_fwd_piter<P, N>::is_valid() const + { + return + // The reference point must be valid... + this->p_ref_.is_valid() + // ...and must not have changed since the neighborhood has been + // computed... + && this->p_ref_ == this->saved_p_ref_ + // ...and the iterator i_ must point a valid value. + && i_ != this->sites_.end(); } template <typename P, typename N> inline void - graph_neighborhood_fwd_piter<P, N>::start() + graph_neighborhood_fwd_piter<P, N>::invalidate() { - this->nbh_.start(*this); - if (this->is_valid()) - this->update_(); + i_ = this->sites_.end(); } template <typename P, typename N> inline void - graph_neighborhood_fwd_piter<P, N>::next_() + graph_neighborhood_fwd_piter<P, N>::start() { - this->nbh_.next_(*this); - if (this->is_valid()) - this->update_(); + mln_precondition(this->p_ref_.is_valid()); + // Update the neighbors, if needed. + if (!this->saved_p_ref_.is_valid() || this->p_ref_ != this->saved_p_ref_) + { + this->saved_p_ref_ = this->p_ref_; + nbh_.compute_sites_(*this); + } + i_ = this->sites_.begin(); + // FIXME: We might move the is_valid condition within update_. + if (is_valid()) + update_(); } template <typename P, typename N> inline void - graph_neighborhood_fwd_piter<P, N>::first_() + graph_neighborhood_fwd_piter<P, N>::next_() { - this->id_ = 0; + // Ensure the p_ref_ has not changed. + mln_precondition(this->p_ref_ == this->saved_p_ref_); + ++i_; + // FIXME: We might move the is_valid condition within update_. + if (is_valid()) + update_(); } template <typename P, typename N> inline void - graph_neighborhood_fwd_piter<P, N>::step_() + graph_neighborhood_fwd_piter<P, N>::update_() { - ++this->id_; + // Update psite_. + this->psite_ = graph_psite<P>(this->pg(), *i_); } @@ -201,42 +223,71 @@ : super_(p_ref), nbh_(exact(nbh)) { + // Invalidate i_. + invalidate(); + } + + template <typename P, typename N> + inline + bool + graph_neighborhood_bkd_piter<P, N>::is_valid() const + { + return + // The reference point must be valid... + this->p_ref_.is_valid() + // ...and must not have changed since the neighborhood has been + // computed... + && this->p_ref_ == this->saved_p_ref_ + // ...and the iterator i_ must point a valid value. + && i_ != this->sites_.rend(); } template <typename P, typename N> inline void - graph_neighborhood_bkd_piter<P, N>::start() + graph_neighborhood_bkd_piter<P, N>::invalidate() { - this->nbh_.start(*this); - if (this->is_valid()) - this->update_(); + i_ = this->sites_.rend(); } template <typename P, typename N> inline void - graph_neighborhood_bkd_piter<P, N>::next_() + graph_neighborhood_bkd_piter<P, N>::start() + { + mln_precondition(this->p_ref_.is_valid()); + // Update the neighbors, if needed. + if (!this->saved_p_ref_.is_valid() || this->p_ref_ != this->saved_p_ref_) { - this->nbh_.next_(*this); - if (this->is_valid()) - this->update_(); + this->saved_p_ref_ = this->p_ref_; + nbh_.compute_sites_(*this); + } + i_ = this->sites_.rbegin(); + // FIXME: We might move the is_valid condition within update_. + if (is_valid()) + update_(); } template <typename P, typename N> inline void - graph_neighborhood_bkd_piter<P, N>::first_() + graph_neighborhood_bkd_piter<P, N>::next_() { - this->id_ = this->p_ref_.pg().gr_->nnodes() - 1; + // Ensure the p_ref_ has not changed. + mln_precondition(this->p_ref_ == this->saved_p_ref_); + ++i_; + // FIXME: We might move the is_valid condition within update_. + if (is_valid()) + update_(); } template <typename P, typename N> inline void - graph_neighborhood_bkd_piter<P, N>::step_() + graph_neighborhood_bkd_piter<P, N>::update_() { - --this->id_; + // Update psite_. + this->psite_ = graph_psite<P>(this->pg(), *i_); } # endif // ! MLN_INCLUDE_ONLY Index: mln/core/graph_elt_window.hh --- mln/core/graph_elt_window.hh (revision 1904) +++ mln/core/graph_elt_window.hh (working copy) @@ -40,6 +40,10 @@ - mln::line_graph_elt_window - mln::line_graph_elt_neighborhood. */ +/* FIXME: Due to the poor interface of mln::p_line_graph and + mln::util::graph, we show to much implementation details here. + Enrich their interfaces to avoid that. */ + # include <mln/core/concept/window.hh> # include <mln/core/graph_psite.hh> # include <mln/core/graph_window_piter.hh> @@ -65,6 +69,9 @@ typedef P point; /// The type of psite corresponding to the window. typedef graph_psite<P> psite; + // The type of the set of window sites (node ids adjacent to the + // reference psite). + typedef std::set<util::node_id> sites_t; // FIXME: This is a dummy value. typedef void dpoint; @@ -81,17 +88,11 @@ typedef fwd_qiter qiter; /// \} - /// Construct an elementary graph window. - graph_elt_window(); - /// Services for iterators. /// \{ - /// Move \a piter to the beginning of the iteration on this window. + /// Compute the set of sites for this window around \a piter. template <typename Piter> - void start(Point_Iterator<Piter>& piter) const; - /// Move \a piter to the next site on this window. - template <typename Piter> - void next_(Point_Iterator<Piter>& piter) const; + void compute_sites_(Point_Iterator<Piter>& piter) const; /// \} /// Interface of the concept Window. @@ -125,37 +126,32 @@ # ifndef MLN_INCLUDE_ONLY template <typename P> - inline - graph_elt_window<P>::graph_elt_window() - { - } - - template <typename P> template <typename Piter> inline void - graph_elt_window<P>::start(Point_Iterator<Piter>& piter_) const + graph_elt_window<P>::compute_sites_(Point_Iterator<Piter>& piter_) const { Piter& piter = exact(piter_); - piter.first_(); - if (!piter.adjacent_or_equal_to_p_ref_()) - next_(piter); + util::node_id ref_node_id = piter.p_ref().id(); + const util::node<P>& ref_node = piter.pg().gr_->node(ref_node_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 + 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); } - - template <typename P> - template <typename Piter> - inline - void - graph_elt_window<P>::next_(Point_Iterator<Piter>& piter_) const - { - Piter& piter = exact(piter_); - /* 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. */ - do - piter.step_(); - while (piter.is_valid() && !piter.adjacent_or_equal_to_p_ref_()); } template <typename P> Index: mln/core/graph_elt_neighborhood.hh --- mln/core/graph_elt_neighborhood.hh (revision 1904) +++ mln/core/graph_elt_neighborhood.hh (working copy) @@ -40,6 +40,10 @@ - mln::line_graph_elt_window - mln::line_graph_elt_neighborhood. */ +/* FIXME: Due to the poor interface of mln::p_line_graph and + mln::util::graph, we show to much implementation details here. + Enrich their interfaces to avoid that. */ + # include <mln/core/concept/neighborhood.hh> # include <mln/core/graph_psite.hh> # include <mln/core/graph_neighborhood_piter.hh> @@ -66,6 +70,9 @@ typedef P point; /// The type of psite corresponding to the neighborhood. typedef graph_psite<P> psite; + // The type of the set of neighbors (node ids adjacent to the + // reference psite). + typedef std::set<util::node_id> sites_t; // FIXME: This is a dummy value. typedef void dpoint; @@ -84,12 +91,9 @@ /// Services for iterators. /// \{ - /// Move \a piter to the beginning of the iteration on this neighborhood. - template <typename Piter> - void start(Point_Iterator<Piter>& piter) const; - /// Move \a piter to the next site on this neighborhood. + /// Compute the set of sites for this neighborhood around \a piter. template <typename Piter> - void next_(Point_Iterator<Piter>& piter) const; + void compute_sites_(Point_Iterator<Piter>& piter) const; /// \} }; @@ -100,28 +104,30 @@ template <typename Piter> inline void - graph_elt_neighborhood<P>::start(Point_Iterator<Piter>& piter_) const + graph_elt_neighborhood<P>::compute_sites_(Point_Iterator<Piter>& piter_) const { Piter& piter = exact(piter_); - piter.first_(); - if (!piter.adjacent_to_p_ref_()) - next_(piter); - } - - template <typename P> - template <typename Piter> - inline - void - graph_elt_neighborhood<P>::next_(Point_Iterator<Piter>& piter_) const + util::node_id ref_node_id = piter.p_ref().id(); + const util::node<P>& ref_node = piter.pg().gr_->node(ref_node_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) { - Piter& piter = exact(piter_); - /* 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. */ - do - piter.step_(); - while (piter.is_valid() && !piter.adjacent_to_p_ref_()); + util::node_id n1 = piter.pg().gr_->edges()[*e]->n1(); + // We explicitly enforce that the reference piter node id is + // *not* inserted into SITES. + if (n1 != ref_node_id) + sites.insert(n1); + util::node_id n2 = piter.pg().gr_->edges()[*e]->n2(); + // Likewise. + if (n2 != ref_node_id) + sites.insert(n2); + } } # endif // ! MLN_INCLUDE_ONLY