Struct SparseBinMat

pub struct SparseBinMat { /* private fields */ }

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.

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 the number of columns, a row is unsorted or a row contains duplicate.

pub fn try_new( number_of_columns: usize, rows: Vec<Vec<usize>>, ) -> Result<Self, InvalidPositions>

Creates a new matrix with the given number of columns and list of rows or returns an error if a position in a row is greater or equal the number of columns, a row is unsorted or a row contains duplicate.

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

Example

let first_matrix = SparseBinMat::try_new(4, vec![vec![0, 1, 2], vec![0, 2, 3]]);
let second_matrix = SparseBinMat::new(4, vec![vec![0, 1, 2], vec![0, 2, 3]]);
assert_eq!(first_matrix, Ok(second_matrix));

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

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

A row is a list of the positions where the elements have value 1.

The capacity is used to pre-allocate enough memory to store that amount of 1s in the matrix. This is mostly useful in combination with inplace operations modifying the number of 1s in the matrix.

Example

let matrix = SparseBinMat::with_capacity(4, 7, 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);
assert_eq!(matrix.capacity(), 7);

Panic

Panics if a position in a row is greater or equal the number of columns, a row is unsorted or a row contains duplicate.

pub fn try_with_capacity( number_of_columns: usize, capacity: usize, rows: Vec<Vec<usize>>, ) -> Result<Self, InvalidPositions>

Creates a new matrix with the given number of columns, capacity and list of rows Returns an error if a position in a row is greater or equal the number of columns, a row is unsorted or a row contains duplicate.

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

The capacity is used to pre-allocate enough memory to store that amount of 1s in the matrix. This is mostly useful in combination with inplace operations modifying the number of 1s in the matrix.

Example

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

assert_eq!(try_matrix, Ok(matrix));
assert_eq!(try_matrix.unwrap().capacity(), 7);

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 capacity(&self) -> usize

Returns the maximum number of 1s the matrix can store before reallocating.

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 push_row(&mut self, row: &[usize])

Inserts a new row at the end the matrix.

This update the matrix inplace.

Example

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

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

assert_eq!(matrix, expected);

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

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.into()));
assert_eq!(matrix.get(1, 0), Some(0.into()));
assert_eq!(matrix.get(2, 0), None);

pub fn emplace_at<B: Into<BinNum>>( self, value: B, row: usize, column: usize, ) -> Self

Inserts the given value at the given row and column.

This operation is perform in place. That is, it take ownership of the matrix and returns an updated matrix using the same memory.

To avoid having to reallocate new memory, it is reccommended to construct the matrix using with_capacity or try_with_capacity.

Example

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

// This doesn't change the matrix
matrix = matrix.emplace_at(1, 0, 0);
assert_eq!(matrix.number_of_ones(), 3);

// Add a 1 in the first row.
matrix = matrix.emplace_at(1, 0, 2);
let expected = SparseBinMat::new(3, vec![vec![0, 2], vec![1, 2]]);
assert_eq!(matrix, expected);

// Remove a 1 in the second row.
matrix = matrix.emplace_at(0, 1, 1);
let expected = SparseBinMat::new(3, vec![vec![0, 2], vec![2]]);
assert_eq!(matrix, expected);

Panic

Panics if either the row or column is out of bound.

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(3, &rows[0])));
assert_eq!(matrix.row(1), Some(SparseBinSlice::new(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(7, &rows[0])));
assert_eq!(iter.next(), Some(SparseBinSlice::new(7, &rows[1])));
assert_eq!(iter.next(), Some(SparseBinSlice::new(7, &rows[2])));
assert_eq!(iter.next(), Some(SparseBinSlice::new(7, &rows[3])));
assert_eq!(iter.next(), None);

pub fn non_trivial_elements(&self) -> NonTrivialElements<'_>

Returns an iterator yielding the positions of the non trivial elements.

Example

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

let mut iter = matrix.non_trivial_elements();

assert_eq!(iter.next(), Some((0, 0)));
assert_eq!(iter.next(), Some((0, 2)));
assert_eq!(iter.next(), Some((1, 1)));
assert_eq!(iter.next(), Some((2, 0)));
assert_eq!(iter.next(), Some((2, 2)));
assert_eq!(iter.next(), Some((3, 1)));
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 all rows have a 1 at their first non trivial position. Also, all rows are linearly independent.

Example

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

pub fn solve(&self, rhs: &SparseBinMat) -> Option<Self>

Solves a linear system of equations define from this matrix.

One solution is provided for each column of rhs. That is, for each row r of rhs, this solves the system A*x = r and returns x into a matrix where the row i is the solution for the column i of rhs.

Returns None if at least one equation is not solvable and returns an arbitrary solution if it is not unique.

Example

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

let rhs = SparseBinMat::new(3, vec![vec![0, 1], vec![0, 2]]);
let expected = SparseBinMat::new(2, vec![vec![0], vec![0, 1]]);
assert_eq!(matrix.solve(&rhs), Some(expected));

let rhs = SparseBinMat::new(3, vec![vec![0]]);
assert!(matrix.solve(&rhs).is_none());

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 normal_form(&self) -> (Self, Vec<usize>)

pub fn permute_columns(&self, permutation: &[usize]) -> SparseBinMat

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) -> Self

Returns the vertical concatenation of two matrices.

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

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);

pub fn dot_with_vector<T>( &self, vector: &SparseBinVecBase<T>, ) -> Result<SparseBinVec, MatVecIncompatibleDimensions>

where T: Deref<Target = [usize]>,

Returns the dot product between a matrix and a vector or an error if the number of columns in the matrix is not equal to the length of the vector.

Use the Mul (*) operator for a version that panics instead of returning a Result.

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(&vector), Ok(result));

pub fn dot_with_matrix( &self, other: &Self, ) -> Result<SparseBinMat, MatMatIncompatibleDimensions>

Returns the dot product between two matrices or an error if the number of columns in the first matrix is not equal to the number of rows in the second matrix.

Use the Mul (*) operator for a version that panics instead of returning a Result.

Example

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

assert_eq!(matrix.dot_with_matrix(&other_matrix), Ok(result));

pub fn bitwise_xor_with( &self, other: &Self, ) -> Result<Self, MatMatIncompatibleDimensions>

Returns the bitwise xor sum of two matrices or an error if the matrices have different dimensions.

Use the Add (+) operator for a version that panics instead of returning a Result.

Example

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

assert_eq!(matrix.bitwise_xor_with(&other_matrix), Ok(result));

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

Returns a new matrix keeping only the given rows or an error if rows are out of bound, unsorted or not unique.

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]), Ok(truncated));
assert_eq!(matrix.keep_only_rows(&[0, 2, 3]).unwrap().number_of_rows(), 3);

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

Returns a truncated matrix where the given rows are removed or an error if rows are out of bound or unsorted.

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]), Ok(truncated));
assert_eq!(matrix.without_rows(&[1, 2, 3]).unwrap().number_of_rows(), 1);

pub fn split_rows(&self, split: usize) -> (Self, Self)

Returns two matrices where the first one contains all rows until split and the second one contains all rows starting from split.

Example

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

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

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

pub fn split_rows_top(&self, split: usize) -> Self

Returns a matrix that contains all rows until split.

Example

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

let expected_top = SparseBinMat::new(5, vec![
    vec![0, 1, 2],
]);
assert_eq!(top, expected_top);

pub fn split_rows_bottom(&self, split: usize) -> Self

Returns a matrix that contains all rows starting from split.

Example

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

let expected_bottom = SparseBinMat::new(5, vec![
    vec![1, 3],
    vec![0, 1, 3],
]);
assert_eq!(bottom, expected_bottom);

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

Returns a new matrix keeping only the given columns or an error if columns are out of bound, unsorted or not unique.

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]), Ok(truncated));
assert_eq!(matrix.keep_only_columns(&[1, 2]).unwrap().number_of_columns(), 2);

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

Returns a truncated matrix where the given columns are removed or an error if columns are out of bound or unsorted.

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]), Ok(truncated));

pub fn kron_with(&self, other: &Self) -> Self

Returns the Kronecker product of two matrices.

Example

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

let product = left_matrix.kron_with(&right_matrix);
let expected = SparseBinMat::new(6, vec![vec![3, 4], vec![4, 5], vec![0, 1], vec![1, 2]]);

assert_eq!(product, expected);

pub fn as_json(&self) -> Result<String, Error>

Returns a json string for the matrix.

Trait Implementations

impl Add<&SparseBinMat> for &SparseBinMat

type Output = SparseBinMat

The resulting type after applying the + operator.

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

Performs the + operation.

impl Clone for SparseBinMat

fn clone(&self) -> SparseBinMat

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for SparseBinMat

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

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for SparseBinMat

fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>

where D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Display for SparseBinMat

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

Formats the value using the given formatter.

impl Hash for SparseBinMat

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

Feeds this value into the given Hasher.

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

where H: Hasher, Self: Sized,

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.

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

Performs the * operation.

impl<T: Deref<Target = [usize]>> Mul<&SparseBinVecBase<T>> for &SparseBinMat

type Output = SparseBinVecBase<Vec<usize>>

The resulting type after applying the * operator.

fn mul(self, other: &SparseBinVecBase<T>) -> SparseBinVec

Performs the * operation.

impl PartialEq for SparseBinMat

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

Tests for self and other values to be equal, and is used by ==.

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

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Serialize for SparseBinMat

fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>

where S: Serializer,

Serialize this value into the given Serde serializer.

impl Eq for SparseBinMat

impl StructuralPartialEq for SparseBinMat