Concepts

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