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

Properties

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.

Helper Classes

Helper Functions

Iterators

Circulators

Euler Operations

Selection

Conversion Functions

CGAL::split_graph_into_polylines()

Graph Adaptors

Partitioning Methods

I/O Functions

Modules
	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.

	Named Parameters
	The algorithms of the Boost Graph Library (Bgl) often have many parameters with default values that are appropriate for most cases.

	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`.

	Dynamic Properties
	The dynamic property tags enable to associate information to simplices of a `FaceGraph` on the fly.

	External Indices
	A number of BGL and CGAL algorithms require the graph to have (initialized) integer-like indices for its vertices, edges, or faces.

	Helper Functions
	Generic convenience functions for testing if an edge is a border edge, if a mesh is triangular, for conversion between models of different `FaceGraph` concepts, etc.

	Iterators and Circulators
	Several iterators and circulators are provided that enable, for example, to iterate through the halfedges incident to a given face or vertex.

	Selection Functions
	Several functions to enlarge or reduce a k-ring selection of vertices, edges, or faces.

	Graph Adaptors
	Graph adaptors are classes that build an interface over an existing graph to provide new functionalities.

	Euler Operations
	We call high level operations that maintain the validity of a halfedge graph Euler Operations.

	Partitioning Operations
	Methods to split a mesh into subdomains, using the library METIS or a graphcut implementation.

	I/O Functions
	Methods to read and write graphs.

Files
file	partition.h
	Convenience header file including the headers for all the partitioning-related free functions of this package.

file	graph_traits_inheritance_macros.h
	Convenience header file defining the necessary specializations and overloads to make a class, inheriting from a model of a face graph concept, a model of that face graph concept itself.

Functions
template<typename Graph , typename Visitor , typename IsTerminal >
void	CGAL::split_graph_into_polylines (const Graph &graph, Visitor &polyline_visitor, IsTerminal is_terminal)
	splits into polylines the graph `g` at vertices of degree greater than 2 and at vertices for which `is_terminal(v,graph)==true`. More...

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.

Examples:: Surface_mesh_skeletonization/simple_mcfskel_example.cpp.