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

Question

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

编辑

对无限数量路径的关注

我所说的图实际上是一个带有单根的有向无环图(DAG).它代表了一个单向的级联事件,在级联的各个级别上,可以分裂或连接在一起.正如我所说,这是一个单向图.还规定图表不包含任何循环.由于这两个原因,无限的路径列表是不可能的.

我想做什么？

我的目标是找到从图形顶部(根)到给定节点的所有可能路径.

Answer 1

您正在寻找有向无环图(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)

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