1.6. BranchDecomp class

The BranchDecomp class computes and stores a branch decomposition of a Reeb graph.

For a worked example, see the branch decomposition tutorial.

This implementation and tutorial are based in part on the branch decomposition and unsmoothing perspective developed in Samira Jabry’s thesis: Unsmoothing of Reeb Graphs, Saint Louis University, 2025. Available via ProQuest at https://www.proquest.com/dissertations-theses/unsmoothing-reeb-graphs/docview/3231769569/se-2.

A branch decomposition breaks a Reeb graph into a collection of non-overlapping upward paths called branches. Each branch travels strictly upward in function value, starting at either a local minimum or a saddle point and ending at either a local maximum or another saddle point. The decomposition also records how branch endpoints attach to previously-computed branches, allowing the original Reeb graph to be fully reconstructed.

The decomposition can be computed either directly via this class, or via the convenience method on the Reeb graph:

import cereeberus
import cereeberus.data.ex_reebgraphs as ex_rg
from cereeberus.reeb.branchdecomp import BranchDecomp

R = ex_rg.dancing_man()

# Option 1: via the ReebGraph method
bd = R.branch_decomp()

# Option 2: directly
bd = BranchDecomp()
bd.decompose(R)

# Visualise the decomposition alongside the original graph
import matplotlib.pyplot as plt
fig, axes = plt.subplots(1, 2, figsize=(14, 6))
R.draw(ax=axes[0])
bd.draw(ax=axes[1])

# Reconstruct the original graph
R2 = bd.reconstruct()

class cereeberus.reeb.branchdecomp.BranchDecomp

A branch decomposition of a Reeb graph.

A branch decomposition breaks a Reeb graph into a collection of non-overlapping upward paths called branches. Each branch is a path that travels strictly upward in function value, starting at either a local minimum or a saddle point (where a previous branch split off) and ending at either a local maximum or another saddle point. The decomposition is built greedily and is not unique.

Algorithm: Branches are extracted one at a time by repeatedly finding the unprocessed vertex with the lowest function value that still has outgoing edges, then greedily following successors upward until a local maximum is reached. The edges along that path are removed from a working copy of the graph, and the process repeats until no edges remain. Isolated vertices (no edges) are added last as degenerate branches.

Branch storage (``self.branches``): An n x 4 numpy array where each row represents one branch in the order they were extracted:

• Column 0 (f_low): function value of the lower endpoint.

• Column 1 (f_high): function value of the upper endpoint. Equal to f_low for degenerate (isolated vertex) branches.

• Column 2 (low_attach): index of the branch that owns the lower endpoint vertex. If the lower endpoint is a local minimum, this is the branch’s own index.

• Column 3 (high_attach): index of the branch that owns the upper endpoint vertex. If the upper endpoint is a local maximum, this is the branch’s own index. Otherwise it points to the earlier branch whose path passes through that vertex.

Because branches are extracted in order, attachment indices always satisfy low_attach <= branch_id and high_attach <= branch_id.

Path storage (``self.paths``): A list of lists, in the same order as self.branches. Each entry is the ordered list of vertex names (from the original ReebGraph) that make up the branch path.

Reconstruction: The original Reeb graph can be recovered exactly from the stored paths and function values via reconstruct().

Example:

import cereeberus.data.ex_reebgraphs as ex_rg
from cereeberus.reeb.branchdecomp import BranchDecomp

R = ex_rg.dancing_man()
bd = BranchDecomp()
bd.decompose(R)
bd.draw()
R2 = bd.reconstruct()

__init__()

decompose(reebgraph)

Decomposes the Reeb graph into branches.

get_branches()

Returns the branches of the Reeb graph.

get_branch(branch_id)

Returns the branch with the given ID.

get_branch_path(branch_id)

Returns the list of vertices constituting the path for the given branch ID.

Parameters:

branch_id (int) – The ID of the branch.

Returns:

The list of vertices in the path for the given branch.

Return type:

list

reconstruct()

Reconstructs the Reeb graph from the branch decomposition stored in self.paths and self._f.

Returns:

The reconstructed Reeb graph.

Return type:

ReebGraph

draw(ax=None, figsize=(12, 8))

Draw the branch decomposition with branches ordered left to right.

Each branch is drawn as a vertical line at its proper function values. Endpoint labels show the branch attachment information: - Lower endpoint labeled with low_attach branch ID - Upper endpoint labeled with high_attach branch ID

Parameters:

• ax – matplotlib axis object. If None, creates a new figure.

• figsize – tuple of figure size (width, height)

Returns:

the matplotlib axis object

Return type:

ax