Supprimer des cycles d'un graphe multiple non dirigé à l'aide de Python networkx - python, graph, networkx

J'ai donc un graphe multiple non dirigé (dérivé deune ontologie), je souhaite supprimer les arêtes qui créent des cycles (mais pas toutes les arêtes, les constituants du graphe multiple doivent rester connectés). Y at-il un bon moyen de faire cela avec le paquet networkx?

Réponses:

Il n’existe peut-être pas un moyen unique de le faire pour votre graphique. Mais peut-être que trouver un Spanning Tree résoudra votre problème? https://networkx.github.io/documentation/latest/reference/generated/networkx.algorithms.mst.minimum_spanning_tree.html

Alors j'ai fini avec

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