Milena (Olena): line_graph.hh Source File

00001 // Copyright (C) 2008, 2009, 2010 EPITA Research and Development
00002 // Laboratory (LRDE)
00003 //
00004 // This file is part of Olena.
00005 //
00006 // Olena is free software: you can redistribute it and/or modify it under
00007 // the terms of the GNU General Public License as published by the Free
00008 // Software Foundation, version 2 of the License.
00009 //
00010 // Olena is distributed in the hope that it will be useful,
00011 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00012 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00013 // General Public License for more details.
00014 //
00015 // You should have received a copy of the GNU General Public License
00016 // along with Olena.  If not, see <http://www.gnu.org/licenses/>.
00017 //
00018 // As a special exception, you may use this file as part of a free
00019 // software project without restriction.  Specifically, if other files
00020 // instantiate templates or use macros or inline functions from this
00021 // file, or you compile this file and link it with other files to produce
00022 // an executable, this file does not by itself cause the resulting
00023 // executable to be covered by the GNU General Public License.  This
00024 // exception does not however invalidate any other reasons why the
00025 // executable file might be covered by the GNU General Public License.
00026 
00027 #ifndef MLN_UTIL_LINE_GRAPH_HH
00028 # define MLN_UTIL_LINE_GRAPH_HH
00029 
00033 
00034 # include <mln/util/internal/graph_base.hh>
00035 # include <mln/util/internal/graph_iter.hh>
00036 # include <mln/util/internal/graph_nbh_iter.hh>
00037 # include <mln/util/ord_pair.hh>
00038 
00039 namespace mln
00040 {
00041 
00042   namespace util
00043   {
00045     template <typename G>
00046     class line_graph;
00047   }
00048 
00049 
00050   namespace internal
00051   {
00052 
00054     template <typename G>
00055     struct data< util::line_graph<G> >
00056     {
00057       typedef util::line_graph<G> lg_t;
00058       typedef std::vector<std::vector<util::edge_id_t> > vertices_t;
00059       typedef std::vector<util::ord_pair<util::vertex_id_t> > edges_t;
00060 
00061       data();
00062       data(const G& g);
00063       ~data();
00064 
00065       G g_;
00067       vertices_t vertices_;
00069       edges_t edges_;
00070     };
00071 
00072   } // end of namespace mln::internal
00073 
00074 
00075   namespace util
00076   {
00077 
00081     template <typename G>
00082     class line_graph : public internal::graph_base< line_graph<G> >
00083     {
00085       typedef internal::graph_base< line_graph<G> > super;
00086 
00087       typedef typename super::vertex_t vertex_t;
00088       typedef typename super::edge_t edge_t;
00089 
00090       typedef typename super::vertex_data_t vertex_data_t;
00091       typedef typename super::edge_data_t edge_data_t;
00092 
00093     public:
00095       typedef std::vector<vertex_data_t> vertices_t;
00096 
00098       typedef std::vector<edge_data_t> edges_t;
00099 
00104       typedef mln::internal::vertex_fwd_iterator< line_graph<G> >
00105         vertex_fwd_iter;
00106       typedef mln::internal::vertex_bkd_iterator< line_graph<G> >
00107         vertex_bkd_iter;
00108       typedef vertex_fwd_iter vertex_iter;
00110 
00113       typedef mln::internal::edge_fwd_iterator< line_graph<G> >
00114         edge_fwd_iter;
00115       typedef mln::internal::edge_bkd_iterator< line_graph<G> >
00116         edge_bkd_iter;
00117       typedef edge_fwd_iter edge_iter;
00119 
00122       typedef mln::internal::edge_nbh_edge_fwd_iterator< line_graph<G> >
00123         edge_nbh_edge_fwd_iter;
00124       typedef mln::internal::edge_nbh_edge_bkd_iterator< line_graph<G> >
00125         edge_nbh_edge_bkd_iter;
00126       typedef edge_nbh_edge_fwd_iter edge_nbh_edge_iter;
00128 
00131       typedef mln::internal::vertex_nbh_vertex_fwd_iterator< line_graph<G> >
00132         vertex_nbh_vertex_fwd_iter;
00133       typedef mln::internal::vertex_nbh_vertex_bkd_iterator< line_graph<G> >
00134         vertex_nbh_vertex_bkd_iter;
00135       typedef vertex_nbh_vertex_fwd_iter vertex_nbh_vertex_iter;
00137 
00140       typedef mln::internal::vertex_nbh_edge_fwd_iterator< line_graph<G> >
00141         vertex_nbh_edge_fwd_iter;
00142       typedef mln::internal::vertex_nbh_edge_bkd_iterator< line_graph<G> >
00143         vertex_nbh_edge_bkd_iter;
00144       typedef vertex_nbh_edge_fwd_iter vertex_nbh_edge_iter;
00147 
00148       line_graph();
00149       line_graph(const G& g);
00150 
00157       vertex_t vertex(const vertex_id_t& id_v) const;
00159 
00161       // FIXME: Rename as nvertices.
00162       size_t v_nmax() const;
00163 
00165       // FIXME: Is the `_v' suffix really needed?
00166       bool has_v(const vertex_id_t& id_v) const;
00167 
00169       template <typename G2>
00170       bool has(const util::vertex<G2>& v) const;
00171 
00172 
00174       size_t v_nmax_nbh_edges(const vertex_id_t& id_v) const;
00175 
00177       edge_id_t v_ith_nbh_edge(const vertex_id_t& id_v, unsigned i) const;
00178 
00180       size_t v_nmax_nbh_vertices(const vertex_id_t& id_v) const;
00181 
00183       vertex_id_t v_ith_nbh_vertex(const vertex_id_t& id_v, unsigned i) const;
00185 
00186 
00187 
00188 
00192       edge_t edge(const edge_id_t& e) const;
00193 
00195       // FIXME: Rename as nedges.
00196       size_t e_nmax() const;
00197 
00199       // FIXME: Is the `_e' suffix really needed?
00200       bool has_e(const util::edge_id_t& id_e) const;
00201 
00203       template <typename G2>
00204       bool has(const util::edge<G2>& e) const;
00205 
00206 
00208       vertex_id_t v1(const edge_id_t& id_e) const;
00209 
00211       vertex_id_t v2(const edge_id_t& id_e) const;
00212 
00214       size_t e_nmax_nbh_edges(const edge_id_t& id_e) const;
00215 
00217       edge_id_t e_ith_nbh_edge(const edge_id_t& id_e, unsigned i) const;
00218 
00221       template <typename G2>
00222       bool is_subgraph_of(const G2& g) const;
00223 
00225       const G& graph() const;
00227 
00228     protected:
00229       using super::data_;
00230     };
00231 
00232     template <typename G>
00233     std::ostream&
00234     operator<<(std::ostream& ostr, const line_graph<G>& g);
00235 
00236   } // end of namespace mln::util
00237 
00238 } // end of namespace mln
00239 
00240 # ifndef MLN_INCLUDE_ONLY
00241 
00242 namespace mln
00243 {
00244 
00245   namespace internal
00246   {
00247 
00248     template <typename G>
00249     inline
00250     data< util::line_graph<G> >::data()
00251     {
00252     }
00253 
00254     template <typename G>
00255     inline
00256     data< util::line_graph<G> >::data(const G& g)
00257     {
00258       g_ = g;
00259 
00260       // Initialize vertices and edges.
00261       // FIXME: use an adjacency matrix!!
00262       std::set<util::ord_pair<util::vertex_id_t> > edges_set;
00263 
00264       vertices_.resize(g.e_nmax());
00265       mln_edge_iter(G) e(g);
00266       mln_edge_nbh_edge_iter(G) ne(e);
00267 
00268       for_all(e)
00269       {
00270         util::vertex_id_t v1(e.id().value());
00271         for_all(ne)
00272         {
00273           util::vertex_id_t v2(ne.id().value());
00274           util::ord_pair<util::vertex_id_t> edge(v1, v2);
00275           if (edges_set.find(edge) == edges_set.end())
00276           {
00277             vertices_[v1].push_back(edges_.size());
00278             vertices_[v2].push_back(edges_.size());
00279             edges_set.insert(edge);
00280             edges_.push_back(edge);
00281           }
00282         }
00283       }
00284     }
00285 
00286     template <typename G>
00287     inline
00288     data< util::line_graph<G> >::~data()
00289     {
00290     }
00291 
00292   } // end of namespace mln::internal
00293 
00294   namespace util
00295   {
00296 
00297     template <typename G>
00298     inline
00299     line_graph<G>::line_graph()
00300     {
00301       this->data_ = new mln::internal::data< util::line_graph<G> >();
00302     }
00303 
00304     template <typename G>
00305     inline
00306     line_graph<G>::line_graph(const G& g)
00307     {
00308       this->data_ = new mln::internal::data< util::line_graph<G> >(g);
00309     }
00310 
00311     /*---------------.
00312     | Vertex related |
00313     `---------------*/
00314 
00315     template <typename G>
00316     inline
00317     typename line_graph<G>::vertex_t
00318     line_graph<G>::vertex(const vertex_id_t& id_v) const
00319     {
00320       mln_assertion(has_v(id_v));
00321       return vertex_t(*this, id_v);
00322     }
00323 
00324 
00325     template <typename G>
00326     inline
00327     size_t
00328     line_graph<G>::v_nmax() const
00329     {
00330       return data_->g_.e_nmax();
00331     }
00332 
00333     template <typename G>
00334     inline
00335     bool
00336     line_graph<G>::has_v(const vertex_id_t& id_v) const
00337     {
00338       return data_->g_.has_v(id_v);
00339     }
00340 
00341     template <typename G>
00342     template <typename G2>
00343     inline
00344     bool
00345     line_graph<G>::has(const util::vertex<G2>& v) const
00346     {
00347       // FIXME: not sure...
00348       return v.graph().is_subgraph_of(*this) && has_v(v.id());
00349     }
00350 
00351     template <typename G>
00352     inline
00353     size_t
00354     line_graph<G>::v_nmax_nbh_edges(const vertex_id_t& id_v) const
00355     {
00356       mln_precondition(has_v(id_v));
00357       return data_->vertices_[id_v].size();
00358     }
00359 
00360     template <typename G>
00361     inline
00362     edge_id_t
00363     line_graph<G>::v_ith_nbh_edge(const vertex_id_t& id_v, unsigned i) const
00364     {
00365       mln_precondition(has_v(id_v));
00366       if (i >= v_nmax_nbh_edges(id_v))
00367         return v_nmax();
00368       return data_->vertices_[id_v][i];
00369     }
00370 
00371     template <typename G>
00372     inline
00373     size_t
00374     line_graph<G>::v_nmax_nbh_vertices(const vertex_id_t& id_v) const
00375     {
00376       mln_precondition(has_v(id_v));
00377       return v_nmax_nbh_edges(id_v);
00378     }
00379 
00380     template <typename G>
00381     inline
00382     vertex_id_t
00383     line_graph<G>::v_ith_nbh_vertex(const vertex_id_t& id_v, unsigned i) const
00384     {
00385       mln_precondition(has_v(id_v));
00386 
00387       unsigned id_e = this->v_ith_nbh_edge(id_v, i);
00388       return this->v_other(id_e, id_v);
00389      }
00390 
00391 
00392     /*--------------.
00393     | Edges related |
00394     `---------------*/
00395 
00396     template <typename G>
00397     inline
00398     typename line_graph<G>::edge_t
00399     line_graph<G>::edge(const edge_id_t& e) const
00400     {
00401       mln_assertion(e < e_nmax());
00402       return edge_t(*this, e);
00403     }
00404 
00405     template <typename G>
00406     inline
00407     size_t
00408     line_graph<G>::e_nmax() const
00409     {
00410       return data_->edges_.size();
00411     }
00412 
00413     template <typename G>
00414     inline
00415     bool
00416     line_graph<G>::has_e(const edge_id_t& id_e) const
00417     {
00418       return id_e < data_->edges_.size();
00419     }
00420 
00421     template <typename G>
00422     template <typename G2>
00423     inline
00424     bool
00425     line_graph<G>::has(const util::edge<G2>& e) const
00426     {
00427       return e.graph().is_subgraph_of(*this) && has_e(e.id());
00428     }
00429 
00430     template <typename G>
00431     inline
00432     vertex_id_t
00433     line_graph<G>::v1(const edge_id_t& id_e) const
00434     {
00435       mln_precondition(has_e(id_e));
00436       return data_->edges_[id_e].first();
00437     }
00438 
00439     template <typename G>
00440     inline
00441     vertex_id_t
00442     line_graph<G>::v2(const edge_id_t& id_e) const
00443     {
00444       mln_precondition(has_e(id_e));
00445       return data_->edges_[id_e].second();
00446     }
00447 
00448     template <typename G>
00449     inline
00450     size_t
00451     line_graph<G>::e_nmax_nbh_edges(const edge_id_t& id_e) const
00452     {
00453       mln_precondition(has_e(id_e));
00454       return v_nmax_nbh_edges(v1(id_e)) + v_nmax_nbh_edges(v2(id_e));
00455     }
00456 
00457     template <typename G>
00458     inline
00459     edge_id_t
00460     line_graph<G>::e_ith_nbh_edge(const edge_id_t& id_e, unsigned i) const
00461     {
00462       mln_precondition(has_e(id_e));
00463       if (i >= e_nmax_nbh_edges(id_e))
00464         return e_nmax();
00465 
00466       unsigned v1_nmax = v_nmax_nbh_edges(v1(id_e));
00467       if (i < v1_nmax)
00468         return v_ith_nbh_edge(v1(id_e), i);
00469       return  v_ith_nbh_edge(v2(id_e), i - v1_nmax);
00470     }
00471 
00472 
00473     template <typename G>
00474     template <typename G2>
00475     inline
00476     bool
00477     line_graph<G>::is_subgraph_of(const G2& g) const
00478     {
00479       return g.id() == this->id();
00480     }
00481 
00482     template <typename G>
00483     inline
00484     const G&
00485     line_graph<G>::graph() const
00486     {
00487       return this->data_->g_;
00488     }
00489 
00490     // FIXME: move to graph_base
00491     template <typename G>
00492     inline
00493     std::ostream&
00494     operator<<(std::ostream& ostr, const line_graph<G>& g)
00495     {
00496       typedef line_graph<G> LG;
00497       mln_vertex_iter(LG) v(g);
00498       mln_vertex_nbh_edge_iter(LG) e(v);
00499       for_all(v)
00500       {
00501         ostr << "v(" << v << ") : ";
00502         for_all(e)
00503           ostr << e << " ";
00504         ostr << std::endl;
00505       }
00506 
00507       return ostr;
00508     }
00509 
00510   } // end of namespace mln::util
00511 
00512 } // end of namespace mln
00513 
00514 # endif // ! MLN_INCLUDE_ONLY
00515 
00516 
00517 #endif // ! MLN_UTIL_LINE_GRAPH_HH