//Graph Colouring
// Program for Graph Coloring using Backtracking.
#include<iostream.h>
#include<conio.h>
#include<stdio.h>
#include<process.h>
class GraphColor
{
int X[10],m,G[10][10],N;
public:
void GetData();
int NextValue(int);
void Mcoloring(int);
};
void GraphColor :: GetData()
{
cout << "\n Enter the numbers of nodes : ";
cin >> N;
cout << "\n Enter Graph : \n";
for(int i=1;i<=N;i++)
{
for(int j=1;j<=N;j++)
{
cin >> G[i][j];
X[j]=0;
}
}
cout << "\n Enter the colors : ";
cin >> m;
}
void GraphColor :: Mcoloring(int k)
{
while(1)
{
NextValue(k);
if(X[k]==0)
exit(0);
if(k==N)
{
for(int i=1;i<=N;i++)
cout << "\n Node " <<i<<" is colored with color " << X[i];
cout << endl;
// exit(0);
}
else
{
Mcoloring(k+1);
}
}
}
int GraphColor :: NextValue(int k)
{
while(1)
{
X[k]=(X[k]+1)%(m+1);
if(X[k]==0)
{
cout << "\n Color is not sufficient";
getch();
return 0;
}
else
{
for(int j=1;j<=N;j++)
{
if(G[j][k]!=0 && X[k]==X[j])
break;
}
if(j==N+1)
return (0);
}
}
}
void main()
{
GraphColor g;
clrscr();
g.GetData();
g.Mcoloring(1);
getch();
}
// Program for Graph Coloring using Backtracking.
#include<iostream.h>
#include<conio.h>
#include<stdio.h>
#include<process.h>
class GraphColor
{
int X[10],m,G[10][10],N;
public:
void GetData();
int NextValue(int);
void Mcoloring(int);
};
void GraphColor :: GetData()
{
cout << "\n Enter the numbers of nodes : ";
cin >> N;
cout << "\n Enter Graph : \n";
for(int i=1;i<=N;i++)
{
for(int j=1;j<=N;j++)
{
cin >> G[i][j];
X[j]=0;
}
}
cout << "\n Enter the colors : ";
cin >> m;
}
void GraphColor :: Mcoloring(int k)
{
while(1)
{
NextValue(k);
if(X[k]==0)
exit(0);
if(k==N)
{
for(int i=1;i<=N;i++)
cout << "\n Node " <<i<<" is colored with color " << X[i];
cout << endl;
// exit(0);
}
else
{
Mcoloring(k+1);
}
}
}
int GraphColor :: NextValue(int k)
{
while(1)
{
X[k]=(X[k]+1)%(m+1);
if(X[k]==0)
{
cout << "\n Color is not sufficient";
getch();
return 0;
}
else
{
for(int j=1;j<=N;j++)
{
if(G[j][k]!=0 && X[k]==X[j])
break;
}
if(j==N+1)
return (0);
}
}
}
void main()
{
GraphColor g;
clrscr();
g.GetData();
g.Mcoloring(1);
getch();
}
Comments
Post a Comment