Coloring Graph need help with funcion
Hi.
i have a problem with my C program coloring graph with alghoritm LF.(vertex with largest degree first). i have sorted by degree table 'dummyvertex' but funcion assignColor not working good. Help me please!
input file: 2.c
1 2
1 4
2 1
2 4
2 3
2 5
3 2
3 4
4 1
4 2
4 3
5 2
starting: ./a.out 2.c
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], °ree[lines] ) == 2 ) {
lines++;
}
fclose( fp ); // Closes the file
}
}
v = vertex[lines-1]; //v -> liczba krawędzi
// 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 i, j, x=0, y=0;
colorcounter[y]=1;
int temp[x];
for( i=1; i<=v; i++ ) {
for( j=0; j<lines; j++ ){
if( color[ dummyvertex[i] ] == 0 ){ //dummyvertex to posortowana tablica wierzcholkow
// assign vertex color //przypisanie dummyvertex koloru s
color[ dummyvertex[i] ] = colorcounter[y];
}
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[y]+1;
}
}
}
}
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" );
}
