Python networkxを使って、無向グラフからサイクルを削除する

Question

私は無向グラフ（オントロジから派生したもの）を持っていますので、サイクルを作成するエッジを削除したいのですが（マルチグラフの構成要素は接続されたままである）。 networkxパッケージでこれを行う良い方法はありますか？

Answer 1

グラフに固有の方法はありません。しかし、おそらくスパニングツリーを見つけることがあなたの問題を解決するだろうか？最小全域森 - https://networkx.github.io/documentation/latest/reference/generated/networkx.algorithms.mst.minimum_spanning_tree.html

Answer 2

は、だから私は

def as_spanning_trees(G): 
    """ 
    For a given graph with multiple sub graphs, find the components 
    and draw a spanning tree. 

    Returns a new Graph with components as spanning trees (i.e. without cycles). 

    Parameters 
    --------- 
    G:  - networkx.Graph 
    """ 

    G2 = nx.Graph() 
    # We find the connected constituents of the graph as subgraphs 
    graphs = nx.connected_component_subgraphs(G, copy=False) 

    # For each of these graphs we extract the spanning tree, removing the cycles 
    for g in graphs: 
     T = nx.minimum_spanning_tree(g) 
     G2.add_edges_from(T.edges()) 
     G2.add_nodes_from(T.nodes()) 

    return G2