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

问题描述

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

<现在，我的图形是一个networkx.Graph实例，但我不在乎是否例如

非常感谢！

解决方案

就像扩展Lance Helsten的出色答案一样：

深度限制搜索特定节点内的特定节点（称为长度L），并在发现它时停止。如果您在他的回答中查看 wiki链接中的伪代码，我会明白这一点：$ b​​
$ b pre code DLS（节点，目标，深度）{
if（depth> = 0）{
if（节点==目标）
返回节点

为expand（节点）中的每个子节点
DLS（子节点，目标节点，深度-1）
}
}

然而，就你而言，当你在寻找所有路径长度为L的节点，你不会在任何地方停下来。因此，伪代码必须修改为：对于expand中的每个子节点（节点，深度），

  DLS ）{
将路径记录为[node，child] 
 DLS（child，depth-1）
} 
} 
  

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

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?

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

Thanks a lot!

解决方案

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

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)
  }
}

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)
    }
}

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屋！