Thread: 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], &degree[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" );
}

What is "LF"?
What do you mean by "not working good"?

Largest-First algorithm- firstly descending sorting vertices according to the degree and then greedy coloring starting from the vertex with the greatest degree.

not working good:
input:

Code:

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

output:

Code:

Vertex  Color
======  =====
   1         2
   2         1
   3         2
   4         2
   5         2

vertex 4 cant have color 2 because neighboring vertex(1)
have this color..

Now that I look at your code, it's difficult to understand.

I assume the graph data in the file is an edge list and defines this graph:

Code:

1 --- 2 --- 5
|   / |
|  /  |
| /   |
4 --- 3

Correct me if I'm mistaken.

If that's the case, then why are you reading the second number on each line into an array called degree? That number has nothing to do with the degree of the vertex.

Also, It's not a good idea to use variables for true and false values. How about:

Code:

enum {FALSE, TRUE};   // or use C99 and include <stdbool.h>

Since you're not using them anywhere you could simply get rid of them.

And there's no reason for you to be using global variables.