C Online Compiler
Example: Fast Transpose Algorithm for Sparse Matrix in C
C
C++
C#
Java
Python
PHP
main.c
STDIN
Run
// 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; }
Output
Clear
ADVERTISEMENTS