https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Roland Levillain <roland@lrde.epita.fr> Add adjaceny tests for mln::p_line_graph. * mln/core/p_line_graph.hh (mln::p_line_graph<P>::adjacent) (mln::p_line_graph<P>::adjacent_or_equal): New methods. (mln::p_line_graph<P>::p_line_graph): Remove outdated FIXME. * mln/core/p_graph.hh: Improve documentation. (mln::p_graph<P>::p_graph): Remove outdated FIXME. * tests/core/graph_image.cc, tests/core/line_graph_image.cc: Exercise adjacency tests. * tests/core/line_graph_elt_neighborhood.cc, * tests/core/line_graph_elt_window.cc: Typos in documentation. * tests/core/graph_elt_neighborhood.cc, * tests/core/graph_elt_window.cc: Aesthetic changes. mln/core/p_graph.hh | 22 ++++---- mln/core/p_line_graph.hh | 81 +++++++++++++++++++++++++++++- tests/core/graph_elt_neighborhood.cc | 6 -- tests/core/graph_elt_window.cc | 6 -- tests/core/graph_image.cc | 29 +++++++++- tests/core/line_graph_elt_neighborhood.cc | 9 +-- tests/core/line_graph_elt_window.cc | 9 +-- tests/core/line_graph_image.cc | 26 ++++++++- 8 files changed, 149 insertions(+), 39 deletions(-) Index: mln/core/p_line_graph.hh --- mln/core/p_line_graph.hh (revision 1911) +++ mln/core/p_line_graph.hh (working copy) @@ -89,6 +89,22 @@ bool has(const psite& p) const; + /// Adjacency tests. + /// \{ + /// Return true if the psites \a lhs and \a rhs are adjacent. + /// (If \a lhs and \a rhs are equal, return false). + bool adjacent(const psite& lhs, const psite& rhs) const; + /// Return true if the edges \a lhs and \a rhs are adjacent. + /// (If \a lhs and \a rhs are equal, return false). + bool adjacent(const util::edge_id& lhs, const util::edge_id& rhs) const; + + /// Return true if the psites \a lhs and \a rhs are adjacent, or equal. + bool adjacent_or_equal(const psite& lhs, const psite& rhs) const; + /// Return true if the edges \a lhs and \a rhs are adjacent, or equal + bool adjacent_or_equal(const util::edge_id& lhs, + const util::edge_id& rhs) const; + /// \} + // FIXME: Should be private. util::tracked_ptr<graph> gr_; // FIXME: (Roland) Is it really useful/needed? @@ -125,10 +141,9 @@ template<typename P> inline p_line_graph<P>::p_line_graph (const util::graph<P>& gr) + // Create a deep, managed copy of GR. : gr_ (new util::graph<P>(gr)) { - // FIXME: Warning: if the underlying graph is updated later, this - // won't be taken into account by this p_line_graph! accu::bbox<P> a; for (unsigned i = 0; i < nnodes(); ++i) a.take(gr_->node_data(i)); @@ -179,6 +194,68 @@ (p.id() < gr_->nedges()); } + template <typename P> + inline + bool + p_line_graph<P>::adjacent(const psite& lhs, const psite& rhs) const + { + mln_assertion(&lhs.plg() == this && rhs.plg() == 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_line_graph<P>::adjacent(const util::edge_id& lhs, + const util::edge_id& rhs) const + { + mln_assertion(lhs < this->npoints()); + mln_assertion(rhs < this->npoints()); + + // Ensure LHS and RHS are *not* equal. + if (lhs == rhs) + return false; + + // Check whether LHS and RHS are adjacent (i.e., whether LHS and + // RHS share a common vertex. + /* FIXME: This is too low-level. Yet another service the graph + should provide. */ + if (gr_->edge(lhs).n1() == gr_->edge(rhs).n1() || + gr_->edge(lhs).n1() == gr_->edge(rhs).n2() || + gr_->edge(lhs).n2() == gr_->edge(rhs).n1() || + gr_->edge(lhs).n2() == gr_->edge(rhs).n2()) + return true; + + return false; + } + + template <typename P> + inline + bool + p_line_graph<P>::adjacent_or_equal(const psite& lhs, const psite& rhs) const + { + mln_assertion(&lhs.pg() == this && rhs.pg() == this); + return adjacent_or_equal(lhs.id(), rhs.id()); + } + + template <typename P> + inline + bool + p_line_graph<P>::adjacent_or_equal(const util::edge_id& lhs, + const util::edge_id& rhs) const + { + mln_assertion(lhs < this->npoints()); + mln_assertion(rhs < this->npoints()); + + // Check whether LHS and RHS are equal. + if (lhs == rhs) + return true; + // Check whether RHS and LHS are adjacent. + return adjacent(lhs, rhs); + } + template <typename P> bool Index: mln/core/p_graph.hh --- mln/core/p_graph.hh (revision 1911) +++ mln/core/p_graph.hh (working copy) @@ -96,14 +96,16 @@ /// Adjacency tests. /// \{ - /// Return true if the psites lhs and rhs are adjacent. + /// Return true if the psites \a lhs and \a rhs are adjacent. + /// (If \a lhs and \a rhs are equal, return false). bool adjacent(const psite& lhs, const psite& rhs) const; - /// Return true if the nodes lhs and rhs are adjacent. + /// Return true if the nodes \a lhs and \a rhs are adjacent. + /// (If \a lhs and \a rhs are equal, return false). 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. + /// Return true if the psites \a lhs and \a 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 + /// Return true if the nodes \a lhs and \a rhs are adjacent, or equal bool adjacent_or_equal(const util::node_id& lhs, const util::node_id& rhs) const; /// \} @@ -151,10 +153,9 @@ template<typename P> inline p_graph<P>::p_graph (const util::graph<P>& gr) + // Create a deep, managed copy of GR. : gr_ (new util::graph<P>(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 < npoints(); ++i) a.take(gr_->node_data(i)); @@ -258,7 +259,8 @@ // Ensure LHS and RHS are *not* equal. if (rhs == lhs) return false; - // Check whether RHS and LHS are adjacent (i.e., whether RHS is + + // Check whether LHS and RHS 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; @@ -290,10 +292,10 @@ mln_assertion(rhs < this->npoints()); // Check whether LHS and RHS are equal. - if (rhs == lhs) + if (lhs == rhs) return true; - // Check whether RHS and LHS are adjacent. - return adjacent(rhs, lhs); + // Check whether LHS and RHS are adjacent. + return adjacent(lhs, rhs); } template <typename P> Index: tests/core/graph_image.cc --- tests/core/graph_image.cc (revision 1911) +++ tests/core/graph_image.cc (working copy) @@ -50,6 +50,19 @@ | Graph. | `--------*/ + /* The graph is as follows: + + 0 1 2 3 4 + .----------- + | + 0 | 0 2 + 1 | \ / | + 2 | 1 | + 3 | \ | + 4 | 3-4 + + */ + // Points associated to nodes. std::vector<point2d> points; points.push_back(make::point2d(0,0)); // Point associated to node 0. @@ -70,12 +83,20 @@ g.add_edge(3, 4); g.add_edge(4, 2); - /*-------. - | Graph. | - `-------*/ + g.print_debug(std::cout); + + /*----------------------. + | Graph image support. | + `----------------------*/ p_graph<point2d> pg(g); - g.print_debug(std::cout); + + // Check adjacencies of vertex 1. + mln_assertion( pg.adjacent(1, 0)); + mln_assertion(!pg.adjacent(1, 1)); + mln_assertion( pg.adjacent(1, 2)); + mln_assertion( pg.adjacent(1, 3)); + mln_assertion(!pg.adjacent(1, 4)); /*-------------. | Graph image. | Index: tests/core/line_graph_image.cc --- tests/core/line_graph_image.cc (revision 1911) +++ tests/core/line_graph_image.cc (working copy) @@ -50,6 +50,19 @@ | Graph. | `--------*/ + /* The graph and its corresponding line graph are as follows: + + 0 1 2 3 4 0 1 2 3 4 + .----------- .----------- + | | + 0 | 0 2 0 | * * + 1 | \ / | 1 | 0 1 | + 2 | 1 | 2 | * 4 + 3 | \ | 3 | 2 | + 4 | 3-4 4 | *3* + + */ + // Points associated to nodes. std::vector<point2d> points; points.push_back(make::point2d(0,0)); // Point associated to node 0. @@ -70,12 +83,19 @@ g.add_edge(3, 4); g.add_edge(4, 2); - /*-------. - | Graph. | - `-------*/ + /*---------------------------. + | Line graph image support. | + `---------------------------*/ p_line_graph<point2d> plg(g); + // Check adjacencies of edge 1. + mln_assertion( plg.adjacent(1, 0)); + mln_assertion(!plg.adjacent(1, 1)); + mln_assertion( plg.adjacent(1, 2)); + mln_assertion(!plg.adjacent(1, 3)); + mln_assertion( plg.adjacent(1, 4)); + /*-------------------. | Line graph image. | `-------------------*/ Index: tests/core/line_graph_elt_neighborhood.cc --- tests/core/line_graph_elt_neighborhood.cc (revision 1911) +++ tests/core/line_graph_elt_neighborhood.cc (working copy) @@ -25,10 +25,8 @@ // reasons why the executable file might be covered by the GNU General // Public License. -/*! \file tests/core/line_graph_elt_neighborhood.cc - * - * \brief Tests on mln::line_graph_elt_neighborhood. - */ +/// \file tests/core/line_graph_elt_neighborhood.cc +/// \brief Tests on mln::line_graph_elt_neighborhood. #include <vector> @@ -49,8 +47,7 @@ | Graph. | `--------*/ - /* The graph is as follows and its corresponding line graph are as - follows: + /* The graph and its corresponding line graph are as follows: 0 1 2 3 4 0 1 2 3 4 .----------- .----------- Index: tests/core/line_graph_elt_window.cc --- tests/core/line_graph_elt_window.cc (revision 1911) +++ tests/core/line_graph_elt_window.cc (working copy) @@ -25,10 +25,8 @@ // reasons why the executable file might be covered by the GNU General // Public License. -/*! \file tests/core/line_graph_elt_window.cc - * - * \brief Tests on mln::line_graph_elt_window. - */ +/// \file tests/core/line_graph_elt_window.cc +/// \brief Tests on mln::line_graph_elt_window. #include <vector> @@ -49,8 +47,7 @@ | Graph. | `--------*/ - /* The graph is as follows and its corresponding line graph are as - follows: + /* The graph and its corresponding line graph are as follows: 0 1 2 3 4 0 1 2 3 4 .----------- .----------- Index: tests/core/graph_elt_neighborhood.cc --- tests/core/graph_elt_neighborhood.cc (revision 1911) +++ tests/core/graph_elt_neighborhood.cc (working copy) @@ -25,10 +25,8 @@ // reasons why the executable file might be covered by the GNU General // Public License. -/*! \file tests/core/graph_elt_neighborhood.cc - * - * \brief Tests on mln::graph_elt_neighborhood. - */ +/// \file tests/core/graph_elt_neighborhood.cc +/// \brief Tests on mln::graph_elt_neighborhood. #include <iostream> Index: tests/core/graph_elt_window.cc --- tests/core/graph_elt_window.cc (revision 1911) +++ tests/core/graph_elt_window.cc (working copy) @@ -25,10 +25,8 @@ // reasons why the executable file might be covered by the GNU General // Public License. -/*! \file tests/core/graph_elt_window.cc - * - * \brief Tests on mln::graph_elt_window. - */ +/// \file tests/core/graph_elt_window.cc +/// \brief Tests on mln::graph_elt_window. #include <iostream>