No path in compute cell knn paths

[YannMauge]

Dear Flecs team,
First thank you for your great work !

I'm reporting here an error I had while doing the Tutorial notebook with the base dataset GSE72857. In some configurations, NetworkX seems unable to compute a path between 2 cells. This error arised frequently to me when computing on UMAP but not on PCA.

# Extract trajectories from progenitor cells to either unsorted cells or one of the KO populations
unsorted_shortest_paths = compute_cell_knn_paths(adata, cmp_cells, unsorted_cells, n_bins=10)

# Add to the adata object
adata.uns["unsorted_shortest_paths"] = unsorted_shortest_paths

1%|█▏                                                                                         | 41/3045 [00:00<00:23, 130.01it/s]

---------------------------------------------------------------------------
NetworkXNoPath                            Traceback (most recent call last)
Cell In[27], line 2
      1 # Extract trajectories from progenitor cells to either unsorted cells or one of the KO populations
----> 2 unsorted_shortest_paths = compute_cell_knn_paths(adata, cmp_cells, unsorted_cells, n_bins=10)
      4 # Add to the adata object
      5 adata.uns["unsorted_shortest_paths"] = unsorted_shortest_paths

File ~/anaconda3/envs/flecs/lib/python3.12/site-packages/flecs/sc/utils.py:255, in compute_cell_knn_paths(_adata, source_cells, target_cells, n_bins, option, n_pca)
    253 # Compute shortest paths
    254 for match in tqdm(ot_mapping.T):
--> 255     env_shortest_paths[match[1]] = nx.shortest_path(knn_graph,
    256                                                     source=match[0],
    257                                                     target=match[1],
    258                                                     weight="weight")
    260 if n_bins is not None:
    261     # We subsample the paths to make sure they are of length n_bins
    262     env_shortest_paths = {k: v for k, v in env_shortest_paths.items() if len(v) >= n_bins}

File ~/anaconda3/envs/flecs/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/generic.py:167, in shortest_path(G, source, target, weight, method)
    165     paths = nx.bidirectional_shortest_path(G, source, target)
    166 elif method == "dijkstra":
--> 167     _, paths = nx.bidirectional_dijkstra(G, source, target, weight)
    168 else:  # method == 'bellman-ford':
    169     paths = nx.bellman_ford_path(G, source, target, weight)

File ~/anaconda3/envs/flecs/lib/python3.12/site-packages/networkx/algorithms/shortest_paths/weighted.py:2374, in bidirectional_dijkstra(G, source, target, weight)
   2372                     revpath.reverse()
   2373                     finalpath = paths[0][w] + revpath[1:]
-> 2374 raise nx.NetworkXNoPath(f"No path between {source} and {target}.")

NetworkXNoPath: No path between 1182 and 6543.

As far as I understand this is caused by a few cells getting isolated. Maybe it would be worth to check the path and discard isolated cells (e.g. with nx.has_path(knn_graph, source=match[0], target=match[1]) ).