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

Question

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

以下是一个例子：

假设我删除节点'11'，我希望节点'2'也被删除（在我的示例中，节点下面的节点也必须被删除），因为它不再与主图连接。请注意，节点'9'或'10'不应被删除，因为节点'8'和'3'仍然与它们相连。

我正在使用Python库networkx。我搜索了文档，但我不确定术语，因此不知道这被称为什么。如果可能，我希望使用库提供的函数，而不是通过我的图形创建自己的递归（因为我的图形非常大）。

任何关于如何做到这一点的帮助或建议都将是很好的。

谢谢！

- Lostsoul

---

你的图表是否总是无环的，还是可能包含了环路？ - templatetypedef

它不包含任何循环。每个节点基本上是一组与下一天观察相连的日常观察列表。有时，我会发现错误的观察结果，因此当我删除它时，我希望从该已删除节点派生的其他节点也被删除。 - Lostsoul

Answer 1

我假设以下内容是正确的：

• 图是无环的。你在评论中提到了这一点，但我想明确说明这是一个起始假设。
• 已知一组根节点。我们需要知道哪些节点始终可达，我假设（以某种方式）这些信息已知。
• 初始图不包含任何多余的节点。也就是说，如果初始图包含应该删除的任何节点，则它们已经被删除。这使算法能够通过保持每个节点都存在的不变性来工作。

如果是这种情况，那么给定初始设置，节点在图中的原因只可能是:

1. 该节点在根可达节点集中，或者
2. 该节点有一个父节点在根可达节点集中。

因此，每当您从图中删除一个节点时，可能需要删除的唯一节点是该节点的后代。如果要删除的节点位于根集中，则可能需要修剪大量图形，如果要删除的节点是具有少量自己的后代的后代节点，则可能需要做很少的工作。

在此设置的基础上，一旦删除了一个节点，您将需要扫描该节点的所有子节点，以查看它们是否有其他父节点可以将它们保留在图中。由于我们假设只有需要存在的节点才在图中，因此如果要删除的节点的子节点具有至少一个其他父节点，则它应该仍然存在于图中。否则，该节点需要被删除。因此，执行删除步骤的一种方法是使用以下递归算法：

• 对于要删除的节点的每个子节点：
  • 如果该节点恰好有一个父节点：（它必须是我们即将删除的节点）
    • 从图形中递归删除该节点。
• 从图中删除指定的节点。

然而，这可能不是直接实现的好算法，因为涉及的递归可能会很深，如果您有一个大的图形。因此，您可能希望使用像这样的工作列表算法来实现它：

• 创建一个工作列表 W。
• 将要删除的节点 v 添加到 W 中。
• 当 W 不为空时：
  • 从 W 中删除第一个条目；称其为 w。
  • 对于 w 的每个子节点：
    • 如果该子节点只有一个父节点，则将其添加到 W 中。
  • 从图中删除 w。

这最终会成为最坏情况的O(m)时间，其中m是图中边的数量，因为理论上每个边都必须被扫描。然而，如果您的图中存在一些冗余，则可能会快得多。

希望这可以帮到您！

- templatetypedef

---

非常出色的答案，谢谢你，它帮助我理解了很多正在发生的事情。我的问题是：如果我不知道初始图形是否有冗余节点，这会产生重大影响吗？由于我正在观察一个已经进行了许多年的过程，我开始记录观察结果，并希望在注意到错误时加以清理。 - Lostsoul

@Lostsoul- 如果您不确定初始图是否有多余的节点，您可以始终运行图搜索以确定哪些节点是不必要的。例如，您可以从您知道有效的每个节点（“根集”）开始运行深度优先搜索，标记遇到的每个节点。然后，您可以从图中删除未标记的所有节点。这实际上非常高效（如果使用深度优先搜索，则需要时间与图中节点和边的数量成比例），并将为您设置稍后的算法。 - templatetypedef

@Lostsoul- 如果你以后有任何有关图形或图形算法的问题，随时问吧！ - templatetypedef

@templateypedef 非常感谢您！我认为我明白了你的意思，但我会在代码实验中尝试一下，希望能看到它的效果。感谢您的帮助！另外，当我开始研究算法时，我曾问过一个关于暴力算法是否可扩展的问题，而你为我解答了。你不仅教会了我动态规划的思想，还让我对算法非常感兴趣（事实上，我已经把你的答案打印出来并经常参考）。最近你还帮助了我解决图问题，所以我无法感谢你帮我奠定了坚实的基础！非常感谢你，你太棒了！ - Lostsoul

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

- Max Li