\( \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.9 - CGAL and the Boost Graph Library
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
User Manual

Authors
Andreas Fabri, Fernando Cacciola, Philipp Moeller, and Ron Wein

Many geometric data structures can be interpreted as graphs as they consist of vertices and edges. This is the case for the halfedge data structure, for the polyhedral surface, for the arrangement, and for the 2D triangulation classes. With means of duality one can also interpret faces as vertices and edges between adjacent faces as edges of the dual graph.

The scope of CGAL is geometry and not graph algorithms. Nevertheless, this package provides the necessary classes and functions that enable using the algorithms of the Boost Graph Library [2] (Bgl for short) with CGAL data structures.

Furthermore, this package extends the Bgl by introducing concepts such as HalfedgeGraph and FaceGraph allowing to handle halfedges and faces. These concepts reflect the design of the halfedge data structure described in Chapter Halfedge Data Structures, with opposite halfedges, and the circular sequence of halfedges around vertices and around faces.

This chapter is organized as follows. Section A Short Introduction to the Boost Graph Library present the ideas of Bgl in a nutshell. Section Header Files, Namespaces, and Naming Conventions explains where to find header files and the chosen naming conventions, as we blend two different libraries. The four following sections give examples for how the surface mesh, the polyhedron, the arrangement, and the 2D triangulation classes are adapted to Bgl. Finally, Section Extensions of the BGL introduces the HalfedgeGraph which is an extension to the graph concepts of the Bgl.

A Short Introduction to the Boost Graph Library

The algorithms of Bgl operate on models of the various graph concepts. The traits class boost::graph_traits enable the algorithms determining the types of vertices and edges (similar to std::iterator_traits for iterators). Free functions that operate on graphs enable the algorithms to obtain, for example, the source vertex of an edge, or all edges incident to a vertex. The algorithms use property maps to associate information with vertices and edges. The algorithms enable visitors to register callbacks that are called later on during the execution of the algorithms. Finally, the graph algorithms use the named parameter mechanism, which enambles passing the arguments in arbitrary order.

Graph Concepts

Bgl introduces several graph concepts, which have different sets of characteristics and requirements. For example iterating through all vertices or all edges in a graph, obtaining the outgoing edges of a vertex, or also the in-going edges, inserting vertices and edges into a graph, and removing vertices and edges from a graph.

The Graph Traits Class

An algorithm operating on a graph model determines types with the help of the traits class boost::graph_traits. Such types are the vertex_descriptor, which is similar to a vertex handle in CGAL data structures, the edge_descriptor which is similar to the halfedge handle in the halfedge data structure and to the type Edge in 2D triangulations. There are also iterators, such as the vertex_iterator, which is similar to a vertex iterator in CGAL data structures, and the out_edge_iterator, which is similar to the edge circulator; it enables to iterate through the edges incident to a vertex. The iterators are similar and not equivalent, because their value type is a vertex_descriptor, whereas in CGAL handles, iterators, and circulators all have the same value type, namely the vertex or edge type. Given a graph type G the definition of a vertex descriptor looks as follows:

boost::graph_traits<Graph>::vertex_descriptor vd;

Free Functions for Exploring a Graph

The algorithms obtain incidence information with the help of global functions such as:

  • std::pair<vertex_iterator,vertex_iterator> vertices(const Graph& g); for obtaining an iterator range providing access to all the vertices, or
  • int num_vertices(const Graph&); for obtaining the number of vertices of a graph, or
  • vertex_descriptor source(edge_descriptor, const Graph&); for obtaining the source vertex of an edge.

Note, that the way we have written the types is a simplification, that is in reality the signature of the first of the above functions is

typedef boost::graph_traits<Graph>::vertex_iterator vertex_iterator;
std::pair<vertex_iterator,vertex_iterator> vertices(const Graph& g);

Property Maps

Another feature extensively used in Bgl is the property map, which is offered by the Boost Property Map Library. Property maps are a general purpose interface for mapping key objects to corresponding value objects.

Bgl uses property maps to associate information with vertices and edges. This mechanism uses a traits class (boost::property_traits) and free functions for obtaining (get) and writing (put) information in vertices, edges, and also halfedges and faces for models of the CGAL graph concepts. For example, Bgl Dijksta's shortest path algorithm writes the predecessor of each vertex, as well as the distance to the source in such a property map.

Some default property maps are associated with the graph types. They are called internal property maps and can be retrieved using an overload of the function get(). For example, pm = get(boost::vertex_index, g) returns a property map that associates an index in the range [0, num_vertices(g)) with each vertex of the graph. This reduces the number of parameters to pass. The data itself may be stored in the vertex or the edge, or it may be stored in an external data structure, or it may be computed on the fly. This is an implementation detail of a particular property map.

See also the Chapter CGAL and Boost Property Maps.

Visitors

Visitors are objects that provide functions that are called at specified event points by the algorithm they visit.

The functions as well as the event points are algorithm specific. Examples of event points in graph algorithms are when a vertex is traversed the first time, or when all outgoing edges of a vertex are traversed.

See also Section Visitor Concepts in the Bgl manual.

Named Parameters

The algorithms of Bgl often have many parameters with default values that are appropriate for most cases. In general, when no special treatment is applied, the values of such parameters are passed as a sequence. Deviating from the default for a certain parameter requires the user to explicitly pass values for all preceding parameters. The solution to this problem is to first write a tag and then the parameter, which for Dijkstra's shortest path algorithm might look as follows:

std::vector<vertex_descriptor> p(num_vertices(g));
std::vector<int> d(num_vertices(g));
vertex_descriptor s = vertex(A, g);
dijkstra_shortest_paths(g, s, predecessor_map(&p[0]).distance_map(&d[0]));

In the Bgl manual this is called named parameters. The named parameters in the example use the tags predecessor_map and distance_map and they are concatenated with the dot operator.

Header Files, Namespaces, and Naming Conventions

Partial specializations of the boost::graph_traits<Graph> for the CGAL package PACKAGE are in the namespace boost and in the header file CGAL/boost/graph/graph_traits_PACKAGE.h. The free functions are in the namespace CGAL, as the compiler uses argument dependent lookup to find them. The Euler operations are in the namespace CGAL::Euler, as the function remove_face() is at the same time a low level and an Euler operation. Concerning the naming conventions we have to use those of Bgl, as we have to fulfill the requirements of the concepts defined in Bgl.

The Class Surface_mesh as Model of the Boost Graph Concept

The class Surface_mesh is a model of most of Bgl graph concepts as well as the concepts provided by CGAL. A full list can be found in the documentation of boost::graph_traits. The examples show how to use some of the Bgl algorithms with Surface_mesh and show how to use the concepts provided by CGAL to implement a simple algorithm.

Example: Minimum Spanning Tree of a Surface_mesh

The following example program computes the minimum spanning tree on a surface mesh. More examples can be found in the chapters Triangulated Surface Mesh Simplification, Triangulated Surface Mesh Segmentation, and Triangulated Surface Mesh Deformation.

The surface mesh class uses integer indices to address vertices and edges, and it comes with a built-in property mechanism that maps nicely on the Bgl.


File BGL_surface_mesh/prim.cpp

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Surface_mesh.h>
#include <iostream>
#include <fstream>
#include <boost/graph/prim_minimum_spanning_tree.hpp>
#include <boost/foreach.hpp>
typedef Kernel::Point_3 Point;
typedef boost::graph_traits<Mesh>::vertex_descriptor vertex_descriptor;
int main(int, char* argv[])
{
Mesh P;
//std::cin >> P;
std::ifstream in(argv[1]);
in >> P;
Mesh::Property_map<vertex_descriptor,vertex_descriptor> predecessor;
predecessor = P.add_property_map<vertex_descriptor,vertex_descriptor>("v:predecessor").first;
boost::prim_minimum_spanning_tree(P, predecessor, boost::root_vertex(*vertices(P).first));
std::cout << "#VRML V2.0 utf8\n"
"DirectionalLight {\n"
"direction 0 -1 0\n"
"}\n"
"Shape {\n"
" appearance Appearance {\n"
" material Material { emissiveColor 1 0 0}}\n"
" geometry\n"
" IndexedLineSet {\n"
" coord Coordinate {\n"
" point [ \n";
BOOST_FOREACH(vertex_descriptor vd, vertices(P)){
std::cout << " " << P.point(vd) << "\n";
}
std::cout << " ]\n"
" }\n"
" coordIndex [\n";
BOOST_FOREACH(vertex_descriptor vd, vertices(P)){
if(predecessor[vd]!=vd){
std::cout << " " << std::size_t(vd) << ", " << std::size_t(predecessor[vd]) << ", -1\n";
}
}
std::cout << "]\n"
" }#IndexedLineSet\n"
"}# Shape\n";
P.remove_property_map(predecessor);
return 0;
}

The Class Polyhedron_3 as Model of the Boost Graph Concept

The class Polyhedron_3 is a model of most of Bgl graph concepts as well as the concepts provided by CGAL. A full list can be found in the documentation of boost::graph_traits. The examples show how to use some of the Bgl algorithms with Polyhedron_3 and show how to use the concepts provided by CGAL to implement a simple algorithm.

Example: Minimum Spanning Tree of a Polyhedral Surface

The following example program computes the minimum spanning tree on a polyhedral surface. More examples can be found in the Chapter Triangulated Surface Mesh Simplification.


File BGL_polyhedron_3/kruskal.cpp

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Polyhedron_3.h>
#include <CGAL/IO/Polyhedron_iostream.h>
#include <CGAL/boost/graph/graph_traits_Polyhedron_3.h>
#include <iostream>
#include <list>
#include <boost/graph/kruskal_min_spanning_tree.hpp>
typedef Kernel::Vector_3 Vector;
typedef Kernel::Point_3 Point;
typedef CGAL::Polyhedron_3<Kernel> Polyhedron;
typedef boost::graph_traits<Polyhedron>::vertex_descriptor vertex_descriptor;
typedef boost::graph_traits<Polyhedron>::vertex_iterator vertex_iterator;
typedef boost::graph_traits<Polyhedron>::edge_descriptor edge_descriptor;
// The BGL makes heavy use of indices associated to the vertices
// We use a std::map to store the index
typedef std::map<vertex_descriptor,int> Vertex_index_map;
Vertex_index_map vertex_index_map;
// A std::map is not a property map, because it is not lightweight
typedef boost::associative_property_map<Vertex_index_map> Vertex_index_pmap;
Vertex_index_pmap vertex_index_pmap(vertex_index_map);
void
kruskal(const Polyhedron& P)
{
// associate indices to the vertices
vertex_iterator vb, ve;
int index = 0;
// boost::tie assigns the first and second element of the std::pair
// returned by boost::vertices to the variables vb and ve
for(boost::tie(vb, ve)=vertices(P); vb!=ve; ++vb){
vertex_index_pmap[*vb]= index++;
}
// We use the default edge weight which is the length of the edge
// This property map is defined in graph_traits_Polyhedron_3.h
// In the function call you can see a named parameter: vertex_index_map
std::list<edge_descriptor> mst;
boost::kruskal_minimum_spanning_tree(P,
std::back_inserter(mst),
boost::vertex_index_map(vertex_index_pmap));
std::cout << "#VRML V2.0 utf8\n"
"Shape {\n"
" appearance Appearance {\n"
" material Material { emissiveColor 1 0 0}}\n"
" geometry\n"
" IndexedLineSet {\n"
" coord Coordinate {\n"
" point [ \n";
for(boost::tie(vb, ve) = vertices(P); vb!=ve; ++vb){
std::cout << " " << (*vb)->point() << "\n";
}
std::cout << " ]\n"
" }\n"
" coordIndex [\n";
for(std::list<edge_descriptor>::iterator it = mst.begin(); it != mst.end(); ++it)
{
edge_descriptor e = *it ;
vertex_descriptor s = source(e,P);
vertex_descriptor t = target(e,P);
std::cout << " " << vertex_index_pmap[s] << ", " << vertex_index_pmap[t] << ", -1\n";
}
std::cout << "]\n"
" }#IndexedLineSet\n"
"}# Shape\n";
}
int main() {
Polyhedron P;
Point a(1,0,0);
Point b(0,1,0);
Point c(0,0,1);
Point d(0,0,0);
P.make_tetrahedron(a,b,c,d);
kruskal(P);
return 0;
}

Example: Using Vertices, and Edges with an ID

The following example program shows a call to the Bgl Kruskal's minimum spanning tree algorithm accessing the id() field stored in a polyhedron vertex.

The main function illustrates the access to the id() field.


File BGL_polyhedron_3/kruskal_with_stored_id.cpp

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Polyhedron_3.h>
#include <CGAL/Polyhedron_items_with_id_3.h>
#include <CGAL/IO/Polyhedron_iostream.h>
#include <CGAL/boost/graph/graph_traits_Polyhedron_3.h>
#include <iostream>
#include <list>
#include <boost/graph/kruskal_min_spanning_tree.hpp>
typedef Kernel::Point_3 Point;
typedef boost::graph_traits<Polyhedron>::vertex_descriptor vertex_descriptor;
typedef boost::graph_traits<Polyhedron>::vertex_iterator vertex_iterator;
typedef boost::graph_traits<Polyhedron>::edge_descriptor edge_descriptor;
void
kruskal( const Polyhedron& P)
{
// We use the default edge weight which is the length of the edge
// This property map is defined in graph_traits_Polyhedron_3.h
// This function call requires a vertex_index_map named parameter which
// when ommitted defaults to "get(vertex_index,graph)".
// That default works here because the vertex type has an "id()" method
// field which is used by the vertex_index internal property.
std::list<edge_descriptor> mst;
boost::kruskal_minimum_spanning_tree(P,std::back_inserter(mst));
std::cout << "#VRML V2.0 utf8\n"
"Shape {\n"
"appearance Appearance {\n"
"material Material { emissiveColor 1 0 0}}\n"
"geometry\n"
"IndexedLineSet {\n"
"coord Coordinate {\n"
"point [ \n";
vertex_iterator vb, ve;
for(boost::tie(vb,ve) = vertices(P); vb!=ve; ++vb){
std::cout << (*vb)->point() << "\n";
}
std::cout << "]\n"
"}\n"
"coordIndex [\n";
for(std::list<edge_descriptor>::iterator it = mst.begin(); it != mst.end(); ++it){
std::cout << source(*it,P)->id()
<< ", " << target(*it,P)->id() << ", -1\n";
}
std::cout << "]\n"
"}#IndexedLineSet\n"
"}# Shape\n";
}
int main() {
Polyhedron P;
Point a(1,0,0);
Point b(0,1,0);
Point c(0,0,1);
Point d(0,0,0);
P.make_tetrahedron(a,b,c,d);
// associate indices to the vertices using the "id()" field of the vertex.
vertex_iterator vb, ve;
int index = 0;
// boost::tie assigns the first and second element of the std::pair
// returned by boost::vertices to the variables vit and ve
for(boost::tie(vb,ve)=vertices(P); vb!=ve; ++vb ){
vertex_descriptor vd = *vb;
vd->id() = index++;
}
kruskal(P);
return 0;
}

Triangulations as Models of the Boost Graph Concept

Triangulations have vertices and faces. An edge is a pair of a face handle and the index of the edge. Particular care has to be taken with the infinite vertex and its incident edges. One can either use a boost::filtered_graph in order to make the infinite edges invisible, or one can have a property map that returns an infinite length for these edges.

A classical example for an algorithm that is a combination of computational geometry and graph theory is the Euclidean Minimum Spanning Tree for a point set in the plane. It can be computed by running the minimum spanning tree algorithm on a Delaunay triangulation of the point set.

Example: Euclidean Minimum Spanning Tree

In the following example we create a Delaunay triangulation and run Kruskal's minimum spanning tree algorithm on it. Because the vertex handles of the triangulation are not indices in an array, we have to provide a property map that maps vertex handles to integers in the range [0, t.number_of_vertices()).


File BGL_triangulation_2/emst.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Delaunay_triangulation_2.h>
#include <CGAL/boost/graph/graph_traits_Delaunay_triangulation_2.h>
#include <boost/graph/kruskal_min_spanning_tree.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <fstream>
typedef K::Point_2 Point;
typedef CGAL::Delaunay_triangulation_2<K> Triangulation;
// As we only consider finite vertices and edges
// we need the following filter
template <typename T>
struct Is_finite {
const T* t_;
Is_finite()
: t_(NULL)
{}
Is_finite(const T& t)
: t_(&t)
{ }
template <typename VertexOrEdge>
bool operator()(const VertexOrEdge& voe) const {
return ! t_->is_infinite(voe);
}
};
typedef Is_finite<Triangulation> Filter;
typedef boost::filtered_graph<Triangulation,Filter,Filter> Finite_triangulation;
typedef boost::graph_traits<Finite_triangulation>::vertex_descriptor vertex_descriptor;
typedef boost::graph_traits<Finite_triangulation>::vertex_iterator vertex_iterator;
typedef boost::graph_traits<Finite_triangulation>::edge_descriptor edge_descriptor;
// The BGL makes use of indices associated to the vertices
// We use a std::map to store the index
typedef std::map<vertex_descriptor,int> VertexIndexMap;
VertexIndexMap vertex_id_map;
// A std::map is not a property map, because it is not lightweight
typedef boost::associative_property_map<VertexIndexMap> VertexIdPropertyMap;
VertexIdPropertyMap vertex_index_pmap(vertex_id_map);
int
main(int argc,char* argv[])
{
const char* filename = (argc > 1) ? argv[1] : "data/points.xy";
std::ifstream input(filename);
Triangulation t;
Filter is_finite(t);
Finite_triangulation ft(t, is_finite, is_finite);
Point p ;
while(input >> p){
t.insert(p);
}
vertex_iterator vit, ve;
// Associate indices to the vertices
int index = 0;
// boost::tie assigns the first and second element of the std::pair
// returned by boost::vertices to the variables vit and ve
for(boost::tie(vit,ve)=boost::vertices(ft); vit!=ve; ++vit ){
vertex_descriptor vd = *vit;
vertex_id_map[vd]= index++;
}
// We use the default edge weight which is the squared length of the edge
// This property map is defined in graph_traits_Triangulation_2.h
// In the function call you can see a named parameter: vertex_index_map
std::list<edge_descriptor> mst;
boost::kruskal_minimum_spanning_tree(ft,
std::back_inserter(mst),
vertex_index_map(vertex_index_pmap));
std::cout << "The edges of the Euclidean mimimum spanning tree:" << std::endl;
for(std::list<edge_descriptor>::iterator it = mst.begin(); it != mst.end(); ++it){
edge_descriptor ed = *it;
vertex_descriptor svd = source(ed,t);
vertex_descriptor tvd = target(ed,t);
Triangulation::Vertex_handle sv = svd;
Triangulation::Vertex_handle tv = tvd;
std::cout << "[ " << sv->point() << " | " << tv->point() << " ] " << std::endl;
}
return 0;
}

Example: Storing the Vertex ID in the Vertex

The algorithms of Bgl extensively use of the indices of vertices. In the previous example we stored the indices in a std::map and turned that map in a property map. This property map was then passed as argument to the shortest path function.

If the user does not pass explicitly a property map, the graph algorithms use the property map returned by the call get(boost::vertex_index,ft). This property map assumes that the vertex has a member function id() that returns a reference to an int. Therefore CGAL offers a class Triangulation_vertex_base_with_id_2. It is in the users responsibility to set the indices properly.

The example further illustrates that the graph traits also works for the Delaunay triangulation.


File BGL_triangulation_2/dijkstra_with_internal_properties.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Delaunay_triangulation_2.h>
#include <CGAL/Triangulation_vertex_base_with_id_2.h>
#include <CGAL/boost/graph/graph_traits_Delaunay_triangulation_2.h>
#include <CGAL/boost/graph/dijkstra_shortest_paths.h>
#include <boost/graph/filtered_graph.hpp>
#include <fstream>
typedef K::Point_2 Point;
typedef CGAL::Triangulation_data_structure_2<Tvb,Tfb> Tds;
// consider finite vertices and edges.
template <typename T>
struct Is_finite {
const T* t_;
Is_finite()
: t_(NULL)
{}
Is_finite(const T& t)
: t_(&t)
{ }
template <typename VertexOrEdge>
bool operator()(const VertexOrEdge& voe) const {
return ! t_->is_infinite(voe);
}
};
typedef Is_finite<Triangulation> Filter;
typedef boost::filtered_graph<Triangulation,Filter,Filter> Finite_triangulation;
typedef boost::graph_traits<Finite_triangulation>::vertex_descriptor vertex_descriptor;
typedef boost::graph_traits<Finite_triangulation>::vertex_iterator vertex_iterator;
int
main(int argc,char* argv[])
{
const char* filename = (argc > 1) ? argv[1] : "data/points.xy";
std::ifstream input(filename);
Triangulation t;
Filter is_finite(t);
Finite_triangulation ft(t, is_finite, is_finite);
Point p ;
while(input >> p){
t.insert(p);
}
vertex_iterator vit, ve;
// associate indices to the vertices
int index = 0;
for(boost::tie(vit,ve)=boost::vertices(ft); vit!=ve; ++vit ){
vertex_descriptor vd = *vit;
vd->id()= index++;
}
typedef boost::property_map<Triangulation, boost::vertex_index_t>::type VertexIdPropertyMap;
VertexIdPropertyMap vertex_index_pmap = get(boost::vertex_index, ft);
// Dijkstra's shortest path needs property maps for the predecessor and distance
std::vector<vertex_descriptor> predecessor(boost::num_vertices(ft));
boost::iterator_property_map<std::vector<vertex_descriptor>::iterator, VertexIdPropertyMap>
predecessor_pmap(predecessor.begin(), vertex_index_pmap);
std::vector<double> distance(boost::num_vertices(ft));
boost::iterator_property_map<std::vector<double>::iterator, VertexIdPropertyMap>
distance_pmap(distance.begin(), vertex_index_pmap);
vertex_descriptor source = *boost::vertices(ft).first;
std::cout << "\nStart dijkstra_shortest_paths at " << source->point() << std::endl;
boost::dijkstra_shortest_paths(ft, source ,
distance_map(distance_pmap)
.predecessor_map(predecessor_pmap));
for(boost::tie(vit,ve)=boost::vertices(ft); vit!=ve; ++vit ){
vertex_descriptor vd = *vit;
std::cout << vd->point() << " [" << vd->id() << "] ";
std::cout << " has distance = " << get(distance_pmap,vd) << " and predecessor ";
vd = get(predecessor_pmap,vd);
std::cout << vd->point() << " [" << vd->id() << "]\n";
}
return 0;
}

Arrangements as Models of the Boost Graph Concept

CGAL offers the graph traits for the arrangement itself as well as for its dual graph.

Example for the Arrangement as Graph

Arrangement instances are adapted to boost graphs by specializing the boost:graph_traits template for Arrangement_2 instances. The graph-traits states the graph concepts that the arrangement class models (see below) and defines the types required by these concepts.

In this specialization the Arrangement_2 vertices correspond to the graph vertices, where two vertices are adjacent if there is at least one halfedge connecting them. More precisely, Arrangement_2::Vertex_handle is the graph-vertex type, while Arrangement_2::Halfedge_handle is the graph-edge type. As halfedges are directed, we consider the graph to be directed as well. Moreover, as several interior-disjoint \( x\)-monotone curves (say circular arcs) may share two common endpoints, inducing an arrangement with two vertices that are connected with several edges, we allow parallel edges in our boost graph.

Given an Arrangement_2 instance, we can efficiently traverse its vertices and halfedges. Thus, the arrangement graph is a model of the concepts VertexListGraph and EdgeListGraph introduced by Bgl. At the same time, we use an iterator adapter of the circulator over the halfedges incident to a vertex (Halfedge_around_target_circulator - see Section Traversal Methods for an Arrangement Vertex of the chaper on arrangements), so it is possible to go over the ingoing and outgoing edges of a vertex in linear time. Thus, our arrangement graph is a model of the concept BidirectionalGraph (this concept refines IncidenceGraph, which requires only the traversal of outgoing edges).

It is important to notice that the vertex descriptors we use are Vertex_handle objects and not vertex indices. However, in order to gain more efficiency in most Bgl algorithm, it is better to have them indexed \( 0, 1, \ldots, (n-1)\), where \( n\) is the number of vertices. We therefore introduce the Arr_vertex_index_map<Arrangement> class-template, which maintains a mapping of vertex handles to indices, as required by Bgl. An instance of this class must be attached to a valid arrangement vertex when it is created. It uses the notification mechanism (see Section The Notification Mechanism) to automatically maintain the mapping of vertices to indices, even when new vertices are inserted into the arrangement or existing vertices are removed.

In most algorithm provided by Bgl, the output is given by property maps, such that each map entry corresponds to a vertex. For example, when we compute the shortest paths from a given source vertex \( s\) to all other vertices we can obtain a map of distances and a map of predecessors - namely for each \( v\) vertex we have its distance from \( s\) and a descriptor of the vertex that precedes \( v\) in the shortest path from \( s\). If the vertex descriptors are simply indices, one can use vectors to efficiently represent the property maps. As this is not the case with the arrangement graph, we offer the Arr_vertex_property_map<Arrangement,Type> template allows for an efficient mapping of Vertex_handle objects to properties of type Type. Note however that unlike the Arr_vertex_index_map class, the vertex property-map class is not kept synchronized with the number of vertices in the arrangement, so it should not be reused in calls to Bgl functions in case the arrangement is modified in between these calls.

ex_bgl.png
Figure 87.1 An arrangement of 7 line segments, as constructed by ex_bgl_primal_adapter.cpp and ex_bgl_dual_adapter.cpp. The breadth-first visit times for the arrangement faces, starting from the unbounded face \( f_0\), are shown in brackets.

In the following example we construct an arrangement of 7 line segments, as shown in Figure 87.1, then use Bgl Dijkstra's shortest-paths algorithm to compute the graph distance of all vertices from the leftmost vertex in the arrangement \( v_0\). Note the usage of the Arr_vertex_index_map and the Arr_vertex_property_map classes. The latter one, instantiated by the type double is used to map vertices to their distances from \( v_0\).


File BGL_arrangement_2/primal.cpp

// Adapting an arrangement to a BGL graph.
#include "arr_rational_nt.h"
#include <CGAL/Cartesian.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Arrangement_2.h>
#include <CGAL/graph_traits_Arrangement_2.h>
#include <CGAL/Arr_vertex_index_map.h>
#include <CGAL/boost/graph/dijkstra_shortest_paths.h>
#include <CGAL/property_map.h>
typedef Traits_2::Point_2 Point_2;
typedef Traits_2::X_monotone_curve_2 Segment_2;
typedef CGAL::Arrangement_2<Traits_2> Arrangement_2;
// A functor used to compute the length of an edge.
class Edge_length_func
{
public:
// Boost property type definitions:
typedef boost::readable_property_map_tag category;
typedef double value_type;
typedef value_type reference;
double operator()(Arrangement_2::Halfedge_handle e) const
{
const double x1 = CGAL::to_double (e->source()->point().x());
const double y1 = CGAL::to_double (e->source()->point().y());
const double x2 = CGAL::to_double (e->target()->point().x());
const double y2 = CGAL::to_double (e->target()->point().y());
const double diff_x = x2 - x1;
const double diff_y = y2 - y1;
return std::sqrt(diff_x*diff_x + diff_y*diff_y);
}
};
double get(Edge_length_func edge_length, Arrangement_2::Halfedge_handle e)
{
return edge_length(e);
}
/* The folowing is a workaround for a bug in the BGL upto and including version
* 103400.
*
* Unfortunately some of the calls to the get() function below from the BGL
* code are qualified with the boost namespace, while others are not. For The
* qualified calls the compiler naturally looks for the definition of the
* function in boost namespace. For the other calls it searches the CGAL
* namespace according to ADL (Koenig Lookup), as the type of the 1st
* parameter is in CGAL namespace.
*
* One way to get around it is to provide 2 similar functions that do the
* same thing. One in CGAL namespace provided in CGAL/Arr_vertex_map.h, and
* the other in boost namespace below. The signature of the latter is slightly
* changed to avoid redefinition. The type of its 1st parameter is defined in
* boost namespace, and is a simple derivation of the 1st parameter of the
* CGAL::get() function.
*/
namespace boost {
template <typename Arrangement_2>
class Arr_vertex_index_map_boost :
public CGAL::Arr_vertex_index_map<Arrangement_2>
{
public:
Arr_vertex_index_map_boost() : Base() {}
Arr_vertex_index_map_boost(Base & other) :
CGAL::Arr_vertex_index_map<Arrangement_2>(other)
{}
};
template<class Arrangement>
unsigned int
get(const boost::Arr_vertex_index_map_boost<Arrangement> & index_map,
typename Arrangement::Vertex_handle v)
{
static_cast<const CGAL::Arr_vertex_index_map<Arrangement> &>(index_map);
return CGAL::get<Arrangement>(index_map_tmp, v);
}
}
int main()
{
Arrangement_2 arr;
// Construct an arrangement of seven intersecting line segments.
// We keep a handle for the vertex v_0 that corresponds to the point (1,1).
insert_non_intersecting_curve (arr, Segment_2 (Point_2 (1, 1),
Point_2 (7, 1)));
Arrangement_2::Vertex_handle v0 = e->source();
insert (arr, Segment_2 (Point_2 (1, 1), Point_2 (3, 7)));
insert (arr, Segment_2 (Point_2 (1, 4), Point_2 (7, 1)));
insert (arr, Segment_2 (Point_2 (2, 2), Point_2 (9, 3)));
insert (arr, Segment_2 (Point_2 (2, 2), Point_2 (4, 4)));
insert (arr, Segment_2 (Point_2 (7, 1), Point_2 (9, 3)));
insert (arr, Segment_2 (Point_2 (3, 7), Point_2 (9, 3)));
// Create a mapping of the arrangement vertices to indices.
boost::Arr_vertex_index_map_boost<Arrangement_2> index_map(index_map_tmp);
// Perform Dijkstra's algorithm from the vertex v0.
Edge_length_func edge_length;
boost::vector_property_map<double, boost::Arr_vertex_index_map_boost<Arrangement_2> > dist_map(static_cast<unsigned int>(arr.number_of_vertices()), index_map);
boost::dijkstra_shortest_paths(arr, v0,
boost::vertex_index_map(index_map).
weight_map(edge_length).
distance_map(dist_map));
// Print the results:
std::cout << "The distances of the arrangement vertices from ("
<< v0->point() << ") :" << std::endl;
for (vit = arr.vertices_begin(); vit != arr.vertices_end(); ++vit)
std::cout << "(" << vit->point() << ") at distance "
<< dist_map[vit] << std::endl;
return 0;
}

Example for the Dual of an Arrangement as Graph

It is possible to give a dual graph representation for an arrangement instance, such that each arrangement face corresponds to a graph vertex and two vertices are adjacent iff the corresponding faces share a common edge on their boundaries. This is done by specializing the boost:graph_traits template for Dual<Arrangement_2> instances, where Dual<Arrangement_2> is a template specialization that gives a dual interpretation to an arrangement instance.

In dual representation, Arrangement_2::Face_handle is the graph-vertex type, while Arrangement_2::Halfedge_handle is the graph-edge type. We treat the graph edges as directed, such that a halfedge e is directed from \( f_1\), which is its incident face, to \( f_2\), which is the incident face of its twin halfedge. As two arrangement faces may share more than a single edge on their boundary, we allow parallel edges in our boost graph. As is the case in the primal graph, the dual arrangement graph is also a model of the concepts VertexListGraph, EdgeListGraph and BidirectionalGraph (thus also of IncidenceGraph).

Since we use Face_handle objects as the vertex descriptors, we define the Arr_face_index_map<Arrangement> class-template, which maintains an efficient mapping of face handles to indices. We also provide the template Arr_face_property_map<Arrangement,Type> for associating arbitrary data with the arrangement faces.

In the following example we construct the same arrangement as in example ex_bgl_primal_adapter.cpp (see Figure 32.29), and perform breadth-first search on the graph faces, starting from the unbounded face. We extend the Dcel faces with an unsigned integer, marking the discover time of the face and use a breadth-first-search visitor to obtain these times and update the faces accordingly:


File BGL_arrangement_2/arrangement_dual.cpp

// Adapting the dual of an arrangement to a BGL graph.
#include "arr_rational_nt.h"
#include <CGAL/Cartesian.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Arr_extended_dcel.h>
#include <CGAL/Arrangement_2.h>
#include <CGAL/graph_traits_Dual_Arrangement_2.h>
#include <CGAL/Arr_face_index_map.h>
#include <climits>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/visitors.hpp>
#include "arr_print.h"
// A property map that reads/writes the information to/from the extended
// face.
template <typename Arrangement, class Type> class Extended_face_property_map {
public:
typedef typename Arrangement::Face_handle Face_handle;
// Boost property type definitions.
typedef boost::read_write_property_map_tag category;
typedef Type value_type;
typedef value_type& reference;
typedef Face_handle key_type;
// The get function is required by the property map concept.
friend reference get(const Extended_face_property_map&, key_type key)
{ return key->data(); }
// The put function is required by the property map concept.
friend void put(const Extended_face_property_map&,
key_type key, value_type val)
{ key->set_data(val); }
};
typedef CGAL::Arrangement_2<Traits_2, Dcel> Ex_arrangement;
typedef CGAL::Dual<Ex_arrangement> Dual_arrangement;
typedef Extended_face_property_map<Ex_arrangement,unsigned int>
Face_property_map;
typedef Kernel::Point_2 Point_2;
typedef Kernel::Segment_2 Segment_2;
int main()
{
// Construct an arrangement of seven intersecting line segments.
Point_2 p1(1, 1), p2(1, 4), p3(2, 2), p4(3, 7), p5(4, 4), p6(7, 1), p7(9, 3);
Ex_arrangement arr;
insert(arr, Segment_2(p1, p6));
insert(arr, Segment_2(p1, p4)); insert(arr, Segment_2(p2, p6));
insert(arr, Segment_2(p3, p7)); insert(arr, Segment_2(p3, p5));
insert(arr, Segment_2(p6, p7)); insert(arr, Segment_2(p4, p7));
// Create a mapping of the arrangement faces to indices.
Face_index_map index_map(arr);
// Perform breadth-first search from the unbounded face, using the event
// visitor to associate each arrangement face with its discover time.
unsigned int time = 0;
boost::breadth_first_search(Dual_arrangement(arr), arr.unbounded_face(),
boost::vertex_index_map(index_map).visitor
(boost::make_bfs_visitor
(stamp_times(Face_property_map(), time,
boost::on_discover_vertex()))));
// Print the discover time of each arrangement face.
Ex_arrangement::Face_iterator fit;
for (fit = arr.faces_begin(); fit != arr.faces_end(); ++fit) {
std::cout << "Discover time " << fit->data() << " for ";
if (fit != arr.unbounded_face()) {
std::cout << "face ";
print_ccb<Ex_arrangement>(fit->outer_ccb());
}
else std::cout << "the unbounded face." << std::endl;
}
return 0;
}

Extensions of the BGL

The previous sections introduced partial specializations and free functions so that several CGAL data structures are adapted as models of some of the Bgl graph concepts. In this section we define a set of new concepts to extend the functionality of Bgl in order to match Halfedge Data Structures more closely and to enable writing generic algorithms, which operate on data structures that have faces and halfedges.

HalfedgeGraph refines Bidirectional Graph with operations to accommodate halfedge data structures. Given a halfedge, say h, the concept HalfedgeGraph requires the provision of the halfedge opposite to h, the halfedge that succeeds h, and the halfedge that precedes h.

MutableHalfedgeGraph adds the requirement for operations to change the next/previous relation and to adjust the target of a halfedge.

FaceGraph adds the requirements to explicitly handle faces in a graph, to provide quick access to incident halfedges of a face, and to enable access from every halfedge to an adjacent face. FaceListGraph adds the requirement for efficient traversal of faces. MutableFaceGraph adds requirements to change adjacency of faces and halfedges, and to remove and add faces.

The halfedge extensions are used by the surface simplification algorithms, which follow the design of Bgl as sketched in Section A Short Introduction to the Boost Graph Library.

Iterators and Circulators

Starting at a halfedge h of a halfedge graph g, applying several times next(h,g) brings us back to the halfedge where we started. All halfedges traversed on the way are incident to the same face.

Using the composition of the next(h,g) and opposite(h,g) functions results in another cycle, namely the cycle of halfedges which are incident to the same vertex.

For convenience, two iterator and circulator types enable the traversal of all halfedges incident to a given face, and all halfedges having a given vertex as target.

These types are not part of the concept HalfedgeGraph, but they are class templates that work for any model of this concept.

Euler Operations

There are two categories of mutating operations. The first category comprises low level operations that change incidences such as the target vertex of a halfedge. A halfedge graph might turn invalid by the application of inconsistent low lever operations. The second category of operations are called Euler Operations. These are high level operations such as adding a center vertex to a face, which means also adding halfedges and faces, and updating incidence information. The Euler operations enable manipulating models of MutableFaceGraph.

The Dual Graph

The dual graph of a FaceGraph G is a graph that has a vertex for each face of G. The dual graph has an edge whenever two faces of G are separated from each other by an edge. Thus, each edge e of G has a corresponding dual edge, the edge that connects the two faces on either side of e.

The class template Dual is an adaptor that creates the dual view of a FaceGraph. Faces of the original graph correspond to vertices in the Dual and vice versa.

The dual graph comes in handy when one wants to compute the connected component of a surface mesh.

Note that border edges in a Dual have the null_face of the original graph as either source or target. This is unusual and might break other algorithms since edges are always assumed to have non-null vertices as a source and target. It is possible to filter border edges using boost::filtered_graph as shown in the following example.


File BGL_surface_mesh/surface_mesh_dual.cpp

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Surface_mesh.h>
#include <CGAL/boost/graph/Dual.h>
#include <CGAL/boost/graph/helpers.h>
#include <iostream>
#include <fstream>
#include <boost/graph/filtered_graph.hpp>
#include <boost/graph/connected_components.hpp>
#include <boost/foreach.hpp>
typedef Kernel::Point_3 Point;
typedef CGAL::Dual<Mesh> Dual;
typedef boost::graph_traits<Dual>::edge_descriptor edge_descriptor;
template <typename G>
struct noborder {
noborder() : g(NULL) {} // default-constructor required by filtered_graph
noborder(G& g) : g(&g) {}
bool operator()(const edge_descriptor& e) const
{ return !is_border(e,*g); }
G* g;
};
// A dual border edge has a null_face as the source or target "vertex"
// BGL algorithms won't like that, so we remove border edges through a
// boost::filtered_graph.
typedef boost::filtered_graph<Dual, noborder<Mesh> > FiniteDual;
typedef boost::graph_traits<Mesh>::vertex_descriptor vertex_descriptor;
typedef boost::graph_traits<Mesh>::face_descriptor face_descriptor;
typedef boost::graph_traits<Mesh>::edge_descriptor edge_descriptor;
int main(int argc, char* argv[])
{
Mesh primal;
const char* filename = (argc > 1) ? argv[1] : "data/prim.off";
std::ifstream in(filename);
if(!(in >> primal)) {
std::cerr << "Error reading polyhedron from file " << filename << std::endl;
return EXIT_FAILURE;
}
Dual dual(primal);
FiniteDual finite_dual(dual,noborder<Mesh>(primal));
std::cout << "dual has " << num_vertices(dual) << " vertices" << std::endl;
std::cout << "The vertices of dual are faces in primal"<< std::endl;
BOOST_FOREACH(boost::graph_traits<Dual>::vertex_descriptor dvd , vertices(dual)) {
std::cout << dvd << std::endl;
}
std::cout << "The edges in primal and dual with source and target" << std::endl;
BOOST_FOREACH(edge_descriptor e , edges(dual)) {
std::cout << e << " in primal: " << source(e,primal) << " -- " << target(e,primal) << " "
<< " in dual : " << source(e,finite_dual) << " -- " << target(e,finite_dual) << std::endl;
}
std::cout << "edges of the finite dual graph" << std::endl;
BOOST_FOREACH(boost::graph_traits<FiniteDual>::edge_descriptor e , edges(finite_dual)) {
std::cout << e << " " << source(e,primal) << " " << source(e,finite_dual) << std::endl;
}
// the storage of a property map is in primal
Mesh::Property_map<face_descriptor,int> fccmap;
fccmap = primal.add_property_map<face_descriptor,int>("f:CC").first;
int num = connected_components(finite_dual, fccmap);
std::cout << "The graph has " << num << " connected components (face connectivity)" << std::endl;
BOOST_FOREACH(face_descriptor f , faces(primal)) {
std::cout << f << " in connected component " << fccmap[f] << std::endl;
}
Mesh::Property_map<vertex_descriptor,int> vccmap;
vccmap = primal.add_property_map<vertex_descriptor,int>("v:CC").first;
num = connected_components(primal, vccmap);
std::cout << "The graph has " << num << " connected components (edge connectvity)" << std::endl;
BOOST_FOREACH(vertex_descriptor v , vertices(primal)) {
std::cout << v << " in connected component " << vccmap[v] << std::endl;
}
return 0;
}

Example: Finding Incident Vertices in a HalfedgeGraph

The following example shows several functions that enable navigating in a HalfedgeGraph. We have two implementations of the operation that finds the vertices adjacent to a vertex v. Let us have a look at the first version. Given a vertex descriptor vd, we first call halfedge(vd,g) to obtain the halfedge with vd as target. Applying source() then gives us an adjacent vertex. We then get to the next halfedge with vd as target, by first going to the next halfedge around the face, and then going to the opposite halfedge.

The second version does the next() and opposite() jumping with an iterator. Note that when calling source() we have to dereference hi, as the function expects a halfedge descriptor and not a halfedge iterator. Also note that halfedges_around_target() expects a halfedge, and not a vertex. This provides the user with the ability to start the traversal at a specific halfedge incident to the input vertex (and not the arbitrary incident halfedge stored in the vertex record.)


File BGL_polyhedron_3/incident_vertices.cpp

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Polyhedron_3.h>
#include <CGAL/IO/Polyhedron_iostream.h>
#include <CGAL/boost/graph/graph_traits_Polyhedron_3.h>
#include <CGAL/boost/graph/iterator.h>
#include <iostream>
#include <fstream>
typedef CGAL::Polyhedron_3<Kernel> Polyhedron;
typedef boost::graph_traits<Polyhedron> GraphTraits;
typedef GraphTraits::vertex_descriptor vertex_descriptor;
typedef CGAL::Halfedge_around_target_iterator<Polyhedron> halfedge_around_target_iterator;
template <typename OutputIterator>
adjacent_vertices_V1(const Polyhedron& g,
vertex_descriptor vd,
{
typename GraphTraits::halfedge_descriptor hb = halfedge(vd,g), done(hb);
do {
*out++ = source(hb,g);
hb = opposite(next(hb,g),g);
} while(hb!= done);
return out;
}
template <typename OutputIterator>
adjacent_vertices_V2(const Polyhedron& g,
vertex_descriptor vd,
{
halfedge_around_target_iterator hi, he;
for(boost::tie(hi, he) = halfedges_around_target(halfedge(vd,g),g); hi != he; ++hi)
{
*out++ = source(*hi,g);
}
return out;
}
int main(int, char** argv)
{
std::ifstream in(argv[1]);
Polyhedron P;
in >> P;
GraphTraits::vertex_iterator vi = vertices(P).first;
std::list<vertex_descriptor> V;
adjacent_vertices_V1(P, *vi, std::back_inserter(V));
++vi;
adjacent_vertices_V2(P, *vi, std::back_inserter(V));
std::cerr << "done\n";
return 0;
}

Example: Calculating Facet Normals using HalfedgeGraph

The following example program shows a simple algorithm for calculating facet normals for a polyhedron using the Bgl API. A boost::vector_property_map is used to to store the calculated normals instead of changing the Polyhedron items class.


File BGL_polyhedron_3/normals.cpp

#include <fstream>
#include <boost/graph/graph_traits.hpp>
#include <CGAL/property_map.h>
#include <CGAL/basic.h>
#include <CGAL/Kernel/global_functions.h>
// Polyhedron
#include <CGAL/Cartesian.h>
#include <CGAL/Polyhedron_3.h>
#include <CGAL/IO/Polyhedron_iostream.h>
#include <CGAL/Polyhedron_items_with_id_3.h>
// Graph traits adaptors
#include <CGAL/boost/graph/graph_traits_Polyhedron_3.h>
typedef CGAL::Cartesian<double> Kernel;
typedef Kernel::Point_3 Point;
typedef Kernel::Vector_3 Vector;
template<typename HalfedgeGraph,
typename PointMap,
typename NormalMap>
void calculate_face_normals(const HalfedgeGraph& g,
PointMap pm,
NormalMap nm)
{
typedef boost::graph_traits<HalfedgeGraph> GraphTraits;
typedef typename GraphTraits::face_iterator face_iterator;
typedef typename GraphTraits::halfedge_descriptor halfedge_descriptor;
typedef typename boost::property_traits<PointMap>::value_type point;
typedef typename boost::property_traits<NormalMap>::value_type normal;
face_iterator fb, fe;
for(boost::tie(fb, fe) = faces(g); fb != fe; ++fb)
{
halfedge_descriptor edg = halfedge(*fb, g);
halfedge_descriptor edgb = edg;
point p0 = pm[target(edg, g)];
edg = next(edg, g);
point p1 = pm[target(edg, g)];
edg = next(edg, g);
point p2 = pm[target(edg, g)];
edg = next(edg, g);
if(edg == edgb) {
// triangle
nm[*fb] = CGAL::unit_normal(p1, p2, p0);
} else {
// not a triangle
normal n(CGAL::NULL_VECTOR);
do {
n = n + CGAL::normal(p1, p2, p0);
p0 = p1;
p1 = p2;
edg = next(edg, g);
p2 = pm[target(edg, g)];
} while(edg != edgb);
nm[*fb] = n / CGAL::sqrt(n.squared_length());
}
}
}
int main(int, char** argv)
{
typedef boost::property_map<
Polyhedron,
>::const_type Face_index_map;
std::ifstream in(argv[1]);
Polyhedron P;
in >> P ;
// initialize facet indices
std::size_t i = 0;
for(Polyhedron::Facet_iterator it = P.facets_begin(); it != P.facets_end(); ++it, ++i)
{
it->id() = i;
}
// Ad hoc property_map to store normals. Face_index_map is used to
// map face_descriptors to a contiguous range of indices. See
// http://www.boost.org/libs/property_map/doc/vector_property_map.html
// for details.
boost::vector_property_map<Vector, Face_index_map>
normals(get(CGAL::face_index, P));
calculate_face_normals(
P // Graph
, get(CGAL::vertex_point, P) // map from vertex_descriptor to point
, normals // map from face_descriptor to Vector_3
);
std::cout << "Normals" << std::endl;
for(Polyhedron::Facet_iterator it = P.facets_begin(); it != P.facets_end(); ++it) {
// Facet_iterator is a face_descriptor, so we can use it as the
// key here
std::cout << normals[it] << std::endl;
}
return 0;
}