CGAL 6.1 - CGAL and the Boost Graph Library

Loading...
Searching...
No Matches
Classes
Concepts
Reference Manual

##

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).

Notations

`G`
  A type that is a model of a graph concept.
`g`
  An object of type `G`.
`u`, `v`
  Objects 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 | 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 face-halfedge 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 face-halfedge 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...