// Copyright (c) 2007 GeometryFactory (France). All rights reserved. // // This file is part of CGAL (www.cgal.org) // // $URL: https://github.com/CGAL/cgal/blob/v5.2/HalfedgeDS/include/CGAL/boost/graph/graph_traits_HalfedgeDS.h $ // $Id: graph_traits_HalfedgeDS.h 0779373 2020-03-26T13:31:46+01:00 Sébastien Loriot // SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-Commercial // // // Author(s) : Andreas Fabri, Fernando Cacciola #ifndef CGAL_BOOST_GRAPH_GRAPH_TRAITS_HALFEDGEDS_H #define CGAL_BOOST_GRAPH_GRAPH_TRAITS_HALFEDGEDS_H #include // include this to avoid a VC15 warning #include #include #include #include #include #include #include #include #include #include #include #ifndef CGAL_NO_DEPRECATED_CODE #include #endif namespace CGAL { namespace internal { // a HDS_halfedge pretending to be an Edge template struct HDS_edge { HDS_edge() : halfedge_() { } explicit HDS_edge(const Halfedge_handle& h) : halfedge_(h) {} bool operator==(const HDS_edge& other) const { // equality is tricky, we are equal when both halfedges are the // same or when the opposite halfedge of this is the same as // halfedge_.other but we need to be careful not to apply this // should this be the invalid halfedge or opposite is going to // blow up if(halfedge_ == other.halfedge_) { return true; } else if(halfedge_ != Halfedge_handle()) { // not default constructed return halfedge_->opposite() == other.halfedge_; } else { // this is the invalid halfedge, it can only be equal to the // invalid halfedge and this is covered by the first case return false; } } bool operator!=(const HDS_edge& other) const { return !(*this == other); } friend bool operator<(const HDS_edge& a,const HDS_edge& b) { if(a==b) return false; return a.halfedge_ < b.halfedge_; } // forward some function to avoid boilerplate and typedefs inside // the free functions HDS_edge next() { return HDS_edge(halfedge_->next()); } // this is potentially broken as it does not use the decorator to // find prev, but we cannot instantiate the entire decorator // without the full polyhedron type and taking all necessary // template parameters seems overkill HDS_edge prev() { return HDS_edge(halfedge_->prev()); } HDS_edge opposite() { return HDS_edge(halfedge_->opposite()); } // this is hacky, we don't know the actual type of the id and if we // start adding decltype special cases we have to do it consistently // up to the property map and maybe back down to Polyhedron. std::size_t id() const { return halfedge_->id() / 2; } Halfedge_handle halfedge() const { return halfedge_; } // save us some work to do function chaining HDS_edge opposite_next() { return HDS_edge(halfedge_->opposite()->next()); } HDS_edge next_opposite() { return HDS_edge(halfedge_->next()->opposite()); } HDS_edge prev_opposite() { return HDS_edge(halfedge_->prev()->opposite()); } HDS_edge opposite_prev() { return HDS_edge(halfedge_->opposite()->prev()); } friend std::size_t hash_value(const HDS_edge& i) { if (i.halfedge()==Halfedge_handle()) return 0; return hash_value(i.halfedge()opposite()? i.halfedge():i.halfedge()->opposite()); } private: Halfedge_handle halfedge_; }; // make edge_descriptor hashable by default in Unique_hash_map namespace handle{ template struct Hash_functor< HDS_edge > { std::size_t operator()(const HDS_edge& edge) { Halfedge_handle he = edge.halfedge(); if (he==Halfedge_handle()) return 0; if ( he < he->opposite() ) return Hash_functor()(he); return Hash_functor()(he->opposite()); } }; } //end of namespace handle template struct Construct_edge { typedef HDS_edge result_type; HDS_edge operator()(const Halfedge_handle& he) const { return HDS_edge(he); } }; template struct Construct_edge_opposite { typedef HDS_edge result_type; HDS_edge operator()(const Halfedge_handle& he) const { return HDS_edge(he->opposite()); } }; } // internal template struct HDS_graph_traits { private: struct HDS_graph_traversal_category : public virtual boost::bidirectional_graph_tag, public virtual boost::vertex_list_graph_tag, public virtual boost::edge_list_graph_tag {}; public: typedef typename HDS::Vertex_handle vertex_descriptor; typedef typename internal::HDS_edge edge_descriptor; typedef typename HDS::Face_handle face_descriptor; typedef typename HDS::Halfedge_handle halfedge_descriptor; typedef CGAL::Prevent_deref vertex_iterator; typedef CGAL::Prevent_deref face_iterator; typedef CGAL::Prevent_deref edge_iterator_i; typedef CGAL::Prevent_deref halfedge_iterator; typedef boost::transform_iterator< internal::Construct_edge, edge_iterator_i, edge_descriptor> edge_iterator; typedef Out_edge_iterator out_edge_iterator; typedef In_edge_iterator in_edge_iterator; typedef boost::undirected_tag directed_category; typedef boost::disallow_parallel_edge_tag edge_parallel_category; typedef HDS_graph_traversal_category traversal_category; typedef typename HDS::size_type vertices_size_type; typedef vertices_size_type edges_size_type; typedef vertices_size_type halfedges_size_type; typedef vertices_size_type degree_size_type; typedef vertices_size_type faces_size_type; static vertex_descriptor null_vertex() { return vertex_descriptor(); } static halfedge_descriptor null_halfedge() { return halfedge_descriptor(); } static face_descriptor null_face() { return face_descriptor(); } }; } //namespace CGAL namespace std { #if defined(BOOST_MSVC) # pragma warning(push) # pragma warning(disable:4099) // For VC10 it is class hash #endif #ifndef CGAL_CFG_NO_STD_HASH template struct hash > { std::size_t operator()(const CGAL::internal::HDS_edge& e) const { std::hash fct; if (e.halfedge()==H()) return 0; return fct(e.halfedge()opposite()? e.halfedge():e.halfedge()->opposite()); } }; #endif // CGAL_CFG_NO_STD_HASH #if defined(BOOST_MSVC) # pragma warning(pop) #endif } // namespace std #endif // CGAL_BOOST_GRAPH_GRAPH_TRAITS_HALFEDGEDS_H