introduce_cycles_to_DAG.py 文件源码

def add_cycle_edges_by_path(g,number_of_edges,path_length = 5):
    number = 0
    num_nodes = g.number_of_nodes()
    nodes = g.nodes()
    extra_edges = []
    while number < number_of_edges:
        u,v = np.random.randint(0,num_nodes,2)
        u = nodes[u]
        v = nodes[v]
        if nx.has_path(g,u,v):
            length = nx.shortest_path_length(g,source = u,target = v)
            if length <= path_length:
                extra_edges.append((v,u))
                number += 1
        if nx.has_path(g,v,u):
            length = nx.shortest_path_length(g,source = v,target = u)
            if length <= path_length:
                extra_edges.append((u,v))
                number += 1
    print("# extra edges added with path length <= %d: %d" % (path_length,len(extra_edges)))
    return extra_edges