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], °ree[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.