PC_Project/mColoringSequential.cpp at master · SwastikUdupa/PC_Project · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<stdio.h>
#include<stdlib.h>
#include<omp.h>
#include<stdbool.h>
// Number of vertices in the graph
int V;

void printSolution(int color[]);

/* Function to check if the color can be safely assigned */

bool isSafe (int v, int graph[][100], int color[], int c)
{
    for (int i = 0; i < V; i++)
        if (graph[v][i]==1 && c == color[i])
            return false;
    return true;
}


bool graphColoringUtil(int graph[][100], int m, int color[], int v)
{
    /* return true if all vertices have been assigned some color */
    if (v == V)
        return true;

    /* for all colors from color 1 to m */
    for (int c = 1; c <= m; c++)
    {
        /* Check if assignment of color c to v is fine*/
        if (isSafe(v, graph, color, c))
        {
           color[v] = c;

           /* recur to assign colors to rest of the vertices */
           if (graphColoringUtil (graph, m, color, v+1) == true)
             return true;

            /* if the color c cannot be assigned */
           color[v] = 0;
        }
    }

    /* return false if no assignment is possible */
    return false;
}


bool graphColoring(int graph[][100], int m)
{
    // Initialize all color values as 0.
    int *color = new int[V];
    for (int i = 0; i < V; i++)
       color[i] = 0;

    bool ret=false;
    if (graphColoringUtil(graph, m, color, 0 ) == false)
    {
      printf("Solution does not exist");
      return false;
    }

    printSolution(color);
    return true;
}

void printSolution(int color[])
{
    printf("Solution Exists:"
            " Following are the assigned colors \n");
    for (int i = 0; i < V; i++)
      printf(" %d ", color[i]);
    printf("\n");
}

int main()
{

    printf("Enter Number of vertices\n");
    scanf("%d",&V);
    int graph[100][100];
/* Example Graph
    (3)---(2)
     |   / |
     |  /  |
     | /   |
    (0)---(1)
    {{0, 1, 1, 1},
        {1, 0, 1, 0},
        {1, 1, 0, 1},
        {1, 0, 1, 0},
    };
*/
    printf("Enter Adjacency Matrix\n");

    for(int i=0;i<V;i++)
    {
      for (int j=0;j<V;j++)
      {
        scanf("%d", &graph[i][j]);
      }
    }
    printf("Enter Number of colours\n");
    int m;
     // Number of colors
     scanf("%d", &m);
    graphColoring (graph, m);
    return 0;
}