\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.8 - CGAL and the Boost Graph Library
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
Specializations of boost::graph_traits
CGAL and the Boost Graph Library Reference

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.

Specialization for the Surface_mesh Class

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 out-edges of a vertex.
in_edge_iterator CGAL::Out_edge_iterator<Surface_mesh<P> > Iterate through the in-edges 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

Specialization for the Polyhedron Class

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 out-edges of a vertex.
in_edge_iterator CGAL::Out_edge_iterator<Polyhedron_3<T> > Iterate through the in-edges 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.

Specializations for the 2D Triangulation Classes

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

Specialization for the Arrangement Classes

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