有向树（igraph）中从一个节点到另一个节点的所有可能路径

  • Z时代
  • 2024-01-10
  • 分类：问答

我使用python绑定到igraph来表示有向树。我想找到从该图中一个节点到另一节点的所有可能路径。不幸的是，我在执行此任务的igraph中找不到现成的功能？

对无数路径的关注

我在说的图实际上是一个有根的有向无环图（DAG）。它表示事件的单向级联，可以在级联的各个级别上拆分或合并在一起。如我所说，这是一个单向图。还规定该图不包含任何循环。由于这两个原因，不可能有无限的路径列表。

我想做什么？

我的目标是找到从图的顶部（根）到给定节点的所有可能路径。

回答：

您正在寻找有向无环图（DAG）中一个节点与另一节点之间的所有路径。

树始终是DAG，但DAG并不总是树。区别在于，只要不引入任何循环，一棵树的分支就不允许连接，只能分开，而DAG的分支可以一起流动。

您可以find_all_paths()在“ Python模式-

实现图”中找到您的解决方案。这需要一些修改才能与igraph一起使用。我没有安装igraph，但使用模拟程序似乎可行：

def adjlist_find_paths(a, n, m, path=[]):
  "Find paths from node index n to m using adjacency list a."
  path = path + [n]
  if n == m:
    return [path]
  paths = []
  for child in a[n]:
    if child not in path:
      child_paths = adjlist_find_paths(a, child, m, path)
      for child_path in child_paths:
        paths.append(child_path)
  return paths
def paths_from_to(graph, source, dest):
  "Find paths in graph from vertex source to vertex dest."
  a = graph.get_adjlist()
  n = source.index
  m = dest.index
  return adjlist_find_paths(a, n, m)

从文档中尚不清楚附加列表是顶点索引列表的列表还是顶点对象本身的列表。我假设列表包含索引以简化使用邻接表。结果，返回的路径取决于顶点索引。如果需要，则必须将它们映射回顶点对象，或者修改代码以附加顶点而不是其索引。

以上是 有向树（igraph）中从一个节点到另一个节点的所有可能路径 的全部内容， 来源链接： utcz.com/qa/422122.html

回到顶部