计算节点到一组节点的距离的快速方法。

Question

对于无向/无权图中的每个节点(粉色节点)，我想计算到给定连接节点集(红色节点)的最近距离。重要的是，计算速度要快，也适用于大型图(~4000个节点)和大量连接节点。请参见下面的示例。哪种算法/图库最适合我做这个？

我已经尝试使用NetworkX - shortest_path_length 来实现类似的功能，但速度太慢了。特别是对于一个大型连接的红节点集合。

import networkx as nx

all_distances = []
for node in red_nodes:
    distances = nx.shortest_path_length(graph, source=node) # compute distances to all nodes in the graph from the source node
    all_distances.append(distances)
shortest_distances = filter_for_shortest_distance(all_distances)

这是一个关于如何访问我正在使用的图形的示例。红色节点可以是图中任意连通节点的子集。

# Import navis
import navis

# Load one of the example neurons
sk = navis.example_neurons(n=1, kind='skeleton')

# Inspect the neuron graph
graph = sk.get_graph_nx()

- Jakob Troidl

---

图形总是一棵树吗（就像绘图中的那样）？如果不是，它里面还有其他结构吗（模块化）？红色/粉色节点的比率是多少？这个问题会受益于示例数据，最好是多个网络。 - Paul Brodersen

图形很可能总是一棵树。红色/粉色比例各异，但平均来说，图形包含1/4的红节点和3/4的粉色节点。我添加了一个访问我正在使用的图形的示例。 - Jakob Troidl

所以这是一个树突树？那么，您可以通过在靠近细胞体的红色节点上方剪切树来将问题立即简化为一个纯粉色子树和混合子树。纯粉红色子树中的所有粉色节点都将具有切点处的红色节点作为它们最接近的红色节点。 - Paul Brodersen

仅供参考（来自一位神经科学家）：红色是什么，粉色又是什么？ - Paul Brodersen

此外，值得提醒其他用户的是，navis 中的 TreeNeurons 是有向、无权网络。 - Paul Brodersen

对于混合树，从每个粉色节点开始，我会递归调用 nx.predecessors，直到遇到红色节点（因为红色节点是混合树的根节点，所以这是有保证的）。 - Paul Brodersen

Answer 1

你可以使用迪杰斯特拉算法（Dijkstra's algorithm）来处理多个起点：

import networkx as nx
import matplotlib.pyplot as plt
import typing

Node = int

def get_distances(graph: nx.Graph, red_nodes: typing.Set[Node]) -> typing.Dict[Node, int]:
    node_to_distance = {}
    node_to_neighbours = graph.adj

    # fill node_to_distance for red nodes and init set of reachable nodes
    reachable = set()
    for node in red_nodes:
        node_to_distance[node] = 0
        for neighbour in node_to_neighbours[node]:
            if neighbour not in red_nodes:
                node_to_distance[neighbour] = 1
                reachable.add(neighbour)

    # for each reachable node add neighbours as reachable nodes with greater distance
    while reachable:
        node = reachable.pop()
        distance = node_to_distance[node]
        for neighbour in node_to_neighbours[node]:
            if distance + 1 < node_to_distance.get(neighbour, len(graph)):
                node_to_distance[neighbour] = distance + 1
                reachable.add(neighbour)

    return node_to_distance

def check():
    g = nx.petersen_graph()
    red_nodes = {1, 2}
    node_to_distance = get_distances(g, red_nodes=red_nodes)
    plt.subplot(121)
    node_colors = ["red" if node in red_nodes else "yellow" for node in g.nodes()]
    nx.draw(g, with_labels=True, node_color=node_colors, labels=node_to_distance)
    plt.show()

check()

我已在一个包含40000个节点的图上进行了测试，计算10000个红色节点之间的距离只需要42毫秒。

- Trizalio