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 #ifndef MLN_UTIL_LINE_GRAPH_HH
00027 # define MLN_UTIL_LINE_GRAPH_HH
00028
00032
00033 # include <mln/util/internal/graph_base.hh>
00034 # include <mln/util/internal/graph_iter.hh>
00035 # include <mln/util/internal/graph_nbh_iter.hh>
00036 # include <mln/util/ord_pair.hh>
00037
00038 namespace mln
00039 {
00040
00041 namespace util
00042 {
00044 template <typename G>
00045 class line_graph;
00046 }
00047
00048
00049 namespace internal
00050 {
00051
00053 template <typename G>
00054 struct data< util::line_graph<G> >
00055 {
00056 typedef util::line_graph<G> lg_t;
00057 typedef std::vector<std::vector<util::edge_id_t> > vertices_t;
00058 typedef std::vector<util::ord_pair<util::vertex_id_t> > edges_t;
00059
00060 data();
00061 data(const G& g);
00062 ~data();
00063
00064 G g_;
00066 vertices_t vertices_;
00068 edges_t edges_;
00069 };
00070
00071 }
00072
00073
00074 namespace util
00075 {
00076
00080 template <typename G>
00081 class line_graph : public internal::graph_base< line_graph<G> >
00082 {
00084 typedef internal::graph_base< line_graph<G> > super;
00085
00086 typedef typename super::vertex_t vertex_t;
00087 typedef typename super::edge_t edge_t;
00088
00089 typedef typename super::vertex_data_t vertex_data_t;
00090 typedef typename super::edge_data_t edge_data_t;
00091
00092 public:
00094 typedef std::vector<vertex_data_t> vertices_t;
00095
00097 typedef std::vector<edge_data_t> edges_t;
00098
00103 typedef mln::internal::vertex_fwd_iterator< line_graph<G> >
00104 vertex_fwd_iter;
00105 typedef mln::internal::vertex_bkd_iterator< line_graph<G> >
00106 vertex_bkd_iter;
00107 typedef vertex_fwd_iter vertex_iter;
00109
00112 typedef mln::internal::edge_fwd_iterator< line_graph<G> >
00113 edge_fwd_iter;
00114 typedef mln::internal::edge_bkd_iterator< line_graph<G> >
00115 edge_bkd_iter;
00116 typedef edge_fwd_iter edge_iter;
00118
00121 typedef mln::internal::edge_nbh_edge_fwd_iterator< line_graph<G> >
00122 edge_nbh_edge_fwd_iter;
00123 typedef mln::internal::edge_nbh_edge_bkd_iterator< line_graph<G> >
00124 edge_nbh_edge_bkd_iter;
00125 typedef edge_nbh_edge_fwd_iter edge_nbh_edge_iter;
00127
00130 typedef mln::internal::vertex_nbh_vertex_fwd_iterator< line_graph<G> >
00131 vertex_nbh_vertex_fwd_iter;
00132 typedef mln::internal::vertex_nbh_vertex_bkd_iterator< line_graph<G> >
00133 vertex_nbh_vertex_bkd_iter;
00134 typedef vertex_nbh_vertex_fwd_iter vertex_nbh_vertex_iter;
00136
00139 typedef mln::internal::vertex_nbh_edge_fwd_iterator< line_graph<G> >
00140 vertex_nbh_edge_fwd_iter;
00141 typedef mln::internal::vertex_nbh_edge_bkd_iterator< line_graph<G> >
00142 vertex_nbh_edge_bkd_iter;
00143 typedef vertex_nbh_edge_fwd_iter vertex_nbh_edge_iter;
00146
00147 line_graph();
00148 line_graph(const G& g);
00149
00156 vertex_t vertex(const vertex_id_t& id_v) const;
00158
00160 size_t v_nmax() const;
00161
00163 bool has_v(const vertex_id_t& id_v) const;
00165 template <typename G2>
00166 bool has(const util::vertex<G2>& v) const;
00167
00168
00170 size_t v_nmax_nbh_edges(const vertex_id_t& id_v) const;
00171
00173 edge_id_t v_ith_nbh_edge(const vertex_id_t& id_v, unsigned i) const;
00174
00176 size_t v_nmax_nbh_vertices(const vertex_id_t& id_v) const;
00177
00179 vertex_id_t v_ith_nbh_vertex(const vertex_id_t& id_v, unsigned i) const;
00181
00182
00183
00184
00188 edge_t edge(const edge_id_t& e) const;
00189
00191 size_t e_nmax() const;
00192
00194 bool has_e(const util::edge_id_t& id_e) const;
00195
00197 template <typename G2>
00198 bool has(const util::edge<G2>& e) const;
00199
00200
00202 vertex_id_t v1(const edge_id_t& id_e) const;
00203
00205 vertex_id_t v2(const edge_id_t& id_e) const;
00206
00208 size_t e_nmax_nbh_edges(const edge_id_t& id_e) const;
00209
00211 edge_id_t e_ith_nbh_edge(const edge_id_t& id_e, unsigned i) const;
00212
00215 template <typename G2>
00216 bool is_subgraph_of(const G2& g) const;
00217
00219 const G& graph() const;
00221
00222 protected:
00223 using super::data_;
00224 };
00225
00226 template <typename G>
00227 std::ostream&
00228 operator<<(std::ostream& ostr, const line_graph<G>& g);
00229
00230 }
00231
00232 }
00233
00234 # ifndef MLN_INCLUDE_ONLY
00235
00236 namespace mln
00237 {
00238
00239 namespace internal
00240 {
00241
00242 template <typename G>
00243 inline
00244 data< util::line_graph<G> >::data()
00245 {
00246 }
00247
00248 template <typename G>
00249 inline
00250 data< util::line_graph<G> >::data(const G& g)
00251 {
00252 g_ = g;
00253
00254
00255
00256 std::set<util::ord_pair<util::vertex_id_t> > edges_set;
00257
00258 vertices_.resize(g.e_nmax());
00259 mln_edge_iter(G) e(g);
00260 mln_edge_nbh_edge_iter(G) ne(e);
00261
00262 for_all(e)
00263 {
00264 util::vertex_id_t v1(e.id().value());
00265 for_all(ne)
00266 {
00267 util::vertex_id_t v2(ne.id().value());
00268 util::ord_pair<util::vertex_id_t> edge(v1, v2);
00269 if (edges_set.find(edge) == edges_set.end())
00270 {
00271 vertices_[v1].push_back(edges_.size());
00272 vertices_[v2].push_back(edges_.size());
00273 edges_set.insert(edge);
00274 edges_.push_back(edge);
00275 }
00276 }
00277 }
00278 }
00279
00280 template <typename G>
00281 inline
00282 data< util::line_graph<G> >::~data()
00283 {
00284 }
00285
00286 }
00287
00288 namespace util
00289 {
00290
00291 template <typename G>
00292 inline
00293 line_graph<G>::line_graph()
00294 {
00295 this->data_ = new mln::internal::data< util::line_graph<G> >();
00296 }
00297
00298 template <typename G>
00299 inline
00300 line_graph<G>::line_graph(const G& g)
00301 {
00302 this->data_ = new mln::internal::data< util::line_graph<G> >(g);
00303 }
00304
00305
00306
00307
00308
00309 template <typename G>
00310 inline
00311 typename line_graph<G>::vertex_t
00312 line_graph<G>::vertex(const vertex_id_t& id_v) const
00313 {
00314 mln_assertion(has_v(id_v));
00315 return vertex_t(*this, id_v);
00316 }
00317
00318
00319 template <typename G>
00320 inline
00321 size_t
00322 line_graph<G>::v_nmax() const
00323 {
00324 return data_->g_.e_nmax();
00325 }
00326
00327 template <typename G>
00328 inline
00329 bool
00330 line_graph<G>::has_v(const vertex_id_t& id_v) const
00331 {
00332 return data_->g_.has_v(id_v);
00333 }
00334
00335 template <typename G>
00336 template <typename G2>
00337 inline
00338 bool
00339 line_graph<G>::has(const util::vertex<G2>& v) const
00340 {
00341
00342 return v.graph().is_subgraph_of(*this) && has_v(v.id());
00343 }
00344
00345 template <typename G>
00346 inline
00347 size_t
00348 line_graph<G>::v_nmax_nbh_edges(const vertex_id_t& id_v) const
00349 {
00350 mln_precondition(has_v(id_v));
00351 return data_->vertices_[id_v].size();
00352 }
00353
00354 template <typename G>
00355 inline
00356 edge_id_t
00357 line_graph<G>::v_ith_nbh_edge(const vertex_id_t& id_v, unsigned i) const
00358 {
00359 mln_precondition(has_v(id_v));
00360 if (i >= v_nmax_nbh_edges(id_v))
00361 return v_nmax();
00362 return data_->vertices_[id_v][i];
00363 }
00364
00365 template <typename G>
00366 inline
00367 size_t
00368 line_graph<G>::v_nmax_nbh_vertices(const vertex_id_t& id_v) const
00369 {
00370 mln_precondition(has_v(id_v));
00371 return v_nmax_nbh_edges(id_v);
00372 }
00373
00374 template <typename G>
00375 inline
00376 vertex_id_t
00377 line_graph<G>::v_ith_nbh_vertex(const vertex_id_t& id_v, unsigned i) const
00378 {
00379 mln_precondition(has_v(id_v));
00380
00381 unsigned id_e = this->v_ith_nbh_edge(id_v, i);
00382 return this->v_other(id_e, id_v);
00383 }
00384
00385
00386
00387
00388
00389
00390 template <typename G>
00391 inline
00392 typename line_graph<G>::edge_t
00393 line_graph<G>::edge(const edge_id_t& e) const
00394 {
00395 mln_assertion(e < e_nmax());
00396 return edge_t(*this, e);
00397 }
00398
00399 template <typename G>
00400 inline
00401 size_t
00402 line_graph<G>::e_nmax() const
00403 {
00404 return data_->edges_.size();
00405 }
00406
00407 template <typename G>
00408 inline
00409 bool
00410 line_graph<G>::has_e(const edge_id_t& id_e) const
00411 {
00412 return id_e < data_->edges_.size();
00413 }
00414
00415 template <typename G>
00416 template <typename G2>
00417 inline
00418 bool
00419 line_graph<G>::has(const util::edge<G2>& e) const
00420 {
00421 return e.graph().is_subgraph_of(*this) && has_e(e.id());
00422 }
00423
00424 template <typename G>
00425 inline
00426 vertex_id_t
00427 line_graph<G>::v1(const edge_id_t& id_e) const
00428 {
00429 mln_precondition(has_e(id_e));
00430 return data_->edges_[id_e].first();
00431 }
00432
00433 template <typename G>
00434 inline
00435 vertex_id_t
00436 line_graph<G>::v2(const edge_id_t& id_e) const
00437 {
00438 mln_precondition(has_e(id_e));
00439 return data_->edges_[id_e].second();
00440 }
00441
00442 template <typename G>
00443 inline
00444 size_t
00445 line_graph<G>::e_nmax_nbh_edges(const edge_id_t& id_e) const
00446 {
00447 mln_precondition(has_e(id_e));
00448 return v_nmax_nbh_edges(v1(id_e)) + v_nmax_nbh_edges(v2(id_e));
00449 }
00450
00451 template <typename G>
00452 inline
00453 edge_id_t
00454 line_graph<G>::e_ith_nbh_edge(const edge_id_t& id_e, unsigned i) const
00455 {
00456 mln_precondition(has_e(id_e));
00457 if (i >= e_nmax_nbh_edges(id_e))
00458 return e_nmax();
00459
00460 unsigned v1_nmax = v_nmax_nbh_edges(v1(id_e));
00461 if (i < v1_nmax)
00462 return v_ith_nbh_edge(v1(id_e), i);
00463 return v_ith_nbh_edge(v2(id_e), i - v1_nmax);
00464 }
00465
00466
00467 template <typename G>
00468 template <typename G2>
00469 inline
00470 bool
00471 line_graph<G>::is_subgraph_of(const G2& g) const
00472 {
00473 return g.id() == this->id();
00474 }
00475
00476 template <typename G>
00477 inline
00478 const G&
00479 line_graph<G>::graph() const
00480 {
00481 return this->data_->g_;
00482 }
00483
00484
00485 template <typename G>
00486 inline
00487 std::ostream&
00488 operator<<(std::ostream& ostr, const line_graph<G>& g)
00489 {
00490 typedef line_graph<G> LG;
00491 mln_vertex_iter(LG) v(g);
00492 mln_vertex_nbh_edge_iter(LG) e(v);
00493 for_all(v)
00494 {
00495 ostr << "v(" << v << ") : ";
00496 for_all(e)
00497 ostr << e << " ";
00498 ostr << std::endl;
00499 }
00500
00501 return ostr;
00502 }
00503
00504 }
00505
00506 }
00507
00508 # endif // ! MLN_INCLUDE_ONLY
00509
00510
00511 #endif // ! MLN_UTIL_LINE_GRAPH_HH