steiner_tree/lib.rs
1// SPDX-FileCopyrightText: 2022 Thomas Kramer <code@tkramer.ch>
2//
3// SPDX-License-Identifier: GPL-3.0-or-later
4
5//! Fast lookup-table based computation of rectilinear Steiner minimal trees (RSMT).
6//!
7//! # Example
8//!
9//! ```
10//! use steiner_tree;
11//!
12//! // Generate a lookup-table for up to 3 points.
13//! // This is an expensive computation.
14//! // Up to 8 points, this runs in less than a second on a laptop from 2011.
15//! // For 9 points takes 16 seconds.
16//! let lut = steiner_tree::gen_lut::gen_full_lut(3);
17//!
18//! let points = vec![(1, 2).into(), (3, 4).into(), (5, 6).into()];
19//!
20//! // Up steiner trees with up to 5 pins can be computed by direct lookup.
21//! // This method will panic if it is called with too many points.
22//! let (small_tree, small_tree_weight) = lut.rsmt_low_degree(points);
23//!
24//! // If the number of points exceeds the size of the lookup-table, a net-breaking heuristic will be used.
25//! let points = vec![(1, 2).into(), (3, 4).into(), (5, 6).into(), (7, 8).into()];
26//! // An accuracy value must be provided for the heuristic.
27//! // Larger values lead to better results but also to longer computations.
28//! let accuracy = 3;
29//! let (medium_tree, medium_tree_weight) = lut.rsmt_medium_degree(points, accuracy);
30//! ```
31//!
32//! # References
33//! * [FLUTE, Chris Chu and Yiu-Chung Wong, 2008](https://eecs.wsu.edu/~daehyun/teaching/2016_EE582/papers/r-flute.pdf)
34//! ([archived](https://web.archive.org/web/20220423092341/https://eecs.wsu.edu/~daehyun/teaching/2016_EE582/papers/r-flute.pdf))
35
36#![deny(missing_docs)]
37#![allow(unused)] // TODO: Remove once crate stabilizes.
38
39extern crate bitvec;
40extern crate core;
41extern crate itertools;
42extern crate num_traits;
43extern crate smallvec;
44
45pub mod gen_lut;
46pub mod lut;
47pub mod serialization;
48
49mod compaction_expansion;
50mod hanan_grid;
51mod iterator_set_operations;
52mod marker_types;
53mod minimum_spanning_tree;
54mod net_breaking_medium_degree;
55mod permutations;
56mod pins;
57mod point;
58mod position_sequence;
59mod rectangle;
60mod tree;
61mod wirelength_vector;
62
63use hanan_grid::*;
64pub use point::Point;
65
66type HananCoord = i16;
67
68/// Maximum number of pins supported for the lookup-table.
69const MAX_DEGREE: usize = 9;