- steiner_tree(G, terminal_nodes, weight='weight', method=None)#
Return an approximation to the minimum Steiner tree of a graph.
The minimum Steiner tree of
Gw.r.t a set of
terminal_nodes(also S) is a tree within
Gthat spans those nodes and has minimum size (sum of edge weights) among all such trees.
The approximation algorithm is specified with the
methodkeyword argument. All three available algorithms produce a tree whose weight is within a (2 - (2 / l)) factor of the weight of the optimal Steiner tree, where l is the minimum number of leaf nodes across all possible Steiner trees.
kou (runtime \(O(|S| |V|^2)\)) computes the minimum spanning tree of
the subgraph of the metric closure of G induced by the terminal nodes, where the metric closure of G is the complete graph in which each edge is weighted by the shortest path distance between the nodes in G.
mehlhorn (runtime \(O(|E|+|V|\log|V|)\)) modifies Kou et al.’s
algorithm, beginning by finding the closest terminal node for each non-terminal. This data is used to create a complete graph containing only the terminal nodes, in which edge is weighted with the shortest path distance between them. The algorithm then proceeds in the same way as Kou et al..
- GNetworkX graph
A list of terminal nodes for which minimum steiner tree is to be found.
- weightstring (default = ‘weight’)
Use the edge attribute specified by this string as the edge weight. Any edge attribute not present defaults to 1.
- methodstring, optional (default = ‘kou’)
The algorithm to use to approximate the Steiner tree. Supported options: ‘kou’, ‘mehlhorn’. Other inputs produce a ValueError.
- NetworkX graph
Approximation to the minimum steiner tree of
For multigraphs, the edge between two nodes with minimum weight is the edge put into the Steiner tree.
Steiner_tree_problem on Wikipedia. https://en.wikipedia.org/wiki/Steiner_tree_problem
Kou, L., G. Markowsky, and L. Berman. 1981. ‘A Fast Algorithm for Steiner Trees’. Acta Informatica 15 (2): 141–45. https://doi.org/10.1007/BF00288961.