Python igraph：在有向图中获取所有可能的路径 [英] Python igraph: get all possible paths in a directed graph

问题描述

我使用igraph（Python）并希望在有向图中的两个节点之间获得所有可能的路径。我知道函数 get_all_shortest_paths ，它用于最短路径，但找不到一个通用路径。

更新：

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

<因为你在你的问题中提到你的最终目标是只得到这些路径中的节点而不是路径本身，我认为你甚至不需要必须计算路径。

在igraph中的 Graph 对象有一个名为子组件的方法。默认情况下，它为您提供与给定输入节点处于相同（弱连接）组件的所有节点。但是，它也有一个模式参数。当您将 mode 设置为out时，它会为您提供从某个节点到达的所有节点。当您在中将 mode 设置为时，它会为您提供到达某个节点的所有节点。因此，您可能需要从源顶点到可以到达目标顶点的一组可达节点的交集：



  s = set（graph.subcomponent（source，mode =out））
t = set（graph.subcomponent（target，mode =in））
 s.intersection t）
  

无论如何，这可能比计算所有路径要快。

I am using igraph (Python) and would like to get all possible paths between two nodes in a directed graph. I am aware of the function get_all_shortest_paths, which is for shortest paths, but could not find a general one.

Update:

My main goal is to get all nodes in these paths, so that I can then get a subgraph of these nodes.

解决方案

Since you mentioned in your question that your ultimate goal is to get only the nodes that are in these paths and not the paths themselves, I think you don't even have to calculate the paths.

The Graph object in igraph has a method called subcomponent. By default, it gives you all the nodes that are in the same (weakly connected) component as a given input node. However, it also has a mode argument. When you set mode to "out", it will give you all the nodes that are reachable from a certain node. When you set mode to "in", it will give you all the nodes from where you can reach a certain node. So, you'll probably need the intersection of the set of reachable nodes from your source vertex and the set of nodes that can reach your target vertex:

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

This is probably way faster than calculating all the paths anyway.

这篇关于Python igraph：在有向图中获取所有可能的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！