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

Question

我不确定我的问题的正确术语是什么，所以我只会解释我想做的事情。我有一个有向图，删除节点后我希望所有独立相关的节点也被删除。

这是一个示例：

比如说，我删除节点“11”，我希望删除节点“2”同样（在我自己的示例中，它们将是 2 以下的节点，现在也必须删除），因为它不再连接到主图。请注意，不应删除节点“9”或“10”，因为节点“8”和“3”仍然连接到它们。

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

任何有关如何执行此操作的帮助或建议都会很棒。

谢谢！

Answer 1

我假设以下条件成立：

• 该图是非循环的。您在评论中提到了这一点，但我想明确表示这是一个起始假设。
• 有一组已知的根节点。我们需要有某种方法来知道哪些节点始终被认为是可达的，并且我假设（以某种方式）该信息是已知的。
• 初始图不包含任何多余的节点。也就是说，如果初始图包含任何应该删除的节点，那么它们就已经被删除了。这允许算法通过维护每个节点都应该存在的不变量来工作。

如果是这种情况，则给定初始设置，节点位于图中的唯一原因是

1. 该节点位于根可达节点集中，或者
2. 该节点具有位于根可达节点集中的父节点。节点。

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

鉴于此设置，一旦删除节点，您将需要扫描该节点的所有子节点，以查看其中是否有任何节点没有其他父节点将它们保留在图中。由于我们假设图中唯一的节点是需要存在的节点，因此如果已删除节点的子节点至少有一个其他父节点，那么它仍然应该在图中。否则，需要删除该节点。因此，执行删除步骤的一种方法是以下递归算法：

• 对于要删除的节点的每个子节点：
  • 如果该节点只有一个父节点：（它一定是我们要删除的节点）
    • 从图中递归地删除该节点。
• 从图中删除指定的节点。

不过，这可能不是一个直接实现的好算法，因为如果您有一个大图，所涉及的递归可能会变得相当深。因此，您可能希望使用如下工作列表算法来实现它：

• 创建一个工作列表 W。
• 将要删除的节点 v 添加到 W。
• 当 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()