Question

How to compact a sparse matrix in C++

Answer 1

#include <iostream>
#include <vector>

using std::vector;

// 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
vector<vector<int>> compactMatrix(const vector<vector<int>>& matrix) {
    int rows = matrix.size();
    int cols = matrix[0].size();

    // Count non-zero elements
    int count = 0;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (matrix[i][j] != 0) {
                count++;
            }
        }
    }

    // Compact matrix has 3 rows: row index, col index, value
    vector<vector<int>> compact(3, vector<int>(count));

    int k = 0;

    // Fill compact matrix
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (matrix[i][j] != 0) {
                compact[0][k] = i;            // row
                compact[1][k] = j;            // column
                compact[2][k] = matrix[i][j]; // value
                k++;
            }
        }
    }

    return compact;
}

int main() {
    vector<vector<int>> matrix = {
        {0, 0, 3, 0, 8, 0, 0, 0, 0},
        {0, 0, 5, 7, 0, 0, 1, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 2, 6, 0, 0, 4, 0, 0, 0},
        {0, 0, 0, 0, 9, 0, 0, 0, 0}
    };

    vector<vector<int>> compact = compactMatrix(matrix);

    std::cout << "Compact matrix:\n";
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < compact[0].size(); j++) {
            std::cout << compact[i][j] << " ";
        }
        std::cout << "\n";
    }
}


/*
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