rustworkx.steiner_tree#
- steiner_tree(graph, terminal_nodes, weight_fn, /)#
Return an approximation to the minimum Steiner tree of a graph.
The minimum tree of
graphwith regard to a set ofterminal_nodesis a tree withingraphthat spans those nodes and has a minimum size (measured as the sum of edge weights) amoung all such trees.The minimum steiner tree can be approximated by computing the minimum spanning tree of the subgraph of the metric closure of
graphinduced by the terminal nodes, where the metric closure ofgraphis the complete graph in which each edge is weighted by the shortest path distance between nodes ingraph.This algorithm [1] produces a tree whose weight is within a \((2 - (2 / t))\) factor of the weight of the optimal Steiner tree where \(t\) is the number of terminal nodes. The algorithm implemented here is due to [2] . It avoids computing all pairs shortest paths but rather reduces the problem to a single source shortest path and a minimum spanning tree problem.
- Parameters:
graph (PyGraph) – The graph to compute the minimum Steiner tree for
terminal_nodes (list) – The list of node indices for which the Steiner tree is to be computed for.
weight_fn – A callable object that will be passed an edge’s weight/data payload and expected to return a
float. For example, you can useweight_fn=floatto cast every weight as a float.
- Returns:
An approximation to the minimal steiner tree of
graphinduced byterminal_nodes.- Return type:
- Raises:
ValueError – when an edge weight with NaN or negative value is provided.