Sunday 14 August 2016

Sparse Matrix: Fast Transpose

Sparse Matrix: Fast Transpose

#include<stdio.h>
#include<stdlib.h>
#define MAX 100

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


void readsparse(sparse a[], int m, int n)
{
            int i, j, k, item, p;
            a[0].row = m;
            a[0].col = n;
            k = 1;

            printf("\nEnter the elements:\n");
            for(i=0; i<m; i++)
            {
                        for(j=0; j<n; j++)
                        {
                                    scanf("%d",&item);
                                    if(item == 0)
                                                continue;
                                    a[k].row = i;
                                    a[k].col = j;
                                    a[k].val = item;
                                    k++;
                        }
            }
            a[0].val = k-1;

            printf("\nThe entered sparse matrix is:\n");
            printf("\nRow\tColumn\tValue\n");
            for(p=0;  p<=a[0].val;  p++)
            {
                        printf("%d\t", a[p].row);
                        printf("%d\t", a[p].col);
                        printf("%d\n", a[p].val);
            }
}

void fast_transpose(sparse a[],  sparse b[])
{
            int row_terms[100],  start_pos[100];
            int i,  j,  p;       

            int numTerms = a[0].val;
            int numCols = a[0].col;
             
            b[0].row = numCols;
            b[0].col = a[0].row;
            b[0].val = numTerms;
            if(numTerms>0)
            {
                        for(i =0; i<numCols;  i++)
                                                row_terms[i] = 0;

                        for(i=1; i<=numTerms; i++)
                                                row_terms[a[i].col]++;

                        start_pos[0]=1;

                        for(i=1; i<numCols; i++)
                                                start_pos[i] = start_pos[i-1] + row_terms[i-1];

                        for(i=1; i<=numTerms; i++)
                        {
                                                j = start_pos[a[i].col]++;
                                    b[j].row = a[i].col;
                                                b[j].col = a[i].row;
                                                b[j].val = a[i].val;
                        }
             }
            printf("\nThe Fast Transpose sparse matrix is:\n");
            printf("\nRow\tColumn\tValue\n");
            for(p=0; p<=a[0].val; p++)
            {
                        printf("%d\t", b[p].row);
                        printf("%d\t", b[p].col);
                        printf("%d\n", b[p].val);
            }
}
void main()
{
            int m, n, key;
            sparse a[MAX], b[MAX];
            printf("\nEnter  the no of rows and columns:\t");
            scanf("%d%d",&m, &n);

            readsparse(a, m, n);
             fast_transpose(a, b);
}

Output:
Enter  the no of rows and columns:      6 6


Enter the elements:
15   0   0   22   0   -15
0   11   3   0    0   0
0   0   0   -6   0   0
0   0    0    0   0   0
91  0   0   0   0   0
0   0   28  0   0   0

The entered sparse matrix is:

Row     Column  Value
6       6       8
0       0       15
0       3       22
0       5       -15
1       1       11
1       2       3
2       4       -6
4       1       91
5       3       28

The Fast Transpose sparse matrix is:

Row    Column           Value
6          6                      8
0          0                      15
1          1                      11
1          4                      91
2          1                      3
3          0                      22
3          5                      28
4          2                      -6
5          0                      -15

No comments:

Post a Comment