Python networkx 模块，cycle_basis() 实例源码

def is_serial_system(self):
        for c in nx.cycle_basis(self.Network):
            if len(c) > 1:
                return True
        return False

def findloops(self, G):
        loops = []
        for c in nx.cycle_basis(G):
            if len(c) > 1:
                loops.append(c)
        return loops

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

def correctLoops(code, loops_graph, charge_type):
    while nx.cycle_basis(loops_graph) != []:
        cycle = nx.cycle_basis(loops_graph)[0]
        loop = path.Path(cycle)
        for data in code.Primal.nodes():
            if loop.contains_points([data]) == [True]:
                charge = code.Primal.node[data]['charge'][charge_type]
                code.Primal.node[data]['charge'][charge_type] = (charge + 1)%2

        l = len(cycle)
        for i in range(l):
            n1, n2 = cycle[i], cycle[(i+1)%l]
            loops_graph.remove_edge(*(n1,n2))

    return code, loops_graph

def find_cycles(sub_network, weight='x_pu'):
    """
    Find all cycles in the sub_network and record them in sub_network.C.

    networkx collects the cycles with more than 2 edges; then the 2-edge cycles
    from the MultiGraph must be collected separately (for cases where there
    are multiple lines between the same pairs of buses).

    Cycles with infinite impedance are skipped.
    """
    branches_bus0 = sub_network.branches()["bus0"]
    branches_i = branches_bus0.index

    #reduce to a non-multi-graph for cycles with > 2 edges
    mgraph = sub_network.graph(weight=weight)
    graph = nx.OrderedGraph(mgraph)

    cycles = nx.cycle_basis(graph)

    #number of 2-edge cycles
    num_multi = len(mgraph.edges()) - len(graph.edges())

    sub_network.C = dok_matrix((len(branches_bus0),len(cycles)+num_multi))

    for j,cycle in enumerate(cycles):

        for i in range(len(cycle)):
            branch = next(iterkeys(mgraph[cycle[i]][cycle[(i+1)%len(cycle)]]))
            branch_i = branches_i.get_loc(branch)
            sign = +1 if branches_bus0.iat[branch_i] == cycle[i] else -1
            sub_network.C[branch_i,j] += sign

    #counter for multis
    c = len(cycles)

    #add multi-graph 2-edge cycles for multiple branches between same pairs of buses
    for u,v in graph.edges():
        bs = list(mgraph[u][v].keys())
        if len(bs) > 1:
            first = bs[0]
            first_i = branches_i.get_loc(first)
            for b in bs[1:]:
                b_i = branches_i.get_loc(b)
                sign = -1 if branches_bus0.iat[b_i] == branches_bus0.iat[first_i] else +1
                sub_network.C[first_i,c] = 1
                sub_network.C[b_i,c] = sign
                c+=1