[Olena-patches] 1851: Speed up edge insertion into graphs.

https://svn.lrde.epita.fr/svn/oln/trunk/milena Index: ChangeLog from Roland Levillain &lt;roland(a)lrde.epita.fr&gt; Speed up edge insertion into graphs. * mln/util/internal/graph_base.hh: Stick to the coding style w.r.t. spaces. (mln::util::internal::graph_base<N, E>::edges_set_t): New typedef. (mln::util::internal::graph_base<N, E>::edges_set_): New member. (mln::util::internal::graph_base<N, E>::graph_base): Adjust ctor. (mln::util::internal::graph_base<N, E>::add_edge_): Use edges_set_ instead of edges_ to test the presence of an edge in the graph. * mln/util/graph.hh (mln::util::graph<void, void>::add_edge): Add missing preconditions. graph.hh | 2 ++ internal/graph_base.hh | 29 +++++++++++++++++++++-------- 2 files changed, 23 insertions(+), 8 deletions(-) Index: mln/util/graph.hh --- mln/util/graph.hh (revision 1850) +++ mln/util/graph.hh (working copy) @@ -162,6 +162,8 @@ void graph<void, 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)); } Index: mln/util/internal/graph_base.hh --- mln/util/internal/graph_base.hh (revision 1850) +++ mln/util/internal/graph_base.hh (working copy) @@ -31,12 +31,15 @@ /// \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 <vector> +# include <set> +# include <ostream> + +# include <mln/core/concept/object.hh> # include <mln/util/ordpair.hh> // FIXME: Rename node(s) as vertex (vertices). @@ -156,6 +159,9 @@ typedef std::vector< node<N>* > nodes_t; /// The type of the set of edges. typedef std::vector< edge<E>* > edges_t; + /// A set to test the presence of a given edge. + typedef std::set< edge<E>* > edges_set_t; + /// Constructor. graph_base(); @@ -210,6 +216,8 @@ nodes_t nodes_; /// The edges. edges_t edges_; + /// An index of the set of edges, for fast-access purpose. + edges_set_t edges_set_; }; } // end of namespace mln::util::internal @@ -242,7 +250,7 @@ template<typename N, typename E> inline graph_base<N, E>::graph_base() - : nodes_(), edges_() + : nodes_(), edges_(), edges_set_() { } @@ -354,22 +362,27 @@ nodes_.push_back (node); } + // FIXME: Return the (new) edge id. 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 ()) + if (edges_set_.find(edge) != edges_set_.end ()) { + // Remove the previously allocated data for EDGE. delete edge; edge = 0; } else { + // Otherwise insert it into the graph. edges_.push_back (edge); - nodes_[edge->n1()]->edges.push_back(edge->n2()); - nodes_[edge->n2()]->edges.push_back(edge->n1()); + edge_id id = edges_.size() - 1; + edges_set_.insert(edge); + nodes_[edge->n1()]->edges.push_back(id); + nodes_[edge->n2()]->edges.push_back(id); } }