graphing.py 文件源码

def cleanup_fixed_graph(pruned):
    # remove cycles
    while True:
        cycles = networkx.cycle_basis(pruned)
        if len(cycles) == 0:
            break

        to_delete = None
        worst_val = None
        for cycle in cycles:
            cur_worst_val = None
            cur_worst = None
            for a,b,data in pruned.edges(cycle, data=True):
                cur_val = data["p"]
                if cur_worst_val is None or cur_val < cur_worst_val:
                    cur_worst_val = cur_val
                    cur_worst = (a,b)
            if worst_val is None or cur_worst_val < worst_val:
                worst_val = cur_worst_val
                to_delete = cur_worst

        pruned.remove_edge(*to_delete)

    # remove all cis-edges at the ends of subgraphs
    degrees = pruned.degree()
    to_delete = []
    for node, degree in dict(degrees).items():
        if degree == 1:
            edge = list(pruned.edges([node], data=True))[0]
            if edge[2]["kind"]=="facing":
                to_delete.append(node)
    pruned.remove_nodes_from(to_delete)

    # remove unconnected nodes
    pruned.remove_nodes_from([node for (node, degree) in dict(pruned.degree()).items() if degree==0])

    return pruned