带Networkx的有向图遍历

Question

我有一个大的有向图(networkx.DiGraph())，它由几棵有向树组成，每个树都有一个根。我还有一个函数，它接收一个特定的图，并输出它的一些节点。这是我想做的手术。

1. 给定一个任意有向林，并提供一个级别，在该给定级别上切割该图，并通过该函数运行每个新创建的子图。
2. 如果新创建的图的根显示在函数的输出中，那么继续从图中删除该子图。否则，将其所有后代从图表中删除。

我知道这很复杂，所以让我们通过一个示例运行。

为了简单起见，让我们的任意图是一棵树，而不是几棵树。我将选择nx.balanced_tree(2,4，create_using=nx.DiGraph())作为我的图形。图的编辑人员如下所示

(0,1),(0,2),(1,3),(1,4),(2,5),(2,6),(3,7),(3,8),(4,9),(4,10),(5,11),(5,12),(6,13),(6,14),
(7,15),(7,16),(8,17),(8,18),(9,19),(9,20),(10,21),(10,22),(11,23),(11,24),(12,25),(12,26),
(13,27),(13,28),(14,29),(14,30)

注意，0有0级，1-2有1级，3-6有2级，7-14有3级，15-30有4级.

假设我在我的程序中输入了3。然后，我将3级中的每个节点作为它自己的子图的根，并在我的程序中处理每个节点。因此，表示为

Subgraph 1: (7,15),(7,16)
Subgraph 2: (8,17),(8,18)
etc

将被输入到我的职能中。让函数输出7作为节点，而不是8。然后，节点7、15、16应该全部删除，节点17和18应该删除，而不是8。

我为这件事很复杂而道歉，但实际上，我认为这是一堆简单的步骤连在一起的。然而，我的循环方法绝对不是最优的。什么是最好的方法？

Answer 1

好的，我要介绍的解决方案有点麻烦，但我愿意接受更多优化的建议。

首先，我们将创建一个用于测试的虚拟图。

import networkx as nx
G = nx.balanced_tree(2,4,create_using=nx.DiGraph()) 

接下来，我们将使用networkx的树 API (使用最新版本)，并使用depth_limit属性提取树的深度n和n+1，其中n+1是用户输入的深度(因为它从1开始索引深度)。

T1 = nx.dfs_tree(G, source=0,depth_limit=3)   #here n=3
T1_edges = list(T.edges())
#[(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6), (3, 8), (3, 7), (4, 9), (4, 10), (5, 11), (5, 12), (6, 13), (6, 14)]

然后对深度n+1做同样的操作

T2 = nx.dfs_tree(G, source=0,depth_limit=4)
T2_edges =list(T2.edges())
#[(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6), (3, 8), (3, 7), (4, 9), (4, 10), (5, 11), (5, 12), (6, 13), (6, 14), (7, 16), (7, 15), (8, 17), (8, 18), (9, 19), (9, 20), (10, 21), (10, 22), (11, 24), (11, 23), (12, 25), (12, 26), (13, 27), (13, 28), (14, 29), (14, 30)]

现在取这两个列表的异或

edges_left = list(set(T1_edges).symmetric_difference(T2_edges))
#[(14, 30), (11, 23), (10, 21), (7, 16), (11, 24), (7, 15), (10, 22), (9, 20), (12, 25), (13, 28), (8, 17), (14, 29), (12, 26), (13, 27), (8, 18), (9, 19)]

这些是第3级的边缘。现在提取这些级别的节点。

nodes_at_level = set([x[0] for x in edges_left])
#{7, 8, 9, 10, 11, 12, 13, 14}

然后使用树在这些节点上提取树。

for n in nodes_at_level:
    tree = nx.bfs_tree(G, n)
    print tree.edges()              #Do whatever you want with those subgraphs

#[(7, 16), (7, 15)]
#[(8, 17), (8, 18)]
#[(9, 19), (9, 20)]
#[(10, 21), (10, 22)]
#[(11, 24), (11, 23)]
#[(12, 25), (12, 26)]
#[(13, 27), (13, 28)]
#[(14, 29), (14, 30)]