Thread: Please help!! Vertex Coloring Algorithm

Dear all,

Please provide some help for the code below....

Code:

/* Vertex Coloring Algorithm
   2013-05-05  10:10		 Version 2.5


Ref: 
http://www.csie.ntnu.edu.tw/~u91029/Coloring.html
http://travelsciencetech.blogspot.in/2012/10/graph-coloring-problem-with.html


Done:
- Show error message if input file are invalid
- Read the graph file properly
- Sort graph file's data into 2D array
- can show the actual contain of graph file with numbering start from 0
- lines/vertex numbering corrected
- can show color only, no comparison yet
- Set default color to "no color"


*/




#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define SIZE 255


int vertex[SIZE], degree[SIZE], color[SIZE], countv[SIZE], vnew[SIZE];


int main( int argc, char *argv[] )
{
	int f, i, j, v;
	int lines=0;
	FILE *fp; 


	// Check if execute w/o any graph file 
	if( argc < 2 ) {
   	printf( "Please enter the graph's filename in command.\n" );
   	return 1;
  	}


	// Check if execute w/ invalid graph file
	if( ( fp = fopen( argv[1], "r" ) ) == NULL ) {
    	printf( "Graph file %s not exist.\n", argv[1]);
   	return 1;
  	}


/*
	// CHECKING - Show the contents of file
	printf( "\nContains of %s file", argv[1] );
	printf( "\nLines\tVertex\tDegree" );		 
	// END OF CHECKING
*/


	// Read file from commandline
	if ( argc > 1 ) {
		for ( f = 1; f <= argc-1; f++ ) {
			fp = fopen ( argv[f], "r" );
			while ( !feof (fp) ) {
		  		fscanf( fp, "%d %d", &vertex[lines], &degree[lines] );


/*				// CHECKING
				printf( "\n%d \t%d \t%d", lines, vertex[lines], degree[lines] );	
				// END OF CHECKING
*/
				lines++;
			}	// end while
			fclose( fp );	// Closes the file			
		}	// end for
   }	// end if


	lines = lines - 1;


	// CHECKING - Show the contents of file
	printf( "\nChecking:" );
	printf( "\nlines\tVertex\tDegree" );	
	for( i = 0; i < lines; i++ ) {
		printf( "\n%d \t%d \t%d", i, vertex[i], degree[i] );	// show the contain of every degree
	}
	printf( "\n\nlines = %d\n", lines );	// Here, lines = 42
	// END OF CHECKING


	// CHECKING - Show the Total vertices
	v = vertex[lines-1];	// Total vertices, here, v = 13
	printf( "Total Vertices, v = %d\n", v ); 	// here, Vertex (start from 1-13), v = 13
	// END OF CHECKING


	// Default vertices coloring, all colored with no color, "0"
	for( i = 1; i <= v; i++ ) { 	// loop from 0 to max lines value
		color[i]	= 1;	//coloring degree line [l] with no color, "0"
	// CHECKING
		printf( "\nDefault Color for vertex [%d] = %d", i, color[i] );	
	// END OF CHECKING
	}	// end for


	printf( "\n\nStart sorting....\n" );	


	printf( "\nTotal Vertices, v = %d", v ); 	// Vertex (start from 1-13), v = 13
	printf( "\nlines = %d", lines );	// lines = 42




	// Sort vertices by degree
	for( j = 0; j < lines; j++ ) { 	// loop from 1 to lines = 42
		printf( "\n line [%d], v(j) = %d", j, vertex[j] );
		printf( "\n line [%d], v(j+1) = %d", j+1, vertex[j+1] );		


		for( i = 1;  i <= v; i++ ) { 	// loop from 1 to max vertices, 13


			if ( vertex[j] == vertex[j-1] ) {
				countv[i] += 1;
			}	// end if
			printf( "\ncountv [%d] = %d", i, countv[i] );	


		}	// end for
	}	// end for




	printf( "\n\nCounting result for vertex....\n" );	


	for( i = 1;  i <= v; i++ ) { 	// loop from 1 to max vertices, 13
		printf( "\nNew vertex counter, countv [%d] = %d", i, countv[i] );	
	}	// end for






	// Vertex coloring
	for( i = 1; i <= v; i++ ) { 	// loop from 1 to max vertices, v
		for( j = 1; j <= 10; j++ ) { 	// loop from 1 to max vertices, for degree part
			while (){
				color[i]++;
			// show the contain of every degree
			printf( "\ni = %d\tj = %d\tvertex = %d\tdegree = %d\tcolor = %d", i, j, vertex[i], degree[j], color[i] );
			}	// end while			
		}	// end for
	}	// end for






/*	while( = i && vertex[k] != degree[k] ) {	// at vertex 1
		printf( "Vertex [%d], Degree [%d]: color = %d\n", vertex[k], degree[k], color[k] );
	}	// end while
*/


	// Display color of each vertex
	printf("\n\nColors of Vertices (0 = No Color)\n");
	for( i = 1; i <= v; i++ ) {
   	printf( "vertex [%d] : %d\n", i, color[i] );
	}


 	return 0; 
}25.c

Process of vertex coloring (image link from 演算法ç..†è¨˜ - Coloring)


First, I want to sort the vertices by number of degree, but my vertex and degree input was in 2 separated array, I couldn't get my vertex counter (countv) run properly in the code.

The code for the countv:

Code:

	// Sort vertices by degree
	for( j = 0; j < lines; j++ ) { 	// loop from 1 to lines = 42
		printf( "\n line [%d], v(j) = %d", j, vertex[j] );
		printf( "\n line [%d], v(j+1) = %d", j+1, vertex[j+1] );		


		for( i = 1;  i <= v; i++ ) { 	// loop from 1 to max vertices, 13


			if ( vertex[j] == vertex[j-1] ) {
				countv[i] += 1;
			}	// end if
			printf( "\ncountv [%d] = %d", i, countv[i] );	


		}	// end for
	}	// end for




	printf( "\n\nCounting result for vertex....\n" );	


	for( i = 1;  i <= v; i++ ) { 	// loop from 1 to max vertices, 13
		printf( "\nNew vertex counter, countv [%d] = %d", i, countv[i] );	
	}	// end for

Second, I would like to assign a color to every vertex, the rules are:
1. similar color are not allowed for every neighbor vertex, for example if vertex[1] link to vertex [2], then they should be given color[1] and color[2] separately.
2. Use as minimum color as possible. Repeated color are allowed for every vertex if they are not link to each other.

Code:

	// Vertex coloring
	for( i = 1; i <= v; i++ ) { 	// loop from 1 to max vertices, v
		for( j = 1; j <= 10; j++ ) { 	// loop from 1 to max vertices, for degree part
			while (){
				color[i]++;
			// show the contain of every degree
			printf( "\ni = %d\tj = %d\tvertex = %d\tdegree = %d\tcolor = %d", i, j, vertex[i], degree[j], color[i] );
			}	// end while			
		}	// end for
	}	// end for

I am confusing with 2 separated array, and keep on facing problem on "convert" the rules to proper code.

This is the content of graph file
[Vertex] [Connected Vertex]

Code:

1 2
1 3
2 1
2 3
2 4
2 5
3 1
3 2
3 4
3 5
4 2
4 3
4 5
4 6
5 2
5 3
5 4
5 6
5 7
6 4
6 5
6 7
6 8
7 5
7 6
7 8
7 9
8 6
8 7
8 9
8 10
9 7
9 8
9 10
10 8
10 9
10 11
11 10
11 12
12 11
12 13
13 12

Originally Posted by Malcolm McLean

The vertex colouring problem is a complicated one. You're using the greedy algorithm, which gives usually good but often not optimal results.
So you need to count the vertices, and assign each a degree based on the number of edges it has. Then sort the list so the highest degree is at the top. Assign that colour one. Then go to the next highest, and assign that the lowest colour that isn't used by a neighbour, and so on.
So to make the program easy to write, duplicate the edge list so you have edges A to B and B to A. Sort by edge 1. That gives you a list of edges for each vertex. Declare a struct vertex which maintains an index and count into your edge list, and also a colour (initially 0).

Dear Malcolm McLean, thanks for your detail explanation. I have the duplicated edge list in the graph file for each vertex. But, my problem now is I haven reach the struct of C programming. By referring to the Deitel's C programming book, I still stuck at chapter 6 array part, and my program always having issue between pointer and array :-(

Originally Posted by Salem

First of all, you need to start planning some kind of program structure.
A development process

A 100+ line main (and nowhere near the end of the code) is just too hard to read, write or debug.

Functions like
- readVertices
- countVertices
- colourGraph
spring to mind.

Dear Salem, thank you so much for your guidelines and correction. Before this version of code, I was doing them in function prototype form, but due to pointer and others compilation warning, I was forced to switch to "all in one" pattern, which gives me less error so that I can continue the work, but I know that's very bad.

> while ( !feof (fp) )
> fscanf( fp, "%d %d", &vertex[lines], &degree[lines] );
Read the FAQ for why using feof() to control a loop is bad.

It would be better to do
while ( fscanf( fp, "%d %d", &vertex[lines], &degree[lines] ) == 2 )

> lines = lines - 1;
Then you wouldn't need to do this, because of the +1 loop that your mis-use of feof allowed.

I think you mentioned about the problem of feof() in my previous post as well Thanks for the reminder again.

Managing two separated array is quite difficult for me, is there any other method to read the vertex[lines] and degree[lines] straight away into a 2D array instead of two separated array? I saw most of the verte coloring algorithm are using 2D array, but mine are different with them.

> for( i = 1; i <= v; i++ ) // loop from 0 to max lines value
It would be better to delete the inconsistent comment, rather than leave people wondering which is correct.
Also, without explanation, most programmers will react with horror when they see you trying to index an array starting at 1, and using <= as the end condition. This screams array overrun.

Sorry about the misleading comment, it was copy paste from another line without correction.
for( i = 1; i <= v; i++ ) // loop from vertex 1 to max vertex value

I start the i at value 1 because my vertex numbering start at one. My v equals to 13, so I let the for loop run from 1 to 13.
Shall I correct it become
for( i = 0; i < v; i++ ) // loop from vertex 0 to "max vertex value-1"

Code:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define SIZE 255


int true = 1;
int false = 0;
int vertex[SIZE], degree[SIZE], color[SIZE], colorcounter[SIZE], degreecount[SIZE], dummyvertex[SIZE];




void checking( int lines, int v, int vertex[SIZE], int degree[SIZE] );
void checkDegree ( int lines, int v, int vertex[SIZE] );
void degreeSorting ( int v );
void assignColor ( int lines, int v, int vertex[SIZE], int degree[SIZE], int color[SIZE] );
void displayColor( int v, int color[SIZE] );




int main( int argc, char *argv[] )
{
    int f,v;
    int lines=0;
    FILE *fp; 


    // Check if execute without any graph file 
    if( argc<2 ) {
       printf( "Please enter the graph's filename in command.\n" );
       return 1;
      }


    // Check if execute with invalid graph file
    if( ( fp = fopen( argv[1], "r" ) ) == NULL ) {
        printf( "Graph file %s not exist.\n", argv[1] );
       return 1;
      }


    // Read file from commandline
    if ( argc>1 ) {
        for ( f=1; f<=argc-1; f++ ) {
            fp = fopen ( argv[f], "r" );
            while ( fscanf( fp, "%d %d", &vertex[lines], &degree[lines] ) == 2 ) {
                lines++;
            }    
            fclose( fp );    // Closes the file            
        }    
      }    


    v = vertex[lines-1];
//    checking ( lines, v, vertex, degree );
     checkDegree ( lines, v, vertex );
    degreeSorting ( v );
    assignColor ( lines, v, vertex, degree, color );
    displayColor ( v, color );


     return 0; 
}




void checking ( int lines, int v, int vertex[SIZE], int degree[SIZE] )
{
    int i;
    printf( "\nContain of file: \nlines Vertex[i] Degree[i]\n"
                                         "===== ========= =========\n" );
    for( i=0; i<lines; i++ ){ 
        printf( "  %2d \t %2d \t   %2d\n", i, vertex[i], degree[i] );    // show the contain of every degree
    }
    printf( "\nTotal Vertices, v = %2d, lines = %2d\n", v, lines );     // Vertex (0-12), v=13, lines=42
}






void checkDegree ( int lines, int v, int vertex[SIZE] )
{
    int i,n;

    for( i=1; i <= v; i++ ) {        // vertex 1 to max vertice value
        color[i] = 0;                    // default color = no color
        colorcounter[i] = 0;            // default colorcounter = 0
        degreecount[i] = 0;            // vertex counter set to 0
        dummyvertex[i] = i;            // Set dummy vertex[i] = vertex[i]
    }

    for( i=0; i<=lines; i++ ) {    // check every line
        for( n=1; n<=v; n++ ) {        // count for similar value
            if ( vertex[i] == n ){
                degreecount[n]++;
            }
        }
    }
}





void degreeSorting ( int v )
{
    int i,j;
    double temp1, temp2;


    // "Bubble sort" vertex by degree, duplicate the result to Dummy Vertex
    do{
        j = 0;
        for( i=1; i<=v; i++ ) {            // Vertex counter
            if ( degreecount[i] < degreecount[i+1] ) {
                j = 1;
                temp1 = degreecount[i];    // Sort degree
                degreecount[i] = degreecount[i+1];
                degreecount[i+1] = temp1;


                temp2 = dummyvertex[i];    // Sort vertex
                dummyvertex[i] = dummyvertex[i+1];
                dummyvertex[i+1] = temp2;
            }
        }
    } while( j == 1 );


    printf( "\nSort Vertex Ascending by Numbers of Degree\nVertex  Degree(s)\n"
                                                                           "======  =========\n" );
    for( i=1; i<=v; i++ ) {             // vertex 1 to max vertice value
        printf( "  %2d       %2d\n", dummyvertex[i], degreecount[i] );
    }                                            // dummy vertex having the same index with Vertex
}



 
void assignColor ( int lines, int v, int vertex[SIZE], int degree[SIZE], int color[SIZE] )
{                        
    int i=1;
// default colorcounter[i] = 0


    for( i=1; i<=v; i++ ) {        // vertex counter, v=13
        if( color[ dummyvertex[i] ] == 0 ){                    // if 1st i got no color, color[5]==0
            color[ dummyvertex[i] ] = colorcounter[i];


            if( color[ dummyvertex[i] ] != colorcounter[i] ){
                color[ dummyvertex[i] ] = colorcounter[i];    // assign color
            }
        }
    }
}




void displayColor ( int v, int color[SIZE] )
{
    int i;
    printf( "\nColors of Vertices\nVertex  Color\n======  =====\n" );
    for( i=1; i<=v; i++ )
        printf( "  %2d     %2d\n", i, color[i] );
    printf( "\n" );
}

This is the current output

Sort Vertex Ascending by Numbers of DegreeVertex Degree(s)
====== =========
5 5
2 4
3 4
4 4
6 4
7 4
8 4
9 3
10 3
1 2
11 2
12 2
13 1


Colors of Vertices
Vertex Color
====== =====
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 0
10 0
11 0
12 0
13 0

I would like to assign first color (color 1) to "vertex 5", second color to "vertex 2", but the program have to check whether "vertex 2" having any connection to "vertex 5" (all previous vertex) or not and is it the same color....

I got stuck here.... please show me some guideline.... Thanks in advance.

This is my previous attempt using the normal looping method to assign color. But, it wasn't fulfill the vertex coloring requirement: using minimum numbers of color in the color assignment.....

Output:

Colors of VerticesVertex[i] Color
========= =====
1 10
2 2
3 3
4 4
5 1
6 5
7 6
8 7
9 8
10 9
11 11
12 12
13 13

Code for assign color fucntion

Code:

void assignColor ( int lines, int v, int vertex[SIZE], int degree[SIZE], int color[SIZE] ){
	int i;
	int colorcounter=1;


	for( i=1; i<=v; i++ ) {		// vertex counter
		color[ dummyvertex[i] ] = colorcounter;	// assign color to dummy vertex
		colorcounter++;
	}
}

Originally Posted by Malcolm McLean ... . Declare a struct vertex which maintains an index and count into your edge list, and also a colour (initially 0).

Now, I think I have reach this final part, but I got no idea how to ask the program to check every vertex's for duplicated colour. One of my friend told me that this is bi-directional vertex colouring, its very hard to write the code.

As for every vertex, I had sort them according to numbers of degree in an ascending way successfully. Now, I have t assign a colour to every vertex, start from vertex with highest numbers of degree. During colour assignment, as long as the same colour not assign to any neighbour vertex, then that should be fine.

The example shown above was using 2D array, it wasn't same like mine that using 2 single dimension array...

Dear all,

I am facing error with the function prototype code below, the terminal wasn't response at all after the program execute until the code below....

Code:

void assignColor ( int lines, int v ){						
	int i,j;
    colorcounter = 1;


    // Color assignment for the remaining vertex    
    for( i=1; i<=v; i++ ) { // vertex counter, v=13
        while( color[ dummyvertex[i] ] = colorcounter ){    // color[ v 5 ] = 1
            colorcounter++;
            for( j=1; j<=lines; j++ ) { // vertex counter, v=13
                while( vertex[j] == dummyvertex[i] ){        // vertex j == 5
                    color[ degree[j] ] = colorcounter;
                }
            }
        }
    }
}

May I know what's wrong with them? Thanks in advance.

Code:

while( color[ dummyvertex[i] ] = colorcounter ){    // color[ v 5 ] = 1

= is not the same as ==

Code:

while( vertex[j] == dummyvertex[i] ){        // vertex j == 5
    color[ degree[j] ] = colorcounter;
}

Why do you think this loop will ever stop?

Bye, Andreas

Originally Posted by AndiPersti

Code:

while( color[ dummyvertex[i] ] = colorcounter ){    // color[ v 5 ] = 1

= is not the same as ==

Code:

while( vertex[j] == dummyvertex[i] ){        // vertex j == 5
    color[ degree[j] ] = colorcounter;
}

Why do you think this loop will ever stop?

Bye, Andreas

Hi Andreas, when I execute the program in Ubuntu terminal, it just stuck at this part and not running anymore even after waiting for 10 minutes

You have an infinite loop.

Bye, Andreas

Dear All,

After modifying my vertex coloring code several time, I come out with this code, but I am facing some problem with the color assignment function prototype.

This is the portion for the color assignment:

Code:

void assignColor ( int lines, int v ){                        
    int i,j,x=0,y=0;
    colorcounter=1;
    int temp[x];


    for( i=1; i<=v; i++ ) {  
        for( j=0; j<lines; j++ ){
                    
            if( color[ dummyvertex[i] ] == 0 ){
                // assign vertex color
                   color[ dummyvertex[i] ] = colorcounter;
                }


            if ( vertex[j] == dummyvertex[i] && color[ degree[j] ]==0){
                   // assumed that degree[j] don't have any link to each other
                   color[ degree[j] ] = colorcounter+1;    
             }
        }
    }
}

This is the input file for the program:

Code:

  [i] Vertex[i] Degree[i]
===== ========= =========
   0       1         2
   1       1         3
   2       2         1
   3       2         3 
   4       2         4    
   5       2         5
   6       3         1
   7       3         2
   8       3         4
   9       3         5
  10       4         2
  11       4         3
  12       4         5
  13       4         6
  14       5         2 
  15       5         3
  16       5         4
  17       5         6
  18       5         7
  19       6         4
  20       6         5
  21       6         7
  22       6         8
  23       7         5
  24       7         6
  25       7         8
  26       7         9
  27       8         6
  28       8         7
  29       8         9
  30       8        10
  31       9         7
  32       9         8
  33       9        10
  34      10         8
  35      10         9
  36      10        11
  37      11        10
  38      11        12
  39      12        11
  40      12        13
  41      13        12

Total Vertices, v = 13, lines = 42
It will read from data line 0 until line 41.


This code will generate output:

Code:

Colors of Vertices
Vertex  Color
======  =====
   1      2
   2      2
   3      2
   4      2
   5      1
   6      2
   7      2
   8      2
   9      2
  10      2
  11      2
  12      2
  13      2

Now, I want to assign color "1" to Vertex[14] till Vertex[18], here, they are, Vertex 5.

Then, I will check the neighbor of this Vertex 5, They are:
Vertex 2
Vertex 3
Vertex 4
Vertex 6
Vertex 7

I have to assign one color to these neighbor and they must having different color with Vertex 5. Let say I assign Color 2 to all of them.

Next, I have to make sure that these neighbor of Vertex 5 are not connected to each other as well. So I have to loop within this list, check them one by one.

Let say Vertex 2, when compare the neighbor of it with Vertex 5,

Code:

   2       2         1
   3       2         3 
   4       2         4    
   5       2         5

  14       5         2 
  15       5         3
  16       5         4
  17       5         6
  18       5         7

Vertex 3 and Vertex 4 are connect to Vertex 2 as well. So, All of them, Vertex 2, Vertex 3 and Vertex 4 can not have the same color.
They must be:
Vertex 2 = Color 2
Vertex 3 = Color 3
Vertex 4 = Color 4

This process will keep on repeat for the rest of the vertex until all of them don't have the same color with their neighbor.

The problem is that, how am I going to start writing this part?