Entfernen von Zyklen aus einem ungerichteten Multi-Graphen mit Python-Netzwerkx

Question

So habe ich eine ungerichtete Multi-Grafik (abgeleitet von einer Ontologie), ich möchte die Kanten, die Zyklen erstellen (aber nicht alle Kanten, müssen die Bestandteile der Multi-Graphen zu entfernen) bleiben verbunden). Gibt es eine gute Möglichkeit, dies mit dem Paket networkx zu tun?

Answer 1

Möglicherweise gibt es keine einzigartige Möglichkeit, dies für Ihr Diagramm zu tun. Aber vielleicht finden Sie einen aufspannenden Baum, um Ihr Problem zu lösen? https://networkx.github.io/documentation/latest/reference/generated/networkx.algorithms.mst.minimum_spanning_tree.html

Answer 2

So landete ich mit

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