1 // Copyright (c) 2005,2007,2009,2010,2011 Tel-Aviv University (Israel). 2 // All rights reserved. 3 // 4 // This file is part of CGAL (www.cgal.org). 5 // 6 // $URL: https://github.com/CGAL/cgal/blob/v5.3/Arrangement_on_surface_2/include/CGAL/Arrangement_2/graph_traits_dual.h $ 7 // $Id: graph_traits_dual.h 254d60f 2019-10-19T15:23:19+02:00 Sébastien Loriot 8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial 9 // 10 // 11 // Author(s) : Ron Wein <wein@post.tau.ac.il> 12 // Ophir Setter <ophirset@post.tau.ac.il> 13 // Sebastien Loriot <sebastien.loriot@cgal.org> 14 // Efi Fogel <efifogel@gmail.com> 15 16 // This file contains the follwoing three parts: 17 // 1. The common base class template of the specialized 18 // Dual<specialized-arrangement> class template. 19 // 20 // 2. The common base class template of the specialized 21 // boost::graph_traits<Dual<specialized-arrangement> > class template. 22 // 23 // 3. Macro definitions of free Function templates required by 24 // the various Boost Graph concepts. There is one macro per required function 25 // template. Each macro accepts the name of a template class, an instance of 26 // which represents an arrangement data structure, e.g., Arrangement_2. The 27 // definitios of the free functions templates for a given arrangement data 28 // strcture must be present when a dual of this data structure is defined. 29 30 #include <CGAL/license/Arrangement_on_surface_2.h> 31 32 #ifndef CGAL_GRAPH_TRAITS_DUAL_H 33 #define CGAL_GRAPH_TRAITS_DUAL_H 34 35 namespace CGAL { 36 37 // Forward declaration. 38 template <class Type> class Dual; 39 40 /*! \class 41 * Generic implementation of the common base class template of the specialized 42 * Dual<specialized-arrangement> class template. 43 */ 44 template <typename Arrangement_> 45 class Dual_arrangement_on_surface { 46 public: 47 typedef Arrangement_ Arrangement; 48 typedef typename Arrangement::Geometry_traits_2 Geometry_traits_2; 49 typedef typename Arrangement::Topology_traits Topology_traits; 50 51 typedef typename Arrangement::Size Size; 52 typedef typename Arrangement::Face_handle Vertex_handle; 53 typedef typename Arrangement::Halfedge_handle Edge_handle; 54 55 typedef typename Arrangement::Face_iterator Vertex_iterator; 56 typedef typename Arrangement::Halfedge_iterator Edge_iterator; 57 58 protected: 59 typedef typename Arrangement::Face_handle Face_handle; 60 typedef typename Arrangement::Ccb_halfedge_circulator Ccb_halfedge_circulator; 61 typedef typename Arrangement::Outer_ccb_iterator Outer_ccb_iterator; 62 typedef typename Arrangement::Inner_ccb_iterator Inner_ccb_iterator; 63 64 /*! \class 65 * Iterator over the neighbors of a dual vertex (a face in the primal 66 * arrangement). 67 * These neighbors are the adjacent faces along the outer boundaries of the 68 * face and its inner boundaries. 69 */ 70 class Face_neighbor_iterator { 71 typedef Face_neighbor_iterator Self; 72 73 public: 74 typedef std::forward_iterator_tag iterator_category; 75 typedef Edge_handle value_type; 76 typedef value_type reference; 77 typedef value_type* pointer; 78 typedef int difference_type; 79 80 private: 81 Outer_ccb_iterator _outer_ccb_iter; 82 Inner_ccb_iterator _inner_ccb_iter; 83 Ccb_halfedge_circulator _ccb_curr; 84 Ccb_halfedge_circulator _ccb_first; 85 Face_handle _face; 86 bool _out; 87 Edge_handle _hh; 88 bool _end; 89 90 public: 91 /*! Default constructor. */ Face_neighbor_iterator()92 Face_neighbor_iterator() : _end (true) {} 93 94 /*! Constructor. 95 * \param face The face (dual vertex). 96 * \param out_edges Do we need the outgoing or the ingoing halfedges. 97 * \param start Should we start traversing the edges. 98 * If false, we construct a past-the-end iterator. 99 */ Face_neighbor_iterator(Face_handle face,bool out_edges,bool start)100 Face_neighbor_iterator(Face_handle face, bool out_edges, bool start) : 101 _face(face), 102 _out(out_edges), 103 _end(! start) 104 { 105 CGAL_precondition(! face->is_fictitious()); 106 107 if (start) { 108 _outer_ccb_iter = _face->outer_ccbs_begin(); 109 _inner_ccb_iter = _face->inner_ccbs_begin(); 110 111 if (_outer_ccb_iter != _face->outer_ccbs_end()) { 112 // Start from the first outer CCB, if one exists. 113 _ccb_curr = _ccb_first = *_outer_ccb_iter; 114 } 115 else if (_inner_ccb_iter != face->inner_ccbs_end()) { 116 // Otherwise, start from the first inner CCB. 117 _ccb_curr = _ccb_first = *_inner_ccb_iter; 118 } 119 else { 120 // In this case there are no CCBs to traverse: 121 _end = true; 122 return; 123 } 124 125 _hh = this->_dereference(); 126 127 // In case the incident face of the twin halfedge is fictitious, 128 // skip it and proceed to the next edge. 129 if (_hh->is_fictitious()) ++(*this); 130 } 131 else { // end iterator. 132 _outer_ccb_iter = _face->outer_ccbs_end(); 133 _inner_ccb_iter = _face->inner_ccbs_end(); 134 } 135 } 136 137 /*! Equality operators. */ 138 bool operator==(const Self& it) const { return (this->_equal(it)); } 139 140 bool operator!= (const Self& it) const { return (! this->_equal(it)); } 141 142 /*! Dereference operators. */ 143 reference operator*() const { return (_hh); } 144 145 pointer operator->() const { return (&_hh); } 146 147 /* Increment operators. */ 148 Self& operator++() 149 { 150 do { 151 this->_increment(); 152 if (_end) return (*this); 153 _hh = this->_dereference(); 154 } while (_hh->is_fictitious()); 155 return (*this); 156 } 157 158 Self operator++(int ) 159 { 160 Self tmp = *this; 161 do { 162 this->_increment(); 163 if (_end) return (tmp); 164 _hh = this->_dereference(); 165 } while (_hh->is_fictitious()); 166 return (tmp); 167 } 168 169 private: 170 /*! Check two iterators for equality. */ _equal(const Self & it)171 bool _equal(const Self& it) const 172 { 173 return (_out == it._out && _face == it._face && ((_end && it._end) || 174 (_outer_ccb_iter == it._outer_ccb_iter && 175 _inner_ccb_iter == it._inner_ccb_iter && 176 _ccb_curr == it._ccb_curr))); 177 } 178 179 /*! Derefernce the current circulator. */ _dereference()180 Edge_handle _dereference() const 181 { 182 if (_out) return (_ccb_curr); 183 else return (_ccb_curr->twin()); 184 } 185 186 // Increments of the iterator. _increment()187 void _increment() 188 { 189 CGAL_assertion(! _end); 190 191 // If we have not traversed the entire CCB in full, move to the next 192 // halfedge along the current CCB. 193 ++_ccb_curr; 194 195 if (_ccb_curr != _ccb_first) return; 196 197 // In this case we have completed the current CCB and we have to move 198 // to the next one. 199 if (_outer_ccb_iter != _face->outer_ccbs_end()) { 200 // Try to move to the next outer CCB. 201 ++_outer_ccb_iter; 202 if (_outer_ccb_iter != _face->outer_ccbs_end()) { 203 _ccb_curr = _ccb_first = *_outer_ccb_iter; 204 return; 205 } 206 207 // In this case we start traversing the inner CCBs. 208 if (_inner_ccb_iter != _face->inner_ccbs_end()) { 209 CGAL_assertion (_inner_ccb_iter == _face->inner_ccbs_begin()); 210 211 // Otherwise, start from the first inner CCB. 212 _ccb_curr = _ccb_first = *_inner_ccb_iter; 213 return; 214 } 215 } 216 else if (_inner_ccb_iter != _face->inner_ccbs_end()) { 217 218 // In this case we have already traversed all outer CCBs (and at least 219 // one inner CCB), so we try to move to the next inner CCB. 220 ++_inner_ccb_iter; 221 if (_inner_ccb_iter != _face->inner_ccbs_end()) { 222 // Otherwise, start from the first inner CCB. 223 _ccb_curr = _ccb_first = *_inner_ccb_iter; 224 return; 225 } 226 } 227 228 // In this case we finished traversing all outer and inner CCBs: 229 _end = true; 230 return; 231 } 232 }; 233 234 // Data members: 235 mutable Arrangement* p_arr; // The primal arrangement. 236 237 public: 238 typedef Face_neighbor_iterator Incident_edge_iterator; 239 240 /*! Default constructor. */ Dual_arrangement_on_surface()241 Dual_arrangement_on_surface() : p_arr(nullptr) {} 242 243 /*! Constructor from an arrangement. */ Dual_arrangement_on_surface(const Arrangement & arr)244 Dual_arrangement_on_surface(const Arrangement& arr) : 245 p_arr(const_cast<Arrangement*>(&arr)) 246 {} 247 248 /*! Obtain the primal arrangement (const version). */ arrangement()249 const Arrangement* arrangement() const { return (p_arr); } 250 251 /*! Obtain the primal arrangement (non-const version). */ arrangement()252 Arrangement* arrangement() { return (p_arr); } 253 254 /*! Obtain the number of vertices (face of the primal arrangement). */ number_of_vertices()255 Size number_of_vertices() const { return (p_arr->number_of_faces()); } 256 257 /*! Obtain the begin iterator of the vertices of the dual arrangement 258 * (faces of the primal arrangement). 259 */ vertices_begin()260 Vertex_iterator vertices_begin() const { return (p_arr->faces_begin()); } 261 262 /*! Obtain the pass-the-end iterator of the vertices of the dual arrangement 263 * (faces of the primal arrangement). 264 */ vertices_end()265 Vertex_iterator vertices_end() const { return (p_arr->faces_end()); } 266 267 /*! Obtain the number of edges. */ number_of_edges()268 Size number_of_edges () const { return (p_arr->number_of_halfedges()); } 269 270 /*! Obtain the begin iterator of the edges of the dual arrangement. */ edges_begin()271 Edge_iterator edges_begin() const { return (p_arr->halfedges_begin()); } 272 273 /*! Obtain the pass-the-end iterator of the edges of the dual arrangement. */ edges_end()274 Edge_iterator edges_end() const { return (p_arr->halfedges_end()); } 275 276 /*! Obtain the dual vertex-degree (number of edges forming the face boundary). 277 */ degree(Vertex_handle v)278 Size degree(Vertex_handle v) const 279 { 280 Incident_edge_iterator begin = Incident_edge_iterator(v, true, true); 281 Incident_edge_iterator end = Incident_edge_iterator(v, false, true); 282 Size deg = 0; 283 284 while (begin != end) { 285 deg++; 286 ++begin; 287 } 288 289 return (deg); 290 } 291 292 /*! Traverse the outgoing edges of a given vertex. */ out_edges_begin(Vertex_handle v)293 Incident_edge_iterator out_edges_begin(Vertex_handle v) const 294 { return (Incident_edge_iterator (v, true, true)); } 295 out_edges_end(Vertex_handle v)296 Incident_edge_iterator out_edges_end(Vertex_handle v) const 297 { return (Incident_edge_iterator (v, true, false)); } 298 299 /*! Traverse the ingoing edges of a given vertex. */ in_edges_begin(Vertex_handle v)300 Incident_edge_iterator in_edges_begin(Vertex_handle v) const 301 { return (Incident_edge_iterator (v, false, true)); } 302 in_edges_end(Vertex_handle v)303 Incident_edge_iterator in_edges_end(Vertex_handle v) const 304 { return (Incident_edge_iterator (v, false, false)); } 305 }; 306 307 } //namespace CGAL 308 309 #include <boost/graph/graph_concepts.hpp> 310 #include <CGAL/boost/iterator/counting_iterator.hpp> 311 312 namespace CGAL { 313 314 /*! \class 315 * The common base class template of the specialized 316 * boost::graph_traits<Dual<specialized-arrangement> > class template. 317 * The latter serves as a dual adapter for the specialied arrangment, where the 318 * valid arrangement faces correspond to graph verices, and two graph vertices 319 * are connected if the two corrsponding faces are adjacent. 320 * We consider the graph as directed. We also allow parallel edges, as two 321 * faces may have more than one common edges. 322 */ 323 template <typename Arrangement_> 324 class Graph_traits_dual_arr_on_surface_impl { 325 public: 326 typedef Arrangement_ Arrangement; 327 typedef typename Arrangement::Geometry_traits_2 Geometry_traits_2; 328 typedef typename Arrangement::Topology_traits Topology_traits; 329 typedef Dual_arrangement_on_surface<Arrangement> Dual_arr_2; 330 331 private: 332 typedef typename Dual_arr_2::Vertex_iterator Vertex_iterator; 333 typedef typename Dual_arr_2::Edge_iterator Edge_iterator; 334 typedef typename Dual_arr_2::Incident_edge_iterator Incident_edge_iterator; 335 336 /*! \struct 337 * Define the arrangement traversal category, which indicates the arrangement 338 * models the BidirectionalGraph concept and the VertexListGraph and 339 * EdgeListGraph concepts. 340 */ 341 struct Dual_arr_traversal_category : 342 public virtual boost::bidirectional_graph_tag, // This tag refines the 343 // incidence_graph_tag. 344 public virtual boost::vertex_list_graph_tag, // Can iterate over vertices. 345 public virtual boost::edge_list_graph_tag // Can iterate over edges. 346 {}; 347 348 public: 349 // Types required of the Graph concept: 350 typedef typename Dual_arr_2::Vertex_handle vertex_descriptor; 351 typedef boost::directed_tag directed_category; 352 typedef boost::allow_parallel_edge_tag edge_parallel_category; 353 354 typedef Dual_arr_traversal_category traversal_category; 355 356 // Types required by the IncidenceGraph concept: 357 typedef typename Dual_arr_2::Edge_handle edge_descriptor; 358 typedef Incident_edge_iterator out_edge_iterator; 359 typedef typename Dual_arr_2::Size degree_size_type; 360 361 // Types required by the BidirectionalGraph concept: 362 typedef Incident_edge_iterator in_edge_iterator; 363 364 // Types required by the VertexListGraph concept: 365 typedef boost::counting_iterator<Vertex_iterator> vertex_iterator; 366 typedef typename Dual_arr_2::Size vertices_size_type; 367 368 // Types required by the EdgeListGraph concept: 369 typedef boost::counting_iterator<Edge_iterator> edge_iterator; 370 typedef typename Dual_arr_2::Size edges_size_type; 371 372 // Types not required by any of these concepts: 373 typedef void adjacency_iterator; 374 }; 375 376 } 377 378 // Macro definitions of free Function templates required by the various Boost 379 // Graph concepts. Each macro provides the required free function template with 380 // the specific interface and its implementation. 381 // We use macros (and not base functions similar to 382 // Graph_traits_dual_arr_on_surface_impl) for simplicity. The implementation 383 // is typically a one-liner. However, the interface is typically several lines 384 // of code. The alternative implementation (with base common functions) while 385 // being more safe (provided tight type checking) would consume many repeated 386 // lines of code. 387 388 // Functions required by the IncidenceGraph concept: 389 // ------------------------------------------------- 390 391 /*! Obtain the out-degree of a vertex in a given dual arrangement. 392 * \param v The vertex. 393 * \param darr The dual arrangement. 394 * \param Number of halfedges around the boundary of the primal face. 395 */ 396 #define CGAL_DUAL_ARRANGEMENT_2_OUT_DEGREE(T) \ 397 template <typename T1, typename T2> \ 398 typename boost::graph_traits<Dual<T<T1, T2> > >::degree_size_type \ 399 out_degree(typename boost::graph_traits<Dual<T<T1, T2> > >::vertex_descriptor v,\ 400 const Dual<T<T1, T2> >& darr) \ 401 { return darr.degree(v); } 402 403 /*! Return a range of the out-edges of a vertex given by its descriptor and the 404 * dual arrangement it belongs to. 405 * \param v The vertex. 406 * \param darr The dual arrangement. 407 * \return A pair of out-edges iterators. 408 */ 409 #define CGAL_DUAL_ARRANGEMENT_2_OUT_EDGES(T) \ 410 template <typename T1, typename T2> \ 411 std::pair<typename boost::graph_traits<Dual<T<T1, T2> > >::out_edge_iterator, \ 412 typename boost::graph_traits<Dual<T<T1, T2> > >::out_edge_iterator> \ 413 out_edges(typename boost::graph_traits<Dual<T<T1, T2> > >::vertex_descriptor v,\ 414 const Dual<T<T1, T2> >& darr) \ 415 { return std::make_pair(darr.out_edges_begin(v), darr.out_edges_end(v)); } \ 416 417 /*! Obtain the source vertex of a dual arrangement edge. 418 * \param e The edge. 419 * \param darr The dual arrangement. 420 * \return The incident face of e in the primal arrangement. 421 */ 422 #define CGAL_DUAL_ARRANGEMENT_2_SOURCE(T) \ 423 template <typename T1, typename T2> \ 424 typename boost::graph_traits<Dual<T<T1, T2> > >::vertex_descriptor \ 425 source(typename boost::graph_traits<Dual<T<T1, T2> > >::edge_descriptor e, \ 426 const Dual<T<T1, T2> >& /* darr */) \ 427 { return e->face(); } 428 429 /*! Obtain the target vertex of a dual arrangement edge. 430 * \param e The edge. 431 * \param darr The dual arrangement. 432 * \return The incident face of the twin of e in the primal arrangement. 433 */ 434 #define CGAL_DUAL_ARRANGEMENT_2_TARGET(T) \ 435 template <typename T1, typename T2> \ 436 typename boost::graph_traits<Dual<T<T1, T2> > >::vertex_descriptor \ 437 target(typename boost::graph_traits<Dual<T<T1, T2> > >::edge_descriptor e, \ 438 const Dual<T<T1, T2> >& /* darr */) \ 439 { return e->twin()->face(); } 440 441 // Functions required by the BidirectionalGraph concept: 442 // ----------------------------------------------------- 443 444 /*! Obtain the in-degree of a vertex in a given dual arrangement. 445 * \param v The vertex. 446 * \param darr The dual arrangement. 447 * \param Number of halfedges around the boundary of the primal face. 448 */ 449 #define CGAL_DUAL_ARRANGEMENT_2_IN_DEGREE(T) \ 450 template <typename T1, typename T2> \ 451 typename boost::graph_traits<Dual<T<T1, T2> > >::degree_size_type \ 452 in_degree(typename boost::graph_traits<Dual<T<T1, T2> > >::vertex_descriptor v,\ 453 const Dual<T<T1, T2> >& darr) \ 454 { return darr.degree(v); } 455 456 /*! Return a range of the in-edges of a vertex given by its descriptor and the 457 * dual arrangement it belongs to. 458 * \param v The vertex. 459 * \param darr The dual arrangement. 460 * \return A pair of in-edges iterators. 461 */ 462 #define CGAL_DUAL_ARRANGEMENT_2_IN_EDGES(T) \ 463 template <typename T1, typename T2> \ 464 std::pair<typename boost::graph_traits<Dual<T<T1, T2> > >::in_edge_iterator, \ 465 typename boost::graph_traits<Dual<T<T1, T2> > >::in_edge_iterator> \ 466 in_edges(typename boost::graph_traits<Dual<T<T1, T2> > >::vertex_descriptor v,\ 467 const Dual<T<T1, T2> >& darr) \ 468 { return std::make_pair(darr.in_edges_begin(v), darr.in_edges_end(v)); } 469 470 /*! Obtain the degree of a vertex in a given dual arrangement. 471 * \param v The vertex. 472 * \param darr The dual arrangement. 473 * \param Number of ingoing and outgoing halfedges incident to v. 474 */ 475 #define CGAL_DUAL_ARRANGEMENT_2_DEGREE(T) \ 476 template <typename T1, typename T2> \ 477 typename boost::graph_traits<Dual<T<T1, T2> > >::degree_size_type \ 478 degree(typename boost::graph_traits<Dual<T<T1, T2> > >::vertex_descriptor v, \ 479 const Dual<T<T1, T2> >& darr) \ 480 { return (2 * darr.degree(v)); } 481 482 // Functions required by the VertexListGraph concept: 483 // -------------------------------------------------- 484 485 /*! Obtain the number of vertices in the given dual arrangement. 486 * \param darr The dual arrangement. 487 * \return Number of faces in the primal arrangement. 488 */ 489 #define CGAL_DUAL_ARRANGEMENT_2_NUM_VERTICES(T) \ 490 template <typename T1, typename T2> \ 491 typename boost::graph_traits<Dual<T<T1, T2> > >::vertices_size_type \ 492 num_vertices(const Dual<T<T1, T2> >& darr) \ 493 { return darr.number_of_vertices(); } 494 495 /*! Obtain the range of vertices of the given dual arrangement. 496 * \param darr The dual arrangement. 497 * \return A pair of vertex iterators. 498 */ 499 #define CGAL_DUAL_ARRANGEMENT_2_VERTICES(T) \ 500 template <typename T1, typename T2> \ 501 std::pair<typename boost::graph_traits<Dual<T<T1, T2> > >::vertex_iterator, \ 502 typename boost::graph_traits<Dual<T<T1, T2> > >::vertex_iterator> \ 503 vertices(const Dual<T<T1, T2> >& darr) \ 504 { return std::make_pair(darr.vertices_begin(), darr.vertices_end()); } 505 506 // Functions required by the EdgeListGraph concept: 507 // ------------------------------------------------ 508 509 /*! Obtain the number of edges in the given dual arrangement. 510 * \param darr The dual arrangement. 511 * \return Number of halfedges in the primal arrangement. 512 */ 513 #define CGAL_DUAL_ARRANGEMENT_2_NUM_EDGES(T) \ 514 template <typename T1, typename T2> \ 515 typename boost::graph_traits<Dual<T<T1, T2> > >::edges_size_type \ 516 num_edges(const Dual<T<T1, T2> >& darr) \ 517 { return darr.number_of_edges(); } 518 519 /*! Obtain the range of edges of the given dual arrangement. 520 * \param darr The dual arrangement. 521 * \return A pair of edge iterators. 522 */ 523 #define CGAL_DUAL_ARRANGEMENT_2_EDGES(T) \ 524 template <typename T1, typename T2> \ 525 std::pair<typename boost::graph_traits<Dual<T<T1, T2> > >::edge_iterator, \ 526 typename boost::graph_traits<Dual<T<T1, T2> > >::edge_iterator> \ 527 edges(const Dual<T<T1, T2> >& darr) \ 528 { return std::make_pair(darr.edges_begin(), darr.edges_end()); } 529 530 #endif 531