Thread: Coloring Graph need help with funcion

  1. #1
    Registered User
    Join Date
    May 2016
    Posts
    2

    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" );
    }

  2. #2
    Registered User
    Join Date
    Jun 2015
    Posts
    1,643
    What is "LF"?
    What do you mean by "not working good"?

  3. #3
    Registered User
    Join Date
    May 2016
    Posts
    2
    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..

  4. #4
    Registered User
    Join Date
    Jun 2015
    Posts
    1,643
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Would this be considered defining a funcion?
    By 777funk in forum C Programming
    Replies: 6
    Last Post: 12-13-2010, 09:17 AM
  2. VC++ funcion call problem
    By TriKri in forum Windows Programming
    Replies: 1
    Last Post: 01-11-2010, 04:59 PM
  3. funcion runs 14 times, then program crashes
    By happyclown in forum C Programming
    Replies: 9
    Last Post: 03-03-2009, 11:58 PM
  4. Code-Coloring
    By Vber in forum A Brief History of Cprogramming.com
    Replies: 7
    Last Post: 01-08-2003, 11:29 PM
  5. Coloring with for statements
    By GreenCherry in forum C++ Programming
    Replies: 19
    Last Post: 11-01-2002, 01:30 PM

Tags for this Thread