Bipartite Graphs - The Colorize Code Source
(Page 3 of 4 )
It is time to write into C code what I explained on the previous page. I will use color 1 and color 2 instead of red and yellow as these are much easier to use in programming. The colors WHITE(not visited), GRAY(in travel process), and BLACK(visited) will signify only the state of the vertexes in the matrix.
The variables f1 and f2 count the number of appearances of each color.
int colorize(Node*& list,int s, int* painted, const int& n)
{
int* color = (int*) malloc((n+1)*sizeof(int));
memset(color, WHITE, sizeof(int)*(n+1));
int f1 = 1, f2 = 0;
int u = 0;
int v = 0;
color[s] = GRAY ;
painted[s] = 1;
pListIt Q;
pListIt at;
pListIt endQSe;
Q = NULL;
// put s into the queue
Q = (pListIt) malloc ( sizeof( ListIt));
Q->value = s;
Q->p_next = NULL;
while(Q) // while we have nodes to visit
{
u = Q->value;
// visit the neighbors
for( at = list[u].neighbors; at; at = at->p_next)
{
v = at->value;
if (color[v] == WHITE)
{
color[v] = GRAY;
if( painted[u] == 1) // what color its ancient had
{
painted[v] = 2; //use the other color
++f2;
}
else
{
painted[v] = 1;
++f1;
}
// find the end of Q
for(endQSe = Q; endQSe->p_next;endQSe = endQSe->p_next);
// put v into the queue/ at the end
endQSe->p_next = (pListIt) malloc ( sizeof( ListIt));
endQSe->p_next->value = v;
endQSe->p_next->p_next = NULL;
}
}
//delete first item
endQSe = Q;
Q = Q->p_next;
free(endQSe);
color[u] = BLACK;
}
if(f1 < f2 )
return 1;
else
return 2;
}
Next: The Solution >>
More Code Examples Articles
More By Gabor Bernat
