9. Tutorial: 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 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.

Each branch stores:

• The function values at its two endpoints (f_low, f_high)

• Attachment information: which earlier branch each endpoint belongs to (pointing to itself if it is a local min/max)

This tutorial follows the branch decomposition viewpoint developed in Samira Jabry’s thesis, Unsmoothing of Reeb Graphs, Saint Louis University, 2025:

For the API and class reference, see the branch decomposition documentation page.

import matplotlib.pyplot as plt

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

9.1. A simple example: the dancing man

We’ll start with the dancing_man example graph, which is a connected Reeb graph with several saddle points.

R = ex_rg.dancing_man()

fig, axes = plt.subplots(1, 2, figsize=(14, 6))
R.draw(ax=axes[0])
axes[0].set_title('Reeb Graph', fontsize=14, fontweight='bold')

bd = R.branch_decomp()
bd.draw(ax=axes[1])

plt.tight_layout()
plt.show()

The branch decomposition diagram shows each branch as a vertical line positioned at its function values. Labels next to each endpoint indicate which branch that endpoint is attached to:

• Purple (lower endpoint): the branch ID whose path contains this vertex

• Green (upper endpoint): the branch ID whose path contains this vertex

When a label matches the branch’s own ID, that endpoint is a local min or max (no other branch claims it).

9.2. Inspecting the branches

The branches are stored as an \(n \times 4\) numpy array. Each row is one branch:

Column	Meaning
0	f_low — function value of the lower endpoint
1	f_high — function value of the upper endpoint
2	low_attach — branch ID owning the lower endpoint
3	high_attach — branch ID owning the upper endpoint

print("Branches (f_low, f_high, low_attach, high_attach):")
print(bd.branches)

Branches (f_low, f_high, low_attach, high_attach):
[[1. 7. 0. 0.]
 [4. 5. 1. 0.]
 [4. 6. 0. 0.]
 [5. 6. 2. 3.]]

# You can also inspect individual branches and their vertex paths
for i in range(len(bd.branches)):
    print(f"Branch {i}: f=[{bd.branches[i,0]}, {bd.branches[i,1]}]  "
          f"attaches=({int(bd.branches[i,2])}, {int(bd.branches[i,3])})  "
          f"path={bd.get_branch_path(i)}")

Branch 0: f=[1.0, 7.0]  attaches=(0, 0)  path=[7, 6, 2, 1, 0]
Branch 1: f=[4.0, 5.0]  attaches=(1, 0)  path=[5, 2]
Branch 2: f=[4.0, 6.0]  attaches=(0, 0)  path=[6, 3, 1]
Branch 3: f=[5.0, 6.0]  attaches=(2, 3)  path=[3, 4]

9.3. Reconstructing the Reeb graph

Once you have a branch decomposition, you can reconstruct the original Reeb graph exactly from it using reconstruct().

R2 = bd.reconstruct()

fig, axes = plt.subplots(1, 2, figsize=(12, 5))
R.draw(ax=axes[0])
axes[0].set_title('Original', fontsize=13, fontweight='bold')
R2.draw(ax=axes[1])
axes[1].set_title('Reconstructed', fontsize=13, fontweight='bold')
plt.tight_layout()
plt.show()

print(f"Original:      {R}")
print(f"Reconstructed: {R2}")

Original:      ReebGraph with 8 nodes and 8 edges.
Reconstructed: ReebGraph with 8 nodes and 8 edges.

9.4. Handling isolated vertices: the juggling man

The juggling_man graph has isolated vertices (vertices with no edges), representing disconnected components. These are handled as degenerate branches where f_low == f_high and both attachment IDs point to the branch itself.

J = ex_rg.juggling_man()

fig, axes = plt.subplots(1, 2, figsize=(16, 6))
J.draw(ax=axes[0])
axes[0].set_title('Juggling Man Reeb Graph', fontsize=14, fontweight='bold')

bd_j = J.branch_decomp()
bd_j.draw(ax=axes[1])

plt.tight_layout()
plt.show()

# Identify the degenerate branches (isolated vertices)
print("Degenerate branches (isolated vertices):")
for i, (f_low, f_high, low_a, high_a) in enumerate(bd_j.branches):
    if f_low == f_high:
        print(f"  Branch {i}: vertex={bd_j.get_branch_path(i)}, f={f_low}, "
              f"attaches=({int(low_a)}, {int(high_a)})")

Degenerate branches (isolated vertices):
  Branch 4: vertex=[8], f=6.5, attaches=(4, 4)
  Branch 5: vertex=[9], f=6.5, attaches=(5, 5)
  Branch 6: vertex=[10], f=5.5, attaches=(6, 6)

9.5. Summary

The BranchDecomp class provides:

• decompose(R) — compute the decomposition from a ReebGraph

• branches — the \(n \times 4\) array of branch data

• get_branch(i) — return row \(i\) of the branches array

• get_branch_path(i) — return the list of vertices in branch \(i\)

• reconstruct() — rebuild the original ReebGraph from the stored paths

• draw() — visualise the decomposition

You can also call R.branch_decomp() directly on any ReebGraph or MapperGraph as a shortcut.