[Olena-patches] 1896: Speed up iterations on line graph windows.

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 line graph windows. * mln/core/line_graph_window_piter.hh (mln::line_graph_window_fwd_piter<P>::sites_t) (mln::line_graph_window_bkd_piter<P>::sites_t): New typedefs. (mln::line_graph_window_fwd_piter<P>::adjacent_or_equal_to_p_ref_) (mln::line_graph_window_bkd_piter<P>::adjacent_or_equal_to_p_ref_) (mln::line_graph_window_fwd_piter<P>::first_) (mln::line_graph_window_bkd_piter<P>::first_) (mln::line_graph_window_fwd_piter<P>::step_) (mln::line_graph_window_bkd_piter<P>::step_) (mln::line_graph_window_fwd_piter<P>::id_) (mln::line_graph_window_bkd_piter<P>::id_): Remove. (mln::line_graph_window_fwd_piter<P>::p_ref) (mln::line_graph_window_bkd_piter<P>::p_ref) (mln::line_graph_window_fwd_piter<P>::plg) (mln::line_graph_window_bkd_piter<P>::plg) (mln::line_graph_window_fwd_piter<P>::sites) (mln::line_graph_window_bkd_piter<P>::sites): New accessors. (mln::line_graph_window_fwd_piter<P>::saved_p_ref_) (mln::line_graph_window_bkd_piter<P>::saved_p_ref_) (mln::line_graph_window_fwd_piter<P>::sites_) (mln::line_graph_window_bkd_piter<P>::sites_) (mln::line_graph_window_fwd_piter<P>::i_) (mln::line_graph_window_bkd_piter<P>::i_): New attributes. (mln::line_graph_window_fwd_piter<P, W>::is_valid) (mln::line_graph_window_bkd_piter<P, W>::is_valid) (mln::line_graph_window_fwd_piter<P, W>::invalidate) (mln::line_graph_window_bkd_piter<P, W>::invalidate) (mln::line_graph_window_fwd_piter<P, W>::start) (mln::line_graph_window_bkd_piter<P, W>::start) (mln::line_graph_window_fwd_piter<P, W>::next) (mln::line_graph_window_bkd_piter<P, W>::next): Change the algorithms used in these routines, so that they use a list of computed window sites (new member sites_) instead of iterating over the whole set of edges. (mln::line_graph_window_fwd_piter<P, W>::update_) (mln::line_graph_window_bkd_piter<P, W>::update_): Adjust. * mln/core/line_graph_elt_window.hh: Catch up with the new interface of piters on line graph windows. (mln::line_graph_elt_window<P>::sites_t): New typedef. (mln::line_graph_elt_window<P>::line_graph_elt_window): Remove useless ctor. (mln::line_graph_elt_window<P>::start) (mln::line_graph_elt_window<P>::next_): Remove methods. (mln::line_graph_elt_window<P>::compute_sites_): New method. * mln/core/line_graph_neighborhood_piter.hh (line_graph_neighborhood_fwd_piter<P, N>::adjacent_or_equal_to_p_ref_) (line_graph_neighborhood_bkd_piter<P, N>::adjacent_or_equal_to_p_ref_): Remove spurious method declarations. line_graph_elt_window.hh | 60 +++------ line_graph_neighborhood_piter.hh | 4 line_graph_window_piter.hh | 256 ++++++++++++++++++--------------------- 3 files changed, 146 insertions(+), 174 deletions(-) Index: mln/core/line_graph_window_piter.hh --- mln/core/line_graph_window_piter.hh (revision 1895) +++ mln/core/line_graph_window_piter.hh (working copy) @@ -80,6 +80,9 @@ // FIXME: Dummy typedef. typedef void mesh; + // The type of the set of window sites (adjacent edge ids). + typedef std::set<util::edge_id> sites_t; + public: /// Construction. /// \{ @@ -99,8 +102,6 @@ /// Go to the next point. void next_(); - /// 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_(); /// \} @@ -114,27 +115,30 @@ /// Convert the iterator into a line graph psite. operator psite() const; + /// Return the reference psite. + const psite& p_ref() const; + /// Return the mln::p_line_graph corresponding to this piter. + const p_line_graph<P>& plg() const; + /// Return the set of sites (adjacent edge ids). + sites_t& sites(); + /// Read-only access to the \a i-th coordinate. coord operator[](unsigned i) const; /// \} - /// Internals, used by the window. - /// \{ - public: - /// Set the iterator to the first site of the graph. - void first_(); - /// Advance the position of the iterator by one step. - void step_(); - - /// An internal iterator on the set of edges of the underlying graph. - util::edge_id id_; - /// \} - private: /// The window. const W& win_; /// The ``central'' psite of the window. const psite& p_ref_; + + /// 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_; + /// An iterator on the set of adjacent edges. + sites_t::const_iterator i_; + /// The psite corresponding to this iterator. psite psite_; /// The point corresponding to this iterator. @@ -176,6 +180,9 @@ // FIXME: Dummy typedef. typedef void mesh; + // The type of the set of window sites (adjacent edge ids). + typedef std::set<util::edge_id> sites_t; + public: /// Construction. /// \{ @@ -195,8 +202,6 @@ /// Go to the next point. void next_(); - /// 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_(); /// \} @@ -210,27 +215,30 @@ /// Convert the iterator into a line graph psite. operator psite() const; + /// Return the reference psite. + const psite& p_ref() const; + /// Return the mln::p_line_graph corresponding to this piter. + const p_line_graph<P>& plg() const; + /// Return the set of sites (adjacent edge ids). + sites_t& sites(); + /// Read-only access to the \a i-th coordinate. coord operator[](unsigned i) const; /// \} - /// Internals, used by the window. - /// \{ - public: - /// Set the iterator to the first site of the graph. - void first_(); - /// Advance the position of the iterator by one step. - void step_(); - - /// An internal iterator on the set of edges of the underlying graph. - util::edge_id id_; - /// \} - private: /// The window. const W& win_; /// The ``central'' psite of the window. const psite& p_ref_; + + /// 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_; + /// An iterator on the set of adjacent edges. + sites_t::const_reverse_iterator i_; + /// The psite corresponding to this iterator. psite psite_; /// The point corresponding to this iterator. @@ -275,10 +283,13 @@ bool line_graph_window_fwd_piter<P, W>::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_.plg().gr_->nedges(); + return + // The reference point must be valid... + p_ref_.is_valid() + // ...and must not have changed since the window has been computed... + && p_ref_ == saved_p_ref_ + // ...and the iterator i_ must point a valid value. + && i_ != sites_.end(); } template <typename P, typename W> @@ -286,7 +297,7 @@ void line_graph_window_fwd_piter<P, W>::invalidate() { - id_ = -1; + i_ = sites_.end(); } template <typename P, typename W> @@ -294,7 +305,15 @@ void line_graph_window_fwd_piter<P, W>::start() { - win_.start(*this); + mln_precondition(p_ref_.is_valid()); + // Update the sites, if needed. + if (!saved_p_ref_.is_valid() || p_ref_ != saved_p_ref_) + { + saved_p_ref_ = p_ref_; + win_.compute_sites_(*this); + } + i_ = sites_.begin(); + // FIXME: We might move the is_valid condition within update_. if (is_valid()) update_(); } @@ -304,7 +323,10 @@ void line_graph_window_fwd_piter<P, W>::next_() { - win_.next_(*this); + // Ensure the p_ref_ has not changed. + mln_precondition(p_ref_ == saved_p_ref_); + ++i_; + // FIXME: We might move the is_valid condition within update_. if (is_valid()) update_(); } @@ -312,84 +334,58 @@ template <typename P, typename W> inline void - line_graph_window_fwd_piter<P, W>::first_() + line_graph_window_fwd_piter<P, W>::update_() { - id_ = 0; + // Update psite_. + psite_ = line_graph_psite<P>(plg(), *i_); } template <typename P, typename W> inline - void - line_graph_window_fwd_piter<P, W>::step_() + const P& + line_graph_window_fwd_piter<P, W>::to_point() const { - ++id_; + return p_; } - template <typename P, typename W> inline - bool - line_graph_window_fwd_piter<P, W>::adjacent_or_equal_to_p_ref_() const + const line_graph_psite<P>& + line_graph_window_fwd_piter<P, W>::to_psite() const { - // Check wether the iterator points to P_REF_. - if (id_ == p_ref_.id()) - return true; - - // Check whether the iterator is among the neighbors of P_REF_. - { - // Paranoid assertion. - assert (p_ref_.id() < p_ref_.plg().gr_->nedges()); - /* FIXME: We should have a convenient shortcut for these - repetitive accesses to p_ref_.plg().gr_ (e.g., a method gr() - or g() in this class. */ - const util::tracked_ptr<typename p_line_graph<P>::graph>& gr = - p_ref_.plg().gr_; - // Check whether the edge this iterator points to is adjacent to - // the one p_ref points to, by comparing their ajacent nodes. - /* FIXME: This is too low-level. Yet another service the graph - // should provide. */ - if (gr->edge(id_).n1() == gr->edge(p_ref_.id()).n1() || - gr->edge(id_).n1() == gr->edge(p_ref_.id()).n2() || - gr->edge(id_).n2() == gr->edge(p_ref_.id()).n1() || - gr->edge(id_).n2() == gr->edge(p_ref_.id()).n2()) - return true; - } - - // Otherwise, the iterator is not adjacent to P_REF_. - return false; + return psite_; } template <typename P, typename W> inline - void - line_graph_window_fwd_piter<P, W>::update_() + line_graph_window_fwd_piter<P, W>::operator line_graph_psite<P> () const { - // Update psite_. - psite_ = line_graph_psite<P>(p_ref_.plg(), id_); + mln_precondition(is_valid()); + return psite_; } template <typename P, typename W> inline - const P& - line_graph_window_fwd_piter<P, W>::to_point() const + const line_graph_psite<P>& + line_graph_window_fwd_piter<P, W>::p_ref() const { - return p_; + return p_ref_; } template <typename P, typename W> inline - const line_graph_psite<P>& - line_graph_window_fwd_piter<P, W>::to_psite() const + const p_line_graph<P>& + line_graph_window_fwd_piter<P, W>::plg() const { - return psite_; + return p_ref_.plg(); } template <typename P, typename W> inline - line_graph_window_fwd_piter<P, W>::operator line_graph_psite<P> () const + std::set<util::edge_id>& + line_graph_window_fwd_piter<P, W>::sites() { - mln_precondition(is_valid()); - return psite_; + return sites_; } template <typename P, typename W> @@ -434,10 +430,13 @@ bool line_graph_window_bkd_piter<P, W>::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_.plg().gr_->nedges(); + return + // The reference point must be valid... + p_ref_.is_valid() + // ...and must not have changed since the window has been computed... + && p_ref_ == saved_p_ref_ + // ...and the iterator i_ must point a valid value. + && i_ != sites_.rend(); } template <typename P, typename W> @@ -445,7 +444,7 @@ void line_graph_window_bkd_piter<P, W>::invalidate() { - id_ = -1; + i_ = sites_.rend(); } template <typename P, typename W> @@ -453,7 +452,15 @@ void line_graph_window_bkd_piter<P, W>::start() { - win_.start(*this); + mln_precondition(p_ref_.is_valid()); + // Update the sites, if needed. + if (!saved_p_ref_.is_valid() || p_ref_ != saved_p_ref_) + { + saved_p_ref_ = p_ref_; + win_.compute_sites_(*this); + } + i_ = sites_.rbegin(); + // FIXME: We might move the is_valid condition within update_. if (is_valid()) update_(); } @@ -463,7 +470,10 @@ void line_graph_window_bkd_piter<P, W>::next_() { - win_.next_(*this); + // Ensure the p_ref_ has not changed. + mln_precondition(p_ref_ == saved_p_ref_); + ++i_; + // FIXME: We might move the is_valid condition within update_. if (is_valid()) update_(); } @@ -471,84 +481,58 @@ template <typename P, typename W> inline void - line_graph_window_bkd_piter<P, W>::first_() + line_graph_window_bkd_piter<P, W>::update_() { - id_ = p_ref_.plg().gr_->nedges() - 1; + // Update psite_. + psite_ = line_graph_psite<P>(plg(), *i_); } template <typename P, typename W> inline - void - line_graph_window_bkd_piter<P, W>::step_() + const P& + line_graph_window_bkd_piter<P, W>::to_point() const { - --id_; + return p_; } - template <typename P, typename W> inline - bool - line_graph_window_bkd_piter<P, W>::adjacent_or_equal_to_p_ref_() const + const line_graph_psite<P>& + line_graph_window_bkd_piter<P, W>::to_psite() const { - // Check wether the iterator points to P_REF_. - if (id_ == p_ref_.id()) - return true; - - // Check whether the iterator is among the neighbors of P_REF_. - { - // Paranoid assertion. - assert (p_ref_.id() < p_ref_.plg().gr_->nedges()); - /* FIXME: We should have a convenient shortcut for these - repetitive accesses to p_ref_.plg().gr_ (e.g., a method gr() - or g() in this class. */ - const util::tracked_ptr<typename p_line_graph<P>::graph>& gr = - p_ref_.plg().gr_; - // Check whether the edge this iterator points to is adjacent to - // the one p_ref points to, by comparing their ajacent nodes. - /* FIXME: This is too low-level. Yet another service the graph - // should provide. */ - if (gr->edge(id_).n1() == gr->edge(p_ref_.id()).n1() || - gr->edge(id_).n1() == gr->edge(p_ref_.id()).n2() || - gr->edge(id_).n2() == gr->edge(p_ref_.id()).n1() || - gr->edge(id_).n2() == gr->edge(p_ref_.id()).n2()) - return true; - } - - // Otherwise, the iterator is not adjacent to P_REF_. - return false; + return psite_; } template <typename P, typename W> inline - void - line_graph_window_bkd_piter<P, W>::update_() + line_graph_window_bkd_piter<P, W>::operator line_graph_psite<P> () const { - // Update psite_. - psite_ = line_graph_psite<P>(p_ref_.plg(), id_); + mln_precondition(is_valid()); + return psite_; } template <typename P, typename W> inline - const P& - line_graph_window_bkd_piter<P, W>::to_point() const + const line_graph_psite<P>& + line_graph_window_bkd_piter<P, W>::p_ref() const { - return p_; + return p_ref_; } template <typename P, typename W> inline - const line_graph_psite<P>& - line_graph_window_bkd_piter<P, W>::to_psite() const + const p_line_graph<P>& + line_graph_window_bkd_piter<P, W>::plg() const { - return psite_; + return p_ref_.plg(); } template <typename P, typename W> inline - line_graph_window_bkd_piter<P, W>::operator line_graph_psite<P> () const + std::set<util::edge_id>& + line_graph_window_bkd_piter<P, W>::sites() { - mln_precondition(is_valid()); - return psite_; + return sites_; } template <typename P, typename W> Index: mln/core/line_graph_elt_window.hh --- mln/core/line_graph_elt_window.hh (revision 1895) +++ mln/core/line_graph_elt_window.hh (working copy) @@ -65,6 +65,9 @@ typedef P point; /// The type of psite corresponding to the window. typedef line_graph_psite<P> psite; + // The type of the set of window sites (edge ids adjacent to the + // reference psite). + typedef std::set<util::edge_id> sites_t; // FIXME: This is a dummy value. typedef void dpoint; @@ -81,17 +84,10 @@ typedef fwd_qiter qiter; /// \} - /// Construct an elementary line_graph window. - line_graph_elt_window(); - /// Services for iterators. /// \{ - /// Move \a piter to the beginning of the iteration on this window. - 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 +121,33 @@ # ifndef MLN_INCLUDE_ONLY template <typename P> - inline - line_graph_elt_window<P>::line_graph_elt_window() - { - } - - template <typename P> - template <typename Piter> - inline - void - line_graph_elt_window<P>::start(Point_Iterator<Piter>& piter_) const - { - Piter& piter = exact(piter_); - piter.first_(); - if (!piter.adjacent_or_equal_to_p_ref_()) - next_(piter); - } - - template <typename P> template <typename Piter> inline void - line_graph_elt_window<P>::next_(Point_Iterator<Piter>& piter_) const + line_graph_elt_window<P>::compute_sites_(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_()); + 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. */ + // Add the reference piter itself. + sites.insert(piter.p_ref().id()); + // Ajacent edges connected through node 1. + // FIXME: Far too low-level. + util::node_id id1 = piter.p_ref().first_id(); + const util::node<P>& node1 = piter.plg().gr_->node(id1); + for (std::vector<util::edge_id>::const_iterator e = + node1.edges.begin(); e != node1.edges.end(); ++e) + sites.insert(*e); + // Ajacent edges connected through node 2. + // FIXME: Likewise. + util::node_id id2 = piter.p_ref().second_id(); + const util::node<P>& node2 = piter.plg().gr_->node(id2); + for (std::vector<util::edge_id>::const_iterator e = + node2.edges.begin(); e != node2.edges.end(); ++e) + sites.insert(*e); } template <typename P> Index: mln/core/line_graph_neighborhood_piter.hh --- mln/core/line_graph_neighborhood_piter.hh (revision 1895) +++ mln/core/line_graph_neighborhood_piter.hh (working copy) @@ -104,8 +104,6 @@ /// Go to the next point. void next_(); - /// 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_(); /// \} @@ -208,8 +206,6 @@ /// Go to the next point. void next_(); - /// 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_(); /// \}