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

Question

我在用Python绑定来操作igraph，想表示一个有向树。我想找到从图中的一个节点到另一个节点的所有可能路径。不过，我在igraph里找不到一个现成的函数来完成这个任务。

编辑

关于无限路径的担忧

我说的这个图其实是一个有向无环图（DAG），它有一个根节点。这个图表示的是一个单向的事件级联，在级联的不同层次上，事件可以分开或合并。正如我所说，这个图是单向的，并且不包含任何循环。因此，出现无限路径的情况是不可能的。

我想做什么？

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

Answer 1

你想要找出在一个有向无环图（DAG）中，从一个节点到另一个节点的所有路径。

树结构总是一个DAG，但DAG不一定是树。它们的区别在于，树的分支不能合并，只能分开，而DAG的分支可以汇聚在一起，只要不形成循环就可以。

你可以在“Python Patterns - Implementing Graphs.”中找到名为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）是一个包含顶点索引的列表的列表，还是一个包含顶点对象的列表的列表。我假设这些列表包含索引，以便简化邻接列表的使用。因此，返回的路径是以顶点索引的形式呈现的。如果你需要顶点对象，你需要将这些索引映射回顶点对象，或者调整代码以添加顶点本身，而不是它的索引。