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 OUTPUT */

BELLMAN FORD’S SINGLE SOURCE SHORTEST PATH ALGORITHM

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

  -> This C++ program is to implement Bellmen Ford algorithm.

  -> Bellmen Ford algorithm solves the single source shortest paths
     problem in the general case in which edge weights may be negative.

  -> This algorithm returns true if the graph contains no
     negative-weight cycles that are reachable from the source
  else returns the shortest paths from the source.

  -> This program works in Microsoft VC++ environment in windows xp

  -> Data structures used:
        Graph :: Adjacency matrix

  -> Header files used :
        1)iostream.h
 2)stdlib.h

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

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

#define MAX 20
#define INFINITY 9999

class bell_ford
{
private:
 int n;
 int graph[MAX][MAX];
 int start;
 int distance[MAX];
 int predecessor[MAX];
public:
 void read_graph();
 void initialize();
 void update();
 void check();
 void algorithm();
};

void bell_ford::read_graph()
{
 cout<<”Enter the no. of nodes in the graph ::”;
 cin>>n;
 cout<<”Enter the adjacency matrix for the graph ::\n”;
 for(int i=1;i<=n;i++)
  for(int j=1;j<=n;j++)
   cin>>graph[i][j];
 cout<<”Enter the start vertex ::”;
 cin>>start;
}

void bell_ford::initialize()
{
 for(int i=1;i<=n;i++)
 {
   distance[i]=INFINITY;
   predecessor[i]=0;
 }
 distance[start]=0;
}

void bell_ford::update()
{
 for(int i=1;i<=n-1;i++)
 {
  for(int u=1;u<=n;u++)
  {
   for(int v=1;v<=n;v++)
   {
    if(graph[u][v]!=0)
    {
     if(distance[v]>distance[u]+graph[u][v])
     {
      distance[v]=distance[u]+graph[u][v];
      predecessor[v]=u;
     }
    }
   }
  }
 }
}

void bell_ford::check()
{
 for(int u=1;u<=n;u++)
 {
  for(int v=1;v<=n;v++)
  {
   if(graph[u][v]!=0)
   {
    if(distance[v]>distance[u]+graph[u][v])
    {
     cout<<”does not exist’s “;
     return;
    }
   }
  }
 }

 cout<<”\n\nThere is no negative weight cycle and\n”;
 cout<<”****** The final paths and the distacnes are ******\n\n”;
 for(int i=1;i<=n;i++)
 {
  cout<<”path for node “<<i<<” is ::\n”;
  int arr[MAX],k=1;
  int j=i;
  while(predecessor[j]!=0)
  {
   arr[k]=predecessor[j];
   k++;
   j=predecessor[j];
  }
  for(–k;k>0;k–)
   cout<<arr[k]<<”->”;
  cout<<i<<endl;
  cout<<”distance is “<<distance[i]<<endl<<endl<<endl;
 }
}

void bell_ford::algorithm()
{
 read_graph();
 initialize();
 update();
 check();
}

void main()
{
 bell_ford obj;
 obj.algorithm();
}

TOWERS OF HANOI

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

  -> This C++ program is to solve the towers of hanoi problem.
  -> Implemented using recursion.
  -> Works in Microsoft VC++ 6.0 , windows xp.
  -> Header files used 1)iostream.h

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

#include<iostream.h>

void move(int n,char *s,char *i,char *d)
// s stands for source tower
// d stands for destination tower
// i stands for intermediate tower
{
 if(n>0)
 {
  move(n-1,s,d,i);
  // move n-1 disks from source to intermediate tower
  cout<<”disk “<<n<<” is moved from “<<s<<” to “<<d<<endl;
  // move the disk from to source to destination
  move(n-1,i,s,d);
  // move n-1 disks from intermediate to destination
 }
}

void main()
{
 cout<<”\n**********************************************************\n”;
 cout<<”This C++ program is to solve the towers of hanoi problem”;
 cout<<”\n**********************************************************\n”;
 cout<<”Enter the no. of disks “;
 int n;
 cin>>n;
 move(n,”source tower”,”intermediate tower”,”destination tower”);
}