我使用python binding到igraph来表示有向树。我想找到所有可能的路径,从一个节点在该图到另一个节点。不幸的是,我在igraph中找不到执行此任务的现成函数?
编辑
对无穷多条路径的关注
我所说的图实际上是一个有向无环图(DAG),只有一个根。它表示事件的单向级联,在级联的各个级别上,可以将其拆分或连接在一起。如我所说,这是一个单向图。还提供了图形不包含任何循环的条件。由于这两个原因,无限的路径列表是不可能的。
我想做什么?
我的目标是找到从图的顶部(根)到给定节点的所有可能路径。
Tags:
在有向无环图(DAG)中查找一个节点和另一个节点之间的所有路径。
树永远是一棵树,但它并不总是一棵树。不同的是,树的分支不允许连接,只允许分割,而DAG的分支可以一起流动,只要不引入循环。
您的解决方案可以在"Python Patterns - Implementing Graphs."中找到
find_all_paths()
,这需要对igraph进行一些调整。我没有安装igraph,但使用mocks,这似乎可以工作:从文档中不清楚adjlist是顶点索引列表还是顶点对象本身列表。我假设列表中包含了使用adjlist简化的索引。因此,返回的路径是以顶点索引为基础的。如果需要,则必须将这些对象映射回顶点对象,或者调整代码以附加顶点而不是其索引。
相关问题 更多 >
编程相关推荐