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.

205 lines
6.0 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/>.
*/
//! Data types and routines for sparse matrices.
use num_traits::Num;
use std::collections::BTreeMap;
use std::ops::{Add, Mul, Sub};
use std::fmt;
/// Simple sparse NxN matrix in sparse-row format.
/// This format stores the values for each row `i` as `(j, x)` tuples.
#[derive(Clone, Eq, PartialEq, Debug)]
pub struct SparseRowSquareMatrix<T: Num> {
/// Rows of the matrix.
rows: Vec<BTreeMap<usize, T>>
}
impl<T: Num + fmt::Display + Copy> fmt::Display for SparseRowSquareMatrix<T> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
let n = self.dim();
writeln!(f, "[")?;
for i in 0..n {
write!(f, " [ ")?;
for j in 0..n {
let v = self.get(i, j);
write!(f, "{} ", v)?;
}
writeln!(f, "]")?;
}
writeln!(f, "]")?;
Ok(())
}
}
impl<T: Num + Copy> Mul<&Vec<T>> for &SparseRowSquareMatrix<T> {
type Output = Vec<T>;
fn mul(self, rhs: &Vec<T>) -> Self::Output {
self.mul_vec(rhs)
}
}
impl<T: Num + Copy> Add<Self> for &SparseRowSquareMatrix<T> {
type Output = SparseRowSquareMatrix<T>;
fn add(self, rhs: Self) -> Self::Output {
self.add_element_wise(rhs)
}
}
impl<T: Num + Copy> Sub<Self> for &SparseRowSquareMatrix<T> {
type Output = SparseRowSquareMatrix<T>;
fn sub(self, rhs: Self) -> Self::Output {
self.sub_element_wise(rhs)
}
}
impl<T: Num + Copy> SparseRowSquareMatrix<T> {
/// Create a new all-zero matrix.
pub fn new(dim: usize) -> Self {
SparseRowSquareMatrix {
rows: (0..dim).map(|_| Default::default()).collect()
}
}
/// Get dimension N of this NxN matrix.
pub fn dim(&self) -> usize {
self.rows.len()
}
/// Get value at `i`, `j`.
pub fn get(&self, i: usize, j: usize) -> T {
assert!(i < self.dim(), "Index i out of range.");
assert!(j < self.dim(), "Index j out of range.");
self.rows[i].get(&j)
.map(|v| *v)
.unwrap_or(T::zero())
}
/// Set value at `i`, `j`.
pub fn set(&mut self, i: usize, j: usize, value: T) {
assert!(i < self.dim(), "Index i out of range.");
assert!(j < self.dim(), "Index j out of range.");
*self.rows[i].entry(j)
.or_insert(T::zero()) = value;
}
/// Multiply matrix with column vector.
pub fn mul_vec(&self, rhs: &Vec<T>) -> Vec<T> {
assert_eq!(self.dim(), rhs.len(), "Dimension mismatch.");
self.rows.iter()
.map(|row| {
row.iter()
.map(|(&j, &v)| v * rhs[j])
.fold(T::zero(), |acc, v| acc + v)
})
.collect()
}
/// Add value at `i`, `j`.
pub fn add_at(&mut self, i: usize, j: usize, value: T) {
assert!(i < self.dim(), "Index i out of range.");
assert!(j < self.dim(), "Index j out of range.");
self.rows[i].entry(j)
.and_modify(|x| *x = *x + value)
.or_insert(value);
// More general implementation:
// self.set(i, j, self.get(i, j) + value)
}
/// Add two matrices.
pub fn add_element_wise(&self, other: &Self) -> Self {
assert_eq!(self.dim(), other.dim(), "Dimension mismatch.");
let mut new = self.clone();
for (i, j, v) in other.iter() {
new.add_at(i, j, v);
}
new
}
/// Subtract two matrices.
pub fn sub_element_wise(&self, other: &Self) -> Self {
assert_eq!(self.dim(), other.dim(), "Dimension mismatch.");
let mut new = self.clone();
for (i, j, v) in other.iter() {
new.add_at(i, j, T::zero() - v);
}
new
}
/// Iterate over all non-zero values as `(i, j, v)` tuples.
pub fn iter(&self) -> impl Iterator<Item=(usize, usize, T)> + '_ {
self.rows.iter().enumerate()
.flat_map(|(i, row)|
row.iter()
.map(move |(&j, &v)| (i, j, v))
)
}
/// Iterate over all non-zero values in the row `i` as `(j, v)` tuples.
pub fn iter_row(&self, i: usize) -> impl Iterator<Item=(usize, T)> + '_ {
self.rows[i]
.iter()
.map(|(&i, &v)| (i, v))
}
/// Iterate over all non-zero values in the column `j` as `(i, v)` tuples.
pub fn iter_column(&self, j: usize) -> impl Iterator<Item=(usize, T)> + '_ {
self.rows
.iter().enumerate()
.filter_map(move |(i, row)|
row.get(&j)
.map(|&v| (i, v))
)
}
}
#[test]
fn test_create_matrix() {
let mut m = SparseRowSquareMatrix::new(2);
m.set(0, 0, 1);
m.set(1, 1, 1);
assert_eq!(m.get(0, 0), 1);
assert_eq!(m.get(1, 0), 0);
assert_eq!(m.get(0, 1), 0);
assert_eq!(m.get(1, 1), 1);
}
#[test]
fn test_mul_vector() {
let v = vec![1, 2];
let mut m = SparseRowSquareMatrix::new(2);
m.set(0, 0, 1);
m.set(1, 1, 1);
assert_eq!(m.mul_vec(&v), v);
let mut m = SparseRowSquareMatrix::new(2);
m.set(0, 1, 1);
assert_eq!(m.mul_vec(&v), vec![2, 0]);
let mut m = SparseRowSquareMatrix::new(2);
m.set(1, 0, 1);
assert_eq!(m.mul_vec(&v), vec![0, 1]);
}