[Olena-patches] 3670: Add graph::compute and few related functors.

* mln/canvas/browsing/depth_first_search.hh: update and add more doc. * mln/graph/attribute/card.hh, * mln/graph/attribute/representative.hh, * mln/graph/compute.hh: enable the possibility of computing data on a graph. * tests/Makefile.am, * tests/graph/Makefile.am, * tests/graph/attribute/Makefile.am, * tests/graph/attribute/card.cc, * tests/graph/attribute/representative.cc: add new tests. --- milena/ChangeLog | 17 +++ milena/mln/canvas/browsing/depth_first_search.hh | 29 +++--- milena/mln/graph/attribute/card.hh | 123 ++++++++++++++++++++++ milena/mln/graph/attribute/representative.hh | 123 ++++++++++++++++++++++ milena/mln/graph/compute.hh | 86 +++++++++++++++ milena/tests/Makefile.am | 1 + milena/tests/graph/Makefile.am | 6 + milena/tests/graph/attribute/Makefile.am | 12 ++ milena/tests/graph/attribute/card.cc | 63 +++++++++++ milena/tests/graph/attribute/representative.cc | 63 +++++++++++ 10 files changed, 510 insertions(+), 13 deletions(-) create mode 100644 milena/mln/graph/attribute/card.hh create mode 100644 milena/mln/graph/attribute/representative.hh create mode 100644 milena/mln/graph/compute.hh create mode 100644 milena/tests/graph/Makefile.am create mode 100644 milena/tests/graph/attribute/Makefile.am create mode 100644 milena/tests/graph/attribute/card.cc create mode 100644 milena/tests/graph/attribute/representative.cc diff --git a/milena/ChangeLog b/milena/ChangeLog index 5cd09e3..ef8857b 100644 --- a/milena/ChangeLog +++ b/milena/ChangeLog @@ -1,5 +1,22 @@ 2009-04-15 Guillaume Lazzara &lt;lazzara(a)lrde.epita.fr&gt; + Add graph::compute and few related functors. + + * mln/canvas/browsing/depth_first_search.hh: update and add more doc. + + * mln/graph/attribute/card.hh, + * mln/graph/attribute/representative.hh, + * mln/graph/compute.hh: enable the possibility of computing data on a + graph. + + * tests/Makefile.am, + * tests/graph/Makefile.am, + * tests/graph/attribute/Makefile.am, + * tests/graph/attribute/card.cc, + * tests/graph/attribute/representative.cc: add new tests. + +2009-04-15 Guillaume Lazzara &lt;lazzara(a)lrde.epita.fr&gt; + Handle bool specialization correctly with util::array. * mln/util/array.hh: update return type of operator() and operator[]. diff --git a/milena/mln/canvas/browsing/depth_first_search.hh b/milena/mln/canvas/browsing/depth_first_search.hh index 179bf1c..2880397 100644 --- a/milena/mln/canvas/browsing/depth_first_search.hh +++ b/milena/mln/canvas/browsing/depth_first_search.hh @@ -1,4 +1,4 @@ -// Copyright (C) 2008 EPITA Research and Development Laboratory (LRDE) +// Copyright (C) 2008, 2009 EPITA Research and Development Laboratory (LRDE) // // This file is part of the Olena Library. This library is free // software; you can redistribute it and/or modify it under the terms @@ -39,24 +39,27 @@ ** - template <typename G> void init(const Graph<G>& g) ** Will be called at the beginning. ** -** - void next() -** Will be called after all vertices from a component have been treated. -** -** - void update_treated(unsigned id) -** will be called for the first vertex encountered for each component. -** -** - void update_queued(unsigned id) -** Will be called for every vertex encountered in each component, except -** the first one. -** ** - bool to_be_treated(unsigned id) ** Return whether this vertex has already been marked or if it may be a ** a component representative. ** +** - void new_component_from_vertex(unsigned id) +** will be called for the first vertex encountered for each component. +** +** - void process_vertex(unsigned id) +** Will be called for each vertex queued. +** ** - bool to_be_queued(unsigned id) ** Return whether this vertex has already been marked or if it can be added ** to the current component. ** +** - void added_to_queue(unsigned id) +** Will be called for every vertex encountered in each component, except +** the first one. +** +** - void next_component() +** Will be called after all vertices from a component have been treated. +** ** - void final() ** Will be called at the end; ** @@ -99,7 +102,7 @@ namespace mln const G& g = exact(g_); - f.init(g); + f.init(g); // <--- init mln_vertex_iter(G) v(g); for_all(v) @@ -111,7 +114,7 @@ namespace mln while (!queue.empty()) { util::vertex<G> current_v = g.vertex(queue.front()); - f.process_vertex(current_v); + f.process_vertex(current_v); // <--- process_vertex queue.pop(); for (unsigned nv = 0; nv < current_v.nmax_nbh_vertices(); ++nv) if (f.to_be_queued(current_v.ith_nbh_vertex(nv))) // <--- to_be_queued diff --git a/milena/mln/graph/attribute/card.hh b/milena/mln/graph/attribute/card.hh new file mode 100644 index 0000000..fa892ee --- /dev/null +++ b/milena/mln/graph/attribute/card.hh @@ -0,0 +1,123 @@ +// Copyright (C) 2009 EPITA Research and Development Laboratory +// (LRDE) +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to +// produce an executable, this file does not by itself cause the +// resulting executable to be covered by the GNU General Public +// License. +// reasons why the executable file might be covered by the GNU General +// Public License. + + +#ifndef MLN_GRAPH_ATTRIBUTE_CARD_HH +# define MLN_GRAPH_ATTRIBUTE_CARD_HH + +/// \file mln/graph/attribute/card.hh +/// Functor that computes the cardinality of every component in a graph. +/// +/// \sa graph::compute + + +# include <mln/core/concept/graph.hh> +# include <mln/util/array.hh> + + +namespace mln +{ + + namespace graph + { + + namespace attribute + { + + /// Functor that computes the cardinality of every component in a graph. + struct card_t; + + /// This is a global instance of this functor. + extern card_t card; + + +# ifndef MLN_INCLUDE_ONLY + + /// Compute the cardinality of every component in a graph. + /// + /// \return An array with the cardinality for each component. + /// Components are labeled from 0. + struct card_t + { + /// Type of the computed value + typedef util::array<unsigned> result; + + template <typename G> + void init(const Graph<G>& g) + { + data.resize(0); + deja_vu_.resize(exact(g).v_nmax()); + deja_vu_.fill(false); + comp = 0; + } + + bool to_be_treated(unsigned id) + { return !deja_vu_[id]; } + + void new_component_from_vertex(unsigned id) + { + data.append(1); + deja_vu_[id] = true; + } + + void process_vertex(unsigned) + {} + + bool to_be_queued(unsigned id) + { return !deja_vu_[id]; } + + void added_to_queue(unsigned id) + { + deja_vu_[id] = true; + ++data[comp]; + } + + void next_component() + { ++comp; } + + void final() + {} + + unsigned comp; + util::array<bool> deja_vu_; + util::array<unsigned> data; + }; + + card_t card; + +# endif // ! MLN_INCLUDE_ONLY + + + } // end of namespace mln::graph::attribute + + } // end of namespace mln::graph + +} // end of namespace mln + + +#endif // ! MLN_GRAPH_ATTRIBUTE_CARD_HH diff --git a/milena/mln/graph/attribute/representative.hh b/milena/mln/graph/attribute/representative.hh new file mode 100644 index 0000000..88ed258 --- /dev/null +++ b/milena/mln/graph/attribute/representative.hh @@ -0,0 +1,123 @@ +// Copyright (C) 2009 EPITA Research and Development Laboratory +// (LRDE) +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to +// produce an executable, this file does not by itself cause the +// resulting executable to be covered by the GNU General Public +// License. +// reasons why the executable file might be covered by the GNU General +// Public License. + + +#ifndef MLN_GRAPH_ATTRIBUTE_REPRESENTATIVE_HH +# define MLN_GRAPH_ATTRIBUTE_REPRESENTATIVE_HH + +/// \file mln/graph/attribute/representative.hh +/// +/// Functor that computes the representative vertex of every component in +/// a graph. +/// +/// \sa graph::compute + + +# include <mln/core/concept/graph.hh> +# include <mln/util/array.hh> + + +namespace mln +{ + + namespace graph + { + + namespace attribute + { + + /// Functor that computes the representative vertex of every component + /// in a graph. + struct representative_t; + + /// This is a global instance of this functor. + extern representative_t representative; + +# ifndef MLN_INCLUDE_ONLY + + /// Compute the representative vertex of every component in a graph. + /// + /// \return An array with the representative for each component. + /// Components are labeled from 0. + struct representative_t + { + /// Type of the computed value + typedef util::array<unsigned> result; + + template <typename G> + void init(const Graph<G>& g) + { + data.resize(0); + deja_vu_.resize(exact(g).v_nmax()); + deja_vu_.fill(false); + } + + bool to_be_treated(unsigned id) + { return !deja_vu_[id]; } + + void new_component_from_vertex(unsigned id) + { + data.append(id); + deja_vu_[id] = true; + } + + void process_vertex(unsigned id) + {} + + bool to_be_queued(unsigned id) + { return !deja_vu_[id]; } + + void added_to_queue(unsigned id) + { + deja_vu_[id] = true; + } + + void next_component() + {} + + void final() + {} + + util::array<bool> deja_vu_; + util::array<unsigned> data; + }; + + representative_t representative; + + +# endif // ! MLN_INCLUDE_ONLY + + + } // end of namespace mln::graph::attribute + + } // end of namespace mln::graph + +} // end of namespace mln + + +#endif // ! MLN_GRAPH_ATTRIBUTE_REPRESENTATIVE_HH diff --git a/milena/mln/graph/compute.hh b/milena/mln/graph/compute.hh new file mode 100644 index 0000000..ff69a48 --- /dev/null +++ b/milena/mln/graph/compute.hh @@ -0,0 +1,86 @@ +// Copyright (C) 2009 EPITA Research and Development Laboratory +// (LRDE) +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to +// produce an executable, this file does not by itself cause the +// resulting executable to be covered by the GNU General Public +// License. +// reasons why the executable file might be covered by the GNU General +// Public License. + + +#ifndef MLN_GRAPH_COMPUTE_HH +# define MLN_GRAPH_COMPUTE_HH + +/// \file mln/graph/compute.hh +/// +/// Base routine to compute attributes on a graph. +/// +/// Functors must provide the interface described in depth_first_search_t. +/// \sa canvas::browsing::depth_first_search_t + +# include <mln/core/concept/graph.hh> +# include <mln/canvas/browsing/depth_first_search.hh> +# include <mln/util/array.hh> + + +namespace mln +{ + + namespace graph + { + + /// Base routine to compute attributes on a graph. + /// \param[in] g_ A graph. + /// \param[in] functor A functor implementing the right interface. + /// + /// \return The computed data. + /// + /// \sa canvas::browsing::depth_first_search + template <typename G, typename F> + mln_result(F) + compute(const Graph<G>& g_, F& functor); + + +# ifndef MLN_INCLUDE_ONLY + + template <typename G, typename F> + mln_result(F) + compute(const Graph<G>& g_, F& functor) + { + trace::entering("graph::compute"); + const G& g = exact(g_); + mln_precondition(g.is_valid()); + + canvas::browsing::depth_first_search(g, functor); + + trace::exiting("graph::compute"); + return functor.data; + } + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::graph + +} // end of namespace mln + + +#endif // ! MLN_GRAPH_COMPUTE_HH diff --git a/milena/tests/Makefile.am b/milena/tests/Makefile.am index 0e05a0f..9945b19 100644 --- a/milena/tests/Makefile.am +++ b/milena/tests/Makefile.am @@ -19,6 +19,7 @@ SUBDIRS = \ extension \ fun \ geom \ + graph \ histo \ io \ labeling \ diff --git a/milena/tests/graph/Makefile.am b/milena/tests/graph/Makefile.am new file mode 100644 index 0000000..b663a3f --- /dev/null +++ b/milena/tests/graph/Makefile.am @@ -0,0 +1,6 @@ +## Process this file through Automake to create Makefile.in -*- Makefile -*- + +include $(top_srcdir)/milena/tests/tests.mk + +SUBDIRS = attribute + diff --git a/milena/tests/graph/attribute/Makefile.am b/milena/tests/graph/attribute/Makefile.am new file mode 100644 index 0000000..520371f --- /dev/null +++ b/milena/tests/graph/attribute/Makefile.am @@ -0,0 +1,12 @@ +## Process this file through Automake to create Makefile.in -*- Makefile -*- + +include $(top_srcdir)/milena/tests/tests.mk + +check_PROGRAMS = \ + card \ + representative + +card_SOURCES = card.cc +representative_SOURCES = representative.cc + +TESTS = $(check_PROGRAMS) diff --git a/milena/tests/graph/attribute/card.cc b/milena/tests/graph/attribute/card.cc new file mode 100644 index 0000000..eebf82c --- /dev/null +++ b/milena/tests/graph/attribute/card.cc @@ -0,0 +1,63 @@ +// Copyright (C) 2009 EPITA Research and Development Laboratory +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to +// produce an executable, this file does not by itself cause the +// resulting executable to be covered by the GNU General Public +// License. This exception does not however invalidate any other +// reasons why the executable file might be covered by the GNU General +// Public License. + +/// \file tests/graph/attribute/card.cc +/// +/// Tests on mln::graph::attribute::card. + +#include <mln/util/graph.hh> +#include <mln/graph/compute.hh> +#include <mln/graph/attribute/card.hh> + +int main() +{ + using namespace mln; + + util::graph g; + + /// Construct the following graph: + /// + /// 0 -- 1 -- 2 + /// + /// 3 -- 4 + /// + /// 5 + /// + /// There are 3 components. + // + g.add_vertices(6); + g.add_edge(0,1); + g.add_edge(1,2); + g.add_edge(3,4); + + util::array<unsigned> result = graph::compute(g, graph::attribute::card); + + mln_assertion(result.size() == 3); + mln_assertion(result[0] == 3); + mln_assertion(result[1] == 2); + mln_assertion(result[2] == 1); +} diff --git a/milena/tests/graph/attribute/representative.cc b/milena/tests/graph/attribute/representative.cc new file mode 100644 index 0000000..77e99a0 --- /dev/null +++ b/milena/tests/graph/attribute/representative.cc @@ -0,0 +1,63 @@ +// Copyright (C) 2009 EPITA Research and Development Laboratory +// +// This file is part of the Olena Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License version 2 as published by the +// Free Software Foundation. +// +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. +// +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING. If not, write to +// the Free Software Foundation, 51 Franklin Street, Fifth Floor, +// Boston, MA 02111-1307, USA. +// +// As a special exception, you may use this file as part of a free +// software library without restriction. Specifically, if other files +// instantiate templates or use macros or inline functions from this +// file, or you compile this file and link it with other files to +// produce an executable, this file does not by itself cause the +// resulting executable to be covered by the GNU General Public +// License. This exception does not however invalidate any other +// reasons why the executable file might be covered by the GNU General +// Public License. + +/// \file tests/graph/attribute/representative.cc +/// +/// Tests on mln::graph::attribute::representative. + +#include <mln/util/graph.hh> +#include <mln/graph/compute.hh> +#include <mln/graph/attribute/representative.hh> + +int main() +{ + using namespace mln; + + util::graph g; + + /// Construct the following graph: + /// + /// 0 -- 1 -- 2 + /// + /// 3 -- 4 + /// + /// 5 + /// + /// There are 3 components. + // + g.add_vertices(6); + g.add_edge(0,1); + g.add_edge(1,2); + g.add_edge(3,4); + + util::array<unsigned> result = graph::compute(g, graph::attribute::representative); + + mln_assertion(result.size() == 3); + mln_assertion(result[0] == 0); + mln_assertion(result[1] == 3); + mln_assertion(result[2] == 5); +} -- 1.5.6.5