Struct sparse_bin_mat::SparseBinMat

pub struct SparseBinMat { /* fields omitted */ }

A sparse binary matrix optimized for row operations.

Implementations

impl SparseBinMat

pub fn new(number_of_columns: usize, rows: Vec<Vec<usize>>) -> Self

Creates a new matrix with the given number of columns and list of rows.

A row is a list of the positions where the elements have value 1. All rows are sorted during insertion.

Example

let matrix = SparseBinMat::new(4, vec![vec![0, 1, 2], vec![0, 2, 3]]);

assert_eq!(matrix.number_of_rows(), 2);
assert_eq!(matrix.number_of_columns(), 4);
assert_eq!(matrix.number_of_elements(), 8);

Panic

Panics if a position in a row is greater or equal to the number of columns.

let matrix = SparseBinMat::new(2, vec![vec![1, 2], vec![3, 0]]);

pub fn identity(length: usize) -> Self

Creates an identity matrix of the given length.

Example

let matrix = SparseBinMat::identity(5);

let identity_rows = (0..5).map(|x| vec![x]).collect();
let identity_matrix = SparseBinMat::new(5, identity_rows);

assert_eq!(matrix, identity_matrix);

pub fn zeros(number_of_rows: usize, number_of_columns: usize) -> Self

Creates a matrix fill with zeros of the given dimensions.

Example

let matrix = SparseBinMat::zeros(2, 3);

assert_eq!(matrix.number_of_rows(), 2);
assert_eq!(matrix.number_of_columns(), 3);
assert_eq!(matrix.number_of_zeros(), 6);
assert_eq!(matrix.number_of_ones(), 0);

pub fn empty() -> Self

Creates an empty matrix.

This allocate minimally, so it is a good placeholder.

Example

let matrix = SparseBinMat::empty();

assert_eq!(matrix.number_of_rows(), 0);
assert_eq!(matrix.number_of_columns(), 0); assert_eq!(matrix.number_of_elements(), 0);
// Note that these are not equal since new preallocate some space
// to store the data.
assert_ne!(SparseBinMat::new(0, Vec::new()), SparseBinMat::empty());

// To test for emptyness, you should prefer the following.
assert!(matrix.is_empty());

pub fn number_of_columns(&self) -> usize

Returns the number of columns in the matrix.

pub fn number_of_rows(&self) -> usize

Returns the number of rows in the matrix

pub fn dimension(&self) -> (usize, usize)

Returns the number of rows and columns in the matrix.

pub fn number_of_elements(&self) -> usize

Returns the number of elements in the matrix.

pub fn number_of_zeros(&self) -> usize

Returns the number of elements with value 0 in the matrix.

pub fn number_of_ones(&self) -> usize

Returns the number of elements with value 1 in the matrix.

pub fn is_empty(&self) -> bool

Returns true if the number of elements in the matrix is 0.

pub fn is_zero(&self) -> bool

Returns true if the all elements of the matrix are 0.

pub fn get(&self, row: usize, column: usize) -> Option<u8>

Returns the value at the given row and column or None if one of the index is out of bound.

Example

let rows = vec![vec![0, 1], vec![1, 2]];
let matrix = SparseBinMat::new(3, rows);

assert_eq!(matrix.get(0, 0), Some(1));
assert_eq!(matrix.get(1, 0), Some(0));
assert_eq!(matrix.get(2, 0), None);

pub fn is_zero_at(&self, row: usize, column: usize) -> Option<bool>

Returns true if the value at the given row and column is 0 or None if one of the index is out of bound.

Example

let rows = vec![vec![0, 1], vec![1, 2]];
let matrix = SparseBinMat::new(3, rows);

assert_eq!(matrix.is_zero_at(0, 0), Some(false));
assert_eq!(matrix.is_zero_at(1, 0), Some(true));
assert_eq!(matrix.is_zero_at(2, 0), None);

pub fn is_one_at(&self, row: usize, column: usize) -> Option<bool>

Returns true if the value at the given row and column is 1 or None if one of the index is out of bound.

Example

let rows = vec![vec![0, 1], vec![1, 2]];
let matrix = SparseBinMat::new(3, rows);

assert_eq!(matrix.is_one_at(0, 0), Some(true));
assert_eq!(matrix.is_one_at(1, 0), Some(false));
assert_eq!(matrix.is_one_at(2, 0), None);

pub fn row(&self, row: usize) -> Option<SparseBinSlice<'_>>

Returns a reference to the given row of the matrix or None if the row index is out of bound.

Example

let rows = vec![vec![0, 1], vec![1, 2]];
let matrix = SparseBinMat::new(3, rows.clone());

assert_eq!(matrix.row(0), Some(SparseBinSlice::new_from_sorted(3, &rows[0])));
assert_eq!(matrix.row(1), Some(SparseBinSlice::new_from_sorted(3, &rows[1])));
assert_eq!(matrix.row(2), None);

pub fn rows(&self) -> Rows<'_>

Returns an iterator yielding the rows of the matrix as slice of non zero positions.

Example

let rows = vec![vec![0, 1, 2, 5], vec![1, 3, 4], vec![2, 4, 5], vec![0, 5]];
let matrix = SparseBinMat::new(7, rows.clone());

let mut iter = matrix.rows();

assert_eq!(iter.next(), Some(SparseBinSlice::new_from_sorted(7, &rows[0])));
assert_eq!(iter.next(), Some(SparseBinSlice::new_from_sorted(7, &rows[1])));
assert_eq!(iter.next(), Some(SparseBinSlice::new_from_sorted(7, &rows[2])));
assert_eq!(iter.next(), Some(SparseBinSlice::new_from_sorted(7, &rows[3])));
assert_eq!(iter.next(), None);

pub fn row_weights<'a>(&'a self) -> impl Iterator<Item = usize> + 'a

Returns an iterator yielding the number of non zero elements in each row of the matrix.

Example

let rows = vec![vec![0, 1, 2, 5], vec![1, 3, 4], vec![2, 4, 5], vec![0, 5]];
let matrix = SparseBinMat::new(7, rows);

assert_eq!(matrix.row_weights().collect::<Vec<usize>>(), vec![4, 3, 3, 2]);

pub fn transposed(&self) -> Self

Gets the transposed version of the matrix by swapping the columns with the rows.

Example

let rows = vec![vec![0, 1, 2], vec![1, 3], vec![0, 2, 3]];
let matrix = SparseBinMat::new(4, rows);

let transposed_matrix = matrix.transposed();

let expected_rows = vec![vec![0, 2], vec![0, 1], vec![0, 2], vec![1, 2]];
let expected_matrix = SparseBinMat::new(3, expected_rows);

assert_eq!(transposed_matrix, expected_matrix);

pub fn rank(&self) -> usize

Computes the rank of the matrix. That is, the number of linearly independent rows or columns.

Example

let rows = vec![vec![0, 1], vec![1, 2], vec![0, 2]];
let matrix = SparseBinMat::new(3, rows);

assert_eq!(matrix.rank(), 2);

pub fn echelon_form(&self) -> Self

Returns an echeloned version of the matrix.

A matrix in echelon form as the property that no rows any given row have a 1 in the first non trivial position of that row. Also, all rows are linearly independent.

Example

let rows = vec![vec![0, 1, 2], vec![0], vec![1, 2], vec![0, 2]];
let matrix = SparseBinMat::new(3, rows);

let expected = SparseBinMat::new(3, vec![vec![0, 1, 2], vec![1], vec![2]]);

assert_eq!(matrix.echelon_form(), expected);

pub fn nullspace(&self) -> Self

Returns a matrix for which the rows are the generators of the nullspace of the original matrix.

The nullspace of a matrix M is the set of vectors N such that Mx = 0 for all x in N. Therefore, if N is the nullspace matrix obtain from this function, we have that M * N^T = 0.

Example

let matrix = SparseBinMat::new(
    6,
    vec![vec![0, 1, 3, 5], vec![2, 3, 4], vec![2, 5], vec![0, 1, 3]],
);

let expected = SparseBinMat::new(6, vec![vec![0, 3, 4,], vec![0, 1]]);
let nullspace = matrix.nullspace();

assert_eq!(nullspace, expected);
assert_eq!(&matrix * &nullspace.transposed(), SparseBinMat::zeros(4, 2));

pub fn horizontal_concat_with(&self, other: &SparseBinMat) -> SparseBinMat

Returns the horizontal concatenation of two matrices.

If the matrix have different number of rows, the smallest one is padded with empty rows.

Example

let left_matrix = SparseBinMat::new(3, vec![vec![0, 1], vec![1, 2]]);
let right_matrix = SparseBinMat::new(4, vec![vec![1, 2, 3], vec![0, 1], vec![2, 3]]);

let concatened = left_matrix.horizontal_concat_with(&right_matrix);

let expected = SparseBinMat::new(7, vec![vec![0, 1, 4, 5, 6], vec![1, 2, 3, 4], vec![5, 6]]);

assert_eq!(concatened, expected);

pub fn vertical_concat_with(&self, other: &SparseBinMat) -> SparseBinMat

Returns the vertical concatenation of two matrices.

Example

let left_matrix = SparseBinMat::new(3, vec![vec![0, 1], vec![1, 2]]);
let right_matrix = SparseBinMat::identity(3);

let concatened = left_matrix.vertical_concat_with(&right_matrix);

let expected = SparseBinMat::new(3, vec![vec![0, 1], vec![1, 2], vec![0], vec![1], vec![2]]);

assert_eq!(concatened, expected);

Panic

Panics if the matrices have a different number of columns.

pub fn dot_with<T>(&self, vector: &SparseBinVecBase<T>) -> SparseBinVec where
    T: Deref<Target = [usize]>, 

Returns the dot product between a matrix and a vector.

Example

let matrix = SparseBinMat::new(3, vec![vec![0, 1], vec![1, 2]]);
let vector = SparseBinVec::new(3, vec![0, 1]);
let result = SparseBinVec::new(2, vec![1]);

assert_eq!(matrix.dot_with(&vector), result);

Panic

Panics if the number of columns of the matrix is different from the

let matrix = SparseBinMat::new(3, vec![vec![0, 1], vec![1, 2]]);
let vector = SparseBinVec::new(2, vec![0, 1]);
matrix.dot_with(&vector);

pub fn keep_only_rows(&self, rows: &[usize]) -> Self

Returns a new matrix keeping only the given rows.

Example

use sparse_bin_mat::SparseBinMat;
let matrix = SparseBinMat::new(5, vec![
    vec![0, 1, 2],
    vec![2, 3, 4],
    vec![0, 2, 4],
    vec![1, 3],
]);

let truncated = SparseBinMat::new(5, vec![
    vec![0, 1, 2],
    vec![0, 2, 4],
]);

assert_eq!(matrix.keep_only_rows(&[0, 2]), truncated);
assert_eq!(matrix.keep_only_rows(&[0, 2, 3]).number_of_rows(), 3);

Panic

Panics if some rows are out of bound.

pub fn without_rows(&self, rows: &[usize]) -> Self

Returns a truncated matrix where the given rows are removed.

Example

let matrix = SparseBinMat::new(5, vec![
    vec![0, 1, 2],
    vec![2, 3, 4],
    vec![0, 2, 4],
    vec![1, 3],
]);

let truncated = SparseBinMat::new(5, vec![
    vec![2, 3, 4],
    vec![1, 3],
]);

assert_eq!(matrix.without_rows(&[0, 2]), truncated);
assert_eq!(matrix.without_rows(&[1, 2, 3]).number_of_rows(), 1);

Panic

Panics if some rows are out of bound.

pub fn keep_only_columns(&self, columns: &[usize]) -> Self

Returns a new matrix keeping only the given columns.

Columns are relabeled to the fit new number of columns.

Example

use sparse_bin_mat::SparseBinMat;
let matrix = SparseBinMat::new(5, vec![
    vec![0, 1, 2],
    vec![2, 3, 4],
    vec![0, 2, 4],
    vec![1, 3],
]);

let truncated = SparseBinMat::new(3, vec![
    vec![0, 1],
    vec![2],
    vec![0, 2],
    vec![1],
]);

assert_eq!(matrix.keep_only_columns(&[0, 1, 4]), truncated);
assert_eq!(matrix.keep_only_columns(&[1, 2]).number_of_columns(), 2);

Panic

Panics if some columns are out of bound.

pub fn without_columns(&self, columns: &[usize]) -> Self

Returns a truncated matrix where the given columns are removed.

Columns are relabeled to fit the new number of columns.

Example

let matrix = SparseBinMat::new(5, vec![
    vec![0, 1, 2],
    vec![2, 3, 4],
    vec![0, 2, 4],
    vec![1, 3],
]);

let truncated = SparseBinMat::new(3, vec![
    vec![0],
    vec![1, 2],
    vec![2],
    vec![0, 1],
]);

assert_eq!(matrix.without_columns(&[0, 2]), truncated);

Panic

Panics if some columns are out of bound.

Trait Implementations

impl<'_, '_> Add<&'_ SparseBinMat> for &'_ SparseBinMat

type Output = SparseBinMat

The resulting type after applying the + operator.

pub fn add(self, other: &SparseBinMat) -> SparseBinMat

Performs the + operation.

impl Clone for SparseBinMat

pub fn clone(&self) -> SparseBinMat

Returns a copy of the value.

pub fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for SparseBinMat

pub fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Eq for SparseBinMat

impl Hash for SparseBinMat

pub fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

pub fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given Hasher.

impl<'_, '_> Mul<&'_ SparseBinMat> for &'_ SparseBinMat

type Output = SparseBinMat

The resulting type after applying the * operator.

pub fn mul(self, other: &SparseBinMat) -> SparseBinMat

Performs the * operation.

impl PartialEq<SparseBinMat> for SparseBinMat

pub fn eq(&self, other: &SparseBinMat) -> bool

This method tests for self and other values to be equal, and is used by ==.

pub fn ne(&self, other: &SparseBinMat) -> bool

This method tests for !=.

impl StructuralEq for SparseBinMat

impl StructuralPartialEq for SparseBinMat