<p>我之前的回答特别涉及到一个直接的问题,即是否有一个好的方法来测试单个边缘是否冗余。在</p>
<p>看起来你真的需要一种方法来有效地移除所有冗余的边。这意味着你需要一种同时完成所有任务的方法。这是一个不同的问题,但这里有一个答案。我不认为networkx有什么内置的东西,但它不难找到一个可行的算法。在</p>
<p>这是因为它是一个DAG,所以有些节点没有出边。从它们开始并处理它们。一旦所有这些都被处理,那么它们的一个子集就没有未被处理的子代。看看那些父母。重复。在每个阶段,未处理的节点集是一个DAG,我们正在处理该DAG的“结束节点”。它保证完成(如果原始网络是有限的)。在</p>
<p>在实现中,每当我们处理一个节点时,我们首先检查是否有任何子节点也是间接子代。如果是,请删除边。如果没有,就别管它。当处理所有子对象时,我们通过将其所有子对象添加到父对象的间接子对象集中来更新父对象的信息。如果父对象的所有子对象都被处理,我们现在将其添加到下一次迭代的列表中。在</p>
<pre><code>import networkx as nx
from collections import defaultdict
def remove_redundant_edges(G):
processed_child_count = defaultdict(int) #when all of a nodes children are processed, we'll add it to nodes_to_process
descendants = defaultdict(set) #all descendants of a node (including children)
out_degree = {node:G.out_degree(node) for node in G.nodes_iter()}
nodes_to_process = [node for node in G.nodes_iter() if out_degree[node]==0] #initially it's all nodes without children
while nodes_to_process:
next_nodes = []
for node in nodes_to_process:
'''when we enter this loop, the descendants of a node are known, except for direct children.'''
for child in G.neighbors(node):
if child in descendants[node]: #if the child is already an indirect descendant, delete the edge
G.remove_edge(node,child)
else: #otherwise add it to the descendants
descendants[node].add(child)
for predecessor in G.predecessors(node): #update all parents' indirect descendants
descendants[predecessor].update(descendants[node])
processed_child_count[predecessor]+=1 #we have processed one more child of this parent
if processed_child_count[predecessor] == out_degree[predecessor]: #if all children processed, add to list for next iteration.
next_nodes.append(predecessor)
nodes_to_process=next_nodes
</code></pre>
<p>要测试它:</p>
^{pr2}$
<p>这将是有效的:它必须在开始时处理每个节点,以确定它是否是“结束”节点。然后它处理到达这些边的每个边,并检查是否已处理该父对象的所有子对象。然后它看着那些父母,然后重复。在</p>
<p>因此,它将处理每条边一次(包括浏览父对象),每个顶点将在开始时处理一次,然后处理一次。在</p>