Spanning tree of directed graph with networkx

Question

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 ?

Fred Foo · Accepted Answer · 2014-05-08 09:20:02Z

6

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.

answered May 8, 2014 at 9:20

365k80 gold badges765 silver badges852 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

An to keep weights: [(i,o,w) for i,o,w in G.edges_iter(data=True) if ((i,o) in T.edges() or (o,i) in T.edges())]

Update G.edges_iter has been removed in networkx-2.