Python igraph:获取有向图中的所有可能路径

Question

我正在使用igraph(Python),并希望获得有向图中两个节点之间的所有可能路径.我知道这个函数get_all_shortest_paths是最短的路径,但找不到一般的函数.

更新:

我的主要目标是获取这些路径中的所有节点,以便我可以获得这些节点的子图.

Answer 1

由于您在问题中提到您的最终目标是仅获取这些路径中的节点而不是路径本身,我认为您甚至不必计算路径.

Graphigraph中的对象有一个叫做的方法subcomponent.默认情况下,它为您提供与给定输入节点位于同一(弱连接)组件中的所有节点.但是,它也有一个mode论点.设置mode为时"out",它将为您提供可从某个节点访问的所有节点.设置mode为时"in",它将为您提供可以到达某个节点的所有节点.因此,您可能需要来自源顶点的可到达节点集和可以到达目标顶点的节点集的交集:

s=set(graph.subcomponent(source, mode="out"))
t=set(graph.subcomponent(target, mode="in"))
s.intersection(t)

这可能比计算所有路径更快.