--- ChangeLog | 16 + milena/mln/core/concept/graph.hh | 2 +- milena/mln/util/graph.hh | 304 ++++++++++++++++++- milena/mln/util/internal/graph_base.hh | 326 +++----------------- milena/mln/util/internal/graph_edge.hh | 50 ++-- milena/mln/util/internal/graph_edge_iter.hh | 10 +- .../mln/util/internal/graph_edge_nbh_edge_iter.hh | 4 +- milena/mln/util/internal/graph_vertex.hh | 86 ++++-- milena/mln/util/internal/graph_vertex_iter.hh | 20 +- .../util/internal/graph_vertex_nbh_edge_iter.hh | 4 +- .../util/internal/graph_vertex_nbh_vertex_iter.hh | 4 +- 11 files changed, 463 insertions(+), 363 deletions(-) diff --git a/ChangeLog b/ChangeLog index 5e7c1a2..a01d9c9 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,21 @@ 2008-17-07 Guillaume Lazzara <z@lrde.epita.fr> + Use track_ptr in graph. + * milena/mln/core/concept/graph.hh, + * milena/util/graph.hh, + * milena/util/internal/graph_base.hh, + * milena/util/internal/graph_edge.hh, + * milena/util/internal/graph_edge_iter.hh, + * milena/util/internal/graph_edge_nbh_edge_iter.hh, + * milena/util/internal/graph_vertex.hh, + * milena/util/internal/graph_vertex_iter.hh, + * milena/util/internal/graph_vertex_nbh_edge_iter.hh, + * milena/util/internal/graph_vertex_nbh_vertex_iter.hh: + Share data between graphs. + Refactor some parts of the code. + +2008-17-07 Guillaume Lazzara <z@lrde.epita.fr> + Add sample code for the tutorial. * milena/mln/doc/tutorial/samples/borderthickness-output.tex, * milena/mln/doc/tutorial/samples/borderthickness.tex, diff --git a/milena/mln/core/concept/graph.hh b/milena/mln/core/concept/graph.hh index 36d94c9..c98d9e5 100644 --- a/milena/mln/core/concept/graph.hh +++ b/milena/mln/core/concept/graph.hh @@ -67,7 +67,7 @@ namespace mln typedef bkd_piter; // Misc. - void *graph_id() const; + const E& graph_id() const; template<typename G2> bool is_subgraph_of(const G2& gr) const; diff --git a/milena/mln/util/graph.hh b/milena/mln/util/graph.hh index b94dabc..765c07c 100644 --- a/milena/mln/util/graph.hh +++ b/milena/mln/util/graph.hh @@ -37,23 +37,66 @@ # include <mln/util/internal/graph_vertex_nbh_vertex_iter.hh> # include <mln/util/internal/graph_vertex_nbh_edge_iter.hh> # include <mln/util/internal/graph_edge_nbh_edge_iter.hh> +# include <mln/util/ord_pair.hh> namespace mln { namespace util { + /// Fwd declaration. + class graph; + } + + namespace internal + { + + /// Data structure for \c mln::image2d<T>. + template <> + struct data<util::graph> + { + typedef util::graph G; + typedef std::vector<std::vector<unsigned> > vertices_t; + typedef std::vector<util::ord_pair<unsigned> > edges_t; + typedef std::set<util::ord_pair<unsigned> > edges_set_t; + + data(); + ~data(); + + /// The vertices. + vertices_t vertices_; + /// 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::internal + + + namespace util + { /// \brief Undirected graph. class graph : public internal::graph_base<graph> { - public: /// The super class. typedef internal::graph_base<graph> super; + using super::vertex_data_t; + using super::edge_data_t; + + public: + /// The type of the set of vertices. + typedef std::vector<vertex_data_t> vertices_t; + + /// The type of the set of edges. + typedef std::vector<edge_data_t> edges_t; + /// A set to test the presence of a given edge. + typedef std::set<edge_data_t> edges_set_t; + /// Iterator types /// \{ - /// Vertex iterators /// \{ typedef mln::internal::vertex_fwd_iterator<graph> vertex_fwd_iter; @@ -88,13 +131,81 @@ namespace mln typedef mln::internal::edge_nbh_edge_bkd_iterator<graph> edge_nbh_edge_bkd_iter; typedef edge_nbh_edge_fwd_iter edge_nbh_edge_iter; /// \} + /// \} + + graph(); + /// Vertex oriented. + /// \{ + /// Shortcuts factoring the insertion of vertices and edges. + /// \{ + /// \brief Add a vertex. + /// + /// \return The id of the new vertex. + unsigned add_vertex(); + + /// Return the vertex whose id is \a v. + /// \{ + vertex_t vertex(unsigned id_v) const; /// \} + /// \brief Return the number of vertices in the graph. + size_t v_nmax() const; + + /// Check whether a vertex id \p id_v exists in the graph. + bool has_v(unsigned id_v) const; + + /// Return the number of adjacent edges of vertex \p id_v. + size_t v_nmax_nbh_edges(unsigned id_v) const; + + /// Returns the \p i th edge adjacent to the vertex \p id_v. + unsigned v_ith_nbh_edge(unsigned id_v, unsigned i) const; + + /// Return the number of adjacent vertices of vertex \p id_v. + size_t v_nmax_nbh_vertices(unsigned id_v) const; + + /// Returns the \p i th vertex adjacent to the vertex \p id_v. + unsigned v_ith_nbh_vertex(unsigned id_v, unsigned i) const; + /// \} + + + + + /// Edge oriented. + /// \{ + /// \brief Add an edge. + /// + /// \return The id of the new edge if it does not exist yet; + /// otherwise, return <tt>mln_max(unsigned)</tt>. + unsigned add_edge(unsigned id_v1, unsigned id_v2); + + /// Return the edge whose id is \a e. + edge_t edge(unsigned e) const; + + /// \brief Return the number of edges in the graph. + size_t e_nmax() const; + + /// Return whether \p id_e is in the graph. + bool has_e(unsigned id_e) const; + + /// Return the first vertex associated to the edge \p id_e. + unsigned v1(unsigned id_e) const; + + /// Return the second vertex associated to edge \p id_e + unsigned v2(unsigned id_e) const; + + /// Return the number max of adjacent edge, given an edge \p id_e. + size_t e_nmax_nbh_edges(unsigned id_e) const; + + /// Return the \p i th edge adjacent to the edge \p id_e. + unsigned e_ith_nbh_edge(unsigned id_e, unsigned i) const; + /// Return whether this graph is a subgraph /// Return always false here. template <typename G2> bool is_subgraph_of(const G2& g) const; + /// \} + }; } // end of namespace mln::util @@ -107,9 +218,198 @@ namespace mln namespace mln { + namespace internal + { + + inline + data<util::graph>::data() + { + } + + inline + data<util::graph>::~data() + { + } + + } // end of namespace mln::internal + namespace util { + inline + graph::graph() + { + this->data_ = new mln::internal::data<util::graph>(); + } + + /*---------------. + | Vertex related | + `---------------*/ + + inline + unsigned + graph::add_vertex() + { + /* FIXME: This is not thread-proof (these two lines should + form an atomic section). */ + data_->vertices_.resize(data_->vertices_.size() + 1); + + return v_nmax() - 1; + } + + inline + graph::vertex_t + graph::vertex(unsigned id_v) const + { + mln_assertion(has_v(id_v)); + return vertex_t(*this, id_v); + } + + + inline + size_t + graph::v_nmax() const + { + return data_->vertices_.size(); + } + + inline + bool + graph::has_v(unsigned id_v) const + { + return id_v < data_->vertices_.size(); + } + + inline + size_t + graph::v_nmax_nbh_edges(unsigned id_v) const + { + mln_precondition(has_v(id_v)); + return data_->vertices_[id_v].size(); + } + + inline + unsigned + graph::v_ith_nbh_edge(unsigned id_v, unsigned i) const + { + mln_precondition(has_v(id_v)); + if (i >= v_nmax_nbh_edges(id_v)) + return v_nmax(); + return data_->vertices_[id_v][i]; + } + + inline + size_t + graph::v_nmax_nbh_vertices(unsigned id_v) const + { + mln_precondition(has_v(id_v)); + return v_nmax_nbh_edges(id_v); + } + + inline + unsigned + graph::v_ith_nbh_vertex(unsigned id_v, unsigned i) const + { + mln_precondition(has_v(id_v)); + + unsigned id_e = v_ith_nbh_edge(id_v, i); + return v_other(id_e, id_v); + } + + + /*--------------. + | Edges related | + `---------------*/ + + inline + unsigned + graph::add_edge(unsigned id_v1, unsigned id_v2) + { + // Does this edge already exist in the graph? + edge_data_t edge(id_v1, id_v2); + if (data_->edges_set_.find(edge) != data_->edges_set_.end ()) + { + // Return the erroneous value. + return mln_max(unsigned); + } + else + { + // Otherwise insert it into the graph. + /* FIXME: This is not thread-proof (these two lines should + form an atomic section). */ + data_->edges_.push_back(edge); + unsigned id = data_->edges_.size() - 1; + + // Update the set of edges. + data_->edges_set_.insert(edge); + data_->vertices_[edge.first()].push_back(id); + data_->vertices_[edge.second()].push_back(id); + + return id; + } + } + + inline + graph::edge_t + graph::edge(unsigned e) const + { + mln_assertion(e < e_nmax()); + return edge_t(*this, e); + } + + inline + size_t + graph::e_nmax() const + { + return data_->edges_.size(); + } + + inline + bool + graph::has_e(unsigned id_e) const + { + return id_e < data_->edges_.size(); + } + + inline + unsigned + graph::v1(unsigned id_e) const + { + mln_precondition(has_e(id_e)); + return data_->edges_[id_e].first(); + } + + inline + unsigned + graph::v2(unsigned id_e) const + { + mln_precondition(has_e(id_e)); + return data_->edges_[id_e].second(); + } + + inline + size_t + graph::e_nmax_nbh_edges(unsigned id_e) const + { + mln_precondition(has_e(id_e)); + return v_nmax_nbh_edges(v1(id_e)) + v_nmax_nbh_edges(v2(id_e)); + } + + inline + unsigned + graph::e_ith_nbh_edge(unsigned id_e, unsigned i) const + { + mln_precondition(has_e(id_e)); + if (i >= e_nmax_nbh_edges(id_e)) + return e_nmax(); + + unsigned v1_nmax = v_nmax_nbh_edges(v1(id_e)); + if (i < v1_nmax) + return v_ith_nbh_edge(v1(id_e), i); + return v_ith_nbh_edge(v2(id_e), i - v1_nmax); + } + + template <typename G2> inline bool diff --git a/milena/mln/util/internal/graph_base.hh b/milena/mln/util/internal/graph_base.hh index 9f2e6e2..d98c6ff 100644 --- a/milena/mln/util/internal/graph_base.hh +++ b/milena/mln/util/internal/graph_base.hh @@ -42,12 +42,13 @@ # include <mln/core/concept/object.hh> # include <mln/core/concept/graph.hh> # include <mln/core/concept/proxy.hh> - -# include <mln/util/ord_pair.hh> -# include <mln/value/builtin/integers.hh> +# include <mln/core/internal/data.hh> # include <mln/util/internal/graph_edge.hh> # include <mln/util/internal/graph_vertex.hh> +# include <mln/util/ord_pair.hh> +# include <mln/util/tracked_ptr.hh> + namespace mln { @@ -65,21 +66,17 @@ namespace mln template<typename E> class graph_base : public Graph<E> { + + protected: /// The type of a vertex. typedef util::vertex<E> vertex_t; /// Internal vertex data type typedef std::vector<unsigned> vertex_data_t; - /// The type of the set of vertices. - typedef std::vector<vertex_data_t> vertices_t; /// The type of an edge. typedef util::edge<E> edge_t; /// Internal edge data type. typedef ord_pair<unsigned> edge_data_t; - /// The type of the set of edges. - typedef std::vector<edge_data_t> edges_t; - /// A set to test the presence of a given edge. - typedef std::set<edge_data_t> edges_set_t; public: /// Misc. methods @@ -88,87 +85,24 @@ namespace mln const void * const graph_id() const; /// \} - /// Vertex and edge oriented methods. - /// \{ - /// Returns the other adjacent vertex id of a given edge id \p id_e. - unsigned v_other(unsigned id_e, unsigned id_v) const; - /// \} - - - /// Vertex oriented. - /// \{ - - /// Shortcuts factoring the insertion of vertices and edges. + /// Vertex oriented methods /// \{ - /// \brief Add a vertex. - /// - /// \return The id of the new vertex. - unsigned add_vertex(); - - /// Return the vertex whose id is \a v. - /// \{ - vertex_t vertex(unsigned id_v) const; - /// \} - - /// \brief Return the number of vertices in the graph. - size_t v_nmax() const; - /// Check whether a vertex \p v exists in the graph. bool has(const util::vertex<E>& v) const; - /// Check whether a vertex id \p id_v exists in the graph. - bool has_v(unsigned id_v) const; - - /// Return the number of adjacent edges of vertex \p id_v. - size_t v_nmax_nbh_edges(unsigned id_v) const; - - /// Returns the \p i th edge adjacent to the vertex \p id_v. - unsigned v_ith_nbh_edge(unsigned id_v, unsigned i) const; - - /// Return the number of adjacent vertices of vertex \p id_v. - size_t v_nmax_nbh_vertices(unsigned id_v) const; - - /// Returns the \p i th vertex adjacent to the vertex \p id_v. - unsigned v_ith_nbh_vertex(unsigned id_v, unsigned i) const; - - /// \} - - - /// Edge oriented. - /// \{ - /// \brief Add an edge. - /// - /// \return The id of the new edge if it does not exist yet; - /// otherwise, return <tt>mln_max(unsigned)</tt>. - unsigned add_edge(unsigned id_v1, unsigned id_v2); /// \} - /// Return the edge whose id is \a e. + /// Edge oriented methods /// \{ - const edge_t& edge(unsigned e) const; - /// \} - - /// \brief Return the number of edges in the graph. - size_t e_nmax() const; - /// Check whether an edge \p e exists in the graph. bool has(const util::edge<E>& e) const; + /// \} - /// Return whether \p id_e is in the graph. - bool has_e(unsigned id_e) const; - - /// Return the first vertex associated to the edge \p id_e. - unsigned v1(unsigned id_e) const; - - /// Return the second vertex associated to edge \p id_e - unsigned v2(unsigned id_e) const; - - /// Return the number max of adjacent edge, given an edge \p id_e. - size_t e_nmax_nbh_edges(unsigned id_e) const; - - /// Return the \p i th edge adjacent to the edge \p id_e. - unsigned e_ith_nbh_edge(unsigned id_e, unsigned i) const; + /// Vertex and edge oriented methods. + /// \{ + /// Returns the other adjacent vertex id of a given edge id \p id_e. + unsigned v_other(unsigned id_e, unsigned id_v) const; /// \} // FIXME: We might want to externalize this in routine of @@ -182,20 +116,11 @@ namespace mln protected: - /// The vertices. - vertices_t vertices_; - /// The edges. - edges_t edges_; - /// An index of the set of edges, for fast-access purpose. - edges_set_t edges_set_; + /// Internal data, sharable by several graphs. + util::tracked_ptr< mln::internal::data<E> > data_; - /// Construction, assignments and destruction. - /// \{ + /// Constructor graph_base<E>(); - //graph_base<E>(const self_t& rhs); - //self_t& operator=(const self_t& rhs); - //~graph_base<E>(); - /// \} }; @@ -217,7 +142,6 @@ namespace mln template<typename E> inline graph_base<E>::graph_base() - : vertices_(), edges_(), edges_set_() { } @@ -230,7 +154,7 @@ namespace mln const void * const graph_base<E>::graph_id() const { - return this; + return static_cast<const void * const>(data_.ptr_); } /*-------------------------. @@ -242,15 +166,15 @@ namespace mln unsigned graph_base<E>::v_other(unsigned id_e, unsigned id_v) const { - mln_precondition(has_e(id_e)); - mln_precondition(has_v(id_v)); - mln_precondition(edges_[id_e].first() == id_v - || edges_[id_e].second() == id_v); - - const edge_data_t& e = edges_[id_e]; - if (e.first() == id_v) - return e.second(); - return e.first(); + const E *g = exact(this); + mln_precondition(g->has_e(id_e)); + mln_precondition(g->has_v(id_v)); + mln_precondition(g->v1(id_e) == id_v + || g->v2(id_e) == id_v); + + if (g->v1(id_e) == id_v) + return g->v2(id_e); + return g->v1(id_e); } /*---------------. @@ -259,201 +183,24 @@ namespace mln template<typename E> inline - unsigned - graph_base<E>::add_vertex() - { - /* FIXME: This is not thread-proof (these two lines should - form an atomic section). */ - vertices_.resize(vertices_.size() + 1); - - return vertices_.size() - 1; - } - - template<typename E> - inline - typename graph_base<E>::vertex_t - graph_base<E>::vertex(unsigned id_v) const - { - mln_assertion(has_v(id_v)); - - return vertex_t(this, id_v); - } - - template<typename E> - inline - size_t - graph_base<E>::v_nmax() const - { - return vertices_.size(); - } - - template<typename E> - inline bool graph_base<E>::has(const util::vertex<E>& v) const { return has_v(v.id()); } - template<typename E> - inline - bool - graph_base<E>::has_v(unsigned id_v) const - { - return id_v < vertices_.size(); - } - - template<typename E> - inline - size_t - graph_base<E>::v_nmax_nbh_edges(unsigned id_v) const - { - mln_precondition(has_v(id_v)); - - return vertices_[id_v].size(); - } - - template<typename E> - inline - unsigned - graph_base<E>::v_ith_nbh_edge(unsigned id_v, unsigned i) const - { - mln_precondition(has_v(id_v)); - if (i >= v_nmax_nbh_edges(id_v)) - return v_nmax(); - - return vertices_[id_v][i]; - } - - template<typename E> - inline - size_t - graph_base<E>::v_nmax_nbh_vertices(unsigned id_v) const - { - mln_precondition(has_v(id_v)); - return v_nmax_nbh_edges(id_v); - } - - template<typename E> - inline - unsigned - graph_base<E>::v_ith_nbh_vertex(unsigned id_v, unsigned i) const - { - mln_precondition(has_v(id_v)); - - unsigned id_e = v_ith_nbh_edge(id_v, i); - return v_other(id_e, id_v); - } - - /*--------------. | Edges related | `---------------*/ template<typename E> inline - unsigned - graph_base<E>::add_edge(unsigned id_v1, unsigned id_v2) - { - // Does this edge already exist in the graph? - edge_data_t edge(id_v1, id_v2); - if (edges_set_.find(edge) != edges_set_.end ()) - { - // Return the erroneous value. - return mln_max(unsigned); - } - else - { - // Otherwise insert it into the graph. - /* FIXME: This is not thread-proof (these two lines should - form an atomic section). */ - edges_.push_back(edge); - unsigned id = edges_.size() - 1; - - // Update the set of edges. - edges_set_.insert(edge); - vertices_[edge.first()].push_back(id); - vertices_[edge.second()].push_back(id); - - return id; - } - } - - template<typename E> - inline - const typename graph_base<E>::edge_t& - graph_base<E>::edge(unsigned e) const - { - mln_assertion(e < this->nedges()); - return edge_t(this, edges_[e].first(), edges_[e].second()); - } - - template<typename E> - inline - size_t - graph_base<E>::e_nmax() const - { - return edges_.size(); - } - - template<typename E> - inline bool graph_base<E>::has(const util::edge<E>& e) const { return has_e(e.id()); } - template<typename E> - inline - bool - graph_base<E>::has_e(unsigned id_e) const - { - return id_e < edges_.size(); - } - - template<typename E> - inline - unsigned - graph_base<E>::v1(unsigned id_e) const - { - mln_precondition(has_e(id_e)); - return edges_[id_e].first(); - } - - template<typename E> - inline - unsigned - graph_base<E>::v2(unsigned id_e) const - { - mln_precondition(has_e(id_e)); - return edges_[id_e].second(); - } - - template<typename E> - inline - size_t - graph_base<E>::e_nmax_nbh_edges(unsigned id_e) const - { - mln_precondition(has_e(id_e)); - return v_nmax_nbh_edges(v1(id_e)) + v_nmax_nbh_edges(v2(id_e)); - } - - template<typename E> - inline - unsigned - graph_base<E>::e_ith_nbh_edge(unsigned id_e, unsigned i) const - { - mln_precondition(has_e(id_e)); - if (i >= e_nmax_nbh_edges(id_e)) - return e_nmax(); - - unsigned v1_nmax = v_nmax_nbh_edges(v1(id_e)); - if (i < v1_nmax) - return v_ith_nbh_edge(v1(id_e), i); - return v_ith_nbh_edge(v2(id_e), i - v1_nmax); - } - /*--------. | Debug. | `--------*/ @@ -463,26 +210,25 @@ namespace mln void graph_base<E>::print_debug (std::ostream& ostr) const { + const E *g = exact(this); + ostr << "graph: " << std::endl; - for (unsigned v = 0; v < vertices_.size(); ++v) + for (unsigned v = 0; v < g->v_nmax(); ++v) { ostr << "vertex: " << v << std::endl << " -- adjacent vertices: "; - for (vertex_data_t::const_iterator e = - vertices_[v].begin(); e != vertices_[v].end(); - ++e) - if (v == edges_[*e].first()) - ostr << edges_[*e].second() << " "; - else - ostr << edges_[*e].first() << " "; + for (int n = 0; n < g->v_nmax_nbh_vertices(v); ++n) + ostr << g->v_ith_nbh_vertex(v, n) << " "; ostr << std::endl; } ostr << std::endl; ostr << "edges:" << std::endl; unsigned ei = 0; - for (edges_t::const_iterator e = edges_.begin(); e != edges_.end(); - ++e, ++ei) - ostr << "edge " << ei << ": (" << e->first() << ", " << e->second() << " )" << std::endl; + for (int i = 0; i < g->e_nmax(); ++i) + ostr << "edge " << i << ": (" + << g->v1(i) << ", " + << g->v2(i) << " )" + << std::endl; } } // end of namespace mln::util::internal diff --git a/milena/mln/util/internal/graph_edge.hh b/milena/mln/util/internal/graph_edge.hh index d878685..dcbf6ac 100644 --- a/milena/mln/util/internal/graph_edge.hh +++ b/milena/mln/util/internal/graph_edge.hh @@ -48,14 +48,14 @@ namespace mln template <typename G> class edge : public internal::edge_impl_<G> { - typedef mlc_const(G) graph_t; + typedef mlc_unconst(G) graph_t; public: /// Constructors /// \{ edge(); - explicit edge(graph_t *g); - edge(graph_t *g, unsigned id); + explicit edge(const graph_t& g); + edge(const graph_t& g, unsigned id); /// \} @@ -68,8 +68,8 @@ namespace mln /// Set id_ with \p id; void update_id(unsigned id); - /// Return pointer of the graph holding this edge. - const graph_t * g() const; + /// Return a reference to the graph holding this edge. + const graph_t& g() const; /// Set g_ with \p g; void change_graph(const graph_t& g); @@ -102,7 +102,7 @@ namespace mln /// \} private: - graph_t * g_; + graph_t g_; unsigned id_; }; @@ -126,7 +126,7 @@ namespace mln struct subject_impl< const util::edge<G>, E > { unsigned id() const; - const mlc_const(G) * g() const; + const mlc_const(G)& g() const; unsigned v_other(unsigned id_v) const; bool is_valid() const; unsigned v1() const; @@ -172,17 +172,17 @@ namespace mln template <typename G> inline - edge<G>::edge(graph_t *g) - : g_(g), id_(g->e_nmax()) + edge<G>::edge(const graph_t& g) + : g_(g), id_(g.e_nmax()) { } template <typename G> inline - edge<G>::edge(graph_t *g, unsigned id) + edge<G>::edge(const graph_t& g, unsigned id) : g_(g), id_(id) { - mln_precondition(g->has_e(id)); + mln_precondition(g.has_e(id)); } template <typename G> @@ -203,7 +203,7 @@ namespace mln template <typename G> inline - const typename edge<G>::graph_t * + const typename edge<G>::graph_t& edge<G>::g() const { return g_; @@ -214,7 +214,7 @@ namespace mln void edge<G>::change_graph(const graph_t& g) { - g_ = & g; + g_ = g; } template <typename G> @@ -223,7 +223,7 @@ namespace mln edge<G>::v_other(unsigned id_v) const { mln_precondition(v1() == id_v || v2() == id_v); - return g_->v_other(id_, id_v); + return g_.v_other(id_, id_v); } template <typename G> @@ -231,7 +231,7 @@ namespace mln bool edge<G>::is_valid() const { - return g_ != 0 && g_->has_e(id_); + return g_.has_e(id_); } template <typename G> @@ -239,8 +239,8 @@ namespace mln unsigned edge<G>::v1() const { - mln_precondition(g_->has_e(id_)); - return g_->v1(id_); + mln_precondition(g_.has_e(id_)); + return g_.v1(id_); } template <typename G> @@ -248,8 +248,8 @@ namespace mln unsigned edge<G>::v2() const { - mln_precondition(g_->has_e(id_)); - return g_->v2(id_); + mln_precondition(g_.has_e(id_)); + return g_.v2(id_); } template <typename G> @@ -257,8 +257,8 @@ namespace mln size_t edge<G>::nmax_nbh_edges() const { - mln_precondition(g_->has_e(id_)); - return g_->e_nmax_nbh_edges(id_); + mln_precondition(g_.has_e(id_)); + return g_.e_nmax_nbh_edges(id_); } template <typename G> @@ -266,8 +266,8 @@ namespace mln unsigned edge<G>::ith_nbh_edge(unsigned i) const { - mln_precondition(g_->has_e(id_)); - return g_->e_ith_nbh_edge(id_, i); + mln_precondition(g_.has_e(id_)); + return g_.e_ith_nbh_edge(id_, i); } @@ -315,7 +315,7 @@ namespace mln template <typename G, typename E> inline - const mlc_const(G) * + const mlc_const(G)& subject_impl< const util::edge<G>, E >::g() const { return exact_().get_subject().g(); @@ -387,7 +387,7 @@ namespace mln void subject_impl< util::edge<G>, E >::change_graph(const mlc_const(G)& g) { - return exact_().get_subject().change_graph(&g); + return exact_().get_subject().change_graph(g); } } // End of namespace mln::internal diff --git a/milena/mln/util/internal/graph_edge_iter.hh b/milena/mln/util/internal/graph_edge_iter.hh index 9bcf9ff..b3d83de 100644 --- a/milena/mln/util/internal/graph_edge_iter.hh +++ b/milena/mln/util/internal/graph_edge_iter.hh @@ -142,7 +142,7 @@ namespace mln template <typename G> inline edge_fwd_iterator<G>::edge_fwd_iterator(const G& g) - : e_(util::edge<G>(&g)) + : e_(util::edge<G>(g)) { invalidate(); } @@ -160,7 +160,7 @@ namespace mln void edge_fwd_iterator<G>::invalidate() { - e_.update_id(e_.g()->e_nmax()); + e_.update_id(e_.g().e_nmax()); } template <typename G> @@ -210,7 +210,7 @@ namespace mln template <typename G> inline edge_bkd_iterator<G>::edge_bkd_iterator(const G& g) - : e_(util::edge<G>(&g)) + : e_(util::edge<G>(g)) { invalidate(); } @@ -228,7 +228,7 @@ namespace mln void edge_bkd_iterator<G>::invalidate() { - e_.update_id(e_.g()->e_nmax()); + e_.update_id(e_.g().e_nmax()); } template <typename G> @@ -236,7 +236,7 @@ namespace mln void edge_bkd_iterator<G>::start() { - e_.update_id(e_.g()->e_nmax() - 1); + e_.update_id(e_.g().e_nmax() - 1); } template <typename G> diff --git a/milena/mln/util/internal/graph_edge_nbh_edge_iter.hh b/milena/mln/util/internal/graph_edge_nbh_edge_iter.hh index 084ad23..3ba8d0e 100644 --- a/milena/mln/util/internal/graph_edge_nbh_edge_iter.hh +++ b/milena/mln/util/internal/graph_edge_nbh_edge_iter.hh @@ -158,7 +158,7 @@ namespace mln void edge_nbh_edge_fwd_iterator<G>::invalidate() { - i_ = e_.g()->e_nmax(); + i_ = e_.g().e_nmax(); } template <typename G> @@ -256,7 +256,7 @@ namespace mln void edge_nbh_edge_bkd_iterator<G>::invalidate() { - i_ = e_.g()->e_nmax(); + i_ = e_.g().e_nmax(); } template <typename G> diff --git a/milena/mln/util/internal/graph_vertex.hh b/milena/mln/util/internal/graph_vertex.hh index 8d35282..61b589f 100644 --- a/milena/mln/util/internal/graph_vertex.hh +++ b/milena/mln/util/internal/graph_vertex.hh @@ -43,15 +43,15 @@ namespace mln template<typename G> class vertex : public internal::vertex_impl_<G> { - typedef mlc_const(G) graph_t; + typedef mlc_unconst(G) graph_t; public: /// Constructors. /// \{ vertex(); - explicit vertex(graph_t *g); - vertex(graph_t *g, unsigned id); + explicit vertex(const graph_t& g); + vertex(const graph_t& g, unsigned id); /// \} /// Check whether the vertex is still part of the graph. @@ -82,16 +82,26 @@ namespace mln void update_id(unsigned id); /// Returns the graph pointer this vertex belongs to. - const graph_t * g() const; + const graph_t& g() const; /// Returns vertex id. unsigned id() const; - private: - graph_t * g_; + protected: + graph_t g_; unsigned id_; }; + /// Comparison operator. Test whether two vertices have the same id. + template<typename G> + bool + operator==(const util::vertex<G>& v1, const util::vertex<G>& v2); + + /// Inferior operator. Test whether lhs.id() < rhs.id(). + template<typename G> + bool + operator<(const util::vertex<G>& lhs, const util::vertex<G>& rhs); + } // End of namespace mln::util @@ -103,7 +113,7 @@ namespace mln struct subject_impl< const util::vertex<G>, E > { bool is_valid() const; - const mlc_const(G) * g() const; + const mlc_const(G)& g() const; unsigned id() const; unsigned other(unsigned id_e) const; @@ -142,26 +152,44 @@ namespace mln namespace util { + template<typename G> + inline + bool + operator==(const util::vertex<G>& v1, const util::vertex<G>& v2) + { + return v1.id() == v2.id(); + } + + template<typename G> + inline + bool + operator<(const util::vertex<G>& lhs, const util::vertex<G>& rhs) + { + return lhs.id() < rhs.id(); + } + + + template <typename G> inline vertex<G>::vertex() - : g_(0), id_(0) + : id_(0) { } template <typename G> inline - vertex<G>::vertex(graph_t *g) - : g_(g), id_(g_->v_nmax()) + vertex<G>::vertex(const graph_t& g) + : g_(g), id_(g_.v_nmax()) { } template<typename G> inline - vertex<G>::vertex(graph_t *g, unsigned id) + vertex<G>::vertex(const graph_t& g, unsigned id) : g_(g), id_(id) { - mln_precondition(g_->has_v(id)); + mln_precondition(g_.has_v(id)); } template<typename G> @@ -169,7 +197,7 @@ namespace mln bool vertex<G>::is_valid() const { - return g_ != 0 && g_->has_v(id_); + return g_.has_v(id_); } template<typename G> @@ -177,7 +205,7 @@ namespace mln void vertex<G>::invalidate() { - id_ = g_->v_nmax(); + id_ = g_.v_nmax(); } @@ -186,10 +214,10 @@ namespace mln unsigned vertex<G>::other(unsigned id_e) const { - mln_precondition(g_->has_v(id_)); - mln_precondition(g_->has_e(id_e)); - mln_precondition(g_->v1(id_e) == id_ || g_->v2(id_e) == id_); - return g_->v_other(id_e, id_); + mln_precondition(g_.has_v(id_)); + mln_precondition(g_.has_e(id_e)); + mln_precondition(g_.v1(id_e) == id_ || g_.v2(id_e) == id_); + return g_.v_other(id_e, id_); } template<typename G> @@ -197,8 +225,8 @@ namespace mln unsigned vertex<G>::ith_nbh_edge(unsigned i) const { - mln_precondition(g_->has_v(id_)); - return g_->v_ith_nbh_edge(id_, i); + mln_precondition(g_.has_v(id_)); + return g_.v_ith_nbh_edge(id_, i); } template<typename G> @@ -206,8 +234,8 @@ namespace mln unsigned vertex<G>::nmax_nbh_edges() const { - mln_precondition(g_->has_v(id_)); - return g_->v_nmax_nbh_edges(id_); + mln_precondition(g_.has_v(id_)); + return g_.v_nmax_nbh_edges(id_); } template<typename G> @@ -215,8 +243,8 @@ namespace mln unsigned vertex<G>::ith_nbh_vertex(unsigned i) const { - mln_precondition(g_->has_v(id_)); - return g_->v_ith_nbh_vertex(id_, i); + mln_precondition(g_.has_v(id_)); + return g_.v_ith_nbh_vertex(id_, i); } template<typename G> @@ -224,8 +252,8 @@ namespace mln unsigned vertex<G>::nmax_nbh_vertices() const { - mln_precondition(g_->has_v(id_)); - return g_->v_nmax_nbh_vertices(id_); + mln_precondition(g_.has_v(id_)); + return g_.v_nmax_nbh_vertices(id_); } template<typename G> @@ -233,7 +261,7 @@ namespace mln void vertex<G>::change_graph(const G& g) { - g_ = &g; + g_ = g; } template<typename G> @@ -246,7 +274,7 @@ namespace mln template<typename G> inline - const typename vertex<G>::graph_t * + const typename vertex<G>::graph_t& vertex<G>::g() const { return g_; @@ -283,7 +311,7 @@ namespace mln template <typename G, typename E> inline - const mlc_const(G)* + const mlc_const(G)& subject_impl< const util::vertex<G>, E >::g() const { return exact_().get_subject().g(); diff --git a/milena/mln/util/internal/graph_vertex_iter.hh b/milena/mln/util/internal/graph_vertex_iter.hh index da564e7..d77611f 100644 --- a/milena/mln/util/internal/graph_vertex_iter.hh +++ b/milena/mln/util/internal/graph_vertex_iter.hh @@ -108,6 +108,8 @@ namespace mln /// Go to the next value. void next(); + void update_graph(const G& g); + /// Return current index unsigned index() const; /// \} @@ -156,7 +158,7 @@ namespace mln void vertex_fwd_iterator<G>::invalidate() { - v_.update_id(v_.g()->v_nmax()); + v_.update_id(v_.g().v_nmax()); } template<typename G> @@ -180,7 +182,7 @@ namespace mln void vertex_fwd_iterator<G>::update_graph(const G& g) { - v_ = util::vertex<G>(&g); + v_ = util::vertex<G>(g); } template<typename G> @@ -213,8 +215,8 @@ namespace mln template<typename G> inline vertex_bkd_iterator<G>::vertex_bkd_iterator(const G& g) - : v_(util::vertex<G>(&g)) { + update_graph(g); invalidate(); } @@ -231,7 +233,7 @@ namespace mln void vertex_bkd_iterator<G>::invalidate() { - v_.update_id(v_.g()->v_nmax()); + v_.update_id(v_.g().v_nmax()); } template<typename G> @@ -239,7 +241,7 @@ namespace mln void vertex_bkd_iterator<G>::start() { - v_.update_id(v_.g()->v_nmax() - 1); + v_.update_id(v_.g().v_nmax() - 1); } template<typename G> @@ -252,6 +254,14 @@ namespace mln template<typename G> inline + void + vertex_bkd_iterator<G>::update_graph(const G& g) + { + v_ = util::vertex<G>(g); + } + + template<typename G> + inline unsigned vertex_bkd_iterator<G>::index() const { diff --git a/milena/mln/util/internal/graph_vertex_nbh_edge_iter.hh b/milena/mln/util/internal/graph_vertex_nbh_edge_iter.hh index 4edc652..634dc07 100644 --- a/milena/mln/util/internal/graph_vertex_nbh_edge_iter.hh +++ b/milena/mln/util/internal/graph_vertex_nbh_edge_iter.hh @@ -157,7 +157,7 @@ namespace mln void vertex_nbh_edge_fwd_iterator<G>::invalidate() { - i_ = e_.g()->e_nmax(); + i_ = e_.g().e_nmax(); } template <typename G> @@ -249,7 +249,7 @@ namespace mln void vertex_nbh_edge_bkd_iterator<G>::invalidate() { - e_.update_id(e_.g()->e_nmax()); + e_.update_id(e_.g().e_nmax()); } template <typename G> diff --git a/milena/mln/util/internal/graph_vertex_nbh_vertex_iter.hh b/milena/mln/util/internal/graph_vertex_nbh_vertex_iter.hh index d51bc29..0dc87b5 100644 --- a/milena/mln/util/internal/graph_vertex_nbh_vertex_iter.hh +++ b/milena/mln/util/internal/graph_vertex_nbh_vertex_iter.hh @@ -158,7 +158,7 @@ namespace mln void vertex_nbh_vertex_fwd_iterator<G>::invalidate() { - i_ = v_.g()->v_nmax(); + i_ = v_.g().v_nmax(); } template <typename G> @@ -248,7 +248,7 @@ namespace mln void vertex_nbh_vertex_bkd_iterator<G>::invalidate() { - v_.update_id(v_.g()->e_nmax()); + v_.update_id(v_.g().e_nmax()); } template <typename G> -- 1.5.6.5