Spatial

lineagetree.measure

Functions:

Name	Description
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.

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