spine.math.graph

Numba JIT compiled implementation of graph routines.

In particular, this module supports the CSR data structure and derived methods, which tremendously speeds up graph construction and computation in Numba.

Functions

connected_components(edge_index, num_nodes)

Find connected components.

csr_graph(edge_index, num_nodes[, directed])

Construct the Compressed Sparse Row (CSR) representation of a sparse matrix based on a list of nodes and edges.

dfs(graph, visited, node, component, comp_idx)

Does a depth-first search and builds a connected component.

dfs_iterative(graph, visited, start_node, ...)

Does a depth-first search and builds a connected component.

radius_graph(x, radius[, metric_id, p])

Builds an undirected radius graph.

union_find(edge_index, count[, return_inverse])

Numba implementation of the Union-Find algorithm.

Classes

CSRGraph(*args, **kwargs)

Numba-enabled compressed Sparse Row (CSR) representation of a sparse matrix.
class spine.math.graph.CSRGraph(*args, **kwargs)[source]

Numba-enabled compressed Sparse Row (CSR) representation of a sparse matrix.

neighbors

(E,) List of node neighbors in a compressed array

Type:

np.ndarray

offsets

(N + 1,) Per-node slicing boundaries to query each node neighborhood

Type:

np.ndarray

num_nodes

Number of nodes in the graph, N

Type:

int

Methods

num_neighbors(node_id)

Returns the number of neighbors of a node.

class_type
class_type = jitclass.CSRGraph#79d09e8a2ad0<num_nodes:int64,neighbors:array(int64, 1d, A),offsets:array(int64, 1d, A)>
spine.math.graph.csr_graph(edge_index: ndarray, num_nodes: int, directed: bool = True) → CSRGraph[source]

Construct the Compressed Sparse Row (CSR) representation of a sparse matrix based on a list of nodes and edges.

Parameters:

  • edge_index (np.ndarray) – (E, 2) List of active edge indices in the graph

  • num_nodes (int) – Number of nodes in the graph, N

  • directed (bool) – Whether the input graph is directed or not

spine.math.graph.connected_components(edge_index: ndarray, num_nodes: int, min_samples: int = 1, directed: bool = True) → ndarray[source]

Find connected components.

Parameters:

  • edge_index (np.ndarray) – (E, 2) List of active edge indices in the graph

  • num_nodes (int) – Number of nodes in the graph, N

  • directed (bool, default True) – Whether the input graph is directed or not

Returns:

(N,) Cluster label associated with each node

Return type:

np.ndarray

spine.math.graph.dfs(graph: CSRGraph, visited: ndarray, node: int, component: ndarray, comp_idx: ndarray) → None[source]

Does a depth-first search and builds a connected component.

Parameters:

  • graph (CSRGraph) – CSR representation of a graph

  • visited (np.ndarray) – (N,) Boolean array which specifies whether a node has been visited.

  • node (int) – Current node index

  • component (np.ndarray) – (N,) Current component (padded)

  • comp_idx (np.ndarray) – Current component index (pointer)

Notes

This implementation is recursive, which is the fastest implementation but silently throws segmentation faults if the maximum recursion depth is reached. The dfs_iterative() function is safer, but slightly slower.

spine.math.graph.dfs_iterative(graph: CSRGraph, visited: ndarray, start_node: int, component: ndarray, comp_idx: ndarray) → None[source]

Does a depth-first search and builds a connected component.

Parameters:

  • graph (CSRGraph) – CSR representation of a graph

  • visited (np.ndarray) – (N,) Boolean array which specifies whether a node has been visited.

  • start_node (int) – Starting node index

  • component (np.ndarray) – (N,) Current component (padded)

  • comp_idx (np.ndarray) – Current component index (pointer)

Notes

This implementation is iterative and does not suffer from the recursion depth maximum issue which affects the recursive version, at a small cost to the overall execution speed.

spine.math.graph.radius_graph(x: ndarray, radius: float, metric_id: int = 2, p: float = 2.0) → ndarray[source]

Builds an undirected radius graph.

This function generates a list of edges in a graph which connects all nodes which live within some radius R of each other.

Parameters:

  • x (np.ndarray) – (N, 3) array of node coordinates

  • radius (float) – Radius within which to build connections in the graph

  • metric_id (int, default 2 (Euclidean)) – Distance metric enumerator

  • p (float, default 2.) – p-norm factor for the Minkowski metric, if used

Returns:

(E, 2) array of edges in the radius graph

Return type:

np.ndarray

spine.math.graph.union_find(edge_index: ndarray, count: int, return_inverse: bool = True) → tuple[ndarray, dict[int, ndarray]][source]

Numba implementation of the Union-Find algorithm.

This function assigns a group to each node in a graph, provided a set of edges connecting the nodes together.

Parameters:

  • edge_index (np.ndarray) – (E, 2) List of edges (sparse adjacency matrix)

  • count (int) – Number of nodes in the graph, C

  • return_inverse (bool, default True) – Make sure the group IDs range from 0 to N_groups-1

Returns:

  • np.ndarray – (C,) Group assignments for each of the nodes in the graph

  • Dict[int, np.ndarray] – Dictionary which maps groups to indexes