Showing posts with label sparse matrix. Show all posts
Showing posts with label sparse matrix. Show all posts

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

Tuesday 9 August 2016

Sparse Matrix: Transpose

Sparse Matrix: 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 transpose(sparse a[], sparse b[])
{
          int i, j, k, n, p;
          n = a[0].val;

b[0].row = a[0].col;
b[0].col = a[0].row;
b[0].val  = n;

if( n > 0)
       {
                k = 1;
               for(i =  0; i<a[0].col ; i++)
              {
                     for(j=1; j<=n ; j++)
                    {
                           if(a[j].col == i)
                           {
                                 b[k].row = a[j].col;
                                     b[k].col = a[j].row;
                                     b[k].val = a[j].val;
                                     k++;
                            }
                     }
              }
        }

printf("\nThe 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;
sparse a[MAX], b[MAX];
printf("\nEnter  the no of rows and columns:\t");
scanf("%d%d",&m, &n);
readsparse(a, m, n);
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 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

Sparse Matrix

Sparse Matrix

#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 main()
{
int m, n;
sparse a[MAX];
printf("\nEnter  the no of rows and columns:\t");
scanf("%d%d",&m, &n);
readsparse(a, m, n);
}

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           3               -6
4           0               91
5           2               28