python – 创建“最小连接”有向无环图

看起来你真的想要一种有效去除所有冗余边缘的方法.这意味着您想要一次完成所有操作.这是一个不同的问题,但这是一个答案.我不相信networkx有内置的东西,但是找到一个可行的算法并不困难.

这个想法是因为它是一个DAG,所以有一些节点没有外边缘.从他们开始并处理它们.处理完所有内容后,其父母的子集中没有未经处理的子女.通过那些父母.重复.在每个阶段,未处理节点集是DAG,我们正在处理该DAG的“终端节点”.保证完成(如果原始网络是有限的).

在实现中,每当我们处理节点时,我们首先检查是否有任何子节点也是间接后代.如果是,请删除边缘.如果没有,请保留.当处理所有子项时,我们通过将其所有后代添加到父项的间接后代集来更新其父项的信息.如果处理了父项的所有子项,我们现在将它添加到列表中以供下一次迭代.

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

测试它：

G=nx.DiGraph()
G.add_nodes_from(['termsequence','trail'])
G.add_edges_from([('termsequence','multipletrails')])

print G.size()
>71
print G.order()
>47
descendants = {}  #for testing below
for node in G.nodes():
    descendants[node] = nx.descendants(G,node)

remove_redundant_edges(G)  #this removes the edges

print G.size()  #lots of edges gone
>56
print G.order() #no nodes changed.
>47
newdescendants = {}  #for comparison with above
for node in G.nodes():
    newdescendants[node] = nx.descendants(G,node)

for node in G.nodes():  
    if descendants[node] != newdescendants[node]:
        print 'descendants changed!!'   #all nodes have the same descendants
    for child in G.neighbors(node):  
        if len(list(nx.all_simple_paths(G,node,child)))>1:
            print 'bad edge'  #no alternate path exists from a node to its child.

这将是有效的：它必须在开始时处理每个节点以查看它是否是“结束”节点.然后它处理到达那些边缘的每个边缘并检查是否已经处理了该父节点的所有子节点.然后它看着那些父母和重复.

因此,它将处理每个边缘一次(包括扫视父节点),并且每个顶点将在开头处理一次,然后处理一次.