steiner_tree/
net_breaking_medium_degree.rs

1// SPDX-FileCopyrightText: 2022 Thomas Kramer <code@tkramer.ch>
2//
3// SPDX-License-Identifier: GPL-3.0-or-later
4
5//! Break medium degree nets recursively into smaller nets until
6//! they can be handled by the lookup-table.
7
8use super::lut::LookupTable;
9use super::point::*;
10use itertools::Itertools;
11use num_traits::{FromPrimitive, Num, ToPrimitive, Zero};
12use std::iter::Sum;
13
14impl LookupTable {
15    /// Heuristically break the net into sub-nets until they can be routed using the lookup-table.
16    ///
17    /// # Parameters
18    /// * `accuracy`: Try this number of the most promising split locations. Use the best partitioning.
19    pub fn rsmt_medium_degree<T>(
20        &self,
21        mut pins: Vec<Point<T>>,
22        accuracy: usize,
23    ) -> (Vec<(Point<T>, Point<T>)>, T)
24    where
25        T: Ord + Copy + Num + Zero + Sum + std::fmt::Debug + FromPrimitive + ToPrimitive,
26    {
27        assert!(accuracy > 0);
28
29        pins.sort_unstable_by_key(|p| (p.y, p.x));
30        pins.dedup();
31
32        let num_pins = pins.len();
33
34        if num_pins <= self.max_degree() {
35            // Use the lookup table.
36            return self.rsmt_low_degree(pins);
37        }
38
39        // Find hanan grid lines.
40        let xs = {
41            let mut xs: Vec<_> = pins.iter().map(|p| p.x).collect();
42            xs.sort_unstable();
43            xs
44        };
45        let ys = {
46            let mut ys: Vec<_> = pins.iter().map(|p| p.y).collect();
47            ys.sort_unstable();
48            ys
49        };
50
51        // Number the pins in ascending x direction.
52        let pin_rank = {
53            let mut r: Vec<_> = (0..pins.len()).collect();
54            r.sort_by_key(|&i| pins[i].x);
55            r
56        };
57
58        let score_0 = |r: usize| -> T { hplw(&pins[..r + 1]) + hplw(&pins[r..]) };
59
60        let score_1 = |r: usize| -> T { pins[r + 1].y - pins[r - 1].y };
61
62        let score_2 = |r: usize| -> T {
63            let s_r = pin_rank[r];
64            if s_r < 2 {
65                T::from_usize(2).unwrap() * (xs[2] - xs[1])
66            } else if pin_rank[r] > num_pins - 2 {
67                T::from_usize(2).unwrap() * (xs[num_pins - 2] - xs[num_pins - 3])
68            } else {
69                xs[s_r + 1] - xs[s_r - 1]
70            }
71        };
72
73        let score_3 = |r: usize| -> f64 {
74            let dx: f64 = (xs[num_pins - 2] - xs[1]).to_f64().unwrap() / (num_pins - 4) as f64;
75            let dy: f64 = (ys[num_pins - 2] - ys[1]).to_f64().unwrap() / (num_pins - 4) as f64;
76
77            let s_r = (pin_rank[r] + 1) as f64;
78            let n = num_pins as f64;
79
80            (s_r - ((n + 2.) / 2.)).abs() * dx + ((r + 1) as f64 - ((n + 2.) / 2.)).abs() * dy
81        };
82
83        let score = |r: usize| -> f64 {
84            let n = num_pins as f64;
85
86            // Score weights are determined experimentally.
87            score_1(r).to_f64().unwrap()
88                - 0.3 * score_2(r).to_f64().unwrap()
89                - 7.5 / n * (score_3(r) + 12. * score_0(r).to_f64().unwrap() / (n - 3.))
90        };
91
92        // Compute scores for all potential breaking locations.
93        let mut breaking_scores: Vec<_> = (1..num_pins - 1).map(|r| (r, score(r))).collect();
94        // Find best scores.
95        breaking_scores.sort_by_key(|(_, score)| (1e3 * score) as i64);
96
97        let trees = breaking_scores
98            .into_iter()
99            .take(accuracy)
100            .map(|(r, _score)| {
101                let pins_left = pins[0..r + 1].to_vec();
102                let pins_right = pins[r..].to_vec();
103
104                // Recursive net breaking.
105                let (mut tree_left, tree_left_weight) =
106                    self.rsmt_medium_degree(pins_left, accuracy / 2);
107                let (mut tree_right, tree_right_weight) =
108                    self.rsmt_medium_degree(pins_right, accuracy / 2);
109
110                // Sort the edges for fast set union.
111                tree_left.sort();
112                tree_right.sort();
113
114                // TODO: Merge the trees.
115                let merged_tree =
116                    super::iterator_set_operations::union(tree_left, tree_right).collect();
117
118                let merged_weight = tree_left_weight + tree_right_weight;
119
120                (merged_tree, merged_weight)
121            });
122
123        let best_tree = trees.min_by_key(|(_, weight)| *weight).unwrap();
124
125        best_tree
126    }
127}
128
129/// Half-perimeter wire length.
130fn hplw<T>(pins: &[Point<T>]) -> T
131where
132    T: Ord + Num + Zero + Copy,
133{
134    if pins.is_empty() {
135        T::zero()
136    } else {
137        let mut lower_left = pins[0];
138        let mut upper_right = pins[pins.len() - 1];
139        for p in &pins[1..] {
140            lower_left.x = lower_left.x.min(p.x);
141            upper_right.x = upper_right.x.max(p.x);
142            lower_left.y = lower_left.y.min(p.y);
143            upper_right.y = upper_right.y.max(p.y);
144        }
145        upper_right.x - lower_left.x + upper_right.y - lower_left.y
146    }
147}
148
149#[test]
150fn test_rsmt_medium_degree() {
151    let lut = super::gen_lut::gen_full_lut(3);
152
153    // 4 points
154    let points = vec![(0, 0).into(), (2, 1).into(), (2, 4).into(), (4, 2).into()];
155    let (rsmt, wl) = lut.rsmt_medium_degree(points, 4);
156    assert_eq!(rsmt.len(), 5);
157    assert_eq!(wl, 8);
158
159    // 5 points (cross with a center)
160    let points = vec![
161        (10, 5).into(),
162        (5, 0).into(),
163        (5, 5).into(),
164        (0, 5).into(),
165        (5, 10).into(),
166    ];
167    let (rsmt, wl) = lut.rsmt_medium_degree(points, 4);
168    assert_eq!(rsmt.len(), 4);
169    assert_eq!(wl, 20);
170}
steiner_tree/net_breaking_medium_degree.rs

steiner_tree/
net_breaking_medium_degree.rs
