Function steiner_tree

pub fn steiner_tree<G, F, E>(
    graph: G,
    terminal_nodes: &[G::NodeId],
    weight_fn: F,
) -> Result<Option<SteinerTreeResult>, E>
where
    G: IntoEdges + NodeIndexable + Sync + EdgeCount + IntoNodeReferences + EdgeIndexable + Visitable + NodeCount,
    G::NodeId: Eq + Hash + Send,
    G::EdgeId: Eq + Hash + Send,
    F: FnMut(G::EdgeRef) -> Result<f64, E>,

Return an approximation to the minimum Steiner tree of a graph.

The minimum tree of graph with regard to a set of terminal_nodes is a tree within graph that spans those nodes and has a minimum size (measured as the sum of edge weights) among all such trees.

The minimum steiner tree can be approximated by computing the minimum spanning tree of the subgraph of the metric closure of graph induced by the terminal nodes, where the metric closure of graph is the complete graph in which each edge is weighted by the shortest path distance between nodes in graph.

This algorithm by Kou, Markowsky, and Berman¹ 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 Mehlhorn². It avoids computing all pairs shortest paths but rather reduces the problem to a single source shortest path and a minimum spanning tree problem.

Arguments

• graph - The input graph to compute the Steiner tree of
• terminal_nodes - The terminal nodes of the Steiner tree
• weight_fn - A callable weight function that will be passed an edge reference for each edge in the graph and it is expected to return a Result<f64> which if it doesn’t error represents the weight of that edge.

Returns

A custom struct that contains a set of nodes and edges and None if the graph is disconnected relative to the terminal nodes.

Example

use std::convert::Infallible;

use rustworkx_core::petgraph::Graph;
use rustworkx_core::petgraph::graph::NodeIndex;
use rustworkx_core::petgraph::Undirected;
use rustworkx_core::petgraph::graph::EdgeReference;
use rustworkx_core::petgraph::visit::{IntoEdgeReferences, EdgeRef};

use rustworkx_core::steiner_tree::steiner_tree;

let input_graph = Graph::<(), u8, Undirected>::from_edges(&[
    (0, 1, 10),
    (1, 2, 10),
    (2, 3, 10),
    (3, 4, 10),
    (4, 5, 10),
    (1, 6, 1),
    (6, 4, 1),
]);

let weight_fn = |e: EdgeReference<u8>| -> Result<f64, Infallible> {
   Ok(*e.weight() as f64)
};
let terminal_nodes = vec![
    NodeIndex::new(0),
    NodeIndex::new(1),
    NodeIndex::new(2),
    NodeIndex::new(3),
    NodeIndex::new(4),
    NodeIndex::new(5),
];

let tree = steiner_tree(&input_graph, &terminal_nodes, weight_fn).unwrap().unwrap();

---

1. Kou, Markowsky & Berman, “A fast algorithm for Steiner trees” Acta Informatica 15, 141–145 (1981) https://link.springer.com/article/10.1007/BF00288961 ↩

2. Kurt Mehlhorn, “A faster approximation algorithm for the Steiner problem in graphs” Information Processing Letters 27(3), 125-128 (1987) https://doi.org/10.1016/0020-0190(88)90066-X ↩