使用Python从节点n开始的长度为L的所有路径

Question

给定一个图G、一个节点n和一个长度L，我想收集所有从n出发的长度为L的非循环路径。

您有任何关于如何解决这个问题的想法吗？

目前，我的图是一个networkx.Graph实例，但如果推荐使用igraph，我并不是很在意。

非常感谢！

- Miquel Duran

---

你已经研究过这个了吗？你到目前为止尝试了什么？ - cyroxx

建议在发问时，您应该包括您所研究的内容，最好还附上一些源代码。http://stackoverflow.com/faq#questions - Abhranil Das

Answer 1

解决这个问题的一种非常简单的方法（并完全解决）是使用图的邻接矩阵A。 A^L的(i，j)元素是长度为L的节点i和j之间路径的数量。因此，如果您在保持i固定为n的情况下对所有j求和，则可以得到从节点n发出的所有长度为L的路径。

不幸的是，这也会计算循环路径。幸运的是，可以从元素A^L(n，n)中找到这些路径，所以只需将其减去即可。

因此，您的最终答案是：Σj {A^L(n，j)} - A^L(n，n)。

注意：假设您正在寻找从节点1开始的长度为5的路径：此计算还将计算小循环内的路径，例如1-2-3-2-4，其长度为5或4，具体取决于您如何看待它，请注意。

- Abhranil Das

Answer 2

我想进一步解释Lance Helsten的精彩回答：

深度限制搜索在特定深度（即你所说的长度L）内搜索特定节点，并在找到该节点时停止。如果你查看他的回答中维基链接中的伪代码，你就会明白这一点：

DLS(node, goal, depth) {
  if ( depth >= 0 ) {
    if ( node == goal )
      return node

    for each child in expand(node)
      DLS(child, goal, depth-1)
  }
}

然而在你的情况下，由于你要查找从一个节点出发长度为L的所有路径，因此你不会停止搜索。因此伪代码需要做如下修改：

DLS(node, depth) {
    for each child in expand(node) {
      record paths as [node, child]
      DLS(child, depth-1)
    }
}

完成记录DLS连续嵌套的所有单链路径后，只需对它们进行乘积运算即可得到整个路径。这些路径的数量就是从该节点开始所需深度的路径数。

- Abhranil Das

Answer 3

这个解决方案在效率方面可能需要改进，但它似乎非常简短并利用了networkx的功能：

G = nx.complete_graph(4)
n =  0
L = 3
result = []
for paths in (nx.all_simple_paths(G, n, target, L) for target in G.nodes_iter()):
    print(paths)
    result+=paths

- Michael Mauderer

Answer 4

使用深度限制搜索（http://en.wikipedia.org/wiki/Depth-limited_search），在路径上保留已访问节点的集合以检测循环。例如，您可以从节点n构建一棵树，包括所有节点和长度为L，然后修剪该树。

我快速搜索了一下图形算法，但没有找到任何东西。有一个图形算法列表（http://en.wikipedia.org/wiki/Category:Graph_algorithms），可能会有你要找的内容。

- Lance Helsten

Answer 5

在阅读了这里的答案后，我想出了另一种（相当天真）的实现方式：

def findAllPaths(node, childrenFn, depth, _depth=0, _parents={}):
    if _depth == depth - 1:
        # path found with desired length, create path and stop traversing
        path = []
        parent = node
        for i in xrange(depth):
            path.insert(0, parent)
            if not parent in _parents:
                continue
            parent = _parents[parent]
            if parent in path:
                return # this path is cyclic, forget
        yield path
        return

    for nb in childrenFn(node):
        _parents[nb] = node # keep track of where we came from
        for p in findAllPaths(nb, childrenFn, depth, _depth + 1, _parents):
            yield p


graph = {
    0: [1, 2],
    1: [4, 5],
    2: [3, 10],
    3: [8, 9],
    4: [6],
    5: [6],
    6: [7],
    7: [],
    8: [],
    9: [],
    10: [2] # cycle
}

for p in findAllPaths(0, lambda n: graph[n], depth=4):
    print(p)

# [0, 1, 4, 6]
# [0, 1, 5, 6]
# [0, 2, 3, 8]
# [0, 2, 3, 9]

- Bas Korsmit