00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
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 }
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
00162 size_t v_nmax() const;
00163
00165
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
00196 size_t e_nmax() const;
00197
00199
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 }
00237
00238 }
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
00261
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 }
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
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
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
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
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 }
00511
00512 }
00513
00514 # endif // ! MLN_INCLUDE_ONLY
00515
00516
00517 #endif // ! MLN_UTIL_LINE_GRAPH_HH