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

Question

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

编辑

对无限数量路径的关注

我正在谈论的图实际上是具有单根的有向无环图（DAG）。它代表事件的单向级联，在级联的各个级别上，这些事件可以拆分或连接在一起。正如我所说，这是一个单向图。还假设该图不包含任何循环。由于这两个原因，无限的路径列表是不可能的。

我想做什么？

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

Answer 1

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

树始终是 DAG，但 DAG 并不总是树。不同之处在于，树的分支不允许连接，只能分开，而 DAG 的分支可以流在一起，只要不引入循环。

您的解决方案可以在 “Python 模式 - 实现”中找到 find_all_paths()图表。” 这需要进行一些调整才能与 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)

从文档中不清楚 adjlist 是顶点索引列表的列表还是顶点对象本身列表的列表。我假设列表包含索引以简化 adjlist 的使用。结果，返回的路径是按照顶点索引表示的。如果您需要这些，则必须将它们映射回顶点对象，或者调整代码以附加顶点而不是其索引。