CGAL 4.7  CGAL and the Boost Graph Library

Bgl defines the class template boost::graph_traits
as a uniform interface to the properties and types of graph types.
We provide specializations of this class template for several CGAL data structures.
Defined in <CGAL/boost/graph/graph_traits_Surface_mesh.h>
We provide partial specialization for the class CGAL::Surface_mesh
so that it is a model of the graph concepts BidirectionalGraph
and EdgeAndVertexListGraph
and of the concept MutableFaceGraph
.
The const specialization, boost::graph_traits< CGAL::Surface_mesh<Traits> const>
is also defined, using the constant handles in the polyhedron.
The traits class boost::graph_traits< CGAL::Surface_mesh<T> >
provides the following types:
Member  Value  Description 

vertex_descriptor  Surface_mesh::Vertex_index  The vertex descriptor 
edge_descriptor  Surface_mesh::Edge_index  The edge descriptor 
halfedge_descriptor  Surface_mesh::Halfedge_index  The halfedge descriptor 
face_descriptor  Surface_mesh::Face_index  The face descriptor 
adjacency_iterator  CGAL::Vertex_around_target_iterator<Surface_mesh<P> >  Iterates through adjacent vertices 
out_edge_iterator  CGAL::Out_edge_iterator<Surface_mesh<P> >  Iterate through the outedges of a vertex. 
in_edge_iterator  CGAL::Out_edge_iterator<Surface_mesh<P> >  Iterate through the inedges of a vertex. 
vertex_iterator  Surface_mesh::Vertex_iterator  Iterate through the vertices of a polyhedron. 
edge_iterator  Surface_mesh::Edge_iterator  Iterate through the edges of a polyhedron. 
halfedge_iterator  Surface_mesh::Halfedge_iterator  Iterate through the halfedges of a polyhedron. 
face_iterator  Surface_mesh::Face_iterator  Iterate through the faces of a polyhedron. 
directed_category  Inherits from boost::bidirectional_graph_tag , boost::vertex_list_graph_tag and boost::edge_list_graph_tag  
edge_parallel_category  boost::disallow_parallel_edge_tag  Indicates that this graph does not support multiedges 
traversal_category  boost::bidirectional_graph_tag  Indicates that this graph is bidirectional 
vertices_size_type  Surface_mesh::vertices_size_type  The size type of the vertex list 
edges_size_type  Surface_mesh::edges_size_type  The size type of the edge list 
degree_size_type  Surface_mesh::degree_size_type  The size type of the adjacency list 
Defined in <CGAL/boost/graph/graph_traits_Polyhedron_3.h>
We provide partial specialization for the class CGAL::Polyhedron_3
so that it is a model of the graph concepts BidirectionalGraph
and EdgeAndVertexListGraph
and of the concept MutableFaceGraph
.
The const specialization, boost::graph_traits< CGAL::Polyhedron_3<Traits> const>
is also defined, using the constant handles in the polyhedron.
The traits class boost::graph_traits< CGAL::Polyhedron_3<T> >
provides the following types:
Member  Value  Description 

vertex_descriptor  Polyhedron_3::Vertex_handle  The vertex descriptor 
edge_descriptor  unspecified_type  The edge descriptor 
halfedge_descriptor  Polyhedron_3::Halfedge_handle  The halfedge descriptor 
face_descriptor  Polyhedron_3::Face_handle  The face descriptor 
adjacency_iterator  CGAL::Vertex_around_target_iterator<Polyhedron_3<T> >  Iterates through adjacent vertices 
out_edge_iterator  CGAL::Out_edge_iterator<Polyhedron_3<T> >  Iterate through the outedges of a vertex. 
in_edge_iterator  CGAL::Out_edge_iterator<Polyhedron_3<T> >  Iterate through the inedges of a vertex. 
vertex_iterator  unspecified_type  Iterate through the vertices of a polyhedron. 
edge_iterator  unspecified_type  Iterate through the edges of a polyhedron. 
halfedge_iterator  Polyhedron_3::Halfedge_iterator  Iterate through the halfedges of a polyhedron. 
face_iterator  Polyhedron_3::Face_iterator  Iterate through the faces of a polyhedron. 
directed_category  Inherits from boost::bidirectional_graph_tag , boost::vertex_list_graph_tag and boost::edge_list_graph_tag  
edge_parallel_category  boost::disallow_parallel_edge_tag  Indicates that this graph does not support multiedges 
traversal_category  boost::bidirectional_graph_tag  Indicates that this graph is bidirectional 
vertices_size_type  Polyhedron_3::size_type  The size type of the vertex list 
edges_size_type  Polyhedron_3::size_type  The size type of the edge list 
degree_size_type  Polyhedron_3::size_type  The size type of the adjacency list 
For convenience, the type edge_descriptor
is hashable using the functor CGAL::Handle_hash_function
that is the default hash functor of CGAL::Unique_hash_map
.
Defined in <CGAL/boost/graph/graph_traits_Triangulation_2.h>
and <CGAL/boost/graph/graph_traits_Delaunay_triangulation_2.h>
We provide partial specialization for the classes CGAL::Triangulation_2
and CGAL::Delaunay_triangulation_2
so that they are model of the graph concepts BidirectionalGraph
and EdgeAndVertexListGraph
.
The mapping between vertices and edges of the triangulation and the graph is rather straightforward, but there are some subtleties. The value type of the Bgl iterators is the vertex or edge descriptor, whereas in CGAL all iterators and circulators are also handles and hence have as value type Vertex or Edge.
The graph traits class for triangulations does not distinguish between finite and infinite vertices and edges. As the edge weight computed with the default property map of Bgl algorithms (obtained with get(t, boost::edge_weight)
) is the length of the edge, the edge weight is not well defined for infinite edges. For algorithms that make use of the edge weight the user must therefore define a boost::filtered_graph
or pass a property map to the algorithm that returns "infinity" for infinite edges.
Note also that when you derive from the class CGAL::Triangulation_2
you must upcast the object in order to use this partial specialization.
For the user convenience, CGAL provides the partial specializations for all 2D triangulation classes.
The traits class boost::graph_traits< CGAL::Triangulation_2<GT, TDS> >
and boost::graph_traits< CGAL::Delaunay_triangulation_2<GT, TDS> >
provide the following types:
Member  Value  Description 

vertex_descriptor  Triangulation::Vertex_handle  The vertex descriptor 
edge_descriptor  unspecified_type  It is constructible from and convertible to Triangulation::Edge . The edge descriptor is not a simple typedef, but a proper class, because in an undirected graph the edges (u,v) and (v,u) must be equal. This is not the case for the Edge type of the triangulation. 
adjacency_iterator  unspecified_type  An iterator for the vertices adjacent to a vertex. Its value type is vertex_descriptor 
out_edge_iterator  unspecified_type  An iterator for the outgoing edges incident to a vertex. Its value type is edge_descriptor . 
in_edge_iterator  unspecified_type  An iterator for the incoming edges incident to a vertex. Its value type is edge_descriptor . 
vertex_iterator  unspecified_type  The vertex iterator type. Its value type is vertex_descriptor 
edge_iterator  unspecified_type  The edge iterator type, Its value type is edge_descriptor 
directed_category  boost::undirected_tag  
edge_parallel_category  boost::disallow_parallel_edge_tag  Indicates that this graph does not support multiedges 
traversal_category  boost::bidirectional_graph_tag  Indicates that this graph is bidirectional 
vertices_size_type  Triangulation::size_type  The size type of the vertex list 
edges_size_type  Triangulation::size_type  The size type of the edge list 
degree_size_type  Triangulation::size_type  The size type of the adjacency list 
Defined in <CGAL/boost/graph/graph_traits_Arrangement_2.h>
We provide partial specialization for the class Arrangement_2
so that it is model of the graph concepts BidirectionalGraph
and EdgeAndVertexListGraph
.
The const specialization, boost::graph_traits< CGAL::Arrangement_2<Traits,Dcel> const>
is also defined, using the constant handles in the arrangement.
The traits class boost::graph_traits< CGAL::Arrangement_2<T, DC> >
provides the following types:
Member  Value  Description 

vertex_descriptor  Arrangement_2::Vertex_handle  The vertex descriptor 
edge_descriptor  Arrangement_2::Halfedge_handle  The edge descriptor 
adjacency_iterator  Not provided  
out_edge_iterator  unspecified_type  An edge iterator which only iterates over the outgoing halfedges around a vertex. It corresponds to a Arrangement_2::Halfedge_around_vertex_circulator with the difference that its value type is an edge descriptor and not Arrangement_2::Halfedge 
in_edge_iterator  unspecified_type  An edge iterator which only iterates over the incoming edges around a vertex. It corresponds to a Arrangement_2::Halfedge_around_vertex_circulator with the difference that its value type is an edge descriptor and not Arrangement_2::Halfedge 
vertex_iterator  unspecified_type  An iterator corresponding to Arrangement_2::Vertex_iterator , with the difference that its value type is a vertex descriptor and not Arrangement_2::Vertex 
edge_iterator  unspecified_type  An iterator corresponding to Arrangement_2::Halfedge_iterator with the difference that its value type is an edge descriptor and not Arrangement_2::Halfedge 
directed_category  boost::directed_tag  
edge_parallel_category  boost::disallow_parallel_edge_tag  Indicates that this graph does support multiedges 
traversal_category  boost::bidirectional_graph_tag  Indicates that this graph is bidirectional 
vertices_size_type  Arrangement_2::size_type  The size type of the vertex list 
edges_size_type  Arrangement_2::size_type  The size type of the edge list 
degree_size_type  Arrangement_2::size_type  The size type of the adjacency list 