\( \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.5 - CGAL and the Boost Graph Library
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
HalfedgeGraph Concept Reference


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.

Using the composition of the successor and opposite functions results in another cycle, namely the cycle of halfedges which are incident to the same vertex. We refer to Iterators and Circulators for a description of iterators and circulators for these halfedge cycles.




A model of HalfedgeGraph must have the interior property vertex_point attached to its vertices.

Has Models:


A type that is a model of HalfedgeGraph.
An object of type G.
u, v
Vertex descriptors.
An edge descriptor.
A halfedge descriptor.

Associated Types

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 Expressions

Expression Returns Description
edge(h, g) edge_descriptor The edge corresponding to 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.