CellIncidenceGraphHelpers

Diagram reference: CGAL and BGL concepts diagram

Introduction to helpers of CellIncidenceGraph

Helpers of the CellIncidenceGraph offers a cell-mesh oriented conceptual re-interpretation of the CellIncidenceGraph concept. A low level description would be to consider the helpers as an interface for cell mesh programmers using a data structure which topology is expressed through the CellIncidenceGraph concept.

The CellIncidenceGraphHelpers concept regroups two concerns

topology related expressions that can be derived from the CellIncidenceGraph concept. Such expressions can be generically implemented out of expressions of CellIncidenceGraph.
cell-mesh oriented concerns, like providing vertex, edge, face, volume functionality.

CellIncidenceGraphHelpers expressions will be used in cell-mesh oriented context whereas CellIncidenceGraph expressions will tend be used in a context wishing to modify a topology.

Note that the semantics associated to vertex_descriptor differ between the CellIncidenceGraph and CellIncidenceGraphHelpers concepts:

within the CellIncidenceGraph concept a vertex_descriptor represents a node and suffice to work on the topological structure.
within the CellIncidenceGraphHelpers concept a vertex_descriptor represents a vertex of a cell-mesh i.e. a zero dimensionnal geometrical object. Yet in order to access the represented vertex out a vertex_descriptor one needs an associative data structure which only purpose is to encode this correspondance. Within CGAL, for example, such an associative mean can be a property map (most often internal) for CGAL::vertex_point_t i.e. a property map with the points (geometrical vertices) associated to the nodes (identified with their vertex_descriptor) of CellIncidenceGraph (refer e.g. to CGAL::Polygon_mesh_processing::compute_face_normal() method).

Notations

G A type that is a model of CellIncidenceGraphHelpers.
g An object of type G.
u,v Vertex descriptors.
e An edge descriptor.
f A face descriptor.

Associated types

Type	Reference	Description
`boost::graph_traits<G>::vertex_descriptor`	Graph (boost)	A vertex descriptor corresponds to a unique vertex in a graph instance. A vertex descriptor must be Default Constructible, Assignable, and Equality Comparable.
`boost::graph_traits<G>::vertex_iterator`	VertexListGraph (boost)	A vertex iterator (obtained via `vertices(g)`) provides access to all of the vertices in a graph. A vertex iterator type must meet the requirements of MultiPassInputIterator. The value type of the vertex iterator must be the vertex descriptor of the graph.
`boost::graph_traits<G>::edge_descriptor`	Graph (boost)	An edge descriptor corresponds to a unique edge `(u,v)` in a graph. An edge descriptor must be Default Constructible, Assignable, and Equality Comparable.
`boost::graph_traits<G>::edge_iterator`	EdgeListGraph (boot)	An edge iterator (obtained via `edges(g)`) provides access to all of the edges in a graph. An edge iterator type must meet the requirements of MultiPassInputIterator. The value type of the edge iterator must be the same as the edge descriptor of the graph.
`boost::graph_traits<G>::face_descriptor`	FaceListGraph (boost)	A face_descriptor corresponds to a unique face in a graph. Must be DefaultConstructible, Assignable, EqualityComparable and LessThanComparable.
`boost::graph_traits<G>::face_iterator`	FaceListGraph (boost)	Iterator over all faces.

Valid expressions

Expression	Reference	Returns	Description
Local traversals
`next(u, v, f, g)`	Inspired by `next(h, g)` of HalfedgeGraph (CGAL)	`edge_descriptor`	Returns the "next" (that is other from `(u,v)`) edge in the face `f` which is incident to `v` in graph `g`. Note: if `vertices(f,g)` and/or `edges(f,g)` get implemented they should be syntactic sugar on top of this `next()`.
`prev(u, v, f, g)`	Inspired by `prev(h, g)` of HalfedgeGraph (CGAL)	`edge_descriptor`	Returns the "previous" (that is other from `(u,v)`) edge in the face `f` which is incident to `u` in graph `g`.
`adjacent_vertices(v,g)`	AdjacencyGraph (boost)	`std::pair<adjacency_iterator, adjacency_iterator>`	Returns an iterator-range providing access to the vertices adjacent to vertex `v` in graph `g`.
Global traversals
`vertices(g)`	VertexListGraph (boost)	`std::pair<vertex_iterator, vertex_iterator>`	Returns an iterator-range providing access to all the vertices in the graph `g`.
`edges(g)`	EdgeListGraph (boot)	`std::pair<edge_iterator, edge_iterator>`	Returns an iterator-range providing access to all the edges in the graph `g`.
`faces(g)`	FaceListGraph (CGAL)	`std::pair<face_iterator, face_iterator>`	An iterator range over all faces.
`num_vertices(g)`	VertexListGraph (boost)	`vertices_size_type`	Returns the number of vertices in the graph `g`.
`num_edges(g)`	EdgeListGraph (boot)	`edges_size_type`	Returns the number of edges in the graph `g`.
`num_faces(g)`	FaceListGraph (CGAL)	`faces_size_type`	Returns the number of faces in the graph `g`.

The following are scheduled for removal:

Expression	Reference	Returns	Description
`add_face(g)`	CGAL::Surface_mesh defines an `Face_index add_face()`
`remove_face(f,g)`	CGAL::Surface_mesh defines a `void remove_face (Face_index f)`

Design notes:

Although foreseen at some point the next(v, e, g) and prev(v, e, g) expresssions were eventually disregarded since their result can be obtained through other means.
remove_out_edge_if(u, p, g) and remove_out_edge_if(u, p, g) (mutability) were droped because edges are non oriented.
There is little semantical advantage in distinguishing the vertices_size_type, edges_size_type and faces_size_type types. Additionnally the associated values will be of the same order of magnitude (hence there is little hope in reducing the memory footprint through this distinction).

This documentation generated from CellIncidenceGraphConcept.dox file.

Following diagram to be removed when work is finished.