This program is about implementing an Adjacency Matrix using two dimensional matrix and pointers in C++.
In this program, the following methods are involved :
All of the above mentioned methods are mentioned in a custom made header file graph.h
In this program, the following methods are involved :
- graph() - a default constructor
- graph(int) - which accepts an integer parameter dim to allocate the matrix using malloc
- display() - which displays the adjacency matrix
- add_link(int,int) - which accepts two integer parameters, to check whether a link is needed or whether a link is already present
- add_node() - it creates a temporary matrix with an additional dimension, original matrix is copied to temporary matrix. Then the original matrix is freed from the memory and again reallocated with an additional dimension and then data in the temporary matrix is again copied into the original matrix and temporary matrix is freed from the memory
- path_exist(int,int) - returns 1 if path exists between two vertices and returns 0 if not.
//graph.h
#ifndef GRAPH_H_
#define GRAPH_H_
class graph
{
private :
int **mat;
int n;
public :
graph();
graph(int);
void display();
int add_link(int,int);
void add_node();
int path_exist(int,int);
};
#endif
Now, let us look at the graph.cpp file.
//graph.cpp
#include<iostream>
#include<stdlib.h>
#include "graph.h"
using namespace std;
int n1;
graph::graph()
{
mat=NULL;
}
graph::graph(int dim)
{
n=dim;
n1=n;
int i,j;
mat=(int **)malloc(n*sizeof(int));
for(i=0;i<n;i++)
mat[i]=(int *)malloc(n*sizeof(int));
}
void graph::display()
{
int i,j;
cout<<"\nYour current matrix is : \n";
cout<<"**************************\n";
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
cout<<*(*(mat+i)+j)<<" ";
cout<<"\n";
}
cout<<"\n";
}
int graph::add_link(int r,int c)
{
if(*(*(mat+r)+c)==0)
{
*(*(mat+r)+c)=1;
return 1;
}
else return 0;
}
void graph::add_node()
{
int i,j,**temp;
temp=new int *[n+1];
for(i=0;i<n+1;i++)
temp[i]=new int[n+1];
for(i=0;i<n;i++)
for(j=0;j<n;j++)
*(*(temp+i)+j)=*(*(mat+i)+j);
delete(mat);
n++;
n1=n;
mat=(int **)malloc(n*sizeof(int));
for(i=0;i<n;i++)
mat[i]=(int *)malloc(n*sizeof(int));
for(i=0;i<n;i++)
for(j=0;j<n;j++)
*(*(mat+i)+j)=*(*(temp+i)+j);
delete(temp);
}
int graph::path_exist(int r,int c)
{
if(*(*(mat+r)+c)==1)
return 1;
else return 0;
}
main()
{
int dim,ch,r,c,r1,c1;
cout<<"\nProgram to implement a matrix in c++ \n";
cout<<"\nEnter matrix dimension : ";
cin>>dim;
graph g(dim);
g.display();
do
{
cout<<"[1]Add link"<<" "<<"[2]Add Node"<<" "<<"[3]Path Exist"<<" "<<"[4]Display"<<" "<<"[5]Exit"<<"\n";
cout<<"\nEnter your choice : ";
cin>>ch;
switch(ch)
{
case 1:
cout<<"\nEnter row and column to insert : ";
cin>>r>>c;
if(r>n1-1 || c>n1-1)
cout<<"\nEnter valid row and column...\n";
else
{
int flag=g.add_link(r,c);
if(flag==1)
cout<<"\nInsertion completed....\n";
else
cout<<"\nLink already present...\n";
}
g.display();
break;
case 2:
g.add_node();
g.display();
break;
case 3:
cout<<"\nEnter row and column to check : ";
cin>>r1>>c1;
if(r1>n1-1 || c1>n1-1)
cout<<"\nEnter valid row and column...\n\n";
else
{
int flag1=g.path_exist(r1,c1);
if(flag1==1)
cout<<"\nPath exists..\n\n";
else
cout<<"\nPath doesn't exist..\n\n";
}
break;
case 4:
g.display();
break;
case 5: break;
default: cout<<"\nEnter correct choice .. \n";
break;
}
}while(ch!=5);
}
