How to Represent and Transpose a Sparse Matrix in C++?

A Sparse Matrix (SM) is a popular data structure that is used to stored two-dimension Matrix when the total the empty/zero elements are the majority in the matrix. For example, the following is considered a sparse matrix (5 rows and 6 columns):

0 0 0 0 3 0 
0 0 0 0 0 0 
0 0 1 0 0 0 
0 0 0 0 0 0 
0 0 0 0 2 0 

while the following is not:

1 2 3 4 5 6
1 2 3 0 5 6
1 2 0 4 5 6
1 2 3 4 0 6
1 0 3 4 0 6

How to Represent Sparse Matrix in C/C++?

Generally speaking, you could represent matrix using the two dimensional arrays (static or dynamic), or using the std:vector:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

const int rows = 3;
const int cols = 3;
// static
double matrix[rows][cols];
// dynamic declaration
double **matrix; // a pointer, needs to allocate dynamically;
// allocation
matrix = new *double[rows]; // first dimension allocation
for (int i = 0; i < rows; i ++) {
   matrix[i] = new double[cols];
}
// and delete it
for (int i = 0; i < rows; i ++) {
   delete matrix[i];
}
delete[] matrix;
// using vector:
vector< vector<double> > matrix(rows,vector<double>(cols));

const int rows = 3;
const int cols = 3;
// static
double matrix[rows][cols];
// dynamic declaration
double **matrix; // a pointer, needs to allocate dynamically;
// allocation
matrix = new *double[rows]; // first dimension allocation
for (int i = 0; i < rows; i ++) {
   matrix[i] = new double[cols];
}
// and delete it
for (int i = 0; i < rows; i ++) {
   delete matrix[i];
}
delete[] matrix;
// using vector:
vector< vector<double> > matrix(rows,vector<double>(cols));

Let’s say, the storage size of the element-type of the matrix is a, and there are n empty elements and m non-empty elements. So roughly (without counting the size of pointers/object references in the above methods), the total storage size for the matrix is a(m + n)

If we only store the non-empty elements of the matrix and construct the matrix by filling the rest empty elements in the matrix on the fly, we may save space. Let’s say, we have the following element type definition in C/C++ using struct (for simplicity, using int type):

1
2
3
4
5

typedef struct {
        int row;
        int col;
        int val;
} element_type;

typedef struct {
        int row;
        int col;
        int val;
} element_type;

So, the total size to store the matrix is: (4 + 4 + a)n if we use the fixed-32bit integer to store the position of the non-empty elements. So, if (8 + a)n is much smaller than a(m + n), then it is a sparse matrix, so we can define the matrix type as:

1

typedef element_type *matrix_type;

typedef element_type *matrix_type;

How to use it? Let’s say we want to print the matrix nicely to the console, we then define such function:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void print(matrix_type mat, int len, int nrows, int ncols) {
        // declare full matrix using vector, initialized to zeros
        vector< vector<int> > matrix(nrows, vector<int>(ncols));
        // fill the non-empty elements
        for (int i = 0; i < len; i ++) {
                matrix[mat[i].row][mat[i].col] = mat[i].val;
        }
        for (int r = 0; r < nrows; r ++) {
                for (int c = 0; c < ncols; c ++) {
                        cout << matrix[r][c] << " ";
                }
                cout << endl;
        }
}

void print(matrix_type mat, int len, int nrows, int ncols) {
        // declare full matrix using vector, initialized to zeros
        vector< vector<int> > matrix(nrows, vector<int>(ncols));
        // fill the non-empty elements
        for (int i = 0; i < len; i ++) {
                matrix[mat[i].row][mat[i].col] = mat[i].val;
        }
        for (int r = 0; r < nrows; r ++) {
                for (int c = 0; c < ncols; c ++) {
                        cout << matrix[r][c] << " ";
                }
                cout << endl;
        }
}

matrix

The idea is to first construct the original matrix (two dimensional) using the vectors (or dynamic array).

How to Transpose a Sparse Matrix?

To transpose a matrix, we just need to swap the elements at (i, j) with the elements at (j, i). For example,

1 2 3
3 4 5

transposed, becomes:

1 3
2 4
3 5

This, turns out to be very easy for the sparse matrix representation:

1
2
3
4
5

void transpose(matrix_type mat, int len) {
        for (int i = 0; i < len; i ++) {
                swap(mat[i].col, mat[i].row);
        }
}

void transpose(matrix_type mat, int len) {
        for (int i = 0; i < len; i ++) {
                swap(mat[i].col, mat[i].row);
        }
}

Let’s test this:

1
2
3
4
5
6
7
8
9
10
11
12

int main() {
        const int sz = 3;
        // declare and initialize the matrix
        matrix_type mat = new element_type[sz] {{0, 0, 1}, {0, 1, 2}, {2, 1, 3}};
        cout << "Sparse matrix:" << endl;
        print(mat, 3, 3, sz);
        transpose(mat, sz);
        cout << "Transposed:" << endl;
        print(mat, 3, 3, sz);
        delete []mat;
        return 0;
}

int main() {
        const int sz = 3;
        // declare and initialize the matrix
        matrix_type mat = new element_type[sz] {{0, 0, 1}, {0, 1, 2}, {2, 1, 3}};
        cout << "Sparse matrix:" << endl;
        print(mat, 3, 3, sz);
        transpose(mat, sz);
        cout << "Transposed:" << endl;
        print(mat, 3, 3, sz);
        delete []mat;
        return 0;
}

Let’s compile this using g++:

1
2
3
4

g++ test.cpp
test.cpp: In function ‘int main()’:
test.cpp:37:41: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
matrix_type mat = new element_type[sz] {{0, 0, 1}, {0, 1, 2}, {2, 1, 3}};

g++ test.cpp
test.cpp: In function ‘int main()’:
test.cpp:37:41: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
matrix_type mat = new element_type[sz] {{0, 0, 1}, {0, 1, 2}, {2, 1, 3}};

OK, we need to add -std=c++11 or -std=gnu++11 to suppress the warning when declaring and initializing the matrix (basically it is a array pointer to the struct).

1
2
3
4
5
6
7
8
9

./a.out
Sparse matrix:
1 2 0
0 0 0
0 3 0
Transposed:
1 0 0
2 0 3
0 0 0

./a.out
Sparse matrix:
1 2 0
0 0 0
0 3 0
Transposed:
1 0 0
2 0 3
0 0 0

–EOF (The Ultimate Computing & Technology Blog) —