1. ## 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, "r" ) ) == NULL ) {
printf( "Graph file %s not exist.\n", argv);
return 1;
}

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

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 link to vertex , then they should be given color and color 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. 2. 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``` 3. 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). 4. 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
- countVertices
- colourGraph
spring to mind.

> 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.

> 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. 5. 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 :-( 6. 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
- 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" 7. I found another example at å›¾çš„mç€è‰²é—®é¢˜ - qinyg - åšå®¢å›..

Code:
```//图着色问题回溯法
/*
无向图邻接矩阵示例  Sample matrices format of vertex and degree
1 1 0 0
1 1 0 1
1 0 0 1
1 0 0 1
1 1 1 0
*/
#include<stdio.h>

int color;
//int c;
ok(int k ,int c[])//判断顶点k的着色是否发生冲突
{
int i,j;
for(i=1;i<k;i++)
if(c[k][i]==1&&color[i]==color[k])
return false;
return true;
}

void graphcolor(int n,int m,int c[])
{
int i,k;
for(i=1;i<=n;i++)
color[i]=0;//初始化
k=1;
while(k>=1)
{
color[k]=color[k]+1;
while(color[k]<=m)
if (ok(k,c)) break;
else color[k]=color[k]+1;//搜索下一个颜色

if(color[k]<=m&&k==n)//求解完毕，输出解
{
for(i=1;i<=n;i++)
printf("%d ",color[i]);
printf("\n");
//return;//return表示之求解其中一种解
}
else if(color[k]<=m&&k<n)
k=k+1;    //处理下一个顶点
else
{
color[k]=0;
k=k-1;//回溯
}
}
}

void main()
{
int i,j,n,m;
int c;//存储n个顶点的无向图的数组
printf("输入顶点数n和着色数m:\n");  // Enter vertex number, n and numbers of color
scanf("%d %d",&n,&m);
printf("输入无向图的邻接矩阵:\n");  // Enter the matrices of vertex and edges from command line
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&c[i][j]);
printf("着色所有可能的解:\n");  // List of possible graph coloring
graphcolor(n,m,c);
}```

This program using terminal to enter the vertex and all related degree value, its different with mine, which read from a normal (text) file. As a new user to vertex coloring algorithm, I guess this example also using "greedy method". 8. ## Help ??

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, "r" ) ) == NULL ) {
printf( "Graph file %s not exist.\n", argv );
return 1;
}

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==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. 9. 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... 11. ## Infinite loop??

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. 12. 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 13. 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  14. You have an infinite loop.

Bye, Andreas 15. ## Help.... Color Assignment

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 till Vertex, 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? Popular pages Recent additions algorithm, coloring, vertex 