lineagetree.measure

Modules:

Name	Description
dynamic_time_warping
spatial
uted

Functions:

Name	Description
calculate_dtw	Calculate DTW distance between two chains
clear_comparisons	Clears the comparisons saved on the LineageTree object.
compute_k_nearest_neighbours	Computes the k-nearest neighbors
compute_spatial_density	Computes the spatial density of nodes between t_b and t_e.
compute_spatial_edges	Computes the neighbors at a distance th
get_gabriel_graph	Build the Gabriel graph of the given graph for time point t.
labelled_mappings	Returns the labels or IDs of all the nodes in the subtrees compared.
plot_tree_distance_graphs	Plots the subtrees compared and colors them according to the quality of the matching of their subtree.
unordered_tree_edit_distance	Compute the unordered tree edit distance from Zhang 1996 between the trees spawned
unordered_tree_edit_distances_at_time_t	Compute all the pairwise unordered tree edit distances from Zhang 996 between the trees spawned at time t

calculate_dtw

calculate_dtw(
    lT: LineageTree,
    nodes1: int,
    nodes2: int,
    threshold: int = 1000,
    regist: bool = True,
    start_d: int = 0,
    back_d: int = 0,
    fast: bool = False,
    w: int = 0,
    centered_band: bool = True,
    cost_mat_p: bool = False,
) -> (
    tuple[float, tuple, np.ndarray, np.ndarray, np.ndarray]
    | tuple[float, tuple]
)

Calculate DTW distance between two chains

Parameters:

Name	Type	Description	Default
lT	LineageTree	The LineageTree instance.	required
nodes1	int	node to compare distance	required
nodes2	int	node to compare distance	required
threshold	int	set a maximum number of points a chain can have	1000
regist	bool	Rotate and translate trajectories	True
start_d	int	start delay	0
back_d	int	end delay	0
fast	bool	if True, the algorithm will use a faster version but might not find the optimal alignment	False
w	int	window size	0
centered_band	bool	when running the fast algorithm, True if the windown is centered	True
cost_mat_p	bool	True if print the not normalized cost matrix	False

Returns:

Type	Description
float	DTW distance
tuple of tuples	Aligment path
matrix	Cost matrix
list of lists	rotated and translated trajectories positions
list of lists	rotated and translated trajectories positions

Source code in src/lineagetree/measure/dynamic_time_warping.py

def calculate_dtw(
    lT: LineageTree,
    nodes1: int,
    nodes2: int,
    threshold: int = 1000,
    regist: bool = True,
    start_d: int = 0,
    back_d: int = 0,
    fast: bool = False,
    w: int = 0,
    centered_band: bool = True,
    cost_mat_p: bool = False,
) -> (
    tuple[float, tuple, np.ndarray, np.ndarray, np.ndarray]
    | tuple[float, tuple]
):
    """
    Calculate DTW distance between two chains

    Parameters
    ----------
    lT : LineageTree
        The LineageTree instance.
    nodes1 : int
        node to compare distance
    nodes2 : int
        node to compare distance
    threshold : int, default=1000
        set a maximum number of points a chain can have
    regist : bool, default=True
        Rotate and translate trajectories
    start_d : int, default=0
        start delay
    back_d : int, default=0
        end delay
    fast : bool, default=False
        if `True`, the algorithm will use a faster version but might not find the optimal alignment
    w : int, default=0
        window size
    centered_band : bool, default=True
        when running the fast algorithm, `True` if the windown is centered
    cost_mat_p : bool, default=False
        True if print the not normalized cost matrix

    Returns
    -------
    float
        DTW distance
    tuple of tuples
        Aligment path
    matrix
        Cost matrix
    list of lists
        rotated and translated trajectories positions
    list of lists
        rotated and translated trajectories positions
    """
    nodes1_chain = lT.get_chain_of_node(nodes1)
    nodes2_chain = lT.get_chain_of_node(nodes2)

    interp_chain1, interp_chain2 = __interpolate(
        lT, nodes1_chain, nodes2_chain, threshold
    )

    pos_chain1 = np.array([lT.pos[c_id] for c_id in nodes1_chain])
    pos_chain2 = np.array([lT.pos[c_id] for c_id in nodes2_chain])

    if regist:
        R, t = __rigid_transform_3D(
            np.transpose(interp_chain1), np.transpose(interp_chain2)
        )
        pos_chain1 = np.transpose(np.dot(R, pos_chain1.T) + t)

    dist_mat = distance.cdist(pos_chain1, pos_chain2, "euclidean")

    path, cost_mat, final_cost = __dp(
        dist_mat,
        start_d,
        back_d,
        w=w,
        fast=fast,
        centered_band=centered_band,
    )
    cost = final_cost / len(path)

    if cost_mat_p:
        return cost, path, cost_mat, pos_chain1, pos_chain2
    else:
        return cost, path

clear_comparisons

clear_comparisons(lT: LineageTree)

Clears the comparisons saved on the LineageTree object.

Parameters:

Name	Type	Description	Default
lT	LineageTree	The LineageTree object	required

Source code in src/lineagetree/measure/uted.py

def clear_comparisons(lT: LineageTree):
    """Clears the comparisons saved on the LineageTree object.

    Parameters
    ----------
    lT : LineageTree
        The LineageTree object
    """
    lT._comparisons.clear()

compute_k_nearest_neighbours

compute_k_nearest_neighbours(
    lT: LineageTree, k: int = 10
) -> dict[int, set[int]]

Computes the k-nearest neighbors Writes the output in the attribute kn_graph and returns it.

Parameters:

Name	Type	Description	Default
lT	LineageTree	The LineageTree instance.	required
k	float	number of nearest neighours	10

Returns:

Type	Description
dict mapping int to set of int	dictionary that maps a node id to its k nearest neighbors
dict mapping int to set of float	dictionary that maps a node id to the distances of its k nearest neighbors

Source code in src/lineagetree/measure/spatial.py

def compute_k_nearest_neighbours(
    lT: LineageTree, k: int = 10
) -> dict[int, set[int]]:
    """Computes the k-nearest neighbors
    Writes the output in the attribute `kn_graph`
    and returns it.

    Parameters
    ----------
    lT : LineageTree
        The LineageTree instance.
    k : float
        number of nearest neighours

    Returns
    -------
    dict mapping int to set of int
        dictionary that maps
        a node id to its `k` nearest neighbors
    dict mapping int to set of float
        dictionary that maps
        a node id to the distances of its `k` nearest neighbors
    """
    lT.kn_graph = {}
    lT.kn_distances = {}
    k = k + 1
    for t, nodes in lT.time_nodes.items():
        if 1 < len(nodes):
            use_k = k if k < len(nodes) else len(nodes)
            idx3d, nodes = lT.get_idx3d(t)
            pos = [lT.pos[c] for c in nodes]
            distances, neighbs = idx3d.query(pos, use_k)
            out = dict(
                zip(
                    nodes,
                    nodes[neighbs[:, 1:]],
                    strict=True,
                )
            )
            out_distances = dict(
                zip(
                    nodes,
                    distances[:, 1:],
                    strict=True,
                )
            )
            lT.kn_graph.update(out)
            lT.kn_distances.update(out_distances)
    return lT.kn_graph, lT.kn_distances

compute_spatial_density

compute_spatial_density(
    lT: LineageTree,
    t_b: int | None = None,
    t_e: int | None = None,
    th: float = 50,
) -> dict[int, float]

Computes the spatial density of nodes between t_b and t_e. The results is stored in lT.spatial_density and returned.

Parameters:

Name	Type	Description	Default
lT	LineageTree	The LineageTree instance.	required
t_b	int	starting time to look at, default first time point	None
t_e	int	ending time to look at, default last time point	None
th	float	size of the neighbourhood	50

Returns:

Type	Description
dict mapping int to float	dictionary that maps a node id to its spatial density

Source code in src/lineagetree/measure/spatial.py

def compute_spatial_density(
    lT: LineageTree,
    t_b: int | None = None,
    t_e: int | None = None,
    th: float = 50,
) -> dict[int, float]:
    """Computes the spatial density of nodes between `t_b` and `t_e`.
    The results is stored in `lT.spatial_density` and returned.

    Parameters
    ----------
    lT : LineageTree
        The LineageTree instance.
    t_b : int, optional
        starting time to look at, default first time point
    t_e : int, optional
        ending time to look at, default last time point
    th : float, default=50
        size of the neighbourhood

    Returns
    -------
    dict mapping int to float
        dictionary that maps a node id to its spatial density
    """
    s_vol = 4 / 3.0 * np.pi * th**3
    spatial_density = {
        k: (v + 1) / s_vol
        for k, v in lT.compute_neighbours_in_radius(t_b, t_e, th).items()
    }
    return spatial_density

compute_spatial_edges

compute_spatial_edges(
    lT: LineageTree, th: int = 50
) -> dict[int, set[int]]

Computes the neighbors at a distance th Writes the output in the attribute th_edge and returns it.

Parameters:

Name	Type	Description	Default
lT	LineageTree	The LineageTree instance.	required
th	float	distance to consider neighbors	50

Returns:

Type	Description
dict mapping int to set of int	dictionary that maps a node id to its neighbors at a distance th

Source code in src/lineagetree/measure/spatial.py

def compute_spatial_edges(
    lT: LineageTree, th: int = 50
) -> dict[int, set[int]]:
    """Computes the neighbors at a distance `th`
    Writes the output in the attribute `th_edge`
    and returns it.

    Parameters
    ----------
    lT : LineageTree
        The LineageTree instance.
    th : float, default=50
        distance to consider neighbors

    Returns
    -------
    dict mapping int to set of int
        dictionary that maps a node id to its neighbors at a distance `th`
    """
    lT.th_edges = {}
    for t in set(lT._time.values()):
        nodes = lT.time_nodes[t]
        idx3d, nodes = lT.get_idx3d(t)
        neighbs = idx3d.query_ball_tree(idx3d, th)
        out = dict(zip(nodes, [set(nodes[ni]) for ni in neighbs], strict=True))
        lT.th_edges.update({k: v.difference([k]) for k, v in out.items()})
    return lT.th_edges

get_gabriel_graph

get_gabriel_graph(
    lT: LineageTree, time: int | Iterable[int] | None = None
) -> dict[int, set[int]]

Build the Gabriel graph of the given graph for time point t. The Garbiel graph is then stored in lT.Gabriel_graph and returned.

.. warning:: the graph is not recomputed if already computed, even if the point cloud has changed

Parameters:

Name	Type	Description	Default
lT	LineageTree	The LineageTree instance.	required
time	int or Iterable of int	time or iterable of times. If not given the gabriel graph will be calculated for all timepoints.	None

Returns:

Type	Description
dict of int to set of int	A dictionary that maps a node to the set of its neighbors

Source code in src/lineagetree/measure/spatial.py

def get_gabriel_graph(
    lT: LineageTree, time: int | Iterable[int] | None = None
) -> dict[int, set[int]]:
    """Build the Gabriel graph of the given graph for time point `t`.
    The Garbiel graph is then stored in `lT.Gabriel_graph` and returned.

    .. warning:: the graph is not recomputed if already computed, even if the point cloud has changed

    Parameters
    ----------
    lT : LineageTree
        The LineageTree instance.
    time : int or Iterable of int, optional
        time or iterable of times.
        If not given the gabriel graph will be calculated for all timepoints.

    Returns
    -------
    dict of int to set of int
        A dictionary that maps a node to the set of its neighbors
    """
    if not hasattr(lT, "Gabriel_graph"):
        lT.Gabriel_graph = {}

    if time is None:
        time = lT.time_nodes.keys()
    elif not isinstance(time, Iterable):
        time = [time]

    for t in time:
        if lT.time_nodes[t] - lT.Gabriel_graph.keys():
            nodes = np.fromiter(list(lT.time_nodes[t]), dtype=int)

            data_corres = {}
            data = []
            for i, C in enumerate(nodes):
                data.append(lT.pos[C])
                data_corres[i] = C

            delaunay_graph = {}

            # The delaunay triangulation is only usefult to compute
            # when the number of points is higher than the spatial dimension + 1
            if len(data[0]) + 1 < len(data):
                tmp = Delaunay(data)
                for N in tmp.simplices:
                    for e1, e2 in combinations(np.sort(N), 2):
                        delaunay_graph.setdefault(e1, set()).add(e2)
                        delaunay_graph.setdefault(e2, set()).add(e1)
            # When there are fewer nodes than the number of dimensions + 2
            # The Delaunay is the complete graph
            else:
                for e1, e2 in combinations(data_corres, 2):
                    delaunay_graph.setdefault(e1, set()).add(e2)
                    delaunay_graph.setdefault(e2, set()).add(e1)

            Gabriel_graph = {}

            for e1, neighbs in delaunay_graph.items():
                for ni in neighbs:
                    if not any(
                        np.linalg.norm((data[ni] + data[e1]) / 2 - data[i])
                        < np.linalg.norm(data[ni] - data[e1]) / 2
                        for i in delaunay_graph[e1].intersection(
                            delaunay_graph[ni]
                        )
                    ):
                        Gabriel_graph.setdefault(data_corres[e1], set()).add(
                            data_corres[ni]
                        )
                        Gabriel_graph.setdefault(data_corres[ni], set()).add(
                            data_corres[e1]
                        )
            lT.Gabriel_graph.update(Gabriel_graph)

    return lT.Gabriel_graph

labelled_mappings

labelled_mappings(
    lT: LineageTree,
    n1: int,
    n2: int,
    end_time: int | None = None,
    norm: Literal["max", "sum", None] = "max",
    style: (
        Literal[
            "simple",
            "normalized_simple",
            "full",
            "downsampled",
        ]
        | type[TreeApproximationTemplate]
    ) = "simple",
    downsample: int = 2,
) -> dict[str, list[str]]

Returns the labels or IDs of all the nodes in the subtrees compared.

Parameters:

Name	Type	Description	Default
lT	LineageTree	The LineageTree instance.	required
n1	int	id of the first node to compare	required
n2	int	id of the second node to compare	required
end_time	int	The final time point the comparison algorithm will take into account. If None or not provided all nodes will be taken into account.	None
norm	('max', 'sum')	The normalization method to use, defaults to 'max'.	"max"
style	"simple", "full", "downsampled", "normalized_simple	Which tree approximation is going to be used for the comparisons, defaults to 'simple'.	"simple"
downsample	int	The downsample factor for the downsampled tree approximation. Used only when style="downsampled".	2

Returns:

Type	Description
dict mapping str to list of str	'matched' The labels of the matched nodes of the alignment. 'unmatched' The labels of the unmatched nodes of the alginment.

Source code in src/lineagetree/measure/uted.py

def labelled_mappings(
    lT: LineageTree,
    n1: int,
    n2: int,
    end_time: int | None = None,
    norm: Literal["max", "sum", None] = "max",
    style: (
        Literal["simple", "normalized_simple", "full", "downsampled"]
        | type[TreeApproximationTemplate]
    ) = "simple",
    downsample: int = 2,
) -> dict[str, list[str]]:
    """
    Returns the labels or IDs of all the nodes in the subtrees compared.


    Parameters
    ----------
    lT : LineageTree
        The LineageTree instance.
    n1 : int
        id of the first node to compare
    n2 : int
        id of the second node to compare
    end_time : int, optional
        The final time point the comparison algorithm will take into account.
        If None or not provided all nodes will be taken into account.
    norm : {"max", "sum"}, default="max"
        The normalization method to use, defaults to 'max'.
    style : {"simple", "full", "downsampled", "normalized_simple} or TreeApproximationTemplate subclass, default="simple"
        Which tree approximation is going to be used for the comparisons, defaults to 'simple'.
    downsample : int, default=2
        The downsample factor for the downsampled tree approximation.
        Used only when `style="downsampled"`.

    Returns
    -------
    dict mapping str to list of str
        - 'matched' The labels of the matched nodes of the alignment.
        - 'unmatched' The labels of the unmatched nodes of the alginment.
    """
    parameters = (
        end_time,
        convert_style_to_number(style=style, downsample=downsample),
    )
    n1, n2 = sorted([n1, n2])
    lT._comparisons.setdefault(parameters, {})
    if lT._comparisons[parameters].get((n1, n2)):
        tmp = lT._comparisons[parameters][(n1, n2)]
    else:
        tmp = __unordereded_backtrace(
            lT, n1, n2, end_time, norm, style, downsample
        )
    btrc = tmp["alignment"]
    tree1, tree2 = tmp["trees"]

    (
        *_,
        corres1,
    ) = tree1.edist
    (
        *_,
        corres2,
    ) = tree2.edist

    if norm not in lT.norm_dict:
        raise Warning("Select a viable normalization method (max, sum, None)")
    matched = []
    unmatched = []
    if style not in ("full", "downsampled"):
        for m in btrc:
            if m._left != -1 and m._right != -1:
                cyc1 = lT.get_chain_of_node(corres1[m._left])
                if len(cyc1) > 1:
                    node_1, *_ = cyc1
                elif len(cyc1) == 1:
                    node_1 = cyc1.pop()
                cyc2 = lT.get_chain_of_node(corres2[m._right])
                if len(cyc2) > 1:
                    node_2, *_ = cyc2
                elif len(cyc2) == 1:
                    node_2 = cyc2.pop()
                matched.append(
                    (
                        lT.labels.get(node_1, node_1),
                        lT.labels.get(node_2, node_2),
                    )
                )

            else:
                if m._left != -1:
                    node_1 = lT.get_chain_of_node(corres1.get(m._left, "-"))[0]
                else:
                    node_1 = lT.get_chain_of_node(corres2.get(m._right, "-"))[
                        0
                    ]
                unmatched.append(lT.labels.get(node_1, node_1))
    else:
        for m in btrc:
            if m._left != -1 and m._right != -1:
                node_1 = corres1[m._left]
                node_2 = corres2[m._right]
                matched.append(
                    (
                        lT.labels.get(node_1, node_1),
                        lT.labels.get(node_2, node_2),
                    )
                )
            else:
                if m._left != -1:
                    node_1 = corres1[m._left]
                else:
                    node_1 = corres2[m._right]
                unmatched.append(lT.labels.get(node_1, node_1))
    return {"matched": matched, "unmatched": unmatched}

plot_tree_distance_graphs

plot_tree_distance_graphs(
    lT: LineageTree,
    n1: int,
    n2: int,
    end_time: int | None = None,
    norm: Literal["max", "sum", None] = "max",
    style: (
        Literal[
            "simple",
            "normalized_simple",
            "full",
            "downsampled",
        ]
        | type[TreeApproximationTemplate]
    ) = "simple",
    downsample: int = 2,
    colormap: str = "cool",
    default_color: str = "black",
    size: float = 10,
    lw: float = 0.3,
    ax: list[Axes] | None = None,
    vmin=None,
    vmax=None,
) -> tuple[plt.figure, plt.Axes]

Plots the subtrees compared and colors them according to the quality of the matching of their subtree.

Parameters:

Name	Type	Description	Default
lT	LineageTree	The LineageTree instance.	required
n1	int	id of the first node to compare	required
n2	int	id of the second node to compare	required
end_time	int	The final time point the comparison algorithm will take into account. If None all nodes will be taken into account.	None
norm	('max', 'sum')	The normalization method to use.	"max"
style	"simple", "full", "downsampled", "normalized_simple	Which tree approximation is going to be used for the comparisons.	"simple"
downsample	int	The downsample factor for the downsampled tree approximation. Used only when style="downsampled".	2
colormap	str	The colormap used for matched nodes, defaults to "cool"	"cool"
default_color	str	The color of the unmatched nodes, defaults to "black"	'black'
size	float	The size of the nodes, defaults to 10	10
lw	float	The width of the edges, defaults to 0.3	0.3
ax	ndarray	The axes used, if not provided another set of axes is produced, defaults to None	None
vmin		Values within the range [vmin, vmax] from the input data will be linearly mapped to [0, 1]. vmin defaults to the 0.05 quantile of the values of the unordered tree edist distances of the subtrees. vmax defaults to the 0.95 quantile of the values of the unordered tree edist distances of the subtrees.	None
vmax		Values within the range [vmin, vmax] from the input data will be linearly mapped to [0, 1]. vmin defaults to the 0.05 quantile of the values of the unordered tree edist distances of the subtrees. vmax defaults to the 0.95 quantile of the values of the unordered tree edist distances of the subtrees.	None

Returns:

Type	Description
Figure	The figure of the plot
Axes	The axes of the plot

Source code in src/lineagetree/measure/uted.py

def plot_tree_distance_graphs(
    lT: LineageTree,
    n1: int,
    n2: int,
    end_time: int | None = None,
    norm: Literal["max", "sum", None] = "max",
    style: (
        Literal["simple", "normalized_simple", "full", "downsampled"]
        | type[TreeApproximationTemplate]
    ) = "simple",
    downsample: int = 2,
    colormap: str = "cool",
    default_color: str = "black",
    size: float = 10,
    lw: float = 0.3,
    ax: list[plt.Axes] | None = None,
    vmin=None,
    vmax=None,
) -> tuple[plt.figure, plt.Axes]:
    """
    Plots the subtrees compared and colors them according to the quality of the matching of their subtree.

    Parameters
    ----------
    lT : LineageTree
        The LineageTree instance.
    n1 : int
        id of the first node to compare
    n2 : int
        id of the second node to compare
    end_time : int
        The final time point the comparison algorithm will take into account.
        If None all nodes will be taken into account.
    norm : {"max", "sum"}, default="max"
        The normalization method to use.
    style : {"simple", "full", "downsampled", "normalized_simple} or TreeApproximationTemplate subclass, default="simple"
        Which tree approximation is going to be used for the comparisons.
    downsample : int, default=2
        The downsample factor for the downsampled tree approximation.
        Used only when `style="downsampled"`.
    colormap : str, default="cool"
        The colormap used for matched nodes, defaults to "cool"
    default_color : str
        The color of the unmatched nodes, defaults to "black"
    size : float
        The size of the nodes, defaults to 10
    lw : float
        The width of the edges, defaults to 0.3
    ax : np.ndarray, optional
        The axes used, if not provided another set of axes is produced, defaults to None
    vmin, vmax: float, optional
        Values within the range ``[vmin, vmax]`` from the input data will be
        linearly mapped to ``[0, 1]``.
        *vmin* defaults to the 0.05 quantile of the values of the unordered tree edist distances of the subtrees.
        *vmax* defaults to the 0.95 quantile of the values of the unordered tree edist distances of the subtrees.

    Returns
    -------
    plt.Figure
            The figure of the plot
    plt.Axes
            The axes of the plot
    """
    parameters = (
        end_time,
        convert_style_to_number(style=style, downsample=downsample),
    )
    n1, n2 = sorted([n1, n2])
    lT._comparisons.setdefault(parameters, {})
    if lT._comparisons[parameters].get((n1, n2)):
        tmp = lT._comparisons[parameters][(n1, n2)]
    else:
        tmp = __unordereded_backtrace(
            lT, n1, n2, end_time, norm, style, downsample
        )
    btrc: Alignment = tmp["alignment"]
    tree1, tree2 = tmp["trees"]
    _, times1 = tree1.tree
    _, times2 = tree2.tree
    (
        *_,
        corres1,
    ) = tree1.edist
    (
        *_,
        corres2,
    ) = tree2.edist
    delta_tmp = partial(
        tree1.delta,
        corres1=corres1,
        corres2=corres2,
        times1=times1,
        times2=times2,
    )

    if norm not in lT.norm_dict:
        raise Warning("Select a viable normalization method (max, sum, None)")
    matched_right = []
    matched_left = []
    colors = {}
    if style not in ("full", "downsampled"):
        for m in btrc:
            if m._left != -1 and m._right != -1:
                cyc1 = lT.get_chain_of_node(corres1[m._left])
                if len(cyc1) > 1:
                    node_1, *_, l_node_1 = cyc1
                    matched_left.append(node_1)
                    matched_left.append(l_node_1)
                elif len(cyc1) == 1:
                    node_1 = l_node_1 = cyc1.pop()
                    matched_left.append(node_1)

                cyc2 = lT.get_chain_of_node(corres2[m._right])
                if len(cyc2) > 1:
                    node_2, *_, l_node_2 = cyc2
                    matched_right.append(node_2)
                    matched_right.append(l_node_2)

                elif len(cyc2) == 1:
                    node_2 = l_node_2 = cyc2.pop()
                    matched_right.append(node_2)

                colors[node_1] = __calculate_distance_of_sub_tree(
                    lT,
                    node_1,
                    node_2,
                    btrc,
                    corres1,
                    corres2,
                    delta_tmp,
                    lT.norm_dict[norm],
                    tree1.get_norm(node_1),
                    tree2.get_norm(node_2),
                )
                colors[node_2] = colors[node_1]
                colors[l_node_1] = colors[node_1]
                colors[l_node_2] = colors[node_2]
    else:
        for m in btrc:
            if m._left != -1 and m._right != -1:
                node_1 = corres1[m._left]
                node_2 = corres2[m._right]

                if (
                    lT.get_chain_of_node(node_1)[0] == node_1
                    or lT.get_chain_of_node(node_2)[0] == node_2
                    and (node_1 not in colors or node_2 not in colors)
                ):
                    matched_left.append(node_1)
                    l_node_1 = lT.get_chain_of_node(node_1)[-1]
                    matched_left.append(l_node_1)
                    matched_right.append(node_2)
                    l_node_2 = lT.get_chain_of_node(node_2)[-1]
                    matched_right.append(l_node_2)
                    colors[node_1] = __calculate_distance_of_sub_tree(
                        lT,
                        node_1,
                        node_2,
                        btrc,
                        corres1,
                        corres2,
                        delta_tmp,
                        lT.norm_dict[norm],
                        tree1.get_norm(node_1),
                        tree2.get_norm(node_2),
                    )
                    colors[l_node_1] = colors[node_1]
                    colors[node_2] = colors[node_1]
                    colors[l_node_2] = colors[node_1]
    if ax is None:
        fig, ax = plt.subplots(nrows=1, ncols=2, sharey=True)
    cmap = colormaps[colormap]
    if vmin is None:
        vmin = np.percentile(list(colors.values()), 5)
    if vmax is None:
        vmax = np.percentile(list(colors.values()), 95)
    c_norm = mcolors.Normalize(vmin, vmax)
    colors = {c: cmap(c_norm(v)) for c, v in colors.items()}
    lT.plot_subtree(
        lT.get_ancestor_at_t(n1),
        end_time=end_time,
        size=size,
        selected_nodes=matched_left,
        color_of_nodes=colors,
        selected_edges=matched_left,
        color_of_edges=colors,
        default_color=default_color,
        lw=lw,
        ax=ax[0],
    )
    lT.plot_subtree(
        lT.get_ancestor_at_t(n2),
        end_time=end_time,
        size=size,
        selected_nodes=matched_right,
        color_of_nodes=colors,
        selected_edges=matched_right,
        color_of_edges=colors,
        default_color=default_color,
        lw=lw,
        ax=ax[1],
    )
    return ax[0].get_figure(), ax

unordered_tree_edit_distance

unordered_tree_edit_distance(
    lT: LineageTree,
    n1: int,
    n2: int,
    end_time: int | None = None,
    norm: Literal["max", "sum", None] = "max",
    style: (
        Literal[
            "simple",
            "normalized_simple",
            "full",
            "downsampled",
        ]
        | type[TreeApproximationTemplate]
    ) = "simple",
    downsample: int = 2,
    return_norms: bool = False,
) -> float | tuple[float, tuple[float, float]]

Compute the unordered tree edit distance from Zhang 1996 between the trees spawned by two nodes n1 and n2. The topology of the trees are compared and the matching cost is given by the function delta (see edist doc for more information). The distance is normed by the function norm that takes the two list of nodes spawned by the trees n1 and n2.

Parameters:

Name	Type	Description	Default
lT	LineageTree	The LineageTree instance.	required
n1	int	id of the first node to compare	required
n2	int	id of the second node to compare	required
end_time	int	The final time point the comparison algorithm will take into account. If None or not provided all nodes will be taken into account.	None
norm	('max', 'sum')	The normalization method to use, defaults to 'max'.	"max"
style	('simple', 'normalized_simple', 'full', 'downsampled')	Which tree approximation is going to be used for the comparisons.	"simple"
downsample	int	The downsample factor for the downsampled tree approximation. Used only when style="downsampled".	2

Returns:

Type	Description
float	The normalized unordered tree edit distance between n1 and n2

Source code in src/lineagetree/measure/uted.py

def unordered_tree_edit_distance(
    lT: LineageTree,
    n1: int,
    n2: int,
    end_time: int | None = None,
    norm: Literal["max", "sum", None] = "max",
    style: (
        Literal["simple", "normalized_simple", "full", "downsampled"]
        | type[TreeApproximationTemplate]
    ) = "simple",
    downsample: int = 2,
    return_norms: bool = False,
) -> float | tuple[float, tuple[float, float]]:
    """
    Compute the unordered tree edit distance from Zhang 1996 between the trees spawned
    by two nodes `n1` and `n2`. The topology of the trees are compared and the matching
    cost is given by the function delta (see edist doc for more information).
    The distance is normed by the function norm that takes the two list of nodes
    spawned by the trees `n1` and `n2`.

    Parameters
    ----------
    lT : LineageTree
        The LineageTree instance.
    n1 : int
        id of the first node to compare
    n2 : int
        id of the second node to compare
    end_time : int, optional
        The final time point the comparison algorithm will take into account.
        If None or not provided all nodes will be taken into account.
    norm : {"max", "sum"}, default="max"
        The normalization method to use, defaults to 'max'.
    style : {"simple", "normalized_simple", "full", "downsampled"} or TreeApproximationTemplate subclass, default="simple"
        Which tree approximation is going to be used for the comparisons.
    downsample : int, default=2
        The downsample factor for the downsampled tree approximation.
        Used only when `style="downsampled"`.

    Returns
    -------
    float
        The normalized unordered tree edit distance between `n1` and `n2`
    """
    parameters = (
        end_time,
        convert_style_to_number(style=style, downsample=downsample),
    )
    n1, n2 = sorted([n1, n2])
    lT._comparisons.setdefault(parameters, {})
    if lT._comparisons[parameters].get((n1, n2)):
        tmp = lT._comparisons[parameters][(n1, n2)]
    else:
        tmp = __unordereded_backtrace(
            lT, n1, n2, end_time, norm, style, downsample
        )
    btrc = tmp["alignment"]
    tree1, tree2 = tmp["trees"]
    _, times1 = tree1.tree
    _, times2 = tree2.tree
    (
        nodes1,
        adj1,
        corres1,
    ) = tree1.edist
    (
        nodes2,
        adj2,
        corres2,
    ) = tree2.edist
    delta_tmp = partial(
        tree1.delta,
        corres1=corres1,
        corres2=corres2,
        times1=times1,
        times2=times2,
    )

    if norm not in lT.norm_dict:
        raise ValueError(
            "Select a viable normalization method (max, sum, None)"
        )
    cost = btrc.cost(nodes1, nodes2, delta_tmp)
    norm_values = (tree1.get_norm(n1), tree2.get_norm(n2))
    if return_norms:
        return cost, norm_values
    return cost / lT.norm_dict[norm](norm_values)

unordered_tree_edit_distances_at_time_t

unordered_tree_edit_distances_at_time_t(
    lT: LineageTree,
    t: int,
    end_time: int | None = None,
    style: (
        Literal[
            "simple",
            "full",
            "downsampled",
            "normalized_simple",
        ]
        | type[TreeApproximationTemplate]
    ) = "simple",
    downsample: int = 2,
    norm: Literal["max", "sum", None] = "max",
    recompute: bool = False,
) -> dict[tuple[int, int], float]

Compute all the pairwise unordered tree edit distances from Zhang 996 between the trees spawned at time t

Parameters:

Name	Type	Description	Default
lT	LineageTree	The LineageTree instance.	required
t	int	time to look at	required
end_time	int	The final time point the comparison algorithm will take into account. If None all nodes will be taken into account.	None
style	('simple', 'full', 'downsampled', 'normalized_simple')	Which tree approximation is going to be used for the comparisons.	"simple"
downsample	int	The downsample factor for the downsampled tree approximation. Used only when style="downsampled".	2
norm	('max', 'sum')	The normalization method to use.	"max"
recompute	bool	If True, forces to recompute the distances	False

Returns:

Type	Description
dict mapping a tuple of tuple that contains 2 ints to float	a dictionary that maps a pair of node ids at time t to their unordered tree edit distance

Source code in src/lineagetree/measure/uted.py

def unordered_tree_edit_distances_at_time_t(
    lT: LineageTree,
    t: int,
    end_time: int | None = None,
    style: (
        Literal["simple", "full", "downsampled", "normalized_simple"]
        | type[TreeApproximationTemplate]
    ) = "simple",
    downsample: int = 2,
    norm: Literal["max", "sum", None] = "max",
    recompute: bool = False,
) -> dict[tuple[int, int], float]:
    """Compute all the pairwise unordered tree edit distances from Zhang 996 between the trees spawned at time `t`

    Parameters
    ----------
    lT : LineageTree
        The LineageTree instance.
    t : int
        time to look at
    end_time : int
        The final time point the comparison algorithm will take into account.
        If None all nodes will be taken into account.
    style : {"simple", "full", "downsampled", "normalized_simple"} or TreeApproximationTemplate subclass, default="simple"
        Which tree approximation is going to be used for the comparisons.
    downsample : int, default=2
        The downsample factor for the downsampled tree approximation.
        Used only when `style="downsampled"`.
    norm : {"max", "sum"}, default="max"
        The normalization method to use.
    recompute : bool, default=False
        If True, forces to recompute the distances

    Returns
    -------
    dict mapping a tuple of tuple that contains 2 ints to float
        a dictionary that maps a pair of node ids at time `t` to their unordered tree edit distance
    """
    if not hasattr(lT, "uted"):
        lT.uted = {}
    elif t in lT.uted and not recompute:
        return lT.uted[t]
    lT.uted[t] = {}
    roots = lT.time_nodes[t]
    for n1, n2 in combinations(roots, 2):
        key = tuple(sorted((n1, n2)))
        lT.uted[t][key] = lT.unordered_tree_edit_distance(
            n1,
            n2,
            end_time=end_time,
            style=style,
            downsample=downsample,
            norm=norm,
        )
    return lT.uted[t]