CGAL 5.1 - CGAL and the Boost Graph Library
Specializations of boost::graph_traits

The 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, VertexAndEdgeListGraph, AdjacencyMatrix, and MutableFaceGraph.

The const specialization, boost::graph_traits< CGAL::Surface_mesh<Traits> const> is also defined, using the constant handles in the surface mesh.

The traits class boost::graph_traits< CGAL::Surface_mesh<T> > provides the following types:

Member Value Description
vertex_descriptor Surface_mesh::Vertex_index Identify vertices in the graph.
edge_descriptor Surface_mesh::Edge_index Identify edges in the graph.
halfedge_descriptor Surface_mesh::Halfedge_index Identify halfedges in the graph.
face_descriptor Surface_mesh::Face_index Identify faces in the graph.
adjacency_iterator CGAL::Vertex_around_target_iterator<Surface_mesh<P> > An iterator to traverse through the vertices adjacent to a vertex. Its value type is vertex_descriptor.
out_edge_iterator CGAL::Out_edge_iterator<Surface_mesh<P> > An iterator to traverse through the outgoing edges incident to a vertex. Its value type is edge_descriptor.
in_edge_iterator CGAL::In_edge_iterator<Surface_mesh<P> > An iterator to traverse through the incoming edges incident to a vertex. Its value type is edge_descriptor.
vertex_iterator Surface_mesh::Vertex_iterator An iterator to traverse through the vertices of the graph. Its value type is vertex_descriptor.
edge_iterator Surface_mesh::Edge_iterator An iterator to traverse through the edges of the graph. Its value type is edge_descriptor.
halfedge_iterator Surface_mesh::Halfedge_iterator An iterator to traverse through the halfedges of the graph. Its value type is halfedge_descriptor.
face_iterator Surface_mesh::Face_iterator An iterator to traverse through the faces of the graph. Its value type is face_descriptor.
directed_category boost::undirected_tag This graph is not directed.
edge_parallel_category boost::disallow_parallel_edge_tag This graph does not support multiedges.
traversal_category Inherits from boost::bidirectional_graph_tag, boost::vertex_list_graph_tag, and boost::edge_list_graph_tag The ways in which the vertices in the graph can be traversed.
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, VertexAndEdgeListGraph, AdjacencyMatrix, and 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 Identify vertices in the graph.
edge_descriptor unspecified_type Identify edges in the graph.
halfedge_descriptor Polyhedron_3::Halfedge_handle Identify halfedges in the graph.
face_descriptor Polyhedron_3::Face_handle Identify faces in the graph.
adjacency_iterator CGAL::Vertex_around_target_iterator<Polyhedron_3<T> > An iterator to traverse through the vertices adjacent to a vertex. Its value type is vertex_descriptor.
out_edge_iterator CGAL::Out_edge_iterator<Polyhedron_3<T> > An iterator to traverse through the outgoing edges incident to a vertex. Its value type is edge_descriptor.
in_edge_iterator CGAL::In_edge_iterator<Polyhedron_3<T> > An iterator to traverse through the incoming edges incident to a vertex. Its value type is edge_descriptor.
vertex_iterator unspecified_type An iterator to traverse through the vertices of the graph. Its value type is vertex_descriptor.
edge_iterator unspecified_type An iterator to traverse through the edges of the graph. Its value type is edge_descriptor.
halfedge_iterator unspecified_type An iterator to traverse through the halfedges of the graph. Its value type is halfedge_descriptor.
face_iterator unspecified_type An iterator to traverse through the faces of the graph. Its value type is face_descriptor.
directed_category boost::undirected_tag This graph is not directed.
edge_parallel_category boost::disallow_parallel_edge_tag This graph does not support multiedges.
traversal_category Inherits from boost::bidirectional_graph_tag, boost::vertex_list_graph_tag, and boost::edge_list_graph_tag The ways in which the vertices in the graph can be traversed.
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, which is the default hash functor of CGAL::Unique_hash_map.

# Specialization for the Linear_cell_complex_for_combinatorial_map Class

Defined in <CGAL/boost/graph/graph_traits_Linear_cell_complex_for_combinatorial_map.h>

We provide partial specialization for the class CGAL::Linear_cell_complex_for_combinatorial_map so that it is a model of the graph concepts BidirectionalGraph, VertexAndEdgeListGraph, AdjacencyMatrix, and MutableFaceGraph.

The const specialization is also defined, using the constant handles in the linear cell complex.

Let us denote by LCC an instantiation of CGAL::Linear_cell_complex_for_combinatorial_map<...> class. The traits class boost::graph_traits<LCC> provides the following types:

Member Value Description
vertex_descriptor LCC::Vertex_attribute_handle The vertex descriptor
edge_descriptor unspecified_type The edge descriptor
halfedge_descriptor LCC::Dart_handle The halfedge descriptor
face_descriptor unspecified_type The face descriptor
adjacency_iterator CGAL::Vertex_around_target_iterator<LCC> Iterates through adjacent vertices
out_edge_iterator CGAL::Out_edge_iterator<LCC> Iterate through the out-edges of a vertex.
in_edge_iterator CGAL::Out_edge_iterator<LCC> Iterate through the in-edges of a vertex.
vertex_iterator unspecified_type Iterate through the vertices of LCC.
edge_iterator unspecified_type Iterate through the edges of LCC.
halfedge_iterator unspecified_type Iterate through the halfedges of LCC.
face_iterator unspecified_type Iterate through the faces of LCC.
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 LCC::size_type The size type of the vertex list
edges_size_type LCC::size_type The size type of the edge list
degree_size_type LCC::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.

## Requirements

• The item class used by CGAL::Linear_cell_complex_for_combinatorial_map must have both 0-attributes and 2-attributes enabled.

• No dart is 1-free, nor 2-free. Holes in a mesh are represented by using the same convention than for CGAL::Polyhedron_3 and CGAL::Surface_mesh: a dart d belongs to a border if the 2-attribute of beta<2>(d) is nullptr.

• All darts of the linear cell complexes must be associated with a 2-attribute, except darts that represent holes.

• In order to use property maps, darts and types associated with of 0- and 2-attributes must define the two fonctions:
int id() const; // Returns the index.
int& id(); // Returns a reference to the index stored in the attribute.

For darts, this can be done by defining Darts_with_id as CGAL::Tag_true in the Dart_wrapper struct of the item class.
For attributes, it is possible to use CGAL::Cell_attribute_with_id and CGAL::Cell_attribute_with_point_and_id classes to define your item class using attributes with id.

You can also use the CGAL::Linear_cell_complex_bgl_min_items item class, or you can use directly the CGAL::Linear_cell_complex_for_bgl_combinatorial_map_helper class.

# Specializations for the 2D Triangulation Classes

Defined in <CGAL/boost/graph/graph_traits_Triangulation_2.h>, <CGAL/boost/graph/graph_traits_Delaunay_triangulation_2.h>, <CGAL/boost/graph/graph_traits_Regular_triangulation_2.h>, <CGAL/boost/graph/graph_traits_Constrained_Delaunay_triangulation_2.h>, <CGAL/boost/graph/graph_traits_Constrained_triangulation_2.h>, <CGAL/boost/graph/graph_traits_Constrained_triangulation_plus_2.h>, and <CGAL/boost/graph/graph_traits_Triangulation_hierarchy_2.h>.

We provide partial specialization for the classes CGAL::Triangulation_2, CGAL::Delaunay_triangulation_2, CGAL::Regular_triangulation_2, CGAL::Constrained_triangulation_2, CGAL::Constrained_Delaunay_triangulation_2, CGAL::Constrained_triangulation_plus_2, and CGAL::Triangulation_hierarchy_2 so that they are model of the graph concepts BidirectionalGraph, VertexAndEdgeListGraph, and FaceListGraph.

Only finite simplices exist when viewed through the scope of these graph traits classes. The infinite vertex, halfedges, edges, and faces will thus not appear when looping around a border vertex, or walking through the faces container.

The mapping between vertices, edges, and faces 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.

Member Value Description
vertex_descriptor unspecified_type Identify vertices in the graph.
halfedge_descriptor unspecified_type Identify halfedges in the graph. It is constructible from and convertible to Triangulation::Edge. It is not a simple typedef, but a proper class, because there is no representation for halfedges in the 2D triangulation data structure.
edge_descriptor unspecified_type Identify edges in the graph. It is constructible from and convertible to Triangulation::Edge. It 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.
face_descriptor unspecified_type Identify faces in the graph.
adjacency_iterator unspecified_type An iterator to traverse through the vertices adjacent to a vertex. Its value type is vertex_descriptor.
out_edge_iterator unspecified_type An iterator to traverse through the outgoing edges incident to a vertex. Its value type is edge_descriptor.
in_edge_iterator unspecified_type An iterator to traverse through the incoming edges incident to a vertex. Its value type is edge_descriptor.
vertex_iterator unspecified_type An iterator to traverse through the vertices of the graph. Its value type is vertex_descriptor.
halfedge_iterator unspecified_type An iterator to traverse through the halfedges of the graph. Its value type is halfedge_descriptor.
edge_iterator unspecified_type An iterator to traverse through the edges of the graph. Its value type is edge_descriptor.
face_iterator unspecified_type An iterator to traverse through the faces of the graph. Its value type is face_descriptor.
directed_category boost::undirected_tag This graph is not directed.
edge_parallel_category boost::disallow_parallel_edge_tag This graph does not support multiedges.
traversal_category Inherits from boost::bidirectional_graph_tag, boost::adjacency_graph_tag, boost::vertex_list_graph_tag, and boost::edge_list_graph_tag The ways in which the vertices in the graph can be traversed..
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 CGAL::Arrangement_2 so that it is model of the graph concepts BidirectionalGraph and VertexAndEdgeListGraph.

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, Dcel> > provides the following types:

Member Value Description
vertex_descriptor Arrangement_2::Vertex_handle Identify vertices in the graph.
edge_descriptor Arrangement_2::Halfedge_handle Identify edges in the graph.
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 This graph is directed.
edge_parallel_category boost::allow_parallel_edge_tag This graph supports multiedges.
traversal_category Inherits from boost::bidirectional_graph_tag, boost::vertex_list_graph_tag, and boost::edge_list_graph_tag The ways in which the vertices in the graph can be traversed.
vertices_size_type Arrangement_2::Size The size type of the vertex list.
edges_size_type Arrangement_2::Size The size type of the edge list.
degree_size_type Arrangement_2::Size The size type of the adjacency list.

# Specialization for the OpenMesh::PolyMesh_ArrayKernelT Class

Defined in <CGAL/boost/graph/graph_traits_PolyMesh_ArrayKernelT.h>

We provide partial specialization for the class OpenMesh::PolyMesh_ArrayKernelT so that it is a model of the graph concepts BidirectionalGraph, VertexAndEdgeListGraph, AdjacencyMatrix, and MutableFaceGraph.

The traits class boost::graph_traits<OpenMesh::PolyMesh_ArrayKernelT<K> > provides the following types:

Member Value Description
vertex_descriptor OpenMesh::PolyMesh_ArrayKernelT::VertexHandle Identify vertices in the graph.
edge_descriptor unspecified_type Identify edges in the graph.
halfedge_descriptor OpenMesh::PolyMesh_ArrayKernelT::HalfedgeHandle Identify halfedges in the graph.
face_descriptor OpenMesh::PolyMesh_ArrayKernelT::FaceHandle Identify faces in the graph.
adjacency_iterator unspecified_type An iterator to traverse through the vertices adjacent to a vertex. Its value type is vertex_descriptor.
out_edge_iterator CGAL::Out_edge_iterator<OpenMesh::PolyMesh_ArrayKernelT<K> > An iterator to traverse through the outgoing edges incident to a vertex. Its value type is edge_descriptor.
in_edge_iterator CGAL::In_edge_iterator<OpenMesh::PolyMesh_ArrayKernelT<K> > An iterator to traverse through the incoming edges incident to a vertex. Its value type is edge_descriptor.
vertex_iterator OpenMesh::PolyMesh_ArrayKernelT::VertexIter An iterator to traverse through the vertices of the graph. Its value type is vertex_descriptor.
edge_iterator unspecified_type An iterator to traverse through the edges of the graph. Its value type is edge_descriptor.
halfedge_iterator OpenMesh::PolyMesh_ArrayKernelT::HalfedgeIter An iterator to traverse through the halfedges of the graph. Its value type is halfedge_descriptor.
face_iterator OpenMesh::PolyMesh_ArrayKernelT::FaceIter An iterator to traverse through the faces of the graph. Its value type is face_descriptor.
directed_category boost::undirected_tag This graph is not directed.
edge_parallel_category boost::disallow_parallel_edge_tag This graph does not support multiedges.
traversal_category Inherits from boost::bidirectional_graph_tag, boost::vertex_list_graph_tag, and boost::edge_list_graph_tag The ways in which the vertices in the graph can be traversed.
vertices_size_type unsigned int The size type of the vertex list.
edges_size_type unsigned int The size type of the edge list.
degree_size_type unsigned int The size type of the adjacency list.

# Specialization for the OpenMesh::TriMesh_ArrayKernelT Class

Defined in <CGAL/boost/graph/graph_traits_TriMesh_ArrayKernelT.h>

We provide partial specialization for the class OpenMesh::TriMesh_ArrayKernelT so that it is a model of the graph concepts BidirectionalGraph, VertexAndEdgeListGraph, AdjacencyMatrix, and MutableFaceGraph.

The traits class boost::graph_traits<OpenMesh::TriMesh_ArrayKernelT<K> > provides the following types:

Member Value Description
vertex_descriptor OpenMesh::TriMesh_ArrayKernelT::VertexHandle Identify vertices in the graph.
edge_descriptor unspecified_type Identify edges in the graph.
halfedge_descriptor OpenMesh::TriMesh_ArrayKernelT::HalfedgeHandle Identify halfedges in the graph.
face_descriptor OpenMesh::TriMesh_ArrayKernelT::FaceHandle Identify faces in the graph.
adjacency_iterator unspecified_type An iterator to traverse through the vertices adjacent to a vertex. Its value type is vertex_descriptor.
out_edge_iterator CGAL::Out_edge_iterator<OpenMesh::TriMesh_ArrayKernelT<K> > An iterator to traverse through the outgoing edges incident to a vertex. Its value type is edge_descriptor.
in_edge_iterator CGAL::In_edge_iterator<OpenMesh::TriMesh_ArrayKernelT<K> > An iterator to traverse through the incoming edges incident to a vertex. Its value type is edge_descriptor.
vertex_iterator OpenMesh::PolyMesh_ArrayKernelT::VertexIter An iterator to traverse through the vertices of the graph. Its value type is vertex_descriptor.
edge_iterator unspecified_type An iterator to traverse through the edges of the graph. Its value type is edge_descriptor.
halfedge_iterator OpenMesh::TriMesh_ArrayKernelT::HalfedgeIter An iterator to traverse through the halfedges of the graph. Its value type is halfedge_descriptor.
face_iterator OpenMesh::TriMesh_ArrayKernelT::FaceIter An iterator to traverse through the faces of the graph. Its value type is face_descriptor.
directed_category boost::undirected_tag This graph is not directed.
edge_parallel_category boost::disallow_parallel_edge_tag This graph does not support multiedges.
traversal_category Inherits from boost::bidirectional_graph_tag, boost::vertex_list_graph_tag, and boost::edge_list_graph_tag The ways in which the vertices in the graph can be traversed.
vertices_size_type unsigned int The size type of the vertex list.
edges_size_type unsigned int The size type of the edge list.
degree_size_type unsigned int The size type of the adjacency list.

# Specialization for the Seam_mesh Class

Defined in <CGAL/boost/graph/graph_traits_Seam_mesh.h>

We provide partial specialization for the class CGAL::Seam_mesh so that it is a model of the graph concepts BidirectionalGraph, VertexAndEdgeListGraph, AdjacencyMatrix, and FaceListGraph.

The traits class boost::graph_traits< CGAL::Seam_mesh<T> > provides the following types:

Member Value Description
vertex_descriptor Seam_mesh::vertex_descriptor Identify vertices in the graph.
edge_descriptor Seam_mesh::edge_descriptor Identify edges in the graph.
halfedge_descriptor Seam_mesh::halfedge_descriptor Identify halfedges in the graph.
face_descriptor Seam_mesh::face_descriptor Identify faces in the graph.
adjacency_iterator CGAL::Vertex_around_target_iterator<CGAL::Seam_mesh<T> > An iterator to traverse through the vertices adjacent to a vertex. Its value type is vertex_descriptor.
out_edge_iterator CGAL::Out_edge_iterator<CGAL::Seam_mesh<T> > An iterator to traverse through the outgoing edges incident to a vertex. Its value type is edge_descriptor.
in_edge_iterator CGAL::In_edge_iterator<CGAL::Seam_mesh<T> > An iterator to traverse through the incoming edges incident to a vertex. Its value type is edge_descriptor.
vertex_iterator Seam_mesh::vertex_iterator An iterator to traverse through the vertices of the graph. Its value type is vertex_descriptor.
edge_iterator Seam_mesh::edge_iterator An iterator to traverse through the edges of the graph. Its value type is edge_descriptor.
halfedge_iterator Seam_mesh::halfedge_iterator An iterator to traverse through the halfedges of the graph. Its value type is halfedge_descriptor.
face_iterator Seam_mesh::face_iterator An iterator to traverse through the faces of the graph. Its value type is face_descriptor.
directed_category boost::undirected_tag This graph is not directed.
edge_parallel_category boost::disallow_parallel_edge_tag This graph does not support multiedges.
traversal_category Inherits from boost::bidirectional_graph_tag, boost::vertex_list_graph_tag, and boost::edge_list_graph_tag The ways in which the vertices in the graph can be traversed.
vertices_size_type Seam_mesh::vertices_size_type The size type of the vertex list.
edges_size_type Seam_mesh::edges_size_type The size type of the edge list.
degree_size_type Seam_mesh::degree_size_type The size type of the adjacency list.