[Olena-patches] 1885: Fix the definitions of graph-related neighborhoods.

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Roland Levillain &lt;roland(a)lrde.epita.fr&gt; Fix the definitions of graph-related neighborhoods. * mln/core/line_graph_elt_neighborhood.hh: (mln::line_graph_elt_neighborhood<P>::compute_neighbors_): Don't add the reference (central) point to its own neighborhood. * mln/core/p_line_graph.hh: Add a FIXME. * mln/core/p_graph.hh (mln::p_graph<P>::adjacent): New methods. Use them to factor (mln::p_graph<P>::adjacent_or_equal(const node_id&, const node_id&)): ...this method. * mln/core/graph_neighborhood_piter.hh, * mln/core/graph_elt_neighborhood.hh (mln::graph_elt_neighborhood<P>::start) (mln::graph_elt_neighborhood<P>::next_): s/adjacent_or_equal/adjacent/. graph_elt_neighborhood.hh | 4 +- graph_neighborhood_piter.hh | 16 +++++----- line_graph_elt_neighborhood.hh | 3 - p_graph.hh | 64 ++++++++++++++++++++++++++++++----------- p_line_graph.hh | 2 + 5 files changed, 59 insertions(+), 30 deletions(-) Index: mln/core/line_graph_elt_neighborhood.hh --- mln/core/line_graph_elt_neighborhood.hh (revision 1884) +++ mln/core/line_graph_elt_neighborhood.hh (working copy) @@ -107,9 +107,6 @@ Piter& piter = exact(piter_); 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. */ Index: mln/core/p_line_graph.hh --- mln/core/p_line_graph.hh (revision 1884) +++ mln/core/p_line_graph.hh (working copy) @@ -39,6 +39,8 @@ /* FIXME: This class shares a lot with p_graph. Factor as much as possible. */ +// FIXME: We should move the `adjacent_or_equal method' from +// iterators into this class. /// \file mln/core/p_line_graph.hh /// \brief Definition of a point set based on line graph. Index: mln/core/p_graph.hh --- mln/core/p_graph.hh (revision 1884) +++ mln/core/p_graph.hh (working copy) @@ -94,12 +94,19 @@ /// to the edge id \a e. const P& node2(const util::edge_id& e) const; + /// Adjacency tests. + /// \{ + /// Return true if the psites lhs and rhs are adjacent. + bool adjacent(const psite& lhs, const psite& rhs) const; + /// Return true if the nodes lhs and rhs are adjacent. + bool adjacent(const util::node_id& lhs, const util::node_id& rhs) const; + /// Return true if the psites lhs and rhs are adjacent, or equal. bool adjacent_or_equal(const psite& lhs, const psite& rhs) const; - /// Return true if the nodes lhs and rhs are adjacent, or equal bool adjacent_or_equal(const util::node_id& lhs, const util::node_id& rhs) const; + /// \} /// Return the graph associated to the p_graph domain: const graph& to_graph() const; @@ -231,9 +238,42 @@ template <typename P> inline bool + p_graph<P>::adjacent(const psite& lhs, const psite& rhs) const + { + mln_assertion(&lhs.pg() == this && rhs.pg() == this); + return adjacent(lhs.id(), rhs.id()); + } + + /* FIXME: This could be more efficient, if the graph structure had a + richer interface. */ + template <typename P> + inline + bool + p_graph<P>::adjacent(const util::node_id& lhs, + const util::node_id& rhs) const + { + mln_assertion(lhs < this->npoints()); + mln_assertion(rhs < this->npoints()); + + // Check whether RHS and LHS 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; + 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) + return true; + + return false; + } + + template <typename P> + inline + bool p_graph<P>::adjacent_or_equal(const psite& lhs, const psite& rhs) const { - assert (&lhs.pg() == this && rhs.pg() == this); + mln_assertion(&lhs.pg() == this && rhs.pg() == this); return adjacent_or_equal(lhs.id(), rhs.id()); } @@ -243,24 +283,14 @@ p_graph<P>::adjacent_or_equal(const util::node_id& lhs, const util::node_id& rhs) const { - // FIXME: This is inefficient. - - assert (lhs < this->npoints()); - assert (rhs < this->npoints()); + mln_assertion(lhs < this->npoints()); + mln_assertion(rhs < this->npoints()); + // Check whether LHS and RHS are equal. if (rhs == lhs) return true; - - // Check whether the iterator is among the neighbors of P_REF_. - typedef std::vector<util::node_id> adjacency_type; - const adjacency_type& lhs_neighbs = gr_->nodes()[lhs]->edges; - - adjacency_type::const_iterator j = - std::find (lhs_neighbs.begin(), lhs_neighbs.end(), rhs); - if (j != lhs_neighbs.end()) - return true; - - return false; + // Check whether RHS and LHS are adjacent. + return adjacent(rhs, lhs); } template <typename P> Index: mln/core/graph_neighborhood_piter.hh --- mln/core/graph_neighborhood_piter.hh (revision 1884) +++ mln/core/graph_neighborhood_piter.hh (working copy) @@ -98,8 +98,8 @@ /// 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; + /// Is the piter adjacent to the reference point? + bool adjacent_to_p_ref_() const; /// Update the internal data of the iterator. void update_(); /// \} @@ -180,8 +180,8 @@ /// 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; + /// Is the piter adjacent to the reference point? + bool adjacent_to_p_ref_() const; /// Update the internal data of the iterator. void update_(); /// \} @@ -302,9 +302,9 @@ template <typename P, typename N> inline bool - graph_neighborhood_fwd_piter<P, N>::adjacent_or_equal_to_p_ref_() const + graph_neighborhood_fwd_piter<P, N>::adjacent_to_p_ref_() const { - return p_ref_.pg().adjacent_or_equal(p_ref_.id(), id_); + return p_ref_.pg().adjacent(p_ref_.id(), id_); } template <typename P, typename N> @@ -430,9 +430,9 @@ template <typename P, typename N> inline bool - graph_neighborhood_bkd_piter<P, N>::adjacent_or_equal_to_p_ref_() const + graph_neighborhood_bkd_piter<P, N>::adjacent_to_p_ref_() const { - return p_ref_.pg().adjacent_or_equal(p_ref_.id(), id_); + return p_ref_.pg().adjacent(p_ref_.id(), id_); } template <typename P, typename N> Index: mln/core/graph_elt_neighborhood.hh --- mln/core/graph_elt_neighborhood.hh (revision 1884) +++ mln/core/graph_elt_neighborhood.hh (working copy) @@ -104,7 +104,7 @@ { Piter& piter = exact(piter_); piter.first_(); - if (!piter.adjacent_or_equal_to_p_ref_()) + if (!piter.adjacent_to_p_ref_()) next_(piter); } @@ -121,7 +121,7 @@ neighbors in constant time. */ do piter.step_(); - while (piter.is_valid() && !piter.adjacent_or_equal_to_p_ref_()); + while (piter.is_valid() && !piter.adjacent_to_p_ref_()); } # endif // ! MLN_INCLUDE_ONLY