|
CGAL 4.4 - CGAL and the Boost Graph Library
|
|
CGAL 4.4 - CGAL and the Boost Graph Library
|
Specializations of boost::graph_traits for CGAL types.
The boost graph library (BGL) uses the type trait class boost::graph_traits to provides a uniform interface to the properties and types of graph types.
Defined in <CGAL/boost/graph/graph_traits_Polyhedron_3.h>
Partial specialization for the class CGAL::Polyhedron_3. It provides the types associated to the graph concepts BidirectionalGraph and EdgeAndVertexListGraph.
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 | Polyhedron_3::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 Polyhedron_3::Halfedge_around_vertex_circulator with the difference that its value type is an edge descriptor and not Polyhedron_3::Halfedge |
in_edge_iterator | unspecified_type | An edge iterator which only iterates over the incoming edges around a vertex. It corresponds to a Polyhedron_3::Halfedge_around_vertex_circulator with the difference that its value type is an edge descriptor and not Polyhedron_3::Halfedge |
vertex_iterator | unspecified_type | An iterator corresponding to Polyhedron_3::Vertex_iterator, with the difference that its value type is a vertex descriptor and not Polyhedron_3::Vertex |
edge_iterator | Polyhedron_3::Halfedge_iterator | An iterator corresponding to Polyhedron_3::Halfedge_iterator with the difference that its value type is an edge descriptor and not Polyhedron_3::Halfedge |
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 |
Defined in <CGAL/boost/graph/graph_traits_Triangulation_2.h> and <CGAL/boost/graph/graph_traits_Delaunay_triangulation_2.h>
The triangulations of CGAL are all models of the concepts BidirectionalGraph and VertexAndEdgeListGraph of the Boost Graph Library [1].
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 boost::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>
The class Arrangement_2 is a model of to 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 |
1.8.4