networkx - Bridges

networkx - bridge

• network theory에서 bridge란, “해당 edge가 끊어지면, graph의 connected component가 증가하는 edge”를 말합니다. 즉, edge (u, v)가 끊어진다면, node u, v는 어떠한 방법으로도 서로 도달할 수가 없는 것이죠.
• 매우 간단해서 코딩하는 것도 쉽고, 또한 chain_decomposition을 사용해서 더 쉽게 할 수도 있습니다만, 이해가 쉽도록 간단하게 구현한다면 다음과 같습니다.
• 즉, 그냥 edge를 잘랐을 때, connected component가 증가한다면 그건 edge다, 라는 것을 그대로 사용한 것이죠.

import networkx as nx 

def bridges(G): 
    brg_lst = []
    Before_num_con_comp = nx.number_connected_components(G)
    for e in G.edges(): 
        G_cp = G.copy() 
        G_cp.remove_edge(*e)
        After_num_con_comp = nx.number_connected_components(G_cp)
        if After_num_con_comp > Before_num_con_comp:
            brg_lst.append(e)
    return brg_lst

referencde