CGAL 6.1 - CGAL and the Boost Graph Library

Loading...
Searching...
No Matches
Modules | Files
Reference Manual

##

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-25b
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<K> >`
- `boost::graph_traits<CGAL::Linear_cell_complex_for_combinatorial_map<...> >`
- `boost::graph_traits< CGAL::Seam_mesh<G> >`
- `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()`

## Generator Functions

- `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::remove_all_elements()`
- `CGAL::copy_face_graph()`
- `CGAL::set_triangulation_ids()`
- `CGAL::parameters::default_values()`

## 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::Vertex_around_face_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_degree_2_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 Traversal

- `CGAL::dijkstra_shortest_path()`

## 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`
- `CGAL/boost/graph/graph_traits_inheritance_macros.h`

## Partitioning Methods

- `CGAL::METIS::partition_graph()`
- `CGAL::METIS::partition_dual_graph()`
- `CGAL::alpha_expansion_graphcut()`

## I/O Functions

- `CGAL::IO::read_polygon_mesh()`
- `CGAL::IO::write_polygon_mesh()`
- I/O for STL files
- I/O for PLY files
- I/O for OBJ files
- I/O for OFF files
- I/O for GOCAD files
- I/O for VTP files
- I/O for 3MF files
- I/O for WRL files

## 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.
| Generator Functions
| 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.
| Graph Traversal
| Methods to traverse a graph, for example to find the shortest path between two vertices.
| I/O Functions
| Methods to read and write graphs.

## Files
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.