//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();
}

Comments

Popular posts from this blog

Uploading Image to Sql Server Image Datatype in asp.net using fileupload Control

Get Running Sum of Query SQL Query