steiner-tree 0.0.1

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

//! Break medium degree nets recursively into smaller nets until
//! they can be handled by the lookup-table.

use super::point::*;
use num_traits::{Num, Zero, FromPrimitive, ToPrimitive};
use std::iter::Sum;
use itertools::Itertools;
use super::lut::LookupTable;

impl LookupTable {
    /// Heuristically break the net into sub-nets until they can be routed using the lookup-table.
    ///
    /// # Parameters
    /// * `accuracy`: Try this number of the most promising split locations. Use the best partitioning.
    pub fn rsmt_medium_degree<T>(&self, mut pins: Vec<Point<T>>, accuracy: usize) -> (Vec<(Point<T>, Point<T>)>, T)
        where T: Ord + Copy + Num + Zero + Sum + std::fmt::Debug + FromPrimitive + ToPrimitive {
        assert!(accuracy > 0);

        pins.sort_unstable_by_key(|p| (p.y, p.x));
        pins.dedup();

        let num_pins = pins.len();

        if num_pins <= self.max_degree() {
            // Use the lookup table.
            return self.rsmt_low_degree(pins);
        }

        // Find hanan grid lines.
        let xs = {
            let mut xs: Vec<_> = pins.iter().map(|p| p.x).collect();
            xs.sort_unstable();
            xs
        };
        let ys = {
            let mut ys: Vec<_> = pins.iter().map(|p| p.y).collect();
            ys.sort_unstable();
            ys
        };


        // Number the pins in ascending x direction.
        let pin_rank = {
            let mut r: Vec<_> = (0..pins.len()).collect();
            r.sort_by_key(|&i| pins[i].x);
            r
        };

        let score_0 = |r: usize| -> T {
            hplw(&pins[..r + 1]) + hplw(&pins[r..])
        };

        let score_1 = |r: usize| -> T {
            pins[r + 1].y - pins[r - 1].y
        };

        let score_2 = |r: usize| -> T {
            let s_r = pin_rank[r];
            if s_r < 2 {
                T::from_usize(2).unwrap() * (xs[2] - xs[1])
            } else if pin_rank[r] > num_pins - 2 {
                T::from_usize(2).unwrap() * (xs[num_pins - 2] - xs[num_pins - 3])
            } else {
                xs[s_r + 1] - xs[s_r - 1]
            }
        };


        let score_3 = |r: usize| -> f64 {
            let dx: f64 = (xs[num_pins - 2] - xs[1]).to_f64().unwrap() / (num_pins - 4) as f64;
            let dy: f64 = (ys[num_pins - 2] - ys[1]).to_f64().unwrap() / (num_pins - 4) as f64;

            let s_r = (pin_rank[r] + 1) as f64;
            let n = num_pins as f64;

            (s_r - ((n + 2.) / 2.)).abs() * dx
                + ((r + 1) as f64 - ((n + 2.) / 2.)).abs() * dy
        };

        let score = |r: usize| -> f64 {
            let n = num_pins as f64;

            // Score weights are determined experimentally.
            score_1(r).to_f64().unwrap()
                - 0.3 * score_2(r).to_f64().unwrap()
                - 7.5 / n * (score_3(r) + 12. * score_0(r).to_f64().unwrap() / (n - 3.))
        };

        // Compute scores for all potential breaking locations.
        let mut breaking_scores: Vec<_> = (1..num_pins - 1)
            .map(|r| (r, score(r)))
            .collect();
        // Find best scores.
        breaking_scores.sort_by_key(|(_, score)| (1e3 * score) as i64);

        let trees = breaking_scores.into_iter()
            .take(accuracy)
            .map(|(r, _score)| {
                let pins_left = pins[0..r + 1].to_vec();
                let pins_right = pins[r..].to_vec();

                // Recursive net breaking.
                let (mut tree_left, tree_left_weight) =
                    self.rsmt_medium_degree(pins_left, accuracy / 2);
                let (mut tree_right, tree_right_weight) =
                    self.rsmt_medium_degree(pins_right, accuracy / 2);

                // Sort the edges for fast set union.
                tree_left.sort();
                tree_right.sort();

                // TODO: Merge the trees.
                let merged_tree = super::iterator_set_operations::union(
                    tree_left,
                    tree_right,
                ).collect();


                let merged_weight = tree_left_weight + tree_right_weight;

                (merged_tree, merged_weight)
            });

        let best_tree = trees
            .min_by_key(|(_, weight)| *weight)
            .unwrap();

        best_tree
    }
}

/// Half-perimeter wire length.
fn hplw<T>(pins: &[Point<T>]) -> T
    where T: Ord + Num + Zero + Copy {
    if pins.is_empty() {
        T::zero()
    } else {
        let mut lower_left = pins[0];
        let mut upper_right = pins[pins.len() - 1];
        for p in &pins[1..] {
            lower_left.x = lower_left.x.min(p.x);
            upper_right.x = upper_right.x.max(p.x);
            lower_left.y = lower_left.y.min(p.y);
            upper_right.y = upper_right.y.max(p.y);
        }
        upper_right.x - lower_left.x + upper_right.y - lower_left.y
    }
}

#[test]
fn test_rsmt_medium_degree() {
    let lut = super::gen_lut::gen_full_lut(3);

    // 4 points
    let points = vec![(0, 0).into(), (2, 1).into(), (2, 4).into(), (4, 2).into()];
    let (rsmt, wl) = lut.rsmt_medium_degree(points, 4);
    assert_eq!(rsmt.len(), 5);
    assert_eq!(wl, 8);

    // 5 points (cross with a center)
    let points = vec![(10, 5).into(), (5, 0).into(), (5, 5).into(), (0, 5).into(), (5, 10).into()];
    let (rsmt, wl) = lut.rsmt_medium_degree(points, 4);
    assert_eq!(rsmt.len(), 4);
    assert_eq!(wl, 20);
}