Menu
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 ?
976
A directed graph contains a directed spanning tree rooted at r if and only if all vertices in G are reachable from r. This condition can be easily tested in linear time. The proof of the following lemma is trivial as is left as an exercise.
To check if the graph is directed you can use nx.is_directed(G) , you can find the documentation here. 'weight' in G[1][2] # Returns true if an attribute called weight exists in the edge connecting nodes 1 and 2.
1. How to draw directed graphs using NetworkX in Python? By using the base class for directed graphs, DiGraph(), we are able to draw a directed graph with arrows to indicate the direction of edges.
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.
165
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
