代码之家 › 专栏 › 技术社区 › Rushabh Mehta

用networkx实现有向图遍历

networkx pandas python

Rushabh Mehta · 技术社区 · 8 年前

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

给定一个任意的有向林和一个给定的级别,在该级别上剪切图,并通过函数运行每个新创建的子图。
如果新创建的图的根显示在函数的输出中,则继续从图中删除该子图。否则,请从图形中删除其所有子体。

我知道这很复杂,所以我们来做一个样本。

为了简单起见,让我们的任意图是一棵树,而不是几棵。我将选择nx.balanced_树(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。

我为这件事的复杂性道歉,但实际上,我认为这是一系列简单的步骤串联在一起。然而,我的循环方法绝对不是最优的。什么是最好的方法?

1 回复 | 直到 8 年前

Gambit1614 8 年前

好吧,我要介绍的解决方案有点老套,但我愿意接受更多优化的建议。

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

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

下一步,我们会 dfs_tree 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}

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

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