\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.11.2 - CGAL and the Boost Graph Library
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages

We extend the Boost Graph Library (Bgl for short) with a set of new concepts.

In order to make this documentation self-contained 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).

dot_inline_dotgraph_1.png

Notations

G
A type that is a model of a graph concept.
g
An object of type G.
u, v
An object of type boost::graph_traits<G>::vertex_descriptor.
h
An object of type boost::graph_traits<G>::halfedge_descriptor.
e
An object of type boost::graph_traits<G>::edge_descriptor.
f
An object of type 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 returns 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 returns 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 Returns Description
edge(h, g) edge_descriptor The edge corresponding to halfedges h and opposite(h).
halfedge(e, g) halfedge_descriptor One of the halfedges corresponding to e.
halfedge(v, g) halfedge_descriptor A halfedge with target 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 returns Description
add_vertex(g) vertex_descriptor Adds a new vertex to the graph without initializing the connectivity.
remove_vertex(v, g) void Removes v from the graph.
add_edge(g) edge_descriptor Adds two opposite halfedges to the graph without initializing the connectivity.
remove_edge(e, g) void Removes the two halfedges corresponding to e from the graph.
set_target(h, v, g) void Sets the target vertex of h and the source of opposite(h) to v.
set_halfedge(v, h, g) void Sets the halfedge of 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 A size type.
Valid Expression Returns Description
num_halfedges(g) halfedges_size_type An upper bound of the number of halfedges of the graph.
halfedges(g) std::pair<halfedge_iterator,halfedge_iterator> An iterator range over the 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 Returns 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 face-halfedge relations.

Valid Expression returns 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 returns 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

conceptEdgeListGraph
 The concept EdgeListGraph refines the concept Graph and adds the requirement for traversal of all edges in a graph. More...
 
conceptFaceGraph
 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...
 
conceptFaceListGraph
 The concept FaceListGraph refines the concept FaceGraph and adds the requirement for traversal of all faces in a graph. More...
 
conceptHalfedgeGraph
 The concept HalfedgeGraph is a refinement of the Bgl concept Graph 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...
 
conceptHalfedgeListGraph
 The concept HalfedgeListGraph refines the concept HalfedgeGraph and adds the requirements for traversal of all halfedges in the graph. More...
 
conceptMutableFaceGraph
 The concept MutableFaceGraph refines the concepts FaceGraph and MutableHalfedgeGraph and adds the requirement for operations to add faces and to modify face-halfedge relations. More...
 
conceptMutableHalfedgeGraph
 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...
 
conceptVertexListGraph
 The concept VertexListGraph refines the concept Graph and adds the requirement for traversal of all vertices in a graph. More...