使用python从节点n开始的所有长度为L的路径 [英] All paths of length L from node n using python

问题描述

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

Given a graph G, a node n and a length L, I'd like to collect all (non-cyclic) paths of length L that depart from n.

你知道如何处理这个问题吗?

Do you have any idea on how to approach this?

到目前为止，我的图是一个 networkx.Graph 实例，但我并不在乎，例如推荐使用 igraph.

By now, I my graph is a networkx.Graph instance, but I do not really care if e.g. igraph is recommended.

非常感谢！

推荐答案

我只想扩展 Lance Helsten 的精彩回答:

I would just like to expand on Lance Helsten's excellent answer:

深度限制搜索在特定深度(您称之为长度 L)内搜索特定节点，并在找到时停止.如果您在他的回答中查看 wiki 链接 中的伪代码，您会会明白的:

The depth-limited search searches for a particular node within a certain depth (what you're calling the length L), and stops when it finds it. If you will take a look at the pseudocode in the wiki link in his answer, you'll understand this:

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

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

然而，在您的情况下，当您从一个节点寻找长度为 L 的所有路径时，您不会在任何地方停下来.所以伪代码必须修改为:

In your case, however, as you're looking for all paths of length L from a node, you will not stop anywhere. So the pseudocode must be modified to:

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

在您完成从 DLS 的连续嵌套记录所有单链接路径后，只需取它们的乘积即可获得整个路径.这些的数量为您提供了从节点开始的所需深度的路径数量.

After you're done with recording all the single-link paths from successive nests of the DLS, just take a product of them to get the entire path. The number of these gives you the number of paths of the required depth starting from the node.

这篇关于使用python从节点n开始的所有长度为L的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！