CGAL 6.0  CGAL and the Boost Graph Library

We extend the Boost Graph Library (BGL for short) with a set of new concepts.
In order to make this documentation selfcontained we here also document concepts that are defined in the original version of the BGL. The documentation of the concepts lists at the same time the functions related to it. Models of the concept and their related functions must be in the same namespace (they will be found by Koenig lookup).
Notations
G
g
G
. u
, v
boost::graph_traits<G>::vertex_descriptor
. h
boost::graph_traits<G>::halfedge_descriptor
. e
boost::graph_traits<G>::edge_descriptor
. f
boost::graph_traits<G>::face_descriptor
. VertexListGraph
The concept VertexListGraph
refines the concept Graph
and adds the requirement for traversal of all vertices in a graph.
Associated Type  Description 

boost::graph_traits<G>::vertex_iterator  Iterator over all vertices 
boost::graph_traits<G>::vertices_size_type  Unsigned integer type for number of vertices 
Valid Expression  Return Type  Description 

vertices(g)  std::pair<vertex_iterator, vertex_iterator>  An iterator range over all vertices 
num_vertices(g)  vertices_size_type  An upper bound of the number of vertices of the graph 
EdgeListGraph
The concept EdgeListGraph
refines the concept Graph
and adds the requirement for traversal of all edges in a graph.
Associated Type  Description 

boost::graph_traits<G>::edge_iterator  Iterator over all edges 
boost::graph_traits<G>::edges_size_type  Unsigned integer type for number of edges 
Valid Expression  Return Type  Description 

edges(g)  std::pair<edge_iterator, edge_iterator>  An iterator range over all edges 
num_edges(g)  edges_size_type  An upper bound of the number of edges of the graph 
source(e, g)  vertex_descriptor  The source vertex of e 
target(e, g)  vertex_descriptor  The target vertex of e 
HalfedgeGraph
The concept HalfedgeGraph
refines the concept Graph
and adds the notion of halfedges, where each edge corresponds to two opposite halfedges.
Associated Type  Description 

boost::graph_traits<G>::halfedge_descriptor  A halfedge_descriptor corresponds to a halfedge in a graph. Must be DefaultConstructible , Assignable , EqualityComparable and LessThanComparable 
Valid Expression  Return Type  Description 

edge(h, g)  edge_descriptor  The edge corresponding to the halfedges h and opposite(h) 
halfedge(e, g)  halfedge_descriptor  One of the halfedges corresponding to the edge e 
halfedge(v, g)  halfedge_descriptor  A halfedge with target the vertex v 
halfedge(u, v, g)  std::pair<halfedge_descriptor, bool>  The halfedge with source u and target v . The Boolean is true , iff this halfedge exists 
opposite(h, g)  halfedge_descriptor  The halfedge with source and target swapped 
source(h, g)  vertex_descriptor  The source vertex of h 
target(h, g)  vertex_descriptor  The target vertex of h 
next(h, g)  halfedge_descriptor  The next halfedge around its face 
prev(h, g)  halfedge_descriptor  The previous halfedge around its face 
boost::graph_traits<G>::null_halfedge()  halfedge_descriptor  Returns a special halfedge that is not equal to any other halfedge 
The HalfedgeGraph
has the invariant halfedge(edge(h,g))==h
.
MutableHalfedgeGraph
The concept MutableHalfedgeGraph
refines the concept HalfedgeGraph
and adds the requirements for operations to add vertices and edges, and to update the incidence information between vertices and halfedges.
Valid Expression  Return Type  Description 

add_vertex(g)  vertex_descriptor  Adds a new vertex to the graph without initializing the connectivity 
remove_vertex(v, g)  void  Removes the vertex v from the graph 
add_edge(g)  edge_descriptor  Adds two opposite halfedges to the graph without initializing their connectivity 
remove_edge(e, g)  void  Removes the two halfedges corresponding to the edge e from the graph 
set_target(h, v, g)  void  Sets the target vertex of the halfedge h and the source of opposite(h) to the vertex v 
set_halfedge(v, h, g)  void  Sets the halfedge of the vertex v to h . The target vertex of h must be v 
set_next(h1, h2, g)  void  Sets the successor of h1 around a face to h2 , and the prededecessor of h2 to h1 
HalfedgeListGraph
The concept HalfedgeListGraph
refines the concept HalfedgeGraph
and adds the requirements for traversal of all halfedges in the graph.
Associated Type  Description 

boost::graph_traits<G>::halfedge_iterator  A BidirectionalIterator over all halfedges in a graph. Must be DefaultConstructible , Assignable , EqualityComparable 
boost::graph_traits<G>::halfedges_size_type  Unsigned integer type for number of halfedges 
Valid Expression  Return Type  Description 

halfedges(g)  std::pair<halfedge_iterator, halfedge_iterator>  An iterator range over all halfedges 
num_halfedges(g)  halfedges_size_type  An upper bound of the number of halfedges of the graph 
FaceGraph
The concept FaceGraph
refines the concept HalfedgeGraph
. It adds the requirements for a graph to explicitly maintain faces described by halfedges, to provide access from a face to an incident halfedge, and to provide access from a halfedge to its incident face.
Associated Type  Description 

boost::graph_traits<G>::face_descriptor  A face_descriptor corresponds to a unique face in a graph. Must be DefaultConstructible , Assignable , EqualityComparable and LessThanComparable 
Valid Expression  Return Type  Description 

face(h, g)  face_descriptor  The face incident to halfedge h 
halfedge(f, g)  halfedge_descriptor  A halfedge incident to face f 
degree(f, g)  degree_size_type  The number of halfedges incident to face f 
boost::graph_traits<G>::null_face()  face_descriptor  A special face that is not equal to any other face 
MutableFaceGraph
The concept MutableFaceGraph
refines the concepts FaceGraph
and MutableHalfedgeGraph
and adds the requirement for operations to add faces and to modify facehalfedge relations.
Valid Expression  Return Type  Description 

add_face(g)  face_descriptor  Adds a new face to the graph without initializing the connectivity 
remove_face(f, g)  void  Removes f from the graph 
set_face(h, f, g)  void  Sets the corresponding face of h to f 
set_halfedge(f, h, g)  void  Sets the corresponding halfedge of f to h 
reserve(g, nv, ne, nf)  void  Called to indicate the expected size of vertices (nv ), edges (ed ) and faces (nf ) 
FaceListGraph
The concept FaceListGraph
refines the concept FaceGraph
and adds the requirement for traversal of all faces in a graph.
Associated Type  Description 

boost::graph_traits<G>::face_iterator  Iterator over all faces 
boost::graph_traits<G>::faces_size_type  Unsigned integer type for number of faces 
Valid Expression  Return Type  Description 

faces(g)  std::pair<face_iterator, face_iterator>  An iterator range over all faces 
num_faces(g)  faces_size_type  An upper bound of the number of faces of the graph 
Concepts  
concept  EdgeListGraph 
Concept from the Boost Graph Library. See https://www.boost.org/libs/graph/doc/EdgeListGraph.html. More...  
concept  FaceGraph 
The concept FaceGraph refines the concept HalfedgeGraph . It adds the requirements for a graph to explicitly maintain faces described by halfedges, to provide access from a face to an incident halfedge, and to provide access from a halfedge to its incident face. More...  
concept  FaceListGraph 
The concept FaceListGraph refines the concept FaceGraph and adds the requirement for traversal of all faces in a graph. More...  
concept  HalfedgeGraph 
The concept HalfedgeGraph is a refinement of the BGL concept IncidenceGraph and adds the notion of a halfedge: Each edge is associated with two opposite halfedges with source and target vertices swapped. Furthermore, halfedges have a successor and predecessor, and form cycles we call faces. However, this concept does not introduce a face type. A HalfedgeGraph is undirected and does not allow parallel edges. More...  
concept  HalfedgeListGraph 
The concept HalfedgeListGraph refines the concept HalfedgeGraph and adds the requirements for traversal of all halfedges in the graph. More...  
concept  MutableFaceGraph 
The concept MutableFaceGraph refines the concepts FaceGraph and MutableHalfedgeGraph and adds the requirement for operations to add faces and to modify facehalfedge relations. More...  
concept  MutableHalfedgeGraph 
The concept MutableHalfedgeGraph refines the concept HalfedgeGraph and adds the requirements for operations to add vertices and edges, and to update the incidence information between vertices and halfedges. More...  
concept  VertexListGraph 
Concept from the Boost Graph Library. See https://www.boost.org/libs/graph/doc/VertexListGraph.html. More...  