Graph coloring algorithm - Assign color
I have a function in a graph coloring algorithm that assigns a color to a series of courses. But it picks at random and I would like to improve the algorithm and assign a color more efficiently than picking it at random based on the available colors.
In this function N
, it 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;
}
}
}
The explanation will be great.
source to share
First, let him pose a problem canColor(graph, k)
- it will answer true if and only if you can color the graph on the graph using k colors.
Pseudocode 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 problem of the graph coloring problem.
Now we need to use it to find the optimal coloration.
Note that if canColor (graph, k) == true, then also canColor (graph, k + 1) == true
This means that you have a metaphorical array of answers, 0,0,..0,1,1,...,1
when there is a solution for some k
, all meanings k
after it also has a solution. This metaphorical array is sorted, so you can do a binary search on it (where instead of accessing the array, you calculate the answer for each time canColor(graph,k)
) to get the optimal value k
- the number of colors you can use.
source to share