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

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

你的解决方案是 find_all_paths() 在里面 "Python Patterns - Implementing Graphs." 这需要对igraph稍加修改。我没有安装igraph,但使用mocks,这似乎可以工作:

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简化的索引。因此,返回的路径是以顶点索引为基础的。如果需要,则必须将这些对象映射回顶点对象,或者调整代码以附加顶点而不是其索引。