Удаление циклов из неориентированного мультиграфа с использованием 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