1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

// SPDX-FileCopyrightText: 2022 Thomas Kramer <code@tkramer.ch>
//
// SPDX-License-Identifier: GPL-3.0-or-later

//! 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](https://eecs.wsu.edu/~daehyun/teaching/2016_EE582/papers/r-flute.pdf)
//! ([archived](https://web.archive.org/web/20220423092341/https://eecs.wsu.edu/~daehyun/teaching/2016_EE582/papers/r-flute.pdf))

#![deny(missing_docs)]

extern crate num_traits;
extern crate itertools;
extern crate smallvec;
extern crate core;

pub mod gen_lut;
pub mod lut;
pub mod serialization;

mod permutations;
mod tree;
mod point;
mod pins;
mod hanan_grid;
mod marker_types;
mod rectangle;
mod compaction_expansion;
mod position_sequence;
mod wirelength_vector;
mod iterator_set_operations;
mod net_breaking_medium_degree;
mod travelling_salesperson;

pub use point::Point;
use hanan_grid::*;

type HananCoord = i16;

/// Maximum number of pins supported for the lookup-table.
const MAX_DEGREE: usize = 9;