Graph Coloring in C: Unable to identify the logical error

Question

I am trying to implement the graph coloring algorithm in C, this implementation is based on how we assign the colors by iterating through the adjacency matrix. I am unable to get it after assigning a color to the second vertex.

Here is the code of my program:

int n, a[10][10], i, j, k, c[10], max = 0, col, ct = 0, rt = 0, m, count = 2;
void main() {
    printf("enter n\n");
    scanf("%d", &n);
    printf("enter the Adjacency Matrix for %d rows and %d columns\n", n, n);
    for (i = 0; i < n; i++) {
       c[i] = 0;
       for (j = 0; j < n; j++)
           scanf("%d", &a[i][j]);
    }
    c[0] = 1;
    c[1] = 2;
    for (i = 1; i < n; i++) {  
        for (j = 0; j < n; j++)
            if (a[i][j] > 0) {  
                m = 0;
                for (col = 0; col < n; col++) {
                    if (a[i][col] > 0)
                        rt++;
                    if (a[col][i] > 0)
                        ct++;
                }
                m = rt;
                if (ct > rt)
                    m = ct;
                if (m < 2) {
                    if (a[0][i] > 0)
                        c[i] = 2;
                    else
                        c[i] = 1;
                } else {
                    c[i] = count;
                    if (m > max) {
                        max = m;
                        count++;
                    }
                }    
                rt = 0;
                ct = 0;
            }
        if (c[i] < 1)
            if (c[i - 1] > 1)
                c[i] = 1;
            else
                c[i] = 2;
    }
    printf("The proper coloring is\n");
    for (i = 0; i < n; i++)
        printf("c%d=%d ", i + 1, c[i]);
    printf("\n");
}

Example Input: Consider a complete graph:

0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0

Expected output:

c1=1 c2=2 c3=3 c4=4

Observed output:

c1=1 c2=2 c3=3 c4=3

Answer 1

The error seems to be in logic, as you may have inferred by the looks of the question title. The conditional statement where you are checking if m is greater than max and then updating max and count accordingly seem to be incorrect.

I could not exactly figure out what the intended logic was, but I can tell why it is incorrect.

In your usage, you keep the maximum number of neighbors you encountered in max, and update it when you find a vertex which has more neighbors. With it, you also update count, which I think holds the color of currently highest value. Now, unless you encounter a vertex with more neighbors at each step(while traversing each row), you don't update max, and therefore you don't update count. Consequently, unless you encounter such a vertex, you keep assigning the same currently highest count to all vertices you encountered.

You should explain some more about the algorithm you implemented. However, just by looking at your code I think you should at least increment count somewhere different.

A good idea might by just keeping an array equal to the number of vertices. Then for each vertex (inside outermost loop) you can reset the array and by traversing all of the neighbors of i^th vertex you can set the colors used in them, and pick the smallest unused color.

It is probably not the most efficient way to do it, but you already have an O(n³) algorithm, so I think it wouldn't hurt going this way.

Below is your code, updated to reflect the changes I mentioned.

int n,a[10][10],i,j,k,c[10],max=0,col,ct=0,rt=0,m,count=2;
int used[11]; /* indices used are from 1 to n, inclusive */
void main()
{
    printf("enter n\n");
    scanf("%d",&n);
    printf("enter the Adjacency Matrix for %d rows and %d columns\n",n,n);   
    for(i=0; i < n ; i++)
    {
        c[i]=0;
        for(j=0;j<n;j++)
            scanf("%d",&a[i][j]);
    }
    c[0]=1;
    c[1]=2;
    for(i = 1 ;i < n;i++)
    {
        for(j = 1 ;j <= n ;j++)
            used[j] = 0;
        for(j = 0 ;j < i ;j++)
        {
            if(a[i][j] > 0)
                used[c[j]] = 1;
        }
        for(j = 1 ;j <= n ;j++)
            if(!used[j])
            {
                c[i] = j;
                break;
            }
    }
    printf("The proper coloring is\n");
    for(i = 0;i < n ;i++)
            printf("c%d=%d ",i+1,c[i]);
        printf("\n");
}

Answer 2

What does a straightforward algorithm to colour the verices look like?

• Consider all vertices in a loop and assign a colour. Vertices that have been visited already have a colour; vertices that will still be visited are still uncoloured.
• Determine which colours are used by adjacent vertices that have already been coloured.
• With this information, pick the lowest possible colour.

What does your algorithm look like:

• Assign colour 1 to vertex 1 and colour 2 to vertex 2. (Note that vertex 2 can use the same colour as vertex 1 if the two aren't connected.)
• Loop over all remaining vertices; then loop over all vertices cnnected to that.
• Count the number of incoming and outgoing links to the second vertex in yet another loop. (Note that merely counting the links doesn't give you information on which colours are still available. You could have many vertices coloured with colours 3 and 4, for example, but you base your new colour on the number of links. In this example, colour 1 would be a good choice.)
• Your criterion for chosing a new colour is whether the number of links is greater or equal to 2. You then assign the count, but before incrementing it. That gives you the second 3 in your example, where there should be a 4.

So you loop once too many and have a poor criterion for choosing a colour. Instead of counting the lonks, you should keep a list of used colours in adjacent nodes and base your new colour on that list.

Other stylistic issues with your code:

• All your variables should be local to main; there's no reason to make them global, especially since you don't use functions.
• Please be more systematic with your variable declarations. To have them all slapped together in one large definition, which even claoesces arrays and scalars, make them hard to understand.
• Please use braces around all code blocks, even if they are not strictly necessary. It makes reading the code easier. Small if s without an else in the inner block such as if (ct > rt) m = ct; don't need braces, but consider using them everywhere else.