APGL（另一个Python图形库）在宽度优先搜索后设置子图大小

Question

我一直在使用apgl0.8.1。分析一个巨大网络（4000万个节点）的库。我尝试了apgl，因为它可以很好地处理scipy稀疏矩阵，现在我可以将稀疏矩阵加载到内存中执行分析。我有兴趣在广度优先搜索分析之后，得到一个设计尺寸为全网的子图。在

我在读熊猫的邻接列表来建立一个稀疏矩阵。{（示例，称为cd1>节点的网络}：

1 5 1
5 1 1
1 2 1
5 6 1
6 7 1
7 5 1
5 2 1
2 3 1
3 4 1
4 2 1 
3 8 1
9 10 1
1 11 1
11 12 1
12 13 1
13 1 1
5 14 1

这是我使用的示例代码：

^{pr2}$

返回：

bfs = [ 5  1  2  6 14 11  3  7 12  4  8 13]
subgraph = SparseGraph: vertices 5, edges 6, directed, vertex storage GeneralVertexList, edge storage <class 'scipy.sparse.csr.csr_matrix'>

所以我给结果子图设置了5个节点的限制。但不管搜索的形状如何，节点都是从第一个节点选择到第五个节点。我的意思是，广度优先搜索算法是寻找邻居的邻居等等，我想设置一个限制，包括在最后选择的节点的所有最终邻居级别进行搜索。在本例中，子图包含BFS数组的前五个节点，因此：

子图=[5 1 2 6 14]

但是我还想包括节点7（从节点5开始完成邻居级别）和3（在节点2级别完成搜索）。因此，得到的节点数组应该是：

子图=[5 1 2 3 6 7 14]

任何帮助都将不胜感激。在

编辑： 我想做的是从一个随机节点开始寻找整个图的一个子图，然后执行一个BFS算法，直到子图的大小不同，例如500万、1000万和2000万个节点。我想在停止之前完成每一级的节点邻居，所以不管节点的数量是500万还是500万和100，如果最后100个节点需要完成一级搜索中找到的最后一个节点的所有邻居。在

Answer 1

BFS和DFS在无向图上操作，这些图可能是无环的（即树），也可能不是。在

在操作过程中，这两种算法都可能遇到后边缘。也就是说，如果遍历这些边，算法会考虑到已经访问过的节点。在

这些边及其末端的节点（通常）不会在BFS或DFS的输出中报告。在

Networkx（https://networkx.github.io/）包含^{}，它返回一个迭代器，该迭代器具有每条边的特征。在

就您的代码而言：

limit = 5
subgraph = graph.subgraph(bfs[:limit])

这不会搜索“length”5的所有BFS子图。由于bfs[:5]，它将始终查看BFS输出的前5个条目。在

如果您正在寻找循环，也许您可以使用不同的算法（For example，这还是来自Networkx），或者从原始网络提取子图，然后使用DFS标记其边缘，或者enumerate all of its simplest paths并尝试处理它们。在

希望这有帮助。在

补充信息：

（我也在这里考虑你的这个老问题：https://stackoverflow.com/questions/29169022/scipy-depth-breadth-first-search-tree-size-limit）

你想从主图G（V，E）中提取一个适当的子图U（W，C），其中U的阶数远小于G的阶数（| U |<；| G |），而且U是G的BFS，从G（V，E）的某个节点V_i开始。在

有两种方法可以做到这一点：

1. 写你自己的BFS，你可以添加计数器的深度 遍历和遍历节点，并使用它们来中断 任何你喜欢的算法。由于您拥有的节点数量非常多，您应该研究迭代版本，而不是递归版本的算法。有关更多信息，请参见：Way to go from recursion to iteration以及某种程度上的http://en.wikipedia.org/wiki/Depth-limited_search。这种方法将更有效，因为BFS不必遍历整个图。

2. 截断现有BFS的输出并使用剩余节点 作为你下一步的出发点。

在任何一种情况下，您的算法都将包含一个迭代步骤，并且最终会显示如下所示（选项2）：

^{pr2}$

当然，不同的树之间会有相当大的重叠。在

希望这有帮助。在