Compute distance from a set of seed nodes using fast breadth-first search.

This function computes the shortest path distance from a set of seed nodes to all other nodes in the graph using a breadth-first search (BFS) approach. It iteratively expands the frontier of reached nodes until all reachable nodes have been assigned a distance or the maximum number of iterations is reached.

Usage

distance_from_node_set(cg, seed_nodes, max_iter = 40L, verbose = FALSE)

Arguments

cg

A CellGraph object.

seed_nodes

A character vector of node names to use as seeds for distance calculation.

max_iter

An integer specifying the maximum number of iterations (distance levels) to compute. Default is 40.

verbose

A logical value indicating whether to print progress messages during the computation. Default is FALSE.

Value

A CellGraph object with an added distance_from_seed column in the node data, indicating the shortest path distance from the nearest seed node.

Examples

library(dplyr)
library(tidygraph)
cg <- ReadPNA_Seurat(minimal_pna_pxl_file(), verbose = FALSE) %>%
  LoadCellGraphs(cells = colnames(.)[4], add_layout = TRUE, verbose = FALSE) %>%
  CellGraphs() %>%
  .[[4]]

# Compute distances from the seed set, here we just pick a random point
start_set <- cg@cellgraph %N>%
  pull(name) %>%
  head(1)
cg <- distance_from_node_set(cg, start_set)

# Visualize the distance on the 3D layout
xyz <- cg@layout$wpmds_3d %>%
  mutate(d = cg@cellgraph %N>% pull(distance_from_seed))

plotly::plot_ly(
  data = xyz,
  x = ~x, y = ~y, z = ~z,
  color = ~d,
  colors = c("lightgrey", "mistyrose", "red", "darkred", "black"),
  type = "scatter3d",
  mode = "markers",
  marker = list(size = 2)
)