remove_cycle_edges_by_dfs.py 文件源码

def dfs_remove_back_edges(graph_file):
    '''
    0: white, not visited 
    1: grey, being visited
    2: black, already visited
    '''

    g = nx.read_edgelist(graph_file,create_using = nx.DiGraph(),nodetype = int)
    nodes_color = {}
    edges_to_be_removed = []
    for node in g.nodes_iter():
        nodes_color[node] = 0

    nodes_order = list(g.nodes_iter())
    nodes_order = np.random.permutation(nodes_order)
    num_dfs = 0
    for node in nodes_order:

        if nodes_color[node] == 0:
            num_dfs += 1
            dfs_visit_recursively(g,node,nodes_color,edges_to_be_removed)

    #print("number of nodes to start dfs: %d" % num_dfs)
    #print("number of back edges: %d" % len(edges_to_be_removed))
    edges_to_be_removed_file = graph_file[:len(graph_file)-6] + "_removed_by_dfs.edges"
    print("edges to be removed, saved in file: %s" % edges_to_be_removed_file)
    from file_io import write_pairs_to_file
    write_pairs_to_file(edges_to_be_removed,edges_to_be_removed_file)
    return edges_to_be_removed