Question

How to compact a sparse matrix in C

Answer 1

#include <stdio.h>
#include <stdlib.h>

// 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
int **compactMatrix(int **matrix, int rows, int cols, int *nonZeroCount) {
    int i, j;

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

    *nonZeroCount = count;

    // Compact matrix has 3 rows: row index, col index, value
    int **compact = (int **)malloc(3 * sizeof(int *));
    for (i = 0; i < 3; i++) {
        compact[i] = (int *)malloc(count * sizeof(int));
    }

    int k = 0;

    // Fill compact matrix
    for (i = 0; i < rows; i++) {
        for (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() {
    int rows = 5, cols = 9;
    int i, j;

    int **matrix = (int **)malloc(rows * sizeof(int *));
    for (i = 0; i < rows; i++) {
        matrix[i] = (int *)malloc(cols * sizeof(int));
    }

    int data[5][9] = {
        {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}
    };

    // Copy data into dynamic matrix
    for (i = 0; i < rows; i++)
        for (j = 0; j < cols; j++)
            matrix[i][j] = data[i][j];

    int nonZeroCount;
    int **compact = compactMatrix(matrix, rows, cols, &nonZeroCount);

    printf("Compact matrix:\n");
    for (i = 0; i < 3; i++) {
        for (j = 0; j < nonZeroCount; j++) {
            printf("%d ", compact[i][j]);
        }
        printf("\n");
    }

    printf("\n");

    // Free memory
    for (i = 0; i < 3; i++)
        free(compact[i]);
    free(compact);

    for (i = 0; i < rows; i++)
        free(matrix[i]);
    free(matrix);

    return 0;
}


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