Example standard-cell placement engine for the LibrEDA-Rust framework. This placement algorithm simulates the movement of electric charges that are sparsely connected by springs (wires).
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

73 lines
2.1 KiB

/*
* Copyright (c) 2019-2020 Thomas Kramer.
*
* This file is part of LibrEDA
* (see https://codeberg.org/libreda).
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU Affero General Public License as
* published by the Free Software Foundation, either version 3 of the
* License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU Affero General Public License for more details.
*
* You should have received a copy of the GNU Affero General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
//! Calculate spring forces between particles.
use super::types::*;
fn spring_force(onto: Vec2D, from: Vec2D) -> Cost {
let f = from - onto;
// let df = f / f.norm2();
debug_assert!(f.x.is_finite());
debug_assert!(f.y.is_finite());
Cost {
cost: f.norm2(),
gradient: f,
hessian: (Vec2D::zero(), Vec2D::zero()),
}
}
/// Compute the spring forces between this group of particles.
pub fn calculate_spring_forces(particle_locations: &Vec<Vec2D>) -> Vec<Cost> {
let k = particle_locations.len();
let weight = if k <= 1 {
0.
} else {
1. / ((k - 1) as f64)
};
debug_assert!(weight.is_finite());
particle_locations.iter().map(|&p| {
// Sum up all spring forces to the other particles.
particle_locations.iter().map(|&p2| {
spring_force(p, p2)
}).fold(Cost::zero(), |acc, v| acc + v) * weight
}).collect()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_spring_force() {
let locations = vec!(
Vec2D::new(0., 0.),
Vec2D::new(1., 0.)
);
let forces = calculate_spring_forces(&locations);
assert_eq!(forces[0].gradient, Vec2D::new(1., 0.));
assert_eq!(forces[1].gradient, Vec2D::new(-1., 0.));
}
}