SPARSE MATRIX ADDITION


/******************************************************

-> This C++ program is to perform sparse matrix
   addition.

   THE FOLLOWING ASSUMPTIONS ARE MADE IN ORDER TO
 SIMPLIFY THE PROGRAM
 _______________________________________________

   1) The row numbers and column numbers are supposed
      to be start from 1.
 2) There are no duplicates in the input

-> Data structures used
 Matrix : multi linked list

-> This program works in microsoft vc++ in windows xp

*******************************************************/

#include<iostream.h>
#include<stdlib.h>

class sparse
{
private:
 int r;          // row number
 int c;          // column number
 sparse *rptr;   // row pointer
 sparse *cptr;   // column header
 int data;       // actual data
public:
 sparse * create(sparse*);
 void display(sparse*);
 void add(sparse*,sparse*);
};

sparse * sparse::create(sparse*h)
{
 cout<<“\nEnter the no. of rows ::”;
 cin>>r;
 cout<<“Enter the no. of columns ::”;
 cin>>c;

 // create the head node
 h=new sparse;
 h->r=r;
 h->c=c;
 h->rptr=h;
 h->cptr=h;
 h->data=0;

 // create column headers
 sparse *ptr;
 int i,j,d;
 ptr=h;
 for(i=1;i<=c;i++)
 {
  sparse *node;
  node=new sparse;
  node->r=0;
  node->c=i;
  node->data=0;
  node->rptr=h;
  node->cptr=node;

  ptr->rptr=node;
  ptr=node;
 }

 // create row headers
 ptr=h;
 for(i=1;i<=r;i++)
 {
  sparse *node;
  node=new sparse;
  node->r=i;
  node->c=0;
  node->data=0;
  node->rptr=node;
  node->cptr=h;

  ptr->cptr=node;
  ptr=node;
 }
 cout<<“\n now enter the non zero elements ”
  <<“one by one\n”;
 cout<<“\nEnter row number,column number,data\n”;
 cout<<“Enter (0 0 0) to stop ::”;
 cin>>i>>j>>d;
 if(i>r || j>c ||i<1 ||j<1)
 {
  cout<<” error input”;
  exit(1);
 }
 while(i&&j&&d)
 {
  sparse * row_header=h->cptr;
  sparse * column_header=h->rptr;

  // find the correct row header and column header
  while(row_header->r<i)
   row_header=row_header->cptr;

  while(column_header->c<j)
   column_header=column_header->rptr;

  sparse *ptr1;
  sparse *ptr2;

  // find the correct position to insert
  sparse*row_ptr=row_header;
  while(row_ptr->c<j)
  {
   ptr1=row_ptr;
   row_ptr=row_ptr->rptr;
   if(row_ptr==row_header)
    break;
  }

  sparse*column_ptr=column_header;
  while(column_ptr->r<i)
  {
   ptr2=column_ptr;
   column_ptr=column_ptr->cptr;
   if(column_ptr==column_header)
    break;
  }

  sparse *node;
  node=new sparse;
  node->r=i;
  node->c=j;
  node->data=d;

  ptr1->rptr=node;
  ptr2->cptr=node;
  node->rptr=row_ptr;
  node->cptr=column_ptr;

  cout<<“\nEnter row number,column number,data\n”;
  cout<<“Enter (0 0 0) to stop ::”;
  cin>>i>>j>>d;
  if(i>r || j>c )
  {
   cout<<” error input”;
   exit(1);
  }
 }
 return h;
}

void sparse::display(sparse*h)
{
 sparse *right;
 right=h->cptr;
 
 while(right!=h)
 {
  sparse *r=right;
  right=right->rptr;
  while(right!=r)
  {
   cout<<right->r
    <<‘\t'<<right->c
    <<‘\t'<<right->data<<endl;
   right=right->rptr;
  }
  right=right->cptr;
 }
}

void sparse::add(sparse*h1,sparse*h2)
{
 if(h1->r==h2->r && h1->c==h2->c)
  cout<<“The addition of the two given ”
   <<“sparse matrices is ::\n”;
 else
 {
  cout<<“addition is not possible”;
  exit(1);
 }
 sparse *r1;
 r1=h1->cptr;
 sparse *r2;
 r2=h2->cptr;
 
 while(r1!=h1)
 {
  sparse * p1=r1;
  r1=r1->rptr;

  sparse * p2=r2;
  r2=r2->rptr;

  while(r1!= p1 && r2!=p2)
  {
   if(r1->c==r2->c)
   {
    cout<<r1->r<<‘\t'<<r1->c<<‘\t’
    <<(r1->data+r2->data)<<endl;
    r1=r1->rptr;
    r2=r2->rptr;
   }
   else if(r1->c>r2->c)
   {
    cout<<r2->r<<‘\t'<<r2->c<<‘\t’
    <<r2->data<<endl;
    r2=r2->rptr;
   }
   else
   {
    cout<<r1->r<<‘\t'<<r1->c<<‘\t’
    <<r1->data<<endl;
    r1=r1->rptr;
   }
  }
  while(r1!=p1)
  {
   cout<<r1->r<<‘\t'<<r1->c<<‘\t’
    <<r1->data<<endl;
   r1=r1->rptr;
  }
  while(r2!=p2)
  {
   cout<<r2->r<<‘\t'<<r2->c<<‘\t’
    <<r2->data<<endl;
   r2=r2->rptr;
  }
  r1=r1->cptr;
  r2=r2->cptr;
 }
}

void main()
{
 cout<<“******************************************”;
 cout<<“\nThis program is to perform addition of \n”;
 cout<<” two sparse matrices \n”;
 cout<<“*******************************************\n”;
 sparse s;
 sparse *h1=NULL,*h2=NULL;
 cout<<“Enter the values for sparse matrix 1 ::\n”;
 cout<<“****************************************\n”;
 h1=s.create(h1);
 s.display(h1);
 cout<<“Enter the values for sparse matrix 2 ::\n”;
 cout<<“****************************************\n”;
 h2=s.create(h2);
 s.display(h2);
 s.add(h1,h2);
}

//SAMPLE O/P

38 thoughts on “SPARSE MATRIX ADDITION”

  1. how can we print that

    11111111111111 ———|
    1111111111 11 |—— |
    11 11 | | |
    11111111111111 |——–|

    Saprse Matrix in a fprmat
    I want code in list form

  2. how can we print that

    start ———|
    |—— |
    | | |
    |——–|

    Saprse Matrix in a fprmat
    I want code in list form

  3. this is really very good site as if i will learn alot from that but can u e-mail me the pdf file for data structure on my e-mail.thanks

  4. Good, but it can be more easy according to new user. If any other sit also avlable for a beginner please reply.

    Thanks a lot….

  5. Good, but it can be more easy according to new user. If any other sit also avlable for a beginner please reply.

    1. The short answer is- Above matrix is not sparse.
      The long answer is- Above matrix is not sparse because in this matrix
      No. of non zero elements> No. of zero elements.
      and the definition of sparse matrix says that a matrix is called sparse if
      No. of non zero elements< No. of zero elements.

  6. Write a program to represent sparse integer matrices (that is, most entries are zero) using linked
    lists. For an m  n matrix Amn, let A(i; j), where 0  i  m and 0  j  n, denote the entry at
    ith row and jth column. Your program should store only non-zero entries of A using linked lists as
    described in the following.
    Matrix representation
    Corresponding to each non-zero entry A(i; j), your program should create a record containing
    the following seven elds:
    1. i
    2. j
    3. A(i; j) value
    4. `Up’ pointer pointing to A(k; j), where k i and A(k; j) 6= 0, which is the next element
    in column j. That is, A(l; j) = 0 for all l 2 fi + 1; : : : ; k 􀀀 1g.
    6. `Left’ pointer pointing to A(i; k), where k j and A(i; k) 6= 0, which is the next element in
    row j. That is, A(i; l) = 0 for all l 2 fj + 1; : : : ; k 􀀀 1g.
    For each input matrix Amn, in addition to its non-zero entries, your program should also store
    two pointer arrays R and C of size m and n respectively, where R[i] and C[j] store pointer to the
    rst non-zero element in row i and column j respectively.
    Matrix input format
    To read a matrix A as input, your program should read m and n followed by each row of A.
    Consecutive row elements are tab (`nt’) separated.

    Matrix operations::

    Implement the following ve operations on matrices stored in the above fashion.
    1. Matrix transpose: For a matrix Amn, output AT . Your implementation should not make a
    copy of the matrix elements in memory.
    2. Matrix addition: For two matrices Amn and Bmn, output A + B.
    3. Matrix multiplication: For two matrices Amn and Bnk, output A  B.
    4. Row permutation: The input to your program is a matrix Amn and a permutation of its row
    numbers given by the ordered sequence fp0; : : : ; pm􀀀1g, where pi denotes the new position of
    row i. Your program should output Bmn such that B(pi; j) = A(i; j) for all i 2 f0; : : : ;m􀀀1g
    and j 2 f0; : : : ; n 􀀀 1g. Your implementation should not make a copy of the matrix elements
    in memory.
    5. Column permutation: The input to your program is a matrix Amn and a permutation of
    its column numbers given by the ordered sequence fp0; : : : ; pn􀀀1g, where pj denotes the new
    position of column j. Your program should output Bmn such that B(i; pj) = A(i; j) for all
    i 2 f0; : : : ;m 􀀀 1g and j 2 f0; : : : ; n 􀀀 1g. Your implementation should not make a copy of
    the matrix elements in memory.
    Ensure that the output of addition and multiplication follows the same representation scheme
    where only the non-zero elements are stored in memory.

    Output format::

    Implement a print method to print a matrix and use the same procedure to print the output
    for the above operations. The print method should print the number of rows and columns of the
    matrix in separate lines followed by all its elements (including the zeroes) in row-wise manner.
    Each row should be printed in a separate line and the row elements should be tab separated. Your
    program should not print anything to the output except the output matrix.

  7. Write a program in C to read a sparse matrix of integer values and to search the sparse matrix for an element specified by the user. Print the result of the search appropriately. Use the triple to represent an element in the sparse matrix.

  8. hi

    i tried to implement the code using a matrix for row headers and column headers but i have a problem some where please help me out..

    #include
    using namespace std;

    class sparse{

    int row;
    int column;
    int data;
    sparse *row_link;
    sparse *column_link;
    public:
    sparse * create(sparse*);
    void display(sparse*);

    };

    sparse * sparse::create(sparse*h)
    {
    cout<>row;
    cout<>column;

    // create the head node
    sparse *columnheader[column];
    sparse *rowheader[row];

    //create head node
    h=new sparse;
    h->row=row;
    h->column=column;
    h->data=0;
    h->row_link=columnheader[column];
    h->column_link=rowheader[row];

    //create rowheader

    sparse *ptr;
    int i,j,d;
    ptr=h;
    for (i=0;irow=i;
    rowheader[i]->column=0;
    rowheader[i]->row_link=h;
    rowheader[i]->column_link=rowheader[i];

    ptr->column_link=rowheader[i];
    ptr=rowheader[i];

    }

    //create columnheader

    ptr=h;
    for (i=0;irow=0;
    columnheader[i]->column=i;
    columnheader[i]->row_link=columnheader[i];
    columnheader[i]->column_link=h;

    ptr->row_link=columnheader[i];
    ptr=columnheader[i];

    }
    cout<<"\n now enter the non zero elements "
    <<"one by one\n";
    cout<<"\nEnter row number,column number,data\n";
    cout<>i>>j>>d;
    if(i>row || j>column ||i<1 ||j<1)
    {
    cout<column_link;
    sparse * column_header=h->row_link;

    // find the correct row header and column header
    while(row_header->rowcolumn_link;

    while(column_header->columnrow_link;

    sparse *ptr1;
    sparse *ptr2;

    // find the correct position to insert
    sparse*row_ptr=row_header;
    while(row_ptr->columnrow_link;
    if(row_ptr==row_header)
    break;
    }

    sparse*column_ptr=column_header;
    while(column_ptr->row
    column_link;
    if(column_ptr==column_header)
    break;
    }

    sparse *node;
    node=new sparse;
    node->row=i;
    node->column=j;
    node->data=d;

    ptr1->row_link=node;
    ptr2->column_link=node;
    node->row_link=row_ptr;
    node->column_link=column_ptr;

    cout<<"\nEnter row number,column number,data\n";
    cout<>i>>j>>d;
    if(i>row || j>column )
    {
    cout<column_link;

    while(right!=h)
    {
    sparse *r=right;
    right=right->row_link;
    while(right!=r)
    {
    cout<row
    <<'\t'<column
    <<'\t'<data<row_link;
    }
    right=right->column_link;
    }
    }

    int main()
    {

    sparse s;
    sparse *h1=NULL;
    cout<<"Enter the values for sparse matrix \n";
    h1=s.create(h1);
    s.display(h1);

    }

  9. Hi!. I am trying to trasnpose the matrix the matrix before adding the I ma having issues with that, can you help. I can only scwith the cols to rows, but not the rows to coulms, ezample given:
    1,1,3
    3,1,5
    the result should be
    1,1,3
    1,3,5
    I thoguth of creating a new matrix and switching the los and rows, and return it. here is my code:

    template
    sparse * sparse::traspose(sparse*h)
    {
    sparse *right;
    sparse *left;

    right=h->cptr;
    left=h->cptr;

    while(right!=h)
    {
    sparse *r=right;
    sparse *l=left;

    left=right->rptr;
    right=right->rptr;

    while(right!=r)

    {

    left->c= right->r;
    left->r=right->c;
    left->data=right->data;

    left=right->rptr;
    right=right->rptr;
    }
    left=right->cptr;
    right=right->cptr;
    }

    right=h->rptr;
    left=h->rptr;

    while(right!=h)
    {
    sparse *r=right;
    sparse *l=left;

    left=right->cptr;
    right=right->cptr;
    int x=0;
    while(right!=r)
    //while(x c= right->r;
    left->r=right->c;
    left->data=right->data;

    left=right->cptr;
    right=right->cptr;
    }
    left=right->rptr;
    right=right->rptr;
    }

    return left;

    }

  10. What i do not realize is if truth be told how you are now not actually much more neatly-liked than you might be right now.
    You’re very intelligent. You already know therefore significantly when it comes to this matter, produced me personally imagine it from a lot of varied angles. Its like men and women aren’t
    involved except it’s one thing to accomplish with Woman gaga! Your personal stuffs excellent. Always take care of it up!

  11. I think this is one of the most significant information for me.
    And i am glad reading your article. But should remark on few general things, The site style is wonderful, the articles is really great : D.

    Good job, cheers

  12. Hello There. I found your blog the usage of msn. That is a very neatly written
    article. I’ll be sure to bookmark it and return to read extra of your useful info. Thank you for the post. I’ll definitely comeback.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s