8. Sparse Matrix

  /* Title : Sparse Matrix Operations */



/* header files */
#include<stdio.h>
#include<conio.h>

typedef struct sparse        /* Declaration of structure */
{
int row, col, val;
}sparse; /* Array of structure is declared */

 int main(void) /* starting of main */
{

int iCol=0, iRow=0, iCol1=0, iRow1=0, icValue1=0, iVal1=0, iVal2=0, iVal3=0, iSwChoice=0;
int Mat1[6][6]={'\0'}, Mat2[6][6]={'\0'}, Mat3[6][6]={'\0'};

sparse sp1[40], sp2[40], sp3[40];

int accept(int [6][6],int,int);         /* function prototype */
int display_con(int [6][6],int,int);
int con_sp(int [6][6],int,int,sparse []);
int display_sp(sparse [],int );
int sp_con(int [6][6],int,int, sparse []);
int s_trans(sparse [],sparse []);
int f_trans(sparse [],sparse []);
int add(sparse [],sparse [],sparse []);



clrscr(); /* Clearing the screen */

do /* starting of do while loop */
{
printf("\n\tMenu");
printf("\n1 : Accept Conventional Matrix ");
printf("\n2 : Display Conventional Matrices");
printf("\n3 : Conventional to Sparse");
printf("\n4 : Sparse to Conventional");
printf("\n5 : Simple Transpose");
printf("\n6 : Fast Transpose");
printf("\n7 : Addition of Sparse Matrices");
printf("\n8 : Exit");

printf("\nEnter your choice\t");
scanf("%d",&iSwChoice);

switch (iSwChoice) /* starting of switch */
{

case 1 : printf("\nEnter the number of rows of Matrix : ");
scanf("%d",&iRow);
printf("\nEnter the number of columns of Matrix : ");
scanf("%d",&iCol);
accept(Mat1,iRow,iCol);
break;

case 2 : printf("\n\nThe first matrix is");
display_con(Mat1,iRow,iCol);
break;

case 3 : printf("\nThe Sparse Matrix of Matrix (A) is");
icValue1=con_sp(Mat1,iRow,iCol,sp1);
display_sp(sp1,icValue1);
break;

case 4: printf("\nThe Conventional Matrix of Sparse Matrix is");
sp_con(Mat1,iRow,iCol,sp1);
display_con(Mat1,iRow,iCol);
break;

case 5 : printf("\nThe Simple transpose is");
icValue1=con_sp(Mat1,iRow,iCol,sp1);
s_trans(sp1,sp2);
display_sp(sp2,icValue1);
break;

case 6 : printf("\nThe Fast transpose is");
con_sp(Mat1,iRow,iCol,sp1);
f_trans(sp1,sp2);
display_sp(sp2,icValue1);
break;

case 7 : printf("\n\nEnter the number of rows of Matrix (A) : ");
scanf("%d",&iRow);
printf("\nEnter the number of columns of Matrix (A) : ");
scanf("%d",&iCol);
accept(Mat1,iRow,iCol);
printf("\nEnter the number of rows of Matrix (B) : ");
scanf("%d",&iRow1);
printf("\nEnter the number of columns of Matrix (B) : ");
scanf("%d",&iCol1);
accept(Mat2,iRow1,iCol1);
iVal1=con_sp(Mat1,iRow,iCol,sp1);
iVal2=con_sp(Mat2,iRow1,iCol1,sp2);
display_sp(sp1,iVal1);
display_sp(sp2,iVal2);
printf("\nThe addition of two sparse matrices is");
iVal3=add(sp1,sp2,sp3);
display_sp(sp3,iVal3);
break;


} /* End of Switch */
} /* End of do while loop */
while(iSwChoice<=7&&iSwChoice!=0);
getch();
return 0;

}

/* accept function definition */
int accept(int a[6][6],int r,int c)
{

int i=0,j=0;

printf("\nEnter the elements of the matrix");
for(i=0;i<r;i++)
{
printf("\n");
for(j=0;j<c;j++)
{
scanf("%d",&a[i][j]);
printf("\t");
}
}
return 0;
}

/* display conventional matrix function definition */
int display_con(int a[6][6],int r,int c)
{

int i=0,j=0;

for(i=0;i<r;i++)
{
printf("\n\t\t");

for(j=0;j<c;j++)
{
printf("%d",a[i][j]);
printf("\t");
}
}
return 0;
}

int display_sp(sparse sp1[],int k)
{
int i=0;

printf("\nRow\t\tColumn\t\tValue");

for(i=0;i<k;i++)
{
printf("\n%d\t\t%d\t\t%d",sp1[i].row,sp1[i].col,sp1[i].val);
}
return 0;
}


int con_sp(int a[6][6],int r,int c,sparse sp1[])
{
int i=0,j=0,k=1;

for(i=0;i<r;i++)
{
for(j=0;j<c;j++)
{
if(a[i][j]!=0)
{
sp1[k].row=i;
sp1[k].col=j;
sp1[k].val=a[i][j];
k++;
}
}
}
sp1[0].row=i;
sp1[0].col=j;
sp1[0].val=k-1;
return (k);

}

int sp_con(int a[6][6],int r,int c,sparse sp1[])
{
int k=1,i=0,j=0;

for(i=0;i<r;i++)
{
for(j=0;j<c;j++)
{
if(k<sp1[0].val)
{
i=sp1[k].row;
j=sp1[k].col;
a[i][j]=sp1[k].val;
k++;
}
}
}
return 0;
}

/* simple transpose function definition */
int s_trans(sparse sp1[],sparse sp2[])
{
int i=1,k=0;
sparse temp;
if(sp1[0].val>0)
{
sp2[0].col=sp1[0].row;
sp2[0].row=sp1[0].col;
sp2[0].val=sp1[0].val;


for(k=0;k<=sp1[0].val;k++)
{
for(i=1;i<=sp1[0].val;i++)
{
if(k==sp1[i].col)
{
sp2[i].col=sp1[i].row;
sp2[i].row=sp1[i].col;
sp2[i].val=sp1[i].val;
}
}
}
}
return 0;
}

/* addition function definition */
int add(sparse sp1[],sparse sp2[],sparse sp3[])
{
int i=1,j=1,k=1;

if(sp1[0].row==sp2[0].row && sp1[0].col==sp2[0].col)
{
sp3[0].row=sp1[0].row;
sp3[0].col=sp1[0].col;

while(i<=sp1[0].val && j<=sp2[0].val)
{
if(sp1[i].row==sp2[j].row)
{
if(sp1[i].col==sp2[j].col)
{
sp3[k].row=sp1[i].row;
sp3[k].col=sp1[i].col;
sp3[k].val=(sp1[i].val)+(sp2[j].val);
i++;
j++;
k++;
}
else
{
if(sp1[i].col<sp2[j].col)
{
sp3[k].row=sp1[i].row;
sp3[k].col=sp1[i].col;
sp3[k].val=sp1[i].val;
i++;
k++;

}
else
{
sp3[k].row=sp2[j].row;
sp3[k].col=sp2[j].col;
sp3[k].val=sp2[j].val;
j++;
k++;

}
}
}
else
{
if(sp1[i].row<sp2[j].row)
{
sp3[k].row=sp1[i].row;
sp3[k].col=sp1[i].col;
sp3[k].val=sp1[i].val;
i++;
k++;

}
else
{
sp3[k].row=sp2[j].row;
sp3[k].col=sp1[j].col;
sp3[k].val=sp1[j].val;
j++;
k++;

}
}
}
while(i<=sp1[0].val)
{
sp3[k].row=sp1[i].row;
sp3[k].col=sp1[i].col;
sp3[k].val=sp1[i].val;
i++;
k++;

}
while(j<sp2[0].val)
{
sp3[k].row=sp2[j].row;
sp3[k].col=sp2[j].col;
sp3[k].val=sp2[j].val;
j++;
k++;

}
sp3[0].val=(k-1);
}
return k;
}

/* fast transpose function definition */
int f_trans(sparse sp1[],sparse sp2[])
{

int rowstart[25]={0},rowsize[25]={0};
int i=0;

if(sp1[0].val>0)
{

sp2[0].col=sp1[0].row;
sp2[0].row=sp1[0].col;
sp2[0].val=sp1[0].val;
rowsize[sp1[i].col]++;
rowstart[0]=1;
for(i=1;i<sp1[i].val;i++)
rowstart[i]=rowsize[i-1]+rowstart[i-1];

for(i=1;i<sp1[i].val;i++)
{
i=rowstart[sp1[i].col];
sp2[i]=sp1[i];
rowstart[sp1[i].col]++;
}
}

return (sp2[0].val);
}