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-21b
License: LGPL

Classified Reference Pages

Concepts

• VertexListGraph
• EdgeListGraph
• HalfedgeGraph
• HalfedgeListGraph
• MutableHalfedgeGraph
• FaceGraph
• FaceListGraph
• MutableFaceGraph

Properties

• CGAL::vertex_index_t
• CGAL::halfedge_index_t
• CGAL::edge_index_t
• CGAL::face_index_t
• CGAL::vertex_point_t

CGAL Classes Adapted for the Graph API

A number of CGAL structures 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::Linear_cell_complex_for_combinatorial_map<...> >
• boost::graph_traits<CGAL::Seam_mesh<T> >
• boost::graph_traits<CGAL::Triangulation_2<GT, TDS> > and other 2D triangulations
• boost::graph_traits<CGAL::Arrangement_2<T, DC> >
• boost::graph_traits<OpenMesh::PolyMesh_ArrayKernelT<K> >
• boost::graph_traits<OpenMesh::TriMesh_ArrayKernelT<K> >

Helper Classes

• CGAL::Triangulation_vertex_base_with_id_2
• CGAL::Triangulation_face_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
• CGAL::set_halfedgeds_items_id()
• CGAL::Linear_cell_complex_bgl_min_items
• CGAL::Linear_cell_complex_for_bgl_combinatorial_map_helper

Helper Functions

• CGAL::is_border()
• CGAL::is_border_edge()
• CGAL::is_bivalent()
• CGAL::is_bivalent_mesh()
• CGAL::is_trivalent()
• CGAL::is_trivalent_mesh()
• CGAL::is_isolated_triangle()
• CGAL::is_closed()
• CGAL::is_triangle()
• CGAL::is_triangle_mesh()
• CGAL::is_quad()
• CGAL::is_quad_mesh()
• CGAL::is_isolated_quad()
• CGAL::is_valid_halfedge_graph()
• CGAL::is_valid_face_graph()
• CGAL::is_valid_polygon_mesh()
• CGAL::is_tetrahedron()
• CGAL::is_hexahedron()
• CGAL::make_triangle()
• CGAL::make_tetrahedron()
• CGAL::make_quad()
• CGAL::make_hexahedron()
• CGAL::make_icosahedron()
• CGAL::make_regular_prism()
• CGAL::make_pyramid()
• CGAL::make_grid()
• CGAL::clear()
• CGAL::copy_face_graph()
• CGAL::set_triangulation_ids()

Iterators

• CGAL::Halfedge_around_source_iterator
• CGAL::Halfedge_around_target_iterator
• CGAL::Halfedge_around_face_iterator
• CGAL::Vertex_around_target_iterator
• CGAL::Vertex_around_face_iterator
• CGAL::Face_around_face_iterator
• CGAL::Face_around_target_iterator
• CGAL::halfedges_around_source()
• CGAL::halfedges_around_target()
• CGAL::halfedges_around_face()
• CGAL::faces_around_face()
• CGAL::faces_around_target()
• CGAL::vertices_around_face()
• CGAL::vertices_around_target()

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
• CGAL::Face_around_face_circulator

Euler Operations

• CGAL::Euler::add_center_vertex()
• CGAL::Euler::add_edge()
• CGAL::Euler::add_face()
• CGAL::Euler::add_face_to_border()
• CGAL::Euler::add_vertex_and_face_to_border()
• CGAL::Euler::collapse_edge()
• CGAL::Euler::does_satisfy_link_condition()
• CGAL::Euler::fill_hole()
• CGAL::Euler::flip_edge()
• CGAL::Euler::join_face()
• CGAL::Euler::join_loop()
• CGAL::Euler::join_vertex()
• CGAL::Euler::make_hole()
• CGAL::Euler::remove_center_vertex()
• CGAL::Euler::remove_face()
• CGAL::Euler::split_edge()
• CGAL::Euler::split_face()
• CGAL::Euler::split_loop()
• CGAL::Euler::split_vertex()

Selection

• CGAL::expand_face_selection()
• CGAL::reduce_face_selection()
• CGAL::expand_edge_selection()
• CGAL::reduce_edge_selection()
• CGAL::expand_vertex_selection()
• CGAL::reduce_vertex_selection()
• CGAL::select_incident_faces()
• CGAL::expand_face_selection_for_removal()
• CGAL::regularize_face_selection_borders()

Conversion Functions

• CGAL::split_graph_into_polylines()

Graph Adaptors

• CGAL::Dual
• CGAL::Face_filtered_graph
• CGAL::Graph_with_descriptor_with_graph
• CGAL::Graph_with_descriptor_with_graph_property_map
• CGAL::Seam_mesh

Partitioning Methods

• CGAL::METIS::partition_graph()
• CGAL::METIS::partition_dual_graph()
• CGAL::alpha_expansion_graphcut()

I/O Functions

• CGAL::read_off()
• CGAL::write_off()
• CGAL::write_wrl()
• CGAL::write_vtp()

Modules
	Specializations of boost::graph_traits
	BGL Named Parameters
	Concepts
	Properties
	The property tags model of the boost concept PropertyTag.
	Dynamic Properties
	External Indices
	Helper Functions
	Iterators and Circulators
	Selection Functions
	Graph Adaptors
	Euler Operations
	Partitioning Operations
	I/O Functions

Files
file	partition.h

Functions
template<typename Graph , typename Visitor , typename IsTerminal >
void	CGAL::split_graph_into_polylines (const Graph &graph, Visitor &polyline_visitor, IsTerminal is_terminal)

Function Documentation

split_graph_into_polylines()

template<typename Graph , typename Visitor , typename IsTerminal >

void CGAL::split_graph_into_polylines	(	const Graph &	graph,
		Visitor &	polyline_visitor,
		IsTerminal	is_terminal
	)

#include <CGAL/boost/graph/split_graph_into_polylines.h>

splits into polylines the graph g at vertices of degree greater than 2 and at vertices for which is_terminal(v,graph)==true. The polylines are reported using a visitor.

Template Parameters

Graph	a model of the boost concepts VertexListGraph and EdgeListGraph.
Visitor	a class that provides: void start_new_polyline() called when starting the description of a polyline. void add_node(typename boost::graph_traits<Graph>::vertex_descriptor v) called for each vertex v of the polyline currently described. If the polyline is closed this function will be called twice for the first vertex of the cycle picked (once after calling start_new_polyline() and once before the call to end_polyline(). void end_polyline() called when the description of a polyline is finished.
IsTerminal	A functor providing bool operator()(boost::graph_traits<Graph>::vertex_descriptor v, const Graph& g) const returning true if the vertex v of degree 2 is a polyline endpoint and false otherwise.

An overload without is_terminal is provided if no vertices but those of degree different from 2 are polyline endpoints.

Todo:

Document the version with four parameters

Examples

Surface_mesh_skeletonization/simple_mcfskel_example.cpp.