CGAL and the Boost Graph Library Reference

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

This package provides a framework for interfacing CGAL data structures with the algorithms of the Boost Graph Library, or BGL for short. It allows to run graph algorithms directly on CGAL data structures which are model of the BGL graph concepts, for example the shortest path algorithm on a Delaunay triangulation in order to compute the Euclidean minimum spanning tree. Furthermore, it introduces several new graph concepts describing halfedge data structures.

Introduced in: CGAL 3.3
BibTeX: cgal:cfw-cbgl-15b
License: LGPL

Classified Reference Pages

Concepts

• HalfedgeGraph
• HalfedgeListGraph
• MutableHalfedgeGraph
• FaceGraph
• FaceListGraph
• MutableFaceGraph

Properties

• boost::vertex_index_t
• boost::halfedge_index_t
• boost::edge_index_t
• boost::face_index_t
• boost::vertex_point_t

CGAL Classes Adapted for the Graph API

Different CGAL types have been adapted as graphs for the Bgl. All adapted types are listed here. The pages document which concepts they model, the properties they support, and any possible caveats that a user might encounter.

• boost::graph_traits< CGAL::Surface_mesh<P> >
• boost::graph_traits< CGAL::Polyhedron_3<T> >
• boost::graph_traits< CGAL::Triangulation_2<GT, TDS> >
• boost::graph_traits< CGAL::Arrangement_2<T,DC> >

Helper Classes

• CGAL::Triangulation_vertex_base_with_id_2
• CGAL::Arr_vertex_index_map
• CGAL::Arr_face_index_map
• CGAL::HalfedgeDS_vertex_max_base_with_id
• CGAL::HalfedgeDS_halfedge_max_base_with_id
• CGAL::HalfedgeDS_face_max_base_with_id
• CGAL::Polyhedron_items_with_id_3

Iterators

• CGAL::Halfedge_around_source_iterator
• CGAL::Halfedge_around_target_iterator
• CGAL::Halfedge_around_face_iterator
• CGAL::Vertex_around_target_iterator
• CGAL::Face_around_target_iterator
• CGAL::halfedges_around_source
• CGAL::halfedges_around_target
• CGAL::halfedges_around_face

Circulators

• CGAL::Halfedge_around_source_circulator
• CGAL::Halfedge_around_target_circulator
• CGAL::Halfedge_around_face_circulator
• CGAL::Vertex_around_target_circulator
• CGAL::Face_around_target_circulator

Euler Operations

• CGAL::Euler::join_vertex()
• CGAL::Euler::split_vertex()
• CGAL::Euler::split_edge()
• CGAL::Euler::join_face()
• CGAL::Euler::split_face()
• CGAL::Euler::join_loop()
• CGAL::Euler::split_loop()
• CGAL::Euler::remove_face()
• CGAL::Euler::make_hole()
• CGAL::Euler::add_center_vertex()
• CGAL::Euler::remove_center_vertex()
• CGAL::Euler::add_vertex_and_face_to_border()
• CGAL::Euler::add_face_to_border()
• CGAL::Euler::collapse_edge()
• CGAL::Euler::satisfies_link_condition()

Modules
	Specializations of boost::graph_traits
	Bgl defines the class template boost::graph_traits as a uniform interface to the properties and types of graph types.
	Concepts
	We extend the Boost Graph Library(Bgl for short) with a set of new concepts.
	Properties
	The property tags model of the boost concept PropertyTag.
	Helper Classes
	Iterators and Circulators
	Several iterators and circulators are provided that enable to iterate through the halfedges incident to a given face or vertex.
	Euler Operations
	We call high level operations that maintain the validity of a halfedge graph Euler Operations.