Function steiner_tree

pub fn steiner_tree<N, E, Ix>(
    graph: &UnGraph<N, E, Ix>,
    terminals: &[NodeIndex<Ix>],
) -> StableGraph<N, E, Undirected, Ix>
where
    N: Default + Clone + Eq + Hash + Debug,
    E: Copy + Eq + Ord + Measure + BoundedMeasure,
    Ix: IndexType,

[Generic] Steiner Tree algorithm.

Computes the Steiner tree of an undirected graph given a set of terminal nodes via Kou’s algorithm. Implementation details mirrors NetworkX implementation.

Returns a Graph representing the Steiner tree of the input graph.

Complexity

Time complexity is O(|S| |V|²). where |V| the number of vertices (i.e nodes) and |E| the number of edges.

Example

use petgraph::Graph;
use petgraph::algo::steiner_tree::steiner_tree;
use petgraph::graph::UnGraph;
let mut graph = UnGraph::<(), i32>::default();
let a = graph.add_node(());
let b = graph.add_node(());
let c = graph.add_node(());
let d = graph.add_node(());
let e = graph.add_node(());
let f = graph.add_node(());
graph.extend_with_edges([
    (a, b, 7),
    (a, f, 6),
    (b, c, 1),
    (b, f, 5),
    (c, d, 1),
    (c, e, 3),
    (d, e, 1),
    (d, f, 4),
    (e, f, 10),
]);
let terminals = vec![a, c, e, f];
let tree = steiner_tree(&graph, &terminals);
assert_eq!(tree.edge_weights().sum::<i32>(), 12);