Question

How to compact a sparse matrix in Rust

Answer 1

// A sparse matrix is a matrix in which the majority of elements are zero.

// To compact a sparse matrix, use a method to store only the non‑zero
// entries using a triplet representation (row, column, value). 
// This reduces memory usage.

// Convert a sparse matrix into compact (triplet) form
fn compact_matrix(matrix: &Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let rows = matrix.len();
    let cols = matrix[0].len();

    // Count non-zero elements
    let mut count = 0;
    for i in 0..rows {
        for j in 0..cols {
            if matrix[i][j] != 0 {
                count += 1;
            }
        }
    }

    // Compact matrix has 3 rows: row index, col index, value
    let mut compact = vec![
        vec![0; count],
        vec![0; count],
        vec![0; count],
    ];

    let mut k = 0;

    // Fill compact matrix
    for i in 0..rows {
        for j in 0..cols {
            if matrix[i][j] != 0 {
                compact[0][k] = i as i32;          // row
                compact[1][k] = j as i32;          // column
                compact[2][k] = matrix[i][j];      // value
                k += 1;
            }
        }
    }

    compact
}

fn main() {
    let matrix = vec![
        vec![0, 0, 3, 0, 8, 0, 0, 0, 0],
        vec![0, 0, 5, 7, 0, 0, 1, 0, 0],
        vec![0, 0, 0, 0, 0, 0, 0, 0, 0],
        vec![0, 2, 6, 0, 0, 4, 0, 0, 0],
        vec![0, 0, 0, 0, 9, 0, 0, 0, 0],
    ];

    let compact = compact_matrix(&matrix);

    println!("Compact matrix:");
    for i in 0..3 {
        for val in &compact[i] {
            print!("{} ", val);
        }
        println!();
    }
}



/*
run:

Compact matrix:
0 0 1 1 1 3 3 3 4 
2 4 2 3 6 1 2 5 4 
3 8 5 7 1 2 6 4 9 

*/

 

70+ SQL courses for beginners and professionals