1

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?

arvyzu
  • 137
  • 2
  • 8

3 Answers3

2

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.

Community
  • 1
  • 1
Joel
  • 22,598
  • 6
  • 69
  • 93
  • Thanks for pointing to the right direction. But the algoritms given in the answers doesn't quite solve it. The closest thing to truth is AJed's b) variation but the problem with it is that the outcome pretty much depends on the node you start (maybe it's not a problem for unweighted graph). What I'm thinking now is like this: 1) check dijkstras shortest paths between all nodes 2) put all the nodes to a new graph 3) compute the mst (to remove cycles by breaking longest edge) – arvyzu Mar 27 '15 at 15:09
  • To be a bit pendantic: The problem is NP-hard, not NP-complete (it is not a decision problem). And there is no need to use a heuristic in practice. Most of the time, state-of-the-art Steiner tree solvers will give you optimal solutions within seconds, even for problems with tens out thousands of edges, see my answer below. – daniel Apr 23 '22 at 16:18
0

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)
Max Li
  • 5,069
  • 3
  • 23
  • 35
  • The problem is that I don't know "the nodes I need" (the intermediate nodes). I know all the graph nodes and their edges with weights and I know the "destination nodes" (the nodes that need to be connected). The whole **problem is** "the nodes I need" (or opposite - those that I don't need) besides Berlin, Kiel and Konstanz – arvyzu Mar 31 '15 at 08:54
0

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

daniel
  • 71
  • 2