[Olena-patches] 1713: Ovherhaul undirected graphs.

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Roland Levillain &lt;roland(a)lrde.epita.fr&gt; Ovherhaul undirected graphs. * mln/util/graph.hh (util::node, util::edge, util::graph): Move... * mln/util/internal/graph_base.hh: ...here (new file). (node_id, edge_id): New. (util::graph): Rename as... (util::internal::graph_base): ...this. Factor the common implementations of undirected graphs. (util::internal::consistency): Remove. (util::internal::nb_node_, util::internal::nb_link_): Remove. * mln/util/graph.hh: Include mln/util/internal/graph_base.hh. (util::graph<N, E>): New class, inheriting from util::internal::graph_base. (util::graph<N, void>, util::graph<void, void>): New specializations. * tests/util/graph.cc: Adjust. mln/util/graph.hh | 412 ++++++++++++++++++++-------------------- mln/util/internal/graph_base.hh | 399 ++++++++++++++++++++++++++++++++++++++ tests/util/graph.cc | 11 - 3 files changed, 610 insertions(+), 212 deletions(-) Index: mln/util/internal/graph_base.hh --- mln/util/internal/graph_base.hh (revision 0) +++ mln/util/internal/graph_base.hh (revision 0) @@ -0,0 +1,399 @@ +// Copyright (C) 2007, 2008 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_UTIL_INTERNAL_GRAPH_BASE_HH +# define MLN_UTIL_INTERNAL_GRAPH_BASE_HH + +/// \file mln/util/internal/graph.hh +/// \brief Factored implementation of undirected graphs. + +# include <mln/core/concept/object.hh> +# include <cstddef> +# include <ostream> +# include <vector> +# include <list> +# include <algorithm> +# include <mln/util/ordpair.hh> + +namespace mln +{ + + namespace util + { + /// \bref The type used to identify nodes. + /// + /// Used internally as a key to manipulate nodes. + typedef unsigned node_id; + + /// \bref The type used to identify edges. + /// + /// Used internally as a key to manipulate edges. + typedef unsigned edge_id; + + + /*-------. + | Node. | + `-------*/ + + /// \brief Node of a graph, holding a value of type \p T. + template<typename T> + struct node + { + node(T data) + : data(data) + {} + + T data; + std::vector<edge_id> edges; + }; + + /// \brief Specialization of mln::util::node for nodes with no + /// associated value. + template<> + struct node<void> + { + std::list<node_id> edges; + }; + + + /*-------. + | Edge. | + `-------*/ + + /// \brief Edge of a graph, holding a value of type \p T. + template<typename T> + struct edge + { + edge(node_id n1, node_id n2) + : pair_node_ (n1, n2) + {} + + /// Return the lowest node id adjacent to this edge. + node_id n1 () const { return pair_node_.first; } + /// Return the highest node id adjacent to this edge. + node_id n2 () const { return pair_node_.second; } + + T data; + ordpair_<node_id> pair_node_; + }; + + /// \brief Specialization of mln::util::node for edges with no + /// associated value. + template<> + struct edge <void> + { + edge(node_id n1, node_id n2) + : pair_node_ (n1, n2) + {} + + /// Return the lowest node id adjacent to this edge. + node_id n1 () const { return pair_node_.first; } + /// Return the highest node id adjacent to this edge. + node_id n2 () const { return pair_node_.second; } + + ordpair_<node_id> pair_node_; + }; + + // FIXME: Document this. In particular, we should state that edges are + // only compared w.r.t. their adjacent nodes, not the data they + // possibly hold! + template <typename E> + bool + operator==(const edge<E>& lhs, const edge<E>& rhs); + + template <typename E> + bool + operator< (const edge<E>& lhs, const edge<E>& rhs); + + + /*--------. + | Graph. | + `--------*/ + + namespace internal + { + /// \brief Base class for undirected graphs. + template<typename N, typename E> + class graph_base + { + public: + /* FIXME: Do we really want handle nodes and edges through + pointers? In my (Roland) opinion, this is just a drawback, + here. */ + /// The type of the set of nodes. + typedef std::vector< node<N>* > nodes_t; + /// The type of the set of edges. + typedef std::vector< edge<E>* > edges_t; + + /// Constructor. + graph_base(); + /// Destructor. + ~graph_base(); + + /// Return the node whose id is \a n. + /// \{ + util::node<N>& node(node_id n); + const util::node<N>& node(edge_id n) const; + /// \} + + /// Return the edge whose id is \a e. + /// \{ + util::edge<E>& edge(edge_id e); + const util::edge<E>& edge(edge_id e) const; + /// \} + + /// Return the whole nodes of the graph. + /// \{ + nodes_t& nodes (); + const nodes_t& nodes () const; + /// \} + + /// Return the whole edges of the graph. + /// \{ + edges_t& edges (); + const edges_t& edges () const; + /// \} + + /// \brief Return the number of nodes in the graph. + size_t nnodes() const; + /// \brief Return the number of edges in the graph. + size_t nedges() const; + + // FIXME: We might want to externalize this in routine of + // namespace mln::debug. + /** \brief Print on \p ostr the graph. + + \param[in] ostr The output stream. */ + void print_debug (std::ostream& ostr) const; + + protected: + /// Shortcuts factoring the insertion of nodes and edges. + /// \{ + void add_node_ (util::node<N>* node); + void add_edge_ (util::edge<E>* edge); + /// \} + + protected: + /// The nodes. + nodes_t nodes_; + /// The edges. + edges_t edges_; + }; + + } // end of namespace mln::util::internal + + + +# ifndef MLN_INCLUDE_ONLY + + template <typename E> + bool + operator==(const edge<E>& lhs, const edge<E>& rhs) + { + return lhs.pair_node_ == rhs.pair_node_; + } + + template <typename E> + bool + operator< (const edge<E>& lhs, const edge<E>& rhs) + { + return lhs.pair_node_ < rhs.pair_node_; + } + + namespace internal + { + + /*----------------. + | Ctor and dtor. | + `----------------*/ + + template<typename N, typename E> + inline + graph_base<N, E>::graph_base() + : nodes_(), edges_() + { + } + + template<typename N, typename E> + inline + graph_base<N, E>::~graph_base() + { + // FIXME: Delete data dynamically allocated in nodes_ and + // edges_. + } + + /*------------. + | Accessors. | + `------------*/ + + template<typename N, typename E> + inline + util::node<N>& + graph_base<N, E>::node(node_id n) + { + mln_assertion(n < this->nnodes()); + return *nodes_[n]; + } + + template<typename N, typename E> + inline + const util::node<N>& + graph_base<N, E>::node(node_id n) const + { + mln_assertion(n < this->nnodes()); + return *nodes_[n]; + } + + template<typename N, typename E> + inline + util::edge<E>& + graph_base<N, E>::edge(edge_id e) + { + mln_assertion(e < this->nedges()); + return *edges_[e]; + } + + template<typename N, typename E> + inline + const util::edge<E>& + graph_base<N, E>::edge(edge_id e) const + { + mln_assertion(e < this->nedges()); + return *edges_[e]; + } + + template<typename N, typename E> + inline + typename graph_base<N, E>::nodes_t& + graph_base<N, E>::nodes() + { + return nodes_; + } + + template<typename N, typename E> + inline + const typename graph_base<N, E>::nodes_t& + graph_base<N, E>::nodes() const + { + return nodes_; + } + + template<typename N, typename E> + inline + typename graph_base<N, E>::edges_t& + graph_base<N, E>::edges() + { + return edges_; + } + + template<typename N, typename E> + inline + const typename graph_base<N, E>::edges_t& + graph_base<N, E>::edges() const + { + return edges_; + } + + template<typename N, typename E> + inline + size_t + graph_base<N, E>::nnodes() const + { + return nodes_.size(); + } + + template<typename N, typename E> + inline + size_t + graph_base<N, E>::nedges() const + { + return edges_.size(); + } + + /*---------------. + | Manipulators. | + `---------------*/ + + template<typename N, typename E> + inline + void + graph_base<N, E>::add_node_(util::node<N>* node) + { + nodes_.push_back (node); + } + + template<typename N, typename E> + inline + void + graph_base<N, E>::add_edge_(util::edge<E>* edge) + { + // Does this edge already exist in the graph? + if (std::find(edges_.begin(), edges_.end(), edge) != edges_.end ()) + { + delete edge; + edge = 0; + } + else + { + edges_.push_back (edge); + nodes_[edge->n1()]->edges.push_back(edge->n2()); + nodes_[edge->n2()]->edges.push_back(edge->n1()); + } + } + + /*--------. + | Debug. | + `--------*/ + + template<typename N, typename E> + inline + void + graph_base<N, E>::print_debug (std::ostream& ostr) const + { + ostr << "graph: " << std::endl; + int i = 0; + for (typename nodes_t::const_iterator n = nodes_.begin (); + n != nodes_.end (); ++n, ++i) + { + ostr << "node: " << i << std::endl << " -- adjacent nodes: "; + for (typename edges_t::const_iterator e = (*n)->edges.begin(); + e != (*n)->edges.end(); ++e) + ostr << *e << " "; + ostr << std::endl; + } + ostr << std::endl; + } + + } // end of namespace mln::util::internal + +# endif // ! MLN_INCLUDE_ONLY + + } // end of namespace mln::util + +} // end of namespace mln + +#endif // ! MLN_UTIL_INTERNAL_GRAPH_BASE_HH Index: mln/util/graph.hh --- mln/util/graph.hh (revision 1712) +++ mln/util/graph.hh (working copy) @@ -1,4 +1,4 @@ -// Copyright (C) 2007 EPITA Research and Development Laboratory +// Copyright (C) 2007, 2008 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 @@ -28,274 +28,278 @@ #ifndef MLN_UTIL_GRAPH_HH # define MLN_UTIL_GRAPH_HH -# include <mln/core/concept/object.hh> -# include <cstddef> -# include <ostream> -# include <vector> -# include <list> -# include <algorithm> -# include <mln/util/ordpair.hh> - -/*! \file mln/util/graph.hh - * - * \brief Definition of a graph. - */ - -// FIXME: Rename `s_node' to `node'. -// FIXME: Rename `s_edge' to `edge'. -// FIXME: Rename `links' to `edges'. +/// \file mln/util/graph.hh +/// \brief Definitions of undirected graphs. + +# include <mln/util/internal/graph_base.hh> + + +// FIXME: More doc! + namespace mln { + namespace util { + /*-----------. + | Fwd decl. | + `-----------*/ + + /// \brief Undirected graph. + template<typename N = void, typename E = void> + class graph; + + /*--------------------. + | graph<void, void>. | + `--------------------*/ - /*! \brief Structure of generic node. - * - */ - template<typename T> - struct s_node - { - T data; - // FIXME: Rename to `out_edges'. - std::vector<unsigned> links; - }; - - - /*! \brief Structure of node with void parameter. - * - */ + /// Specialization for undirected graphs with no data on nodes nor + /// on edges. template<> - struct s_node<void> + class graph<void, void> : public internal::graph_base<void, void> { - // FIXME: Rename to `out_edges'. - std::list<unsigned> links; - }; + public: + /// The super class. + typedef internal::graph_base<void, void> super; - - /*! \brief Structure of generic edge. - * - */ - template<typename T> - struct s_edge - { - s_edge() - : pair_node_ (0, 0) - {} - - T data; - ordpair_<unsigned> pair_node_; + // FIXME: We should return the id of the newly created node. + /// \brief Add a node. + void add_node(); + // FIXME: We should return the id of the newly created edge. + /// \brief Add an edge between nodes with ids \p n1 and \p n2. + void add_edge(node_id n1, node_id n2); }; - /*! \brief Structure of edge with void parameter. - * - */ - template<> - struct s_edge <void> - { - s_edge() : pair_node_ (0, 0) {} - ordpair_<unsigned> pair_node_; + /*-----------------. + | graph<N, void>. | + `-----------------*/ + + /// Specialization for undirected graphs with data on nodes. + template <typename N> + class graph<N, void> : public internal::graph_base<N, void> + { + public: + /// The super class. + typedef internal::graph_base<N, void> super; + + // FIXME: We should return the id of the newly created node. + /// \brief Add a node. + void add_node(const N& data); + // FIXME: We should return the id of the newly created edge. + /// \brief Add an edge between nodes with ids \p n1 and \p n2. + void add_edge(node_id n1, node_id n2); + + /// Return the data associated to node with id \a n. + /// \{ + N& node_data(node_id n); + const N& node_data(node_id n) const; + /// \} }; - bool operator==(const struct s_edge <void>& lhs, - const struct s_edge <void>& rhs); - - bool operator< (const struct s_edge <void>& lhs, - const struct s_edge <void>& rhs); + /*--------------. + | graph<N, E>. | + `--------------*/ - /// \brief Generic graph structure using s_node and s_edge. - /* FIXME: We don't mention anywhere whether this graph structure - handles directed or undirected graphs! */ - template<typename N, typename E = void> - struct graph - { - /* FIXME: Do we really want handle edges and nodes through - pointers? In my (Roland) opinion, this is just a drawback, - here. */ - - /// The type of the set of nodes. - typedef std::vector< s_node<N>* > nodes; - /// The type of the set of edges. - typedef std::vector< s_edge<E>* > edges; + /// Specialization for undirected graphs with data on nodes and + /// edges. + template <typename N, typename E> + class graph : public internal::graph_base<N, E> + { + public: + /// The super class. + typedef internal::graph_base<N, E> super; + + // FIXME: We should return the id of the newly created node. + /// \brief Add a node. + void add_node(const N& data); + /// \brief Add an edge between nodes with ids \p n1 and \p n2. + // FIXME: We should return the id of the newly created edge. + void add_edge(node_id n1, node_id n2, const E& data); + + /// Return the data associated to node with id \a n. + /// \{ + N& node_data(node_id n); + const N& node_data(node_id n) const; + /// \} + + /// Return the data associated to the edge with id \a e. + /// \{ + E& edge_data(edge_id e); + const E& edge_data(edge_id e) const; + /// \} + + /// Return the data associated to the edge between nodes with + /// ids \a n1 and \a n2. + /// \{ + E& edge_data(node_id n1, node_id n2); + const E& edge_data(node_id n1, node_id n2) const; + /// \} + }; - /// Constructor. - graph (); - /// Destructor. - ~graph(); - /*! \brief Add a void node. */ - void add_node (); +# ifndef MLN_INCLUDE_ONLY + /*--------------------. + | graph<void, void>. | + `--------------------*/ - /*! \brief Add a void edge between \p n1 and \p n2. - * - * \param[in] n1 The first node to link. - * \param[in] n2 The second node to link. - * - * \pre n1 < nb_node_. - * \pre n2 < nb_node_. - */ - void add_edge (unsigned n1, unsigned n2); - - - /*! \brief Check the consistency of the graph. - * - * Check if all edge have their node in the graph. - * - * \pre nodes_.size () == nb_node_. - * \pre links_.size () == nb_link_. - */ - void consistency () const; - - - /*! \brief Print on \p ostr the graph. - * - * \param[in] ostr The output stream. - */ - void print_debug (std::ostream& ostr) const; + /* Note that ddefinition of members from fully specialized + template classes are not preceded by `template<>'. */ + inline + void + graph<void, void>::add_node() + { + super::add_node_(new util::node<void>); + } + /* Note that ddefinition of members from fully specialized + template classes are not preceded by `template<>'. */ + inline + void + graph<void, void>::add_edge(node_id n1, node_id n2) + { + super::add_edge_(new util::edge<void>(n1, n2)); + } + /*-----------------. + | graph<N, void>. | + `-----------------*/ - /// The nuber of nodes. - unsigned nb_node_; + template<typename N> + inline + void + graph<N, void>::add_node(const N& data) + { + super::add_node_(new util::node<N>(data)); + } - /// The nuber of links. - unsigned nb_link_; + template<typename N> + inline + void + graph<N, void>::add_edge(node_id n1, node_id n2) + { + mln_assertion(n1 < this->nnodes()); + mln_assertion(n2 < this->nnodes()); + super::add_edge_(new util::edge<void>(n1, n2)); + } - /// The vector where is stocked the pointers of nodes. - nodes nodes_; + template <class N> + inline + N& + graph<N, void>::node_data(node_id n) + { + mln_assertion(n < this->nnodes()); + return this->nodes_[n]->data; + } - /// The vector where is stocked the pointers of links. - edges links_; - }; + template<typename N> + inline + const N& + graph<N, void>::node_data(node_id n) const + { + mln_assertion(n < this->nnodes()); + return this->nodes_[n]->data; + } -# ifndef MLN_INCLUDE_ONLY + /*--------------. + | graph<N, E>. | + `--------------*/ - bool - operator==(const struct s_edge <void>& lhs, const struct s_edge <void>& rhs) + template<typename N, typename E> + inline + void + graph<N, E>::add_node(const N& data) { - return lhs.pair_node_ == rhs.pair_node_; + super::add_node_(new util::node<N>(data)); } - bool - operator< (const struct s_edge <void>& lhs, const struct s_edge <void>& rhs) + template<typename N, typename E> + inline + void + graph<N, E>::add_edge(node_id n1, node_id n2, const E& data) { - return lhs.pair_node_ < rhs.pair_node_; + mln_assertion(n1 < this->nnodes()); + mln_assertion(n2 < this->nnodes()); + super::add_edge_(new util::edge<E>(n1, n2, data)); } template<typename N, typename E> inline - graph<N, E>::graph () - : nb_node_ (0), - nb_link_ (0), - nodes_ (0), - links_ (0) + N& + graph<N, E>::node_data(node_id n) { + mln_assertion(n < this->nnodes()); + return this->nodes_[n]->data; } template<typename N, typename E> inline - graph<N, E>::~graph () + const N& + graph<N, E>::node_data(node_id n) const { + mln_assertion(n < this->nnodes()); + return this->nodes_[n]->data; } template<typename N, typename E> inline - void - graph<N, E>::add_node () + E& + graph<N, E>::edge_data(edge_id e) { - struct s_node<N>* n = new struct s_node<N>; - - nodes_.push_back (n); - ++nb_node_; + mln_assertion(e < this->nedges()); + return this->edges_[e]->data; } template<typename N, typename E> inline - void - graph<N, E>::add_edge (unsigned n1, unsigned n2) + const E& + graph<N, E>::edge_data(edge_id e) const { - mln_precondition(n1 < this->nb_node_); - mln_precondition(n2 < this->nb_node_); - - struct s_edge<E>* edge; - - edge = new s_edge<E>; - edge->pair_node_.first = n1; - edge->pair_node_.second = n2; - // Does this edge already exist in the graph? - if (std::find(links_.begin(), links_.end(), edge) != links_.end ()) - { - delete edge; - edge = 0; - } - else - { - links_.push_back (edge); - ++nb_link_; - /* FIXME: In fact, we should store adjaceny information in - *both* nodes. Change this globally later, and mention - that the graph is undirected in the documentation. And - don't forget to update clients! */ - nodes_[n1]->links.push_back (n2); - } + mln_assertion(e < this->nedges()); + return this->edges_[e]->data; } template<typename N, typename E> inline - void - graph<N, E>::consistency () const + E& + graph<N, E>::edge_data(node_id n1, node_id n2) { - mln_precondition(nodes_.size () == this->nb_node_); - mln_precondition(links_.size () == this->nb_link_); - typename std::vector<struct s_node <N>*>::const_iterator it = - nodes_.begin (); - for (; it != nodes_.end (); ++it) - { - typename std::list<unsigned>::const_iterator it2 = - (*it)->links.begin (); - for (; it2 != (*it)->links.end (); ++it2) - mln_precondition((*it2) < nb_node_); - } - - typename std::vector<struct s_edge<E>*>::const_iterator it3 = - links_.begin (); - for (; it3 != links_.end (); ++it3) - { - mln_precondition((*it3)->pair_node_.first < nb_node_); - mln_precondition((*it3)->pair_node_.second < nb_node_); - } + mln_assertion(n1 < this->nnodes()); + mln_assertion(n2 < this->nnodes()); + ordpair_<node_id> node_pair (n1, n2); + std::vector<edge_id>& edges_ids = this->nodes_[n1]->edges; + for (std::vector<edge_id>::iterator e = edges_ids.begin(); + e != edges_ids.end(); ++e) + if (this->edges_[*e] == node_pair) + return this->edges_[*e]->data; + // If no edge between N1 and N2 was found, abort. + abort(); } template<typename N, typename E> inline - void - graph<N, E>::print_debug (std::ostream& ostr) const - { - ostr << "nodes :" << std::endl; - - typename std::vector<struct s_node<N>*>::const_iterator it = - nodes_.begin (); - int i = 0; - for (; it != nodes_.end (); ++it, ++i) - { - ostr << "node number = " << i << " nbh : "; - typename std::list<unsigned>::const_iterator it2 = (*it)->links.begin (); - for (; it2 != (*it)->links.end (); ++it2) + const E& + graph<N, E>::edge_data(node_id n1, node_id n2) const { - ostr << (*it2) << " "; - } - ostr << std::endl; - } - ostr << std::endl; + mln_assertion(n1 < this->nnodes()); + mln_assertion(n2 < this->nnodes()); + ordpair_<node_id> node_pair (n1, n2); + const std::vector<edge_id>& edges_ids = this->nodes_[n1]->edges; + for (std::vector<edge_id>::const_iterator e = edges_ids.begin(); + e != edges_ids.end(); ++e) + if (this->edges_[*e] == node_pair) + return this->edges_[*e]->data; + // If no edge between N1 and N2 was found, abort. + abort(); } # endif // ! MLN_INCLUDE_ONLY - } // end of util + } // end of namespace mln::util -} // end of mln +} // end of namespace mln -#endif // MLN_GRAPH_HH +#endif // ! MLN_UTIL_GRAPH_HH Index: tests/util/graph.cc --- tests/util/graph.cc (revision 1712) +++ tests/util/graph.cc (working copy) @@ -1,4 +1,4 @@ -// Copyright (C) 2007 EPITA Research and Development Laboratory +// Copyright (C) 2007, 2008 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 @@ -25,12 +25,8 @@ // reasons why the executable file might be covered by the GNU General // Public License. -/*! - * \file tests/util/graph.cc - * - * \brief test of mln::util::graph - * - */ +/// \file tests/util/graph.cc +/// \brief test of mln::util::graph #include <mln/util/graph.hh> #include <iostream> @@ -55,5 +51,4 @@ g.add_edge (1, 0); g.add_edge (5, 3); g.add_edge (2, 1); - g.consistency (); }