Example: Fast Transpose Algorithm for Sparse Matrix in C

// Fast Transpose Algorithm for Sparse Matrix
#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
// (Re-using from Approach 2 for completeness)
SparseMatrix* createSparseMatrix(int denseMatrix[][5], int rows, int cols) {
    SparseMatrix *sm = (SparseMatrix*) malloc(sizeof(SparseMatrix));
    if (sm == NULL) { perror("malloc SparseMatrix failed"); exit(EXIT_FAILURE); }
    sm->numRows = rows;
    sm->numCols = cols;
    sm->numNonZero = 0;
    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("malloc elements failed"); 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
// (Re-using from Approach 2 for completeness)
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 free memory
// (Re-using from Approach 2 for completeness)
void freeSparseMatrix(SparseMatrix *sm) {
    if (sm) {
        free(sm->elements);
        free(sm);
    }
}

// Function for Fast Transpose of a sparse matrix
SparseMatrix* fastTransposeSparseMatrix(const SparseMatrix *sm) {
    SparseMatrix *transpose_sm = (SparseMatrix*) malloc(sizeof(SparseMatrix));
    if (transpose_sm == NULL) { perror("malloc transpose SparseMatrix failed"); 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;

    if (sm->numNonZero == 0) { // Handle empty matrix case
        transpose_sm->elements = NULL;
        return transpose_sm;
    }

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

    // Arrays to help with sorting:
    // rowTerms[i]: Stores the number of non-zero terms in original column 'i'.
    // startingPos[i]: Stores the starting position in the transposed elements array
    //                 for elements that will have 'i' as their new row index (original column index).
    int *rowTerms = (int*) calloc(sm->numCols, sizeof(int)); // Initialize to 0
    int *startingPos = (int*) calloc(sm->numCols, sizeof(int)); // Initialize to 0

    if (rowTerms == NULL || startingPos == NULL) {
        perror("malloc helper arrays failed");
        free(rowTerms); free(startingPos);
        free(transpose_sm->elements); free(transpose_sm);
        exit(EXIT_FAILURE);
    }

    // Step 1: Count the number of non-zero elements in each column of the original matrix
    for (int i = 0; i < sm->numNonZero; i++) {
        rowTerms[sm->elements[i].col]++; // Each original column will become a new row
    }

    // Step 2: Determine the starting position for each new row in the transposed matrix
    startingPos[0] = 0;
    for (int i = 1; i < sm->numCols; i++) {
        startingPos[i] = startingPos[i-1] + rowTerms[i-1];
    }

    // Step 3: Populate the transposed matrix
    for (int i = 0; i < sm->numNonZero; i++) {
        int original_col = sm->elements[i].col;
        int new_pos = startingPos[original_col];

        transpose_sm->elements[new_pos].row = sm->elements[i].col;   // New row is original column
        transpose_sm->elements[new_pos].col = sm->elements[i].row;   // New col is original row
        transpose_sm->elements[new_pos].value = sm->elements[i].value;

        startingPos[original_col]++; // Increment position for the next element in this new row
    }

    free(rowTerms);
    free(startingPos);

    return transpose_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: Perform fast transpose
    SparseMatrix *fast_transposed_sm = fastTransposeSparseMatrix(original_sm);
    printf("\nFast Transposed Sparse Matrix (sorted by new row):\n");
    printSparseMatrixTriplet(fast_transposed_sm);

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

    return 0;
}