查找从节点到叶的所有路径

Question

我有一个巨大的networkx图形对象（1.8M节点）。我想用一个给定的节点输入这个对象，并检索从这个节点到一个叶（一个只有一条边连接的节点）的所有路径。顺便说一下，这些路径的长度不是固定的。在

我发现这样做的唯一方法是：

    leaves = [node for node in G.nodes() if len(G.edges(node)) == 1]
    for leaf in leaves:
        paths =  [x for x in nx.all_simple_paths(G, 1, leaf, cutoff=None)]

但是，循环所有可能的leave并在给定节点和叶之间寻找路径需要很长时间。在

有没有办法更快地得到结果？比如在本体论中使用ElasticSearch进行信息检索的爆炸？在

谢谢

Answer 1

将每个叶的边添加到新节点auxiliary。查找从给定节点到auxiliary的所有路径。然后删除每个路径的最后一步，就可以得到从给定节点到叶的所有路径。在