Search code examples
pythongraphnetworkxminimum-spanning-treesubgraph

Spanning tree of directed graph with networkx

I have a directed graph G in networkx and I want to get the minimum spanning tree of it. I do:

 T = nx.algorithms.minimum_spanning_tree( G.to_undirected()  )

This is undirected and I would like to restore the directions but I don't know how to do it. I tried:

G[T.edges()]

This last line looks very pythonic but this is not the way networkx works, apparently... Does anyone knows how to do it?

In other words: How can I get the subgraph of a directed tree given the (undirected) edges ?

Solution

  • You can get the edges in G that appear in the MST T with a simple comprehension:

    E = set(T.edges())  # optimization
[e for e in G.edges() if e in E or reversed(e) in E]

    You can then build a new graph from this.