Crate steiner_tree
source · [−]Expand description
Fast lookup-table based computation of rectilinear Steiner minimal trees (RSMT).
Example
use steiner_tree;
// Generate a lookup-table for up to 3 points.
// This is an expensive computation.
// Up to 8 points, this runs in less than a second on a laptop from 2011.
// For 9 points takes 16 seconds.
let lut = steiner_tree::gen_lut::gen_full_lut(3);
let points = vec![(1, 2).into(), (3, 4).into(), (5, 6).into()];
// Up steiner trees with up to 5 pins can be computed by direct lookup.
// This method will panic if it is called with too many points.
let (small_tree, small_tree_weight) = lut.rsmt_low_degree(points);
// If the number of points exceeds the size of the lookup-table, a net-breaking heuristic will be used.
let points = vec![(1, 2).into(), (3, 4).into(), (5, 6).into(), (7, 8).into()];
// An accuracy value must be provided for the heuristic.
// Larger values lead to better results but also to longer computations.
let accuracy = 3;
let (medium_tree, medium_tree_weight) = lut.rsmt_medium_degree(points, accuracy);References
Modules
Generate the lookup-table.
Data structure of the lookup table.
Convert the lookup-table to and from a compact binary representation.
Structs
Point in the Euclidean plane.