1.2. Merge tree

This is the Merge tree class which inherits structure from ReebGraph.

Note that this class can be imported as:

import cereeberus
T = cereeberus.MergeTree()

class cereeberus.reeb.merge.MergeTree(T=None, root=None, f={}, labels=None, seed=None, verbose=False)

A merge tree stored as a ReebGraph object. Like a Reeb graph, this is a directed graph with a function defined on the vertices. However, in a merge tree, the function is required to iave a single root with function value treated as \(\infty\).

We also store label information to construct a labeled merge tree. Here, this is a dictionary from some set (usually [1,…,n]) to a subset of vertices of the graph.

__init__(T=None, root=None, f={}, labels=None, seed=None, verbose=False)

Initialize a merge tree object.

Parameters:

• T – nx.graph, optional. If not none, it should be a tree with a specified root and function values.

• labels – dict, optional. A dictionary from labels to subsets of vertices.

get_finite_nodes()

Returns a list of the finite nodes of the tree. That is, everything except for v_inf.

get_leaves()

Returns a list of the leaves of the tree.

smoothing_and_maps(eps=1, verbose=False)

Builds the eps-smoothed merge tree and the associated vertex/edge maps.

ReebGraph.smoothing_and_maps already handles the v_inf root correctly (it treats any infinite-valued vertex as a formal marker and reattaches it after smoothing the finite part), but it returns a plain ReebGraph. This override just re-wraps that result as a MergeTree so callers get back the expected type.

Parameters:

• eps (float) – The amount of smoothing to apply.

• verbose (bool) – Optional. If True, prints additional information.

Returns:

MergeTree, vertex_map, edge_map.

Return type:

tuple

add_node(vertex, f_vertex, reset_pos=True)

Adds a node to the tree. Note that this will break the single connected component property of the tree so we assume you will do this in the process of adding more connecting edges.

remove_node(vertex, reset_pos=True)

Removes a node from the tree. Note that this will break the single connected component property of the tree if it is not a leaf so we assume you will do this in the process of adding more connecting edges.

add_edge(u, v, reset_pos=True)

Adds the edge (u,v) to the tree. This command will not allow you to add an edge if it will create a loop.

inputToDirRootTree(T, root, f)

Convert the input to a directed rooted tree that respects the internal structure.

If T is undirected, it will be converted to a directed tree with the root specified.

If f is not specified, a function will be induced from the tree from number of edges from the root.

A vertex will be added with funciton value infinity.

fix_pos_f()

Update drawing locations to deal with the fact that we have np.inf around.

This sets the drawing location of the infinite node to be directly above the maximum finite node of the tree.

set_pos_from_f(seed=None, repulsion=0.5, verbose=False)

Fix the drawing locations for the function values.

draw(with_labels=True, label_type='names', with_colorbar=False)

Draw the merge tree.

If with_labels is True, the labels will be drawn. This is either the vertex names if label_type is ‘names’ or the merge tree labels if label_type is ‘labels’.

label_all_leaves()

Label all the leaves of the tree by adding them to the labels dictionary if they’re not already there.

add_label(vertex, label=None)

Add a label to a vertex. If not provided, the label will be the next available integer.

add_label_edge(u, v, w, f_w, label=None)

Add a new vertex named w at function value f_w by subdividing the edge (u,v) and label it.

LCA(u, v)

Compute the least common ancestor of two vertices in the tree.

LCA_matrix(type='leaves', return_as_df=False)

Compute the matrix of least common ancestors.

If type is leaves, then the rows and columns of the matrix are determined by the leaf sets.

If type is labels, then the rows and columns of the matrix are determined by the labels internal to the MergeTree.