Struct SparseMatrix

pub struct SparseMatrix { /* private fields */ }

A sparse binary matrix

The internal representation for this matrix is based on the alist format.

Implementations

impl SparseMatrix

pub fn new(nrows: usize, ncols: usize) -> SparseMatrix

Create a new sparse matrix of a given size

The matrix is inizialized to the zero matrix.

Examples

let h = SparseMatrix::new(10, 30);
assert_eq!(h.num_rows(), 10);
assert_eq!(h.num_cols(), 30);

pub fn num_rows(&self) -> usize

Returns the number of rows of the matrix

pub fn num_cols(&self) -> usize

Returns the number of columns of the matrix

pub fn row_weight(&self, row: usize) -> usize

Returns the row weight of row

The row weight is defined as the number of entries equal to one in a particular row. Rows are indexed starting by zero.

pub fn col_weight(&self, col: usize) -> usize

Returns the column weight of column

The column weight is defined as the number of entries equal to one in a particular column. Columns are indexed starting by zero.

pub fn contains(&self, row: usize, col: usize) -> bool

Returns true if the entry corresponding to a particular row and column is a one

pub fn insert(&mut self, row: usize, col: usize)

Inserts a one in a particular row and column.

If there is already a one in this row and column, this function does nothing.

Examples

let mut h = SparseMatrix::new(10, 30);
assert!(!h.contains(3, 7));
h.insert(3, 7);
assert!(h.contains(3, 7));

pub fn remove(&mut self, row: usize, col: usize)

Removes a one in a particular row and column.

If there is no one in this row and column, this function does nothing.

Examples

let mut h = SparseMatrix::new(10, 30);
h.insert(3, 7);
assert!(h.contains(3, 7));
h.remove(3, 7);
assert!(!h.contains(3, 7));

pub fn toggle(&mut self, row: usize, col: usize)

Toggles the 0/1 in a particular row and column.

If the row and column contains a zero, this function sets a one, and vice versa. This is useful to implement addition modulo 2.

pub fn insert_row<T, S>(&mut self, row: usize, cols: T)

where T: Iterator<Item = S>, S: Borrow<usize>,

Inserts ones in particular columns of a row

This effect is as calling insert() on each of the elements of the iterator cols.

Examples

let mut h1 = SparseMatrix::new(10, 30);
let mut h2 = SparseMatrix::new(10, 30);
let c = vec![3, 7, 9];
h1.insert_row(0, c.iter());
for a in &c {
    h2.insert(0, *a);
}
assert_eq!(h1, h2);

pub fn insert_col<T, S>(&mut self, col: usize, rows: T)

where T: Iterator<Item = S>, S: Borrow<usize>,

Inserts ones in a particular rows of a column

This works like insert_row().

pub fn clear_row(&mut self, row: usize)

Remove all the ones in a particular row

pub fn clear_col(&mut self, col: usize)

Remove all the ones in a particular column

pub fn set_row<T, S>(&mut self, row: usize, cols: T)

where T: Iterator<Item = S>, S: Borrow<usize>,

Set the elements that are equal to one in a row

The effect of this is like calling clear_row() followed by insert_row().

pub fn set_col<T, S>(&mut self, col: usize, rows: T)

where T: Iterator<Item = S>, S: Borrow<usize>,

Set the elements that are equal to one in a column

pub fn iter_all(&self) -> impl Iterator<Item = (usize, usize)> + '_

Returns an Iterator over the indices entries equal to one in all the matrix.

pub fn iter_row(&self, row: usize) -> Iter<'_, usize>

Returns an Iterator over the entries equal to one in a particular row

pub fn iter_col(&self, col: usize) -> Iter<'_, usize>

Returns an Iterator over the entries equal to one in a particular column

pub fn write_alist<W: Write>(&self, w: &mut W) -> Result

Writes the matrix in alist format to a writer.

This function includes zeros as padding for irregular codes, as originally defined by MacKay.

Errors

If a call to write!() returns an error, this function returns such an error.

pub fn write_alist_no_padding<W: Write>(&self, w: &mut W) -> Result

Writes the matrix in alist format to a writer.

This function does not include zeros as padding for irregular codes.

Errors

If a call to write!() returns an error, this function returns such an error.

pub fn alist(&self) -> String

Returns a String with the alist representation of the matrix.

This function includes zeros as padding for irregular codes, as originally defined by MacKay.

pub fn alist_no_padding(&self) -> String

Returns a String with the alist representation of the matrix.

This function does not include zeros as padding for irregular codes.

pub fn from_alist(alist: &str) -> Result<SparseMatrix>

Constructs and returns a sparse matrix from its alist representation.

This function is able to read alists that use zeros for padding in the case of an irregular code (as was defined originally by MacKay), as well as alists that omit these zeros.

Errors

alist should hold a valid alist representation. If an error is found while parsing alist, a String describing the error will be returned.

pub fn girth(&self) -> Option<usize>

Returns the girth of the bipartite graph defined by the matrix

The girth is the length of the shortest cycle. If there are no cycles, None is returned.

Examples

The following shows that a 2 x 2 matrix whose entries are all equal to one has a girth of 4, which is the smallest girth that a bipartite graph can have.

let mut h = SparseMatrix::new(2, 2);
for j in 0..2 {
    for k in 0..2 {
        h.insert(j, k);
    }
}
assert_eq!(h.girth(), Some(4));

pub fn girth_with_max(&self, max: usize) -> Option<usize>

Returns the girth of the bipartite graph defined by the matrix as long as it is smaller than a maximum

By imposing a maximum value in the girth search algorithm, the execution time is reduced, since paths longer than the maximum do not need to be explored.

Often it is only necessary to check that a graph has at least some minimum girth, so it is possible to use girth_with_max().

If there are no cycles with length smaller or equal to max, then None is returned.

pub fn girth_at_node(&self, node: Node) -> Option<usize>

Returns the local girth at a particular node

The local girth at a node of a graph is defined as the minimum length of the cycles containing that node.

This function returns the local girth of at the node correponding to a column or row of the matrix, or None if there are no cycles containing that node.

pub fn girth_at_node_with_max(&self, node: Node, max: usize) -> Option<usize>

Returns the girth at a particular node with a maximum

This function works like girth_at_node() but imposes a maximum in the length of the cycles considered. None is returned if there are no cycles containing the node with length smaller or equal than max.

pub fn bfs(&self, node: Node) -> BFSResults

Run the BFS algorithm

This uses a node of the graph associated to the matrix as the root for the BFS algorithm and finds the distances from each of the nodes of the graph to that root using breadth-first search.

Examples

Run BFS on a matrix that has two connected components.

let mut h = SparseMatrix::new(4, 4);
for j in 0..4 {
    for k in 0..4 {
        if (j % 2) == (k % 2) {
            h.insert(j, k);
        }
    }
}
println!("{:?}", h.bfs(Node::Col(0)));

Trait Implementations

impl Clone for SparseMatrix

fn clone(&self) -> SparseMatrix

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for SparseMatrix

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

Formats the value using the given formatter.

impl PartialEq for SparseMatrix

fn eq(&self, other: &SparseMatrix) -> 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 Eq for SparseMatrix

impl StructuralPartialEq for SparseMatrix