# Represent Sparse Matrix using array and perform Matrix Addition,Simple Transpose and Fast Transpose

/*Represent sparse matrix using array and perform matrix addition,simple
transpose and fast transpose - DFS */

#include<stdio.h>
#include<conio.h>
#define MAX 20
void printsparse(int[][3]);
void transpose(int[][3],int[][3]);
void Fast_transpose(int B1[MAX][3],int B2[MAX][3]);
void main()
{
int b1[MAX][3],b2[MAX][3],m,n,b3[MAX][3],op;
clrscr();
do
{
printf("\n3)Display the first matrix");
printf("\n4)Display the second matrix");
printf("\n6)Simple transpose of the first matrix");
printf("\n7)Fast transpose of the first matrix");
printf("\n8)Quit");
scanf("%d",&op);
switch(op)
{
case 3: printsparse(b1);break;
case 4: printsparse(b2);break;
case 6: transpose(b1,b3);printsparse(b3);break;
case 7: Fast_transpose(b1,b3);printsparse(b3);break;
}
}while(op!=8);
}
{
int i,t,m,n;

printf("\n Enter the size of matrix (rows,columns)");
scanf("%d%d",&m,&n);
b[0][0]=m;
b[0][1]=n;

printf("\nEnter no. of non-zero elements:");
scanf("%d",&t);
b[0][2]=t;
for(i=1;i<=t;i++)
{
printf("\n Enter the next triple(row,column,value) :");
scanf("%d%d%d",&b[i][0],&b[i][1],&b[i][2]);
}
}
void printsparse(int b[MAX][3])
{
int i,n;
n=b[0][2];   //no of 3-triples
printf("\nrows = %d\tcolumns = %d",b[0][0],b[0][1]);
printf("\n");
for(i=1;i<=n;i++)
printf("%d\t%d\t%d\n",b[i][0],b[i][1],b[i][2]);
}
void transpose(int b1[][3],int b2[][3])
{
int i,j,k,n;
b2[0][0]=b1[0][1];
b2[0][1]=b1[0][0];
b2[0][2]=b1[0][2];
k=1;
n=b1[0][2];
for(i=0;i<b1[0][1];i++)
for(j=1;j<=n;j++)
/* if a column number of current triple == i
then insert the current triple in b2 */
if(i== b1[j][1])
{
b2[k][0]=i;
b2[k][1]=b1[j][0];
b2[k][2]=b1[j][2];
k++;
}
}

void Fast_transpose(int B1[MAX][3],int B2[MAX][3])
{
int m,n,t,i,col_num,location;
int total[MAX],index[MAX];
m=B1[0][0];n=B1[0][1];t=B1[0][2];
B2[0][0]=n;B2[0][1]=m;B2[0][2]=t;
for(i=0;i<n;i++)
total[i]=0;
for(i=1;i<=t;i++)
{
col_num=B1[i][1];
total[col_num]++;
}
index[0]=1;
for(i=1;i<n;i++)
index[i]=index[i-1]+total[i-1];

for(i=1;i<=t;i++)
{
col_num=B1[i][1];
location=index[col_num];
index[col_num]++;
B2[location][0]=B1[i][1];
B2[location][1]=B1[i][0];
B2[location][2]=B1[i][2];
}
}

{
int t1,t2,i,j,k;
t1=b1[0][2];
t2=b2[0][2];
i=j=k=0;
b3[0][0]=b1[0][0];
b3[0][1]=b1[0][1];
while(i<=t1 && j<=t2)
{
if(b1[i][0] < b2[j][0])
{
b3[k][0]=b1[i][0];
b3[k][1]=b1[i][1];
b3[k][2]=b1[i][2];
k++;
i++;
continue;//go to  end of the loop
}
if(b2[j][0] < b1[i][0])
{
b3[k][0]=b2[j][0];
b3[k][1]=b2[j][1];
b3[k][2]=b2[j][2];
k++;
j++;
continue;//go to end of loop
}
if(b1[i][1] < b2[j][1])
{
b3[k][0]=b1[i][0];
b3[k][1]=b1[i][1];
b3[k][2]=b1[i][2];
k++;
i++;
continue;//go to end of loop
}
if(b2[j][1] < b1[i][1])
{
b3[k][0]=b2[j][0];
b3[k][1]=b2[j][1];
b3[k][2]=b2[j][2];
k++;
j++;
continue; //go to end of loop
}
b3[k][0]=b1[i][0];
b3[k][1]=b1[i][1];
b3[k][2]=b1[i][2]+b2[j][2];
k++;
i++;
j++;

}
while(i<=t1)
{
b3[k][0]=b1[i][0];
b3[k][1]=b1[i][1];
b3[k][2]=b1[i][2];
i++;
k++;
}
while(j<=t2)
{
b3[k][0]=b2[j][0];
b3[k][1]=b1[j][1];
b3[k][2]=b1[j][2];
j++;
k++;
}
b3[0][2]=k-1;
}