Example: Fast Sparse Matrix Transpose in C++

// Fast Sparse Matrix Transpose
#include <iostream>
#include <vector>
#include <string> // For std::string

// Structure to represent a non-zero element in the sparse matrix
struct Term {
    int row;
    int col;
    int value;
};

// Structure to represent the sparse matrix itself
struct SparseMatrix {
    int numRows;
    int numCols;
    int numTerms; // Number of non-zero elements
    std::vector<Term> terms;
};

// Function to print a sparse matrix
void printSparseMatrix(const SparseMatrix& matrix, const std::string& title) {
    std::cout << title << ":\n";
    std::cout << "Rows: " << matrix.numRows << ", Cols: " << matrix.numCols 
              << ", Non-zero terms: " << matrix.numTerms << "\n";
    std::cout << "Row\tCol\tValue\n";
    for (const auto& term : matrix.terms) {
        std::cout << term.row << "\t" << term.col << "\t" << term.value << "\n";
    }
    std::cout << "\n";
}

// Function to perform fast transpose
SparseMatrix fastTranspose(const SparseMatrix& original) {
    SparseMatrix transposed;
    transposed.numRows = original.numCols;
    transposed.numCols = original.numRows;
    transposed.numTerms = original.numTerms;
    transposed.terms.resize(original.numTerms);

    if (original.numTerms == 0) {
        return transposed;
    }

    // Step 1: Create 'colCount' array to store the number of non-zero terms in each column
    std::vector<int> colCount(original.numCols, 0);
    for (int i = 0; i < original.numTerms; ++i) {
        colCount[original.terms[i].col]++;
    }

    // Step 2: Create 'startingPos' array to store the starting index for each column in the transposed matrix
    std::vector<int> startingPos(original.numCols, 0);
    // The first column's starting position in the transposed matrix is 0
    // For subsequent columns, the starting position is the sum of previous colCounts
    for (int i = 1; i < original.numCols; ++i) {
        startingPos[i] = startingPos[i-1] + colCount[i-1];
    }

    // Step 3: Populate the transposed matrix
    for (int i = 0; i < original.numTerms; ++i) {
        int originalCol = original.terms[i].col;
        int targetIndex = startingPos[originalCol]; // Get the correct index for this term in transposed
        
        transposed.terms[targetIndex].row = original.terms[i].col;   // New row is old column
        transposed.terms[targetIndex].col = original.terms[i].row;   // New col is old row
        transposed.terms[targetIndex].value = original.terms[i].value;
        
        startingPos[originalCol]++; // Increment starting position for the next term from this column
    }

    return transposed;
}

int main() {
    // Step 1: Define an example sparse matrix
    SparseMatrix originalMatrix = {
        4, // numRows
        5, // numCols
        6, // numTerms
        {
            {0, 4, 8},
            {2, 2, 3},
            {3, 0, 1},
            {0, 0, 10},
            {1, 1, 5},
            {3, 2, 7}
        }
    };

    // Step 2: Print the original matrix representation
    printSparseMatrix(originalMatrix, "Original Sparse Matrix");

    // Step 3: Perform fast transpose
    SparseMatrix transposedMatrix = fastTranspose(originalMatrix);

    // Step 4: Print the transposed matrix representation
    printSparseMatrix(transposedMatrix, "Transposed Sparse Matrix (Fast Transpose)");

    return 0;
}