#include<iostream> using namespace std; #include<stdlib.h> int V1,E1,V2,E2; int **graph_1,**graph_2; struct visited { int data; int flag; }; typedef struct visited visited; visited *visit1,*visit2; int isomorphic() { int i,j,flag; if(V1!=V2) { return 0; } else if(E1!=E2) { return 0; } else { for(i=0;i<V1;i++) { flag=0; for(j=0;j<V2;j++) { if(visit2[j].flag==0) { if(visit2[j].data==visit1[i].data) { visit2[j].flag=visit1[i].flag=1; flag=1; break; } } } if(!flag) break; } if(i<V1) return 0; } return 1; } int main() { int i,j,v1,v2; cout<<"\nEnter no. of vertex and edges for graph 1:"; cin>>V1>>E1; cout<<"\nEnter no. of vertex and edges for graph 2:"; cin>>V2>>E2; graph_1=(int**)malloc(sizeof(int*)*V1); for(i=0;i<V1;i++) graph_1[i]=(int*)malloc(sizeof(int)*V1); graph_2=(int**)malloc(sizeof(int*)*V2); for(i=0;i<V2;i++) graph_2[i]=(int*)malloc(sizeof(int)*V2); visit1=(visited*)malloc(sizeof(visited)*V1); visit2=(visited*)malloc(sizeof(visited)*V2); for(i=0;i<V1;i++) for(j=0;j<V1;j++) graph_1[i][j]=0; for(i=0;i<V2;i++) for(j=0;j<V2;j++) graph_2[i][j]=0; for(i=0;i<V1;i++) { visit1[i].data=0; visit1[i].flag=0; } for(i=0;i<V2;i++) { visit2[i].data=0; visit2[i].flag=0; } cout<<endl<<"Graph-1 Details :"; for(i=0;i<E1;i++) { cout<<"\nEnter vertices for edge "<<i+1<<" :"; cin>>v1>>v2; graph_1[v1-1][v2-1]=1; graph_1[v2-1][v1-1]=1; visit1[v1-1].data++; visit1[v2-1].data++; } cout<<endl<<"Graph-2 Details :"; for(i=0;i<E2;i++) { cout<<"\nEnter vertices for edge "<<i+1<<" :"; cin>>v1>>v2; graph_2[v1-1][v2-1]=1; graph_2[v2-1][v1-1]=1; visit2[v1-1].data++; visit2[v2-1].data++; } if(isomorphic()) { cout<<"\n\nBoth Graphs are Isomorphic"<<endl; } else { cout<<"\n\nBoth Graphs are not Isomorphic"<<endl; } return 0; }
Programs to check given two graphs are isomorphic
Subscribe to:
Posts (Atom)
No comments:
Post a Comment