[Olena-patches] 1855: Speed up iterations on line graph 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 line graph neighborhoods. * mln/core/line_graph_neighborhood_piter.hh (mln::line_graph_neighborhood_fwd_piter::neighbors_t) (mln::line_graph_neighborhood_bkd_piter::neighbors_t): New typedefs. (mln::line_graph_neighborhood_fwd_piter::first_) (mln::line_graph_neighborhood_fwd_piter::step_) (mln::line_graph_neighborhood_fwd_piter::adjacent_or_equal_to_p_ref_) (mln::line_graph_neighborhood_bkd_piter::first_) (mln::line_graph_neighborhood_bkd_piter::step_) (mln::line_graph_neighborhood_bkd_piter::adjacent_or_equal_to_p_ref_): Remove methods. (mln::line_graph_neighborhood_fwd_piter::id_) (mln::line_graph_neighborhood_bkd_piter::id_): Remove attributes. (mln::line_graph_neighborhood_fwd_piter::saved_p_ref_) (mln::line_graph_neighborhood_fwd_piter::neighbors_) (mln::line_graph_neighborhood_fwd_piter::i_) (mln::line_graph_neighborhood_bkd_piter::saved_p_ref_) (mln::line_graph_neighborhood_bkd_piter::neighbors_) (mln::line_graph_neighborhood_bkd_piter::i_): New attributes. (line_graph_neighborhood_fwd_piter) (line_graph_neighborhood_bkd_piter): Adjust ctors. (mln::line_graph_neighborhood_fwd_piter::p_ref) (mln::line_graph_neighborhood_fwd_piter::plg) (mln::line_graph_neighborhood_fwd_piter::neighbors) (mln::line_graph_neighborhood_bkd_piter::p_ref) (mln::line_graph_neighborhood_bkd_piter::plg) (mln::line_graph_neighborhood_bkd_piter::neighbors): New accessors. (mln::line_graph_neighborhood_fwd_piter::is_valid) (mln::line_graph_neighborhood_fwd_piter::invalidate) (mln::line_graph_neighborhood_fwd_piter::start) (mln::line_graph_neighborhood_fwd_piter::next_) (mln::line_graph_neighborhood_bkd_piter::is_valid) (mln::line_graph_neighborhood_bkd_piter::invalidate) (mln::line_graph_neighborhood_bkd_piter::start) (mln::line_graph_neighborhood_bkd_piter::next_): Change the algorithms used in these routines, so that they use a list of computed neighbors (new member neighbors_) instead of iterating over the whole set of edges. (mln::line_graph_neighborhood_fwd_piter::update_) (mln::line_graph_neighborhood_bkd_piter::update_): Adjust. * mln/core/line_graph_elt_neighborhood.hh: Catch up with the new interface of piters on line graph neighborhoods. (mln::line_graph_elt_neighborhood::neighbors_t): New typedef. (mln::line_graph_elt_neighborhood::start) (mln::line_graph_elt_neighborhood::next_): Remove methods. (mln::line_graph_elt_neighborhood::compute_neighbors_): New method. line_graph_elt_neighborhood.hh | 58 ++++---- line_graph_neighborhood_piter.hh | 262 ++++++++++++++++++--------------------- 2 files changed, 158 insertions(+), 162 deletions(-) Index: mln/core/line_graph_neighborhood_piter.hh --- mln/core/line_graph_neighborhood_piter.hh (revision 1854) +++ mln/core/line_graph_neighborhood_piter.hh (working copy) @@ -42,6 +42,8 @@ - mln::line_graph_window_bkd_piter - mln::line_graph_neighborhood_bkd_piter. */ +# include <set> + # include <mln/core/concept/point_iterator.hh> # include <mln/core/p_line_graph.hh> # include <mln/core/line_graph_psite.hh> @@ -80,6 +82,9 @@ // FIXME: Dummy typedef. typedef void mesh; + // The type of the set of neighbors (adjacent edge ids). + typedef std::set<util::edge_id> neighbors_t; + public: /// Construction. /// \{ @@ -114,28 +119,31 @@ /// 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 neighbors (adjacent edge ids). + neighbors_t& neighbors(); + /// Read-only access to the \a i-th coordinate. // FIXME: Dummy. coord operator[](unsigned i) const; /// \} - /// Internals, used by the neighborhood. - /// \{ - 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 neighborhood. const N& nbh_; /// The ``central'' psite of the neighborhood. 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. + neighbors_t neighbors_; + /// An iterator on the set of adjacent edges. + neighbors_t::const_iterator i_; + /// The psite corresponding to this iterator. psite psite_; /// The point corresponding to this iterator. @@ -178,6 +186,9 @@ // FIXME: Dummy typedef. typedef void mesh; + // The type of the set of neighbors (adjacent edge ids). + typedef std::set<util::edge_id> neighbors_t; + public: /// Construction. /// \{ @@ -212,28 +223,31 @@ /// 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 neighbors (adjacent edge ids). + neighbors_t& neighbors(); + /// Read-only access to the \a i-th coordinate. // FIXME: Dummy. coord operator[](unsigned i) const; /// \} - /// Internals, used by the neighborhood. - /// \{ - 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 neighborhood. const N& nbh_; /// The ``central'' psite of the neighborhood. 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. + neighbors_t neighbors_; + /// An iterator on the set of adjacent edges. + neighbors_t::const_reverse_iterator i_; + /// The psite corresponding to this iterator. psite psite_; /// The point corresponding to this iterator. @@ -260,7 +274,6 @@ | line_graph_neighborhood_fwd_piter<P, N>. | `------------------------------------------*/ - // FIXME: Currently, argument nbh is ignored. template <typename P, typename N> template <typename Pref> inline @@ -271,7 +284,7 @@ // Initialize psite_ to a dummy value. psite_() { - // Invalidate id_. + // Invalidate i_. invalidate(); } @@ -280,10 +293,14 @@ bool line_graph_neighborhood_fwd_piter<P, N>::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 neighborhood has been + // computed... + && p_ref_ == saved_p_ref_ + // ...and the iterator i_ must point a valid value. + && i_ != neighbors_.end(); } template <typename P, typename N> @@ -291,7 +308,7 @@ void line_graph_neighborhood_fwd_piter<P, N>::invalidate() { - id_ = -1; + i_ = neighbors_.end(); } template <typename P, typename N> @@ -299,7 +316,15 @@ void line_graph_neighborhood_fwd_piter<P, N>::start() { - nbh_.start(*this); + mln_precondition(p_ref_.is_valid()); + // Update the neighbors, if needed. + if (!saved_p_ref_.is_valid() || p_ref_ != saved_p_ref_) + { + saved_p_ref_ = p_ref_; + nbh_.compute_neighbors_(*this); + } + i_ = neighbors_.begin(); + // FIXME: We might move the is_valid condition within update_. if (is_valid()) update_(); } @@ -309,7 +334,10 @@ void line_graph_neighborhood_fwd_piter<P, N>::next_() { - nbh_.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_(); } @@ -317,84 +345,58 @@ template <typename P, typename N> inline void - line_graph_neighborhood_fwd_piter<P, N>::first_() + line_graph_neighborhood_fwd_piter<P, N>::update_() { - id_ = 0; + // Update psite_. + psite_ = line_graph_psite<P>(plg(), *i_); } template <typename P, typename N> inline - void - line_graph_neighborhood_fwd_piter<P, N>::step_() + const P& + line_graph_neighborhood_fwd_piter<P, N>::to_point() const { - ++id_; + return p_; } - template <typename P, typename N> inline - bool - line_graph_neighborhood_fwd_piter<P, N>::adjacent_or_equal_to_p_ref_() const + const line_graph_psite<P>& + line_graph_neighborhood_fwd_piter<P, N>::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 N> inline - void - line_graph_neighborhood_fwd_piter<P, N>::update_() + line_graph_neighborhood_fwd_piter<P, N>::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 N> inline - const P& - line_graph_neighborhood_fwd_piter<P, N>::to_point() const + const line_graph_psite<P>& + line_graph_neighborhood_fwd_piter<P, N>::p_ref() const { - return p_; + return p_ref_; } template <typename P, typename N> inline - const line_graph_psite<P>& - line_graph_neighborhood_fwd_piter<P, N>::to_psite() const + const p_line_graph<P>& + line_graph_neighborhood_fwd_piter<P, N>::plg() const { - return psite_; + return p_ref_.plg(); } template <typename P, typename N> inline - line_graph_neighborhood_fwd_piter<P, N>::operator line_graph_psite<P> () const + std::set<util::edge_id>& + line_graph_neighborhood_fwd_piter<P, N>::neighbors() { - mln_precondition(is_valid()); - return psite_; + return neighbors_; } template <typename P, typename N> @@ -420,7 +422,6 @@ | line_graph_neighborhood_bkd_piter<P, N>. | `------------------------------------------*/ - // FIXME: Currently, argument nbh is ignored. template <typename P, typename N> template <typename Pref> inline @@ -431,7 +432,7 @@ // Initialize psite_ to a dummy value. psite_() { - // Invalidate id_. + // Invalidate i_. invalidate(); } @@ -440,10 +441,14 @@ bool line_graph_neighborhood_bkd_piter<P, N>::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 neighborhood has been + // computed... + && p_ref_ == saved_p_ref_ + // ...and the iterator i_ must point a valid value. + && i_ != neighbors_.rend(); } template <typename P, typename N> @@ -451,7 +456,7 @@ void line_graph_neighborhood_bkd_piter<P, N>::invalidate() { - id_ = -1; + i_ = neighbors_.rend(); } template <typename P, typename N> @@ -459,7 +464,15 @@ void line_graph_neighborhood_bkd_piter<P, N>::start() { - nbh_.start(*this); + mln_precondition(p_ref_.is_valid()); + // Update the neighbors, if needed. + if (!saved_p_ref_.is_valid() || p_ref_ != saved_p_ref_) + { + saved_p_ref_ = p_ref_; + nbh_.compute_neighbors_(*this); + } + i_ = neighbors_.rbegin(); + // FIXME: We might move the is_valid condition within update_. if (is_valid()) update_(); } @@ -469,7 +482,10 @@ void line_graph_neighborhood_bkd_piter<P, N>::next_() { - nbh_.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_(); } @@ -477,84 +493,58 @@ template <typename P, typename N> inline void - line_graph_neighborhood_bkd_piter<P, N>::first_() + line_graph_neighborhood_bkd_piter<P, N>::update_() { - id_ = p_ref_.plg().gr_->nedges() - 1; + // Update psite_. + psite_ = line_graph_psite<P>(plg(), *i_); } template <typename P, typename N> inline - void - line_graph_neighborhood_bkd_piter<P, N>::step_() + const P& + line_graph_neighborhood_bkd_piter<P, N>::to_point() const { - --id_; + return p_; } - template <typename P, typename N> inline - bool - line_graph_neighborhood_bkd_piter<P, N>::adjacent_or_equal_to_p_ref_() const + const line_graph_psite<P>& + line_graph_neighborhood_bkd_piter<P, N>::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 N> inline - void - line_graph_neighborhood_bkd_piter<P, N>::update_() + line_graph_neighborhood_bkd_piter<P, N>::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 N> inline - const P& - line_graph_neighborhood_bkd_piter<P, N>::to_point() const + const line_graph_psite<P>& + line_graph_neighborhood_bkd_piter<P, N>::p_ref() const { - return p_; + return p_ref_; } template <typename P, typename N> inline - const line_graph_psite<P>& - line_graph_neighborhood_bkd_piter<P, N>::to_psite() const + const p_line_graph<P>& + line_graph_neighborhood_bkd_piter<P, N>::plg() const { - return psite_; + return p_ref_.plg(); } template <typename P, typename N> inline - line_graph_neighborhood_bkd_piter<P, N>::operator line_graph_psite<P> () const + std::set<util::edge_id>& + line_graph_neighborhood_bkd_piter<P, N>::neighbors() { - mln_precondition(is_valid()); - return psite_; + return neighbors_; } template <typename P, typename N> Index: mln/core/line_graph_elt_neighborhood.hh --- mln/core/line_graph_elt_neighborhood.hh (revision 1854) +++ mln/core/line_graph_elt_neighborhood.hh (working copy) @@ -29,7 +29,7 @@ # define MLN_CORE_LINE_GRAPH_ELT_NEIGHBORHOOD_HH /// \file mln/core/line_graph_elt_neighborhood.hh -/// \brief Definition of the elementary ``window'' on a line graph. +/// \brief Definition of the elementary ``neighborhood'' on a line graph. /* FIXME: Have a consistent naming: we have window (without '_') but point_, neighb_, etc. */ @@ -40,6 +40,8 @@ - mln::line_graph_elt_window - mln::line_graph_elt_neighborhood. */ +# include <set> + # include <mln/core/concept/neighborhood.hh> # include <mln/core/line_graph_psite.hh> # include <mln/core/line_graph_neighborhood_piter.hh> @@ -66,6 +68,9 @@ typedef P point; /// The type of psite corresponding to the neighborhood. typedef line_graph_psite<P> psite; + // The type of the set of neighbors (edge ids adjacent to the + // reference psite). + typedef std::set<util::edge_id> neighbors_t; // FIXME: This is a dummy value. typedef void dpoint; @@ -84,43 +89,44 @@ /// 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. template <typename Piter> - void next_(Point_Iterator<Piter>& piter) const; + void compute_neighbors_(Point_Iterator<Piter>& piter) const; /// \} }; -# ifndef MLN_INCLUDE_ONLY - template <typename P> - template <typename Piter> - inline - void - line_graph_elt_neighborhood<P>::start(Point_Iterator<Piter>& piter_) const - { - Piter& piter = exact(piter_); - piter.first_(); - if (!piter.adjacent_or_equal_to_p_ref_()) - next_(piter); - } + +# ifndef MLN_INCLUDE_ONLY template <typename P> template <typename Piter> inline void - line_graph_elt_neighborhood<P>::next_(Point_Iterator<Piter>& piter_) const + line_graph_elt_neighborhood<P>::compute_neighbors_(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_()); + neighbors_t& neighbors = piter.neighbors(); + neighbors.clear(); + // Add the reference piter itself. We might reconsider this, or + // create an elementary neighbors without the reference point. + neighbors.insert(piter.p_ref().id()); + /* 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. + // 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) + neighbors.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) + neighbors.insert(*e); } # endif // ! MLN_INCLUDE_ONLY