如何使用networkx删除有向图中的所有相关节点？

Question

我不确定我的问题的正确术语是什么,所以我只是解释一下我想做什么.我有一个有向图,在我删除一个节点后,我想要删除所有独立相关的节点.

这是一个例子:

比如说,我删除节点'11',我也希望删除节点'2'(在我自己的例子中,它们将是2以下的节点,现在也必须删除)因为它没有连接到主图了.注意,不应删除节点"9"或"10",因为节点"8"和"3"仍然连接到它们.

我正在使用python库networkx.我搜索了文档,但我不确定术语,所以我不确定这是什么.如果可能的话,我想使用库提供的函数,而不是通过图形创建我自己的递归(因为我的图非常大).

任何有关如何做到这一点的帮助或建议都会很棒.

谢谢!

Answer 1

我假设以下是真的:

• 该图是非循环的.你在评论中提到了这一点,但我想明确指出这是一个开始的假设.
• 有一组已知的根节点.我们需要有一些方法来了解哪些节点总是被认为是可达的,我认为(不知何故)这些信息是已知的.
• 初始图形不包含任何多余的节点.也就是说,如果初始图包含应删除的任何节点,则它们已被删除.这允许算法通过维持每个节点应该存在的不变量来工作.

如果是这种情况,那么给定初始设置,节点在图中的唯一原因是

1. 节点位于根可达的节点集中,或
2. 该节点的父节点位于根可达节点集中.

因此,每次从图中删除节点时,可能需要删除的唯一节点就是该节点的后代.如果您删除的节点位于根集中,则可能需要修剪大量图形,如果删除的节点是后代节点,其后代很少,那么您可能需要做很少的事情.

在给定此设置的情况下,一旦删除了一个节点,您将需要扫描该节点的所有子节点,以查看它们中是否有其他父节点将其保留在图形中.由于我们假设图中的唯一节点是需要存在的节点,如果已删除节点的子节点至少有一个其他父节点,则它应该仍然在图中.否则,需要删除该节点.因此,执行删除步骤的一种方法是以下递归算法:

• 对于要删除的节点的每个子节点:
  • 如果该节点只有一个父节点:(它必须是我们要删除的节点)
    • 从图中递归删除该节点.
• 从图中删除指定的节点.

但是,这可能不是一个直接实现的好算法,因为如果你有一个大图,所涉及的递归可能会变得非常深.因此,您可能希望使用像这样的工作列表算法来实现它:

• 创建工作清单W.
• 将要删除的节点v添加到W.
• W不为空时:
  • 从W中删除第一个条目; 叫它w.
  • 对于每个孩子:
    • 如果该孩子只有一个父母,请将其添加到W.
  • 从图表中删除w.

这最终是最坏情况下的O(m)时间,其中m是图中边缘的数量,因为理论上每个边缘都必须被扫描.但是,假设您的图表中有一些冗余,它可能会快得多.

希望这可以帮助!

Answer 2

让我为您提供解决您任务的python networkX代码：

import networkx as nx
import matplotlib.pyplot as plt#for the purpose of drawing the graphs
DG=nx.DiGraph()
DG.add_edges_from([(3,8),(3,10),(5,11),(7,11),(7,8),(11,2),(11,9),(11,10),(8,9)])
DG.remove_node(11)

令人惊讶的是，connected_components方法在有向图上不起作用，因此我们将图变为无向图，找出未连接的节点，然后将它们从有向图中删除

UG=DG.to_undirected()
not_connected_nodes=[]
for component in nx.connected_components(UG):
    if len(component)==1:#if it's not connected, there's only one node inside
        not_connected_nodes.append(component[0])
for node in not_connected_nodes:
    DG.remove_node(node)#delete non-connected nodes

如果要查看结果，请在脚本中添加以下两行：

nx.draw(DG)
plt.show()