4.1. Compute Reeb Graph from Lower Star Filtration

The computeReeb module provides functionality to compute the Reeb graph from a lower star filtration. Information on the lower star filtration can be found in the Lower Star Filtration for Simplicial Complexes documentation.

cereeberus.compute.computereeb.computeReeb(K, verbose=False, *, set_pos=True, validate=True, keep_regular_nodes=False)[source]

Compute the Reeb graph of a lower-star filtered simplicial complex.

The function on the complex is the piecewise-linear extension of the values assigned to its vertices. The complex can have any dimension and need not be a manifold: boundaries, edges shared by three or more triangles, and singular vertices are all allowed.

By default the returned graph contains only the nodes where the topology of the level sets changes (minima, maxima, merges and splits), plus isolated components. Pass keep_regular_nodes=True to also get a node for every level-set component at every vertex height, with a midpoint node on each edge between them.

Parameters:

  • K (LowerStar) – The filtered complex. Only the values on the vertices are used; the filtration of every other simplex must be the maximum of its vertex values (this is what LowerStar maintains).

  • verbose (bool, default=False) – Print progress every 1000 vertex heights.

  • set_pos (bool, default=True) – Compute node positions once at the end, so the result can be drawn with ReebGraph.draw() immediately. Set to False to skip the layout when only the graph itself is needed, for example in batch jobs on large complexes.

  • validate (bool, default=True) – Check that every simplex’s filtration equals the maximum of its vertex values. Vertex values are always checked to be finite. Set to False to skip this check on large complexes that are known to be valid.

  • keep_regular_nodes (bool, default=False) – If True, keep one node for every level-set component at every vertex height, and add a midpoint node named "e_0", "e_1", … on each edge between consecutive heights. This is the output format of cereeberus 0.1.20 and earlier. If False, those nodes (one edge in, one edge out) are left out, which gives the same Reeb graph up to subdivision with far fewer nodes.

Returns:

The Reeb graph. Edges point from the lower to the higher function value, and parallel edges (loops) are kept. By default, nodes are named 0, 1, 2, ... and their function values are vertex values.

Return type:

ReebGraph

Raises:

  • TypeError – If K is not a LowerStar.

  • ValueError – If a vertex value is not finite, the lower-star condition fails (with validate=True), the complex is malformed, or, with keep_regular_nodes=True, no floating-point number lies strictly between two consecutive vertex values.

Notes

The algorithm sweeps upward through the distinct vertex values. At each value it computes the connected components of the level set with a union-find over the vertices at that height and the edges crossing it; it does the same for one level strictly between consecutive values. Each component between two values becomes an edge, attached to the unique components it meets at the values above and below.

Each triangle meets a level set in a convex (hence connected) set, so joining the points where a level crosses a triangle’s boundary gives exactly the level-set components. Only vertices, edges and triangles are needed, even for higher-dimensional input: a level set of any simplex is a convex polytope whose edges lie in the sliced triangles.

Equal vertex values are treated as exact ties (flat regions); no tolerance is applied, so round values yourself first if you want nearby values treated as equal. The result is the Reeb graph of the abstract complex given; for meshes, duplicated vertices (for example along texture seams) should be merged before building K.

Examples

>>> from cereeberus import LowerStar, computeReeb
>>> K = LowerStar()
>>> K.insert([0, 1, 2])
True
>>> K.insert([1, 3])
True
>>> K.insert([2, 3])
True
>>> K.assign_filtration([0], 0.0)
>>> K.assign_filtration([1], 3.0)
>>> K.assign_filtration([2], 5.0)
>>> K.assign_filtration([3], 7)
>>> R = computeReeb(K)
>>> R.number_of_nodes(), R.number_of_edges()
(3, 3)
>>> R.draw()

To get the subdivided output (the format of cereeberus 0.1.20):

>>> R_full = computeReeb(K, keep_regular_nodes=True)
>>> R_full.number_of_nodes(), R_full.number_of_edges()
(10, 10)