Like Tree1Likes

Please help!! Vertex Coloring Algorithm

This is a discussion on Please help!! Vertex Coloring Algorithm within the C Programming forums, part of the General Programming Boards category; Dear all, Please provide some help for the code below.... Code: /* Vertex Coloring Algorithm 2013-05-05 10:10 Version 2.5 Ref: ...

  1. #1
    Registered User
    Join Date
    Apr 2013
    Posts
    35

    Question 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[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], &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)
    Name:  Welsh-PowellAlgorithm.png
Views: 802
Size:  34.0 KB

    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.

  2. #2
    Registered User
    Join Date
    Apr 2013
    Posts
    35
    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. #3
    Registered User
    Join Date
    May 2012
    Posts
    333
    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).
    Sebastiani likes this.
    I'm the author of MiniBasic: How to write a script interpreter and Basic Algorithms
    Visit my website for lots of associated C programming resources.
    http://www.malcolmmclean.site11.com/www

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,540
    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
    - readVertices
    - 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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Registered User
    Join Date
    Apr 2013
    Posts
    35
    Quote Originally Posted by Malcolm McLean View Post
    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. #6
    Registered User
    Join Date
    Apr 2013
    Posts
    35
    Quote Originally Posted by Salem View Post
    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
    - readVertices
    - 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. #7
    Registered User
    Join Date
    Apr 2013
    Posts
    35
    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[100];
    //int c[100][100];
    ok(int k ,int c[][100])//判断顶点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[][100])
    {
        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[100][100];//存储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".
    Last edited by Watervase Chew; 05-05-2013 at 09:24 AM.

  8. #8
    Registered User
    Join Date
    Apr 2013
    Posts
    35

    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[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];
    //    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[5]==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. #9
    Registered User
    Join Date
    Apr 2013
    Posts
    35
    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++;
    	}
    }

  10. #10
    Registered User
    Join Date
    Apr 2013
    Posts
    35

    Please help (again)...

    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. #11
    Registered User
    Join Date
    Apr 2013
    Posts
    35

    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. #12
    Registered User
    Join Date
    May 2012
    Posts
    1,066
    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. #13
    Registered User
    Join Date
    Apr 2013
    Posts
    35
    Quote Originally Posted by AndiPersti View Post
    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. #14
    Registered User
    Join Date
    May 2012
    Posts
    1,066
    You have an infinite loop.

    Bye, Andreas

  15. #15
    Registered User
    Join Date
    Apr 2013
    Posts
    35

    Arrow 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[14] till Vertex[18], 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?

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Coloring text
    By thepolo in forum C Programming
    Replies: 5
    Last Post: 05-25-2009, 07:56 PM
  2. Coloring My Text
    By bjl in forum C++ Programming
    Replies: 10
    Last Post: 02-05-2008, 06:37 PM
  3. Coloring with for statements
    By GreenCherry in forum C++ Programming
    Replies: 19
    Last Post: 11-01-2002, 12:30 PM
  4. about coloring text
    By GanglyLamb in forum C Programming
    Replies: 4
    Last Post: 10-22-2002, 12:21 PM
  5. Coloring Buttons
    By Okiesmokie in forum Windows Programming
    Replies: 5
    Last Post: 03-17-2002, 06:00 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21