2.1. Interleave class

This is the Interleave class which is used to find a good bound for the interleaving distance between two mapper graphs.

To get the bound, we can run:

from cereeberus import Interleave
myInt = Interleave(M1, M2)
myInt.fit()

Note that there are two major classes in this module. The Interleave class is used to compute a bound N on the interleaving distance between two mapper graphs, while the Assignment class is used internally to find the best bound n+k given a fixed value of n where k is the computed loss. A full tutorial can be found in the Interleaving Basics Jupyter Notebook.

class cereeberus.distance.interleave.Interleave(F, G)[source]

A class to compute the interleaving distance between two Mapper graphs, denoted \(F\) and \(G\). The interleaving distance is a measure of how similar two Mapper graphs are, based on the induced maps between them.

Once the Interleave.fit() command has been run, the optimal bound for the distance for the input mapper graphs is stored as Interleave.n. The resulting maps can be found using the Interleave.phi() and Interleave.psi() functions. For more detailed structure, the full interleaving is stored using an Assignment class, documented below, and can be accessed using Interleave.assignment.

__init__(F, G)[source]

Initialize the Interleave object.

Parameters:

F (MapperGraph) – The first Mapper graph.
G (MapperGraph) – The second Mapper graph.

old_fit(pulp_solver=None, verbose=False, max_n_for_error=100)[source]

Compute the interleaving distance between the two Mapper graphs.

Parameters:

pulp_solver (pulp.LpSolver) – The solver to use for the ILP optimization. If None, the default solver is used.
verbose (bool, optional) – If True, print the progress of the optimization. Defaults to False.
max_n_for_error (int, optional) – The maximum value of n to search for. If the interleaving distance is not found by this value, a ValueError is raised. Defaults to 100.
printOptimizerOutput (bool, optional) – If True, the output of the PULP optimizer is printed. Defaults to False.

Returns:

The Interleave object with the computed interleaving distance.

Return type:

Interleave

fit(pulp_solver=None, verbose=False, max_n_for_error=100)[source]

Compute the interleaving distance between the two Mapper graphs.

Parameters:

pulp_solver (pulp.LpSolver) – The solver to use for the ILP optimization. If None, the default solver is used.
verbose (bool, optional) – If True, print the progress of the optimization. Defaults to False.
max_n_for_error (int, optional) – The maximum value of n to search for. If the interleaving distance is not found by this value, a ValueError is raised. Defaults to 100. ####NOTE: this can be replaced by the bounding box.

Returns:

The interleaving distance, that is, the smallest n for which loss is zero.

Return type:

Int

phi(key='0', obj_type='V')[source]

Get the interleaving map \(\varphi: F \to G^n\) if key == '0' or \(\varphi_n: F^n \to G^{2n}\) if key == 'n'.

Parameters:

key (str) – The key for the map. Either '0' or 'n'.
obj_type (str) – The type of map. Either 'V' or 'E'.

Returns:

The interleaving map.

Return type:

LabeledBlockMatrix

psi(key='0', obj_type='V')[source]

Get the interleaving map \(\psi: G \to F^n\) if key == '0' or \(\psi_n: G^n \to F^{2n}\) if key == 'n'.

Parameters:

key (str) – The key for the map. Either '0' or 'n'.
obj_type (str) – The type of map. Either 'V' or 'E'.

Returns:

The interleaving map.

Return type:

LabeledBlockMatrix

get_interleaving_map(maptype='phi', key='0', obj_type='V')[source]

Get the relevant interleaving map. Helpful for iterating over options.

Parameters:

maptype (str) – The type of map. Either 'phi' or 'psi'.
key (str) – The key for the map. Either '0' or 'n'.
obj_type (str) – The type of map. Either 'V' or 'E'.

Returns:

The relevant interleaving map.

Return type:

LabeledBlockMatrix

draw_all_graphs(figsize=(15, 10), **kwargs)[source]

Draw all the graphs stored in the Interleave object.

Parameters:: figsize (tuple, optional) – Sets the size of the figure. Defaults to (15,10).
Returns:: The figure and axes objects.
Return type:: tuple

draw_all_phi(figsize=(15, 10), **kwargs)[source]

Draw all the phi maps stored in the Interleave object.

Parameters:

figsize (tuple, optional) – Sets the size of the figure. Defaults to (15,10).
**kwargs – Additional keyword arguments to pass to the drawing function.

Returns:

The figure and axes objects.

Return type:

tuple

draw_all_psi(figsize=(15, 10), **kwargs)[source]

Draw all the psi maps stored in the Interleave object.

Parameters:

figsize (tuple, optional) – Sets the size of the figure. Defaults to (15,10).
**kwargs – Additional keyword arguments to pass to the drawing function.

Returns:

The figure and axes objects.

Return type:

tuple

class cereeberus.distance.interleave.Assignment(F, G, n=1, initialize_random_maps=False, seed=None)[source]

A class to determine the loss for a given assignment, and thus bound the interleaving distance between two Mapper graphs, denoted \(F\) and \(G\) throughout.

We use keys ['0', 'n', '2n'] to denote the Mapper graphs \(F = F_0\), \(F_n\), and \(F_{2n}\) and similarly for \(G\).

Note that the difference in the ranges of the two Mapper graphs must be within 'n'.

__init__(F, G, n=1, initialize_random_maps=False, seed=None)[source]

Initialize the Interleave object.

Parameters:

F (MapperGraph) – The first Mapper graph.
G (MapperGraph) – The second Mapper graph.
n (int) – The interleaving parameter. The default is 1.

F(key='0')[source]

Get the MapperGraph for \(F\) with key.

Parameters:: key (str) – The key for the MapperGraph. Either '0', 'n', or '2n'. Default is '0'.
Returns:: The MapperGraph for \(F\) with key.
Return type:: MapperGraph

G(key='0')[source]

Get the MapperGraph for \(G\) with key.

Parameters:: key (str) – The key for the MapperGraph. Either '0', 'n', or '2n'. Default is '0'.
Returns:: The MapperGraph for \(G\) with key.
Return type:: MapperGraph

B(graph='F', key='0')[source]

Get the boundary matrix for a Mapper graph. This is the matrix with entry \(B[v,e]\) equal to 1 if vertex \(v\) is an endpoint of edge \(e\) and 0 otherwise. Also, the boundary matrix is not computed for key = '2n' because it is not used in the optimization.

Parameters:

graph (str) – The graph to get the boundary matrix for. Either 'F' or 'G'.
key (str) – The key for the boundary matrix. Either '0' or 'n'.

Returns:

The boundary matrix for the Mapper graph.

Return type:

LabeledBlockMatrix

B_down(graph='F', key='0')[source]

Get the downward boundary matrix for a Mapper graph. This is the matrix with entry \(B[v,e]\) equal to 1 if vertex \(v\) is a lower endpoint of edge \(e\) and 0 otherwise. Also, the boundary matrix is not computed for key = '2n' because it is not used in the optimization.

Parameters:

graph (str) – The graph to get the boundary matrix for. Either 'F' or 'G'.
key (str) – The key for the boundary matrix. Either '0', or 'n'.

Returns:

The downward boundary matrix for the Mapper graph.

Return type:

LabeledBlockMatrix

B_up(graph='F', key='0')[source]

Get the upward boundary matrix for a Mapper graph. This is the matrix with entry \(B[v,e]\) equal to 1 if vertex \(v\) is an upper endpoint of edge \(e\) and 0 otherwise. Also, the boundary matrix is not computed for key = '2n' because it is not used in the optimization.

If shift_indices is True, the indices of the matrix will be shifted (DOWN?) by one to make matrix multiplication work later.

Parameters:

graph (str) – The graph to get the boundary matrix for. Either 'F' or 'G'.
key (str) – The key for the boundary matrix. Either '0' or 'n'.

Returns:

The upward boundary matrix for the Mapper graph.

Return type:

LabeledBlockMatrix

I(graph='F', key='0', obj_type='V')[source]

Get the induced map from one Mapper graph to another, specifically from graph_key to graph_(key+n) sending obj_type to the same type. For example, I('G', 'n', 'E') is the map for edges from \(G_n\) to \(G_{2n}\).

This is the matrix with entry \(I[u, v] = 1\) if vertex \(v\) in the first graph maps to vertex \(u\) in the second graph.

Parameters:

graph (str) – The graph to get the induced map for. Either 'F' or 'G'.
key (str) – The key for the induced map. Either '0' or 'n'.
obj_type (str) – The type of map. Either 'V' or 'E'.

Returns:

The induced map from graph_key to graph_(key+n).

Return type:

LabeledBlockMatrix

D(graph='F', key='n', obj_type='V')[source]

Get the distance matrix for a Mapper graph. This is the matrix with entry \(D[u, v]\) equal to the minimum thickening needed for vertices \(u\) and \(v\) to map to the same connected component (similarly for edges). Note this distance is only defined for vertices or edges at the same function value. Also, the distance matrix is not computed for key = ‘0’ because it is not used in the optimization.

Parameters:

graph (str) – The graph to get the distance matrix for. Either 'F' or 'G'.
key (str) – The key for the distance matrix. Either 'n', or '2n'.

Returns:

The distance matrix for the Mapper graph.

Return type:

LabeledBlockMatrix

phi(key='0', obj_type='V')[source]

Get the interleaving map \(\varphi: F \to G^n\) if key == ‘0’ or \(\varphi_n: F^n \to G^{2n}\) if key == ‘n’.

Parameters:

key (str) – The key for the map. Either '0' or 'n'.
obj_type (str) – The type of map. Either 'V' or 'E'.

Returns:

The interleaving map.

Return type:

LabeledBlockMatrix

psi(key='0', obj_type='V')[source]

Get the interleaving map \(\psi: G \to F^n\) if key == ‘0’ or \(\psi_n: G^n \to F^{2n}\) if key == ‘n’.

Parameters:

key (str) – The key for the map. Either '0' or 'n'.
obj_type (str) – The type of map. Either 'V' or 'E'.

Returns:

The interleaving map.

Return type:

LabeledBlockMatrix

get_interleaving_map(maptype='phi', key='0', obj_type='V')[source]

Get the relevant interleaving map. Helpful for iterating over options.

Parameters:

maptype (str) – The type of map. Either 'phi' or 'psi'.
key (str) – The key for the map. Either '0' or 'n'.
obj_type (str) – The type of map. Either 'V' or 'E'.

Returns:

The relevant interleaving map.

Return type:

LabeledBlockMatrix

set_interleaving_maps(phi_dict=None, psi_dict=None)[source]

Set the phi and psi matrices to a given value. Instead of replacing the matrices, set the values block by block.

Parameters:

phi_dict (dict) – A dictionary of the form {'0': {'V': phi_0_V, 'E': phi_0_E}, 'n': {'V': phi_n_V, 'E': phi_n_E}} where each phi_i_j is a LabeledBlockMatrix.
psi_dict (dict) – A dictionary of the form {'0': {'V': psi_0_V, 'E': psi_0_E}, 'n': {'V': psi_n_V, 'E': psi_n_E}} where each psi_i_j is a LabeledBlockMatrix.

set_single_assignment(obj_a, obj_b, maptype='phi', key='0', objtype='V')[source]

Set a single assignment in the interleaving map.

This will be maptype_key(obj_a) = obj_b.

Note that edges can be passed as a triple (u,v,count) where u and v are the vertices and count is the key for the edge. If passed as a pair, the count will be assumed to be 0.

Parameters:

obj_a (int) – Object in the domain of the map.
obj_b (int) – Object in the codomain of the map.
maptype (str, optional) – Map to be set, either ‘phi’ or ‘psi’. Defaults to ‘phi’.
objtype (str, optional) – Type of object as input, either ‘V’ or ‘E’. Defaults to ‘V’.

set_random_assignment(random_n=True, seed=None)[source]

Set the phi and psi matrices to random values. No matter what, the maps from F to Gn and G to Fn will be randomly set. If 'random_n' is True, the maps from Fn to G2n and Gn to F2n will also be randomly set. Otherwise, we will use matrix tricks to figure out the later from the former.

Note this functions assumes the phi and psi dictionaries were set on initialization. It will overwrite any contents that are there.

draw_all_graphs(figsize=(15, 10), **kwargs)[source]

Draw all the graphs stored in the Interleave object.

Parameters:: figsize (tuple, optional) – Sets the size of the figure. Defaults to (15,10).
Returns:: The figure and axes objects.
Return type:: tuple

draw_I(graph='F', key='0', obj_type='V', ax=None, **kwargs)[source]

Draw the induced map from one Mapper graph to another.

Parameters:

graph (str) – The graph to draw the induced map for. Either 'F' or 'G'.
key (str) – The key for the induced map. Either '0' or 'n'.

Returns:

matplotlib.axes.Axes: The axes the matrix was drawn on.

draw_all_I(graph='F', figsize=(10, 10), **kwargs)[source]

Draw all the induced maps.

Parameters:

graph (str) – The graph to draw the induced maps for. Either 'F' or 'G'.
figsize (tuple) – The size of the figure. Default is (10,10).

Returns:

The figure and axes objects.

Return type:

tuple

draw_B(graph='F', key='0', ax=None, **kwargs)[source]

Draw the boundary matrix for a Mapper graph.

Parameters:

graph (str) – The graph to draw the boundary matrix for. Either 'F' or 'G'.
key (str) – The key for the boundary matrix. Either '0', 'n', or '2n'.

Returns:

matplotlib.axes.Axes: The axes the matrix was drawn on.

draw_all_B(figsize=(18, 18))[source]

Draw all the boundary matrices.

Parameters:: figsize (tuple) – The size of the figure. Default is (24,18).
Returns:: The figure and axes objects.
Return type:: tuple

draw_D(graph='F', key='n', obj_type='V', colorbar=True, ax=None, **kwargs)[source]

Draw the distance matrix for a Mapper graph.

Parameters:

graph (str) – The graph to draw the distance matrix for. Either 'F' or 'G'.
key (str) – The key for the distance matrix. Either 'n', or '2n'.
obj_type (str) – The type of matrix. Either 'V' or 'E'.
colorbar (bool) – Whether to draw a colorbar. Default is True.
ax (matplotlib.axes.Axes) – The axes to draw the matrix on. If None, the current axes will be used.
**kwargs (dict) – Additional keyword arguments to pass to the drawing function.

Returns:

matplotlib.axes.Axes: The axes the matrix was drawn on.

draw_phi(key='0', obj_type='V', ax=None, **kwargs)[source]

Draw the map \(\psi: F \to G^n\).

Parameters:

key (str) – The key for the map. Either '0' or 'n'.
obj_type (str) – The type of map. Either 'V' or 'E'.

Returns:

matplotlib.axes.Axes: The axes the matrix was drawn on.

draw_psi(key='0', obj_type='V', ax=None, **kwargs)[source]

Draw the map \(\psi: G \to F^n\).

Parameters:

key (str) – The key for the map. Either '0' or 'n'.
obj_type (str) – The type of map. Either 'V' or 'E'.

Returns:

matplotlib.axes.Axes: The axes the matrix was drawn on.

draw_all_phi(figsize=(10, 10), **kwargs)[source]

Draw all the phi maps.

Parameters:: figsize (tuple) – The size of the figure. Default is (10,10).
Returns:: The figure and axes objects.
Return type:: tuple

draw_all_psi(figsize=(10, 10), **kwargs)[source]

Draw all the psi maps.

Parameters:: figsize (tuple) – The size of the figure. Default is (10,10).
Returns:: The figure and axes objects.
Return type:: tuple

parallelogram_Edge_Vert_matrix(maptype='phi', up_or_down='down', func_val=None, draw=False)[source]

Check that the parallelogram for the pair \((S_{\tau_i}\subset S_{\sigma_i})\) commutes. This is the one that relates the edge maps to the vertex maps. Because a function value has both an up and down version, we need to specify which one we want to check with the up_or_down parameter.

If func_val is not None, we will only check the parallelogram for that function value.

Parameters:

maptype (str) – The type of map for the relevant diagram. Either 'phi' or 'psi'.
up_or_down (str) – Whether to check the up or down version of the parallelogram. Either 'up', 'down', or 'both'. Default is 'down'.
func_val (int) – The function value to check the parallelogram for. If None, we will check all function values for the full matrix.
draw (bool) – Whether to draw the maps. Default is False.

Returns:

The matrix that gives the thickening required to make the diagram commute.

Return type:

LabeledMatrix

parallelogram_Edge_Vert(maptype='phi', up_or_down='down', func_val=None)[source]: Check that the parallelogram for the pair \((S_{\tau_i}\subset S_{\sigma_i})\) commutes, and return the maximum value in the matrix.

parallelogram_matrix(maptype='phi', obj_type='V', func_val=None, draw=False)[source]

Get the paralellograms for checking that it’s a nat trans. These are types 3-6 from Liz’s Big List.

If func_val is not None, we will only check the parallelogram for that function value.

Parameters:

maptype (str) – The type of map. Either ‘phi’ or ‘psi’.
obj_type (str) – The type of object. Either 'V' or 'E'.
func_val (int) – The function value to check the parallelogram for. If None, we will check all function values for the full matrix.
draw (bool) – Whether to draw the maps. Default is False.

Returns:

The matrix that gives the thickening required to make the diagram commute.

Return type:

LabeledMatrix

parallelogram(maptype='phi', obj_type='V', func_val=None)[source]: Get the loss value for the thickening paralellograms

triangle_matrix(start_graph='F', obj_type='V', func_val=None, draw=False)[source]

Get the triangle for checking that it’s an interleaving.

If func_val is not None, we will only check the parallelogram for that function value.

Parameters:

start_graph (str) – The starting graph. Either ‘F’ or ‘G’.
obj_type (str) – The type of object. Either 'V' or 'E'.
func_val (int) – The function value to check the parallelogram for. If None, we will check all function values for the full matrix.
draw (bool) – Whether to draw the maps. Default is False.

Returns:

The matrix that gives the thickenin grequired to make the diagram commute

Return type:

LabeledMatrix

triangle(start_graph='F', obj_type='V', func_val=None)[source]: Get the loss value for the triangle

loss_table()[source]

Returns a table with the loss for each term in the bound. The actual loss is the maximum of these values, and can be found with the loss method.

Returns:: A table with the loss value for each term. The ‘Loss’ column has the loss value.
Return type:: pd.DataFrame

loss(verbose=False)[source]

Computes the loss for the interleaving distance. Specifically, if the loss is \(L\) and the interleaving class was initiated with \(n\), then the interleaving distance is at most \(n + L\).

Returns:: The loss value.
Return type:: float

loss_by_block()[source]

Computes the loss for each block of the interleaving distance.

Returns:: A dictionary with the loss for each block.
Return type:: dict

all_func_vals()[source]

Get all the function values that are in the graphs.

Returns:: A list of all the function values.
Return type:: list

optimize(pulp_solver=None)[source]

Uses the ILP to find the best interleaving distance bound, returns the loss value found. Further, it stores the optimal phi and psi maps which can be returned using the self.phi and self.psi attributes respectively. This function requires the pulp package to be installed.

Parameters:: pulp_solver (pulp.LpSolver) – the solver to use for the ILP optimization. If None, the default solver is used.
Returns:: The loss value found by the ILP solver.
Return type:: float