Example: Transpose Sparse Matrix using Triplet Representation in C

// Transpose Sparse Matrix using Triplet Representation
#include <stdio.h>
#include <stdlib.h> // For malloc and free

// Structure to represent a non-zero element
typedef struct {
    int row;
    int col;
    int value;
} Element;

// Structure to represent the sparse matrix in triplet form
typedef struct {
    int numRows;
    int numCols;
    int numNonZero;
    Element *elements; // Array of non-zero elements
} SparseMatrix;

// Function to create a sparse matrix from a dense 2D array
SparseMatrix* createSparseMatrix(int denseMatrix[][5], int rows, int cols) {
    SparseMatrix *sm = (SparseMatrix*) malloc(sizeof(SparseMatrix));
    if (sm == NULL) {
        perror("Failed to allocate SparseMatrix");
        exit(EXIT_FAILURE);
    }
    sm->numRows = rows;
    sm->numCols = cols;
    sm->numNonZero = 0;

    // Count non-zero elements first
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (denseMatrix[i][j] != 0) {
                sm->numNonZero++;
            }
        }
    }

    sm->elements = (Element*) malloc(sm->numNonZero * sizeof(Element));
    if (sm->elements == NULL) {
        perror("Failed to allocate elements array");
        free(sm);
        exit(EXIT_FAILURE);
    }

    int k = 0;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (denseMatrix[i][j] != 0) {
                sm->elements[k].row = i;
                sm->elements[k].col = j;
                sm->elements[k].value = denseMatrix[i][j];
                k++;
            }
        }
    }
    return sm;
}

// Function to print the triplet form of the sparse matrix
void printSparseMatrixTriplet(const SparseMatrix *sm) {
    printf("Sparse Matrix Triplet Form (Rows: %d, Cols: %d, Non-zero: %d):\n",
           sm->numRows, sm->numCols, sm->numNonZero);
    printf("Row | Col | Value\n");
    printf("-----------------\n");
    for (int i = 0; i < sm->numNonZero; i++) {
        printf("%3d | %3d | %5d\n", sm->elements[i].row,
               sm->elements[i].col, sm->elements[i].value);
    }
}

// Function to transpose a sparse matrix in triplet form
SparseMatrix* transposeSparseMatrix(const SparseMatrix *sm) {
    SparseMatrix *transpose_sm = (SparseMatrix*) malloc(sizeof(SparseMatrix));
    if (transpose_sm == NULL) {
        perror("Failed to allocate transpose SparseMatrix");
        exit(EXIT_FAILURE);
    }
    transpose_sm->numRows = sm->numCols; // Original columns become rows
    transpose_sm->numCols = sm->numRows; // Original rows become columns
    transpose_sm->numNonZero = sm->numNonZero;

    transpose_sm->elements = (Element*) malloc(transpose_sm->numNonZero * sizeof(Element));
    if (transpose_sm->elements == NULL) {
        perror("Failed to allocate transpose elements array");
        free(transpose_sm);
        exit(EXIT_FAILURE);
    }

    // Iterate through the original non-zero elements and swap row/col
    for (int i = 0; i < sm->numNonZero; i++) {
        transpose_sm->elements[i].row = sm->elements[i].col; // New row is old column
        transpose_sm->elements[i].col = sm->elements[i].row; // New col is old row
        transpose_sm->elements[i].value = sm->elements[i].value;
    }
    return transpose_sm;
}

// Helper to free memory
void freeSparseMatrix(SparseMatrix *sm) {
    if (sm) {
        free(sm->elements);
        free(sm);
    }
}

int main() {
    // Step 1: Define a sample sparse matrix as a dense 2D array
    int denseMatrix[4][5] = {
        {0, 0, 3, 0, 0},
        {0, 0, 0, 0, 7},
        {0, 1, 0, 0, 0},
        {0, 0, 0, 9, 0}
    };
    int rows = 4;
    int cols = 5;

    // Step 2: Convert dense matrix to sparse triplet representation
    SparseMatrix *original_sm = createSparseMatrix(denseMatrix, rows, cols);
    printf("Original Sparse Matrix:\n");
    printSparseMatrixTriplet(original_sm);

    // Step 3: Transpose the sparse matrix
    SparseMatrix *transposed_sm = transposeSparseMatrix(original_sm);
    printf("\nTransposed Sparse Matrix (swapped row/col, unsorted):\n");
    printSparseMatrixTriplet(transposed_sm);

    // Step 4: Free allocated memory
    freeSparseMatrix(original_sm);
    freeSparseMatrix(transposed_sm);

    return 0;
}