3

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

您对如何解决这个问题有任何想法吗？

到目前为止，我的图是一个 networkx.Graph 实例，但我并不关心是否推荐了 igraph。

非常感谢！

4

5 回答 5

6

处理（并完全解决）这个问题的一个非常简单的方法是使用图的邻接矩阵A。A^L的第(i,j)个元素是长度为L的节点i和j之间的路径数。因此，如果您将所有这些j相加并保持i固定在n ，您将获得从长度为L的节点n发出的所有路径。

不幸的是，这也会计算循环路径。这些，很高兴，可以从 element 中找到A^L(n,n)，所以只需减去它。

所以你的最终答案是： Σj{A^L(n,j)} - A^L(n,n) .

注意事项：假设您正在寻找从节点 1 开始的长度为 5 的路径：此计算还将计算内部带有小循环的路径 like 1-2-3-2-4，其长度为 5 或 4，具体取决于您选择查看它的方式，所以要小心那。

于 2012-08-04T16:45:10.007 回答
2

我只想扩展 Lance Helsten 的出色回答：

深度限制搜索在一定深度（你称之为长度 L）内搜索特定节点，并在找到它时停止。如果您在他的回答中查看wiki 链接中的伪代码，您就会明白这一点：

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 的连续嵌套中记录所有单链路路径之后，只需将它们的乘积得到整个路径。这些数量为您提供了从节点开始的所需深度的路径数。

于 2012-08-04T16:29:59.670 回答
1

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

我快速搜索了图形算法来做到这一点，但没有找到任何东西。有一个图形算法列表 ( http://en.wikipedia.org/wiki/Category:Graph_algorithms ) 可能正是您正在寻找的。

于 2012-08-04T16:06:04.940 回答
1

这个解决方案在效率方面可能会有所提高，但它看起来很短并且利用了 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
于 2012-08-04T16:47:02.800 回答
1

这是我在阅读此处的答案后提出的另一个（相当幼稚的）实现：

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]
于 2017-05-23T21:16:14.863 回答