CODEWITHSUNDEEP
pythonnetworkxminimum-spanning-tree
arvyzu
arvyzu

Reputation: 147

Networkx shortest tree algorithm

I have a undirected weighted graph G with a set of nodes and weighted edges.

I want to know if there is a method implemented in networkx to find a minimum spanning tree in a graph between given nodes (e.g. nx.steiner_tree(G, ['Berlin', 'Kiel', 'Munster', 'Nurnberg'])) (aparently there is none?)

I don't have reputation points to post images. The link to similar image could be: Map (A3, C1, C5, E4)

What I'm thinking:

  1. check dijkstras shortest paths between all destination nodes;
  2. put all the nodes (intermediate and destinations) and edges to a new graph V;
  3. compute the mst on V (to remove cycles by breaking longest edge);

Maybe there are better ways(corectness- and computation- wise)? Because this approach does pretty bad with three destination nodes and becomes better with more nodes.

P.S. My graph is planar (it can be drawn on paper so that edges would not intersect). So maybe some kind of spring/force (like in d3 visualisation) algorithm could help?

Upvotes: 2

Views: 3146

Answers (3)

daniel
daniel

Reputation: 71

As pointed out already, this is the Steiner tree problem in graphs. There is a Steiner tree algorithm in networkx:

https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.approximation.steinertree.steiner_tree.html

However, it only gives you an approximate solution, and it is also rather slow. For state-of-the-art solvers, see the section "External Links" under:

https://en.wikipedia.org/wiki/Steiner_tree_problem

Upvotes: 0

Max Li
Max Li

Reputation: 5199

In networkx there's a standard Kruskal algorithm implemented with undirected weighted graph as input. The function is called "minimum_spanning_tree"

I propose you build a subgraph that contains the nodes you need and then let the Kruskal algorithm run on it.

import nertworkx as nx
H=G.subgraph(['Berlin','Kiel', 'Konstanz'])
MST=nx.minimum_spanning_tree(H)

Upvotes: 0

Joel
Joel

Reputation: 23827

As I understand your question, you're trying to find the lowest weight connected component that contains a set of nodes. This is the Steiner tree in graphs problem. It is NP complete. You're probably best off taking some sort of heuristic based on the specific case you are studying.

For two nodes, the approach to do this is Dijkstra's algorithm- it's fastest if you expand around both nodes until the two shells intersect. For three nodes I suspect a version of Dijkstra's algorithm where you expand around each of the nodes will give some good results, but I don't see how to make sure you're getting the best.

I've found another question for this, which has several decent answers (the posted question had an unweighted graph so it's different, but the algorithms given in the answers are appropriate for weighted). There are some good ones beyond just the accepted answer.

Upvotes: 3

Related Questions