Milena (Olena)
User documentation 2.0a Id
|
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