steiner-tree

Fast lookup-table based computation of rectilinear Steiner minimal trees (RSMT).

This crate implements the 'FLUTE' algoritm and includes generating the lookup-tables as well as creating trees based on the lookup tables. Lookup-tables for up to 9 pins can be generated withing 16 seconds.

For higher pin count, a net-breaking heuristic is already implemented but yet inferior to the FLUTE 3.0 algorithm.

Benchmarks

A simple benchmarking infrastructure can be used with cargo bench.

TODOs

[ ] Implement net-breaking algorithms from FLUTE 3.0. [ ] Read/write lookup-tables. Generating lookup-tables of degree larger than 8 is too slow to do on the fly.

lib.rs:

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

• FLUTE, Chris Chu and Yiu-Chung Wong, 2008 (archived)