3.5. Distance

The distance module includes

cereeberus.compute.distance.edit(R1, R2)

Function to return the edit distance between two Reeb graphs. Uses the graph_edit_distance function from https://networkx.org/documentation/stable/reference/algorithms/similarity.html.

Parameters:

• R1 (reeb graph) – Reeb graph or Merge tree

• R2 (reeb graph) – Reeb graph or Merge tree

Returns:

graph edit distance

Return type:

edit_distance (int)

cereeberus.compute.distance.findFiltration(theta, origin=(0, 0))

get line of theta slope going through origin point, also track an inversion flag for dist

cereeberus.compute.distance.getHeightMatrix(mt, verbose=False)

LCA from networkx, assuming it to be better than Eulerian tour + spare table min range query, returning a matrix of pairwise LCA heights and then the matrix of LCA nodes

this uses Tarjan’s offline LCA optimized with inverse Ackermann function so O(Nodes+Queries) approximately

cereeberus.compute.distance.calcDistanceMatrix(mt0, mt1, verbose=False)

calculate difference matrix of LCA heights, also return LCA nodes of mt0 and mt1

cereeberus.compute.distance.calcDistanceInfNorm(mt0, mt1, verbose=False)

calculate infinity norm of two graphs, not used in the complete MT flow but useful as separate utility

cereeberus.compute.distance.getUnitVector(angle)

get 2D unit vector of input angle

cereeberus.compute.distance.getMidpointKey(arr, target)

get the midpoint key of the region that contains the target

cereeberus.compute.distance.computeGraphDistanceAtAngle(angle, G1, G2, criticalDict, midpointDict, verbose=False)

compute distance of two embedded graphs at a given angle using cached precomputation and inferring all other angles

cereeberus.compute.distance.computeDistanceAtAngleFromMT(g1_orig, g2_orig, angle, precision=5, show=False, verbose=False)

given an angle and two graphs, compute full difference matrix and LCA node matrix

cereeberus.compute.distance.computeDistanceFull(g1, g2, precision=5, show=False, verbose=False)

calculate all necessary pre-computations of height and LCA matrices for every critical angle and midpoint of two embedded graphs

cereeberus.compute.distance.directedMergeTreeDistance(G1_orig, G2_orig, precision=5, plot=True, show=False, verbose=False, xMin=0, xMax=6.283185307179586, n=10000)

get distances of two embedded graphs over linspace of n points from xMin to xMax, full driver code, plot to show graph, show is for internal merge trees