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

Question

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

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

现在，我的图形是一个networkx.Graph实例，但是我并不在乎是否建议使用igraph。

非常感谢！

Answer 1

一个非常简单的方式来处理（和完全解决）此问题是使用邻接矩阵甲图形的。的（I，J）个的元件甲^大号是节点之间的路径的数量我和Ĵ长度的大号。因此，如果将所有j求和并保持i固定为n，则所有路径都从长度为L的节点n发出。

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

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

温馨提示：假设您正在从节点1寻找长度为5的路径，此计算还将计算内部的小循环路径（如）1-2-3-2-4，该路径的长度取决于您选择的观看方式，其长度为5或4，因此请注意那。