CGAL 4.7 - CGAL and the Boost Graph Library: HalfedgeGraph Concept Reference

\( \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.7 - CGAL and the Boost Graph Library

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
HalfedgeGraph Concept Reference
Concepts

## Definition

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.

Refines:

  `Graph`

  `PropertyGraph`

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

Has Models:

  `CGAL::Polyhedron_3`

  `CGAL::Surface_mesh`

Notations

`G`
  A type that is a model of `HalfedgeGraph`.
`g`
  An object of type `G`.
`u`, `v`
  Vertex descriptors.
`e`
  An edge descriptor.
`h`
  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.
`boost::graph_traits<G>::null_halfedge()` | `halfedge_descriptor` | Returns a special halfedge that is not equal to any other halfedge.

Examples:
  BGL_polyhedron_3/normals.cpp.