TwitterFacebookGoogle PlusLinkedInRSS FeedEmail

Monday, October 22, 2012

Adjacency Matrix Representation of a graph

Adjacency Matrix: There are three most commonly used representation of graph: adjacency matrices, adjacency list and adjacency multilist. The choice of representation depends upon the application.
                     Let G=(V,E) is a undirected graph where V=5(No. of vertex in graph G), you can take any number of vertex you want, E is a set of pairs of vertices. We will join adjacent vertices  to create edges E. As you know that an undirected graph with n vertex have maximum of  n(n-1)/2 number of edges. So here undirected graph G will have maximum 10 edges.
                    Program for adjacency matrix representation of a graph will have two classes. Class gnode(graph node or vertex) which is nothing but the structure of how node of graph or vertex should look like and what attribute it has. Another Class undirectedgraph which represent the structure of undirected graph. Class gnode have two attribute first is id(value) and second is a pointer *ptr of gnode class, it mean that the pointer *ptr of a vertex will point to another vertex. Class undirectedgraph consist of an array of 5 vertex or  in programming term you can say it has array of 5 gnode class and two method addedge( ) and show( ). The  addedge( ) method will add edges between two adjacent vertices and show( ) method will display the connecting vertices of the graph.

     Now have a look at addedge( ) method of class undirectedgraph.


In this method, the two vertex to be joined is taken from the user in v1 and v2. A pointer *e of gnode class is first initialize with v2 and after that with v1. In coding you see v1-1 and v2-1 is used, this is because the array of vertex taken in class undirectedgraph have indexing form 0 so dont get confused.  When *e is initialize with v2, gnode class constructor is called and id of e will assign v2 value and ptr of e is set with address of v1 using setptr( ) method of gnode class and ptr of v1 is set with the address of e that has id value of v2. It means v1 is joined with e with has the value of v2. Again *e is initialize with v1, this time id value of e is   v1 and its ptr is set to the address of v2 whose ptr is set to the address of e. Look at complete program to make it more clear.

Program:

A word of caution: This program is created in Visual studio C++ IDE, so if you try to run this on TC++, you would be require to make some minor changes.



Click here to download complete program



#include<iostream>
#include<conio.h>
#define N 5
using namespace std;
class gnode
{
 int id;
 gnode *ptr;
public:
gnode(){}
gnode(int x)
{
      id=x;
 ptr=NULL;
}
//getters and setters for the attribute.
int getid()
{
return id;
}
void setid(int k)
{
id=k;
}
   gnode* getptr()
{
return ptr;
}
void setptr(gnode *n)
{
       ptr=n;
}
};
class undirectedgraph
{
gnode vertex[N];
public:
undirectedgraph(){}
    undirectedgraph(int edge)    //parameterised constructor  
       {
for(int i=0;i<N;i++)
{
vertex[i].setid(i+1);             //id value of each gnode is iniatialize with i+1
vertex[i].setptr(NULL);      //ptr is set to NULL for each gnode
}
// addedge() method is called for number of edge
for(int i=0;i<edge;i++)
{
addedge();
}
}
void addedge();
void show();
};
void undirectedgraph::addedge()
{
int v1,v2;
cout<<"Enter two vertex you want to join\n";
cin>>v1;
cin>>v2;
gnode *e=new gnode(v2);
e->setptr(vertex[v1-1].getptr());
vertex[v1-1].setptr(e);
e=new gnode(v1);
e->setptr(vertex[v2-1].getptr());
vertex[v2-1].setptr(e);
}
void undirectedgraph::show()
{
cout<<"graph is"<<endl;
for(int i=0;i<N;i++)
{
cout<<"Node:";
cout<<vertex[i].getid();
cout<<"is connected to ";
gnode *p=new gnode();
p=vertex[i].getptr();
while(p!=NULL)
{
cout<<p->getid()<<"\t";
p=p->getptr();

}
cout<<endl;
}

}
void main()
{
int e;
cout<<"Enter number of edges you want in graph of 5 vertex.\n";
cout<<"Edge number must be between 1-10\n";
cin>>e;
undirectedgraph g(e);
g.show();
getch();

}