从一个节点的所有可能路径中的另一个向树（的igraph） [英] All possible paths from one node to another in a directed tree (igraph)

问题描述

我用蟒蛇结合的 IGRAPH 重新present有向树。我想找到该图到另一个从一个节点的所有可能路径。不幸的是，我无法找到一个现成的使用功能的igraph执行这个任务？

I use python binding to igraph to represent a directed tree. I would like to find all possible paths from one node in that graph to another one. Unfortunately, I couldn't find a ready to use function in igraph that performs this task?

修改

的路径无限多的关注的

图我说的其实是一个向无环图（DAG）有一个根。它重新presents事件，不同层次的级联，既可以拆分或结合在一起的单向级联。正如我所说，这是一个单向的曲线图。它也提供了曲线图不包含任何循环。由于这两个原因，路径无限的名单，是不可能的。

the graph I'm talking about is actually a directed acyclic graph (DAG) with a single root. It represents a unidirectional cascade of events that, on various levels of the cascade, can either split or join together. As I said, this is a unidirectional graph. It is also provided that the graph does not contain any cycles. Due to these two reasons, infinite list of paths, is impossible.

我究竟想干什么？的

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

My goal is to find all the possible paths that lead from the top of the graph (the root) to the given node.

推荐答案

您正在寻找一个有向无环图的一个节点，另一间的所有路径（DAG）。

You are looking for all paths between one node and another in a directed acyclic graph (DAG).

一个树总是一个DAG，但DAG并不总是一棵树。不同的是，一棵树的树枝不准参加，只能鸿沟，而DAG的分支可以流动起来，所以只要没有周期进行了介绍。

A tree is always a DAG, but a DAG isn't always a tree. The difference is that a tree's branches are not allowed to join, only divide, while a DAG's branches can flow together, so long as no cycles are introduced.

您的解决方案可以发现 find_all_paths（）在 蟒蛇纹 - 实施图。这需要一点点适应与IGRAPH使用。我没有IGRAPH安装，但使用嘲弄，这似乎工作：

Your solution can be found as find_all_paths() in "Python Patterns - Implementing Graphs." This requires a little adaptation to use with igraph. I don't have igraph installed, but using mocks, this seems to work:

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简化。其结果，返回的路径是在顶点索引的条款。你将有你需要的，而不是要回这些映射到顶点的对象，或调整code附加顶点，而不是它的索引。

It was unclear from the documentation whether the adjlist is a list of lists of vertex indices or a list of list of vertex objects themselves. I assumed that the lists contained indices to simplify using the adjlist. As a result, the returned paths are in terms of vertex indices. You will have to map these back to vertex objects if you need those instead, or adapt the code to append the vertex rather than its index.

这篇关于从一个节点的所有可能路径中的另一个向树（的igraph）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！