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

Question

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

pythonalgorithmigraphdirected-acyclic-graphs

12

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

编辑

对于无限路径的担忧

我所说的图实际上是一个带有单个根的有向无环图（DAG）。它表示一系列事件的单向级联，这些事件在级联的各个层次上可以分裂或汇合。正如我所说，这是一个单向图。还提供了图形不包含任何循环的信息。由于这两个原因，无限的路径列表是不可能的。

我在尝试什么？

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

- Boris Gorelik

1

只要这两个节点都能到达另一个节点，你就可以通过在到达目标节点之前重复遍历边来构建无限多的路径。因此，所有可能路径的无限列表不太可能对你有什么帮助。你真正想要找到的是什么，为什么？ - Jeremy W. Sherman

@Jeremy W. Sherman，我得提一下，我说的图实际上是一棵树。请看我的编辑，澄清了这种情况。 - Boris Gorelik

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jeremy W. Sherman · Accepted Answer

你正在寻找有向无环图（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是一个顶点索引的列表还是一个顶点对象本身的列表。我假设这些列表包含索引，以简化使用adjlist。因此，返回的路径是基于顶点索引的。如果您需要顶点对象而不是索引，则需要将其映射回顶点对象，或者修改代码来附加顶点而不是它的索引。