如何使用networkx删除有向图所有相关的节点？ [英] How to delete all related nodes in a directed graph using networkx?

问题描述

我不知道确切把握正确的术语是什么，我的问题所以我就解释一下我想做的事情。我有向图，我删除一个节点，我希望所有的独立相关节点被同时删除。在

I'm not sure exactly sure what the correct terminology is for my question so I'll just explain what I want to do. I have a directed graph and after I delete a node I want all independently related nodes to be removed as well.

下面是一个例子：

我说，我删除节点'11'，我想节点2被删除，以及（在我自己的例子，他们将在2个节点，现在将不得不被删除也一样），因为它不是连接到主图形了。注意，节点9或10不应该被删除，因为节点'8'和'3'连接到它们仍然

Say, I delete node '11', I want node '2' to be deleted as well(and in my own example, they'll be nodes under 2 that will now have to be deleted as well) because its not connected to the main graph anymore. Note, that node '9' or '10' should not be deleted because node '8' and '3' connect to them still.

我使用Python库networkx。我搜索的文件，但我不知道的术语，所以我不知道这个叫。如果可能的话，我会希望使用该库提供的功能，通过图形比创建自己的递归（我的图是相当大的）。

I'm using the python library networkx. I searched the documentation but I'm not sure of the terminology so I'm not sure what this is called. If possible, I would want to use a function provided by the library than create my own recursion through the graph(as my graph is quite large).

任何关于如何做到这一点帮助或建议，将是巨大的。

Any help or suggestions on how to do this would be great.

谢谢！

推荐答案

我假定满足下列条件：

• 图为无环。您在您的评论中提到这一点，但我想作出明确这是一个起始的假设。
• 有一组已知的根节点的。我们必须知道什么节点总是被认为是可到达的路，而且我认为（在某种程度上），该信息是已知的。
• 的初始图中不包含任何多余的节点。也就是说，如果在初始图表中包含应该删除任何节点，他们已经被删除。这允许算法通过保持不变的，每个节点应该在那里工作。

• The graph is acyclic. You mentioned this in your comment, but I'd like to make explicit that this is a starting assumption.
• There is a known set of root nodes. We need to have some way of knowing what nodes are always considered reachable, and I assume that (somehow) this information is known.
• The initial graph does not contain any superfluous nodes. That is, if the initial graph contains any nodes that should be deleted, they've already been deleted. This allows the algorithm to work by maintaining the invariant that every node should be there.

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

If this is the case, then given an initial setup, the only reason that a node is in the graph would be either

1. 的节点是根可达的节点集，或
2. 节点有父是根可达节点集合。

因此​​，任何时候删除从图中的一个节点，可能需要被删除，唯一的节点是节点的后代。如果删除的节点是根集，你可能需要修剪了很多图表，如果您删除的节点是一些它自己的后代的后代的节点，那么你可能需要做的很少。

Consequently, any time you delete a node from the graph, the only nodes that might need to be deleted are that node's descendants. If the node that you remove is in the root set, you may need to prune a lot of the graph, and if the node that you remove is a descendant node with few of its own descendants, then you might need to do very little.

鉴于此设置中，一旦一个节点被删除，您将需要扫描所有该节点的孩子，看看其中是否有任何其他家长，将他们留在该图。因为我们假设图中的唯一的节点是需要在那里节点，如果一个删除节点的孩子具有至少一个其他的父，那么它应该仍然是在图中。否则，该节点需要被移除。做删除步骤的一种方式，因此，将下面的递归算法：

Given this setup, once a node is deleted, you would need to scan all of that node's children to see if any of them have no other parents that would keep them in the graph. Since we assume that the only nodes in the graph are nodes that need to be there, if the child of a deleted node has at least one other parent, then it should still be in the graph. Otherwise, that node needs to be removed. One way to do the deletion step, therefore, would be the following recursive algorithm:

• 对于每一个要删除的节点的子节点：
  • 如果该节点有且只有一个父：（必须是我们将要删除的节点）
    • 递归从图中删除该节点。
    • For each of children of the node to delete:
      • If that node has exactly one parent: (it must be the node that we're about to delete)
        • Recursively remove that node from the graph.

        这可能不是一个很好的算法直接实施，不过，因为涉及的递归可能会得到pretty的深，如果你有一个大图。因此，你可能想使用一个工作列表算法，像这样实现它：

        This is probably not a good algorithm to implement directly, though, since the recursion involved might get pretty deep if you have a large graph. Thus you might want to implement it using a worklist algorithm like this one:

        • 创建一个工作列表W的
        • 添加V，节点删除，为W。
        • 当W是不是空的：
          • 删除与W的第一个条目;称之为瓦特
          • 对于每一个W酒店的儿童：
            • 如果发现孩子只有一个家长，将其添加至W。
            • Create a worklist W.
            • Add v, the node to delete, to W.
            • While W is not empty:
              • Remove the first entry from W; call it w.
              • For each of w's children:
                • If that child has just one parent, add it to W.

                此结束是最坏情况为O（米）的时间，其中m是在图中的边数，因为在理论上每边将不得不进行扫描。但是，它可能会快很多，假设你的图有一些重复的吧。

                This ends up being worst-case O(m) time, where m is the number of edges in the graph, since in theory every edge would have to be scanned. However, it could be much faster, assuming that your graph has some redundancies in it.

                希望这有助于！

                这篇关于如何使用networkx删除有向图所有相关的节点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！