Graph Coloring Algorithm - Assign color

Question

I have here a function in a graph coloring algorithm which assigns color to a number of courses. But it chooses randomly, and I'd like to improve the algorithm and assign color more efficiently than picking one at random based on the available colors.

In this function, N is the number of time schedules.

void create_schedule(int **graph, list *courses, int numcourses){
    int i, j, k, col=0;
    for(i=0; i<numcourses; i++){
        for(j=0; j<N; j++){
            for(k=0; k<i; k++){
                if(graph[i][k] > 0 && courses[k].color == j) break;
            }
            //color j was not yet chosen by adjacent nodes
            if(k >= i){
                courses[i].color = j;
                break;
            }
        }
        //if there is no color available, choose randomly
        if(j >= N){
            col = rand()%N;
            courses[i].color = col;
        }
    }
}

An explanation would be great.

Your question is unclear. What do you mean by "assign color more efficiently than giving it randomly based on what color is available" what do you mean "efficiently" here? You want it to run faster? What speed up are you expecting and where are you expecting you can achieve it? — amit
– amit, Commented May 6, 2015 at 8:15
And you are aware this problem is NP-Complete? So an optimal solution is going to take exponential time to achieve (unless P=NP, which is unlikely)? — amit
– amit, Commented May 6, 2015 at 8:17
Yes. As long as I minimize the colors used. I care less about the time :) — CrazyGirl
– CrazyGirl, Commented May 6, 2015 at 8:19
What is approximately the size of N? You might not "care for time" but for lage enough N (say, N>40) - you are unlikely to ever be able to find an optimal solution unless you own a very powerful cluster. — amit
– amit, Commented May 6, 2015 at 8:21

amit · Accepted Answer · 2015-05-06 08:33:44Z

3

First, let's define the problem canColor(graph, k) - it will answer true if and only if you can do a graph coloring to graph using k colors.

Pseudo code for canColor:

canColor(graph, k):
   if graph is completely colored:
        return checkIfColoringValid(graph)
   v = first uncolored vertex
   for each i from 1 to k (inclusive)
       color v with color i
       //can add optimization here to trim upfront unsuccesful results
       res = canColor(graph,k)
       if res == true:
           return true
   //no answer found
   uncolor v (mark it as color[v] = 0)
   return false

The above is the decision problem of graph coloring.

Now, we need to use it to find the optimal coloring.
Note that if canColor(graph,k) == true, then also canColor(graph,k+1) == true

This means, you have a metaphoric array of answers, 0,0,..0,1,1,...,1, once there is a solution for some k, all values of k after it will also have a solution. This metaphoric array is sorted, so you can apply binary search on it (where instead of accessing the array, you calculate answer for canColor(graph,k) each time), to get the optimal value of k - the number of colors you can use.

answered May 6, 2015 at 8:33

amit

179k27 gold badges245 silver badges348 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

CrazyGirl Over a year ago

What if instead of optimizing colors, you optimize the end value of the objective function? It's not really related on the question but I'd like to know too.

amit Over a year ago

@CrazyGirl That's going to depend on your objective function, which objective function do you have? Obviously for objective function that strive to as little as possible number of colors - the answer is identical.

Collectives™ on Stack Overflow

Graph Coloring Algorithm - Assign color

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related