All possible array combinations (parallel programming) - Optimal Graph Colouring

Question

I'm doing again a work of optimal Graph Coloring, so, I need to generate all possible color combinations (the array represents the color for each node) for a graph. I got a lot of help here, as you can see in this question:

Generate all possible array combinations in C - Optimal Graph Colouring

For now, my code is:

void generatearray( int array[], int array_size, int idx = 0, int fixed = 0 )
{
   int i;

   if ( idx == array_size )
   {
       putchar('\n');
       for( i = 0; i < array_size; i++ ) printf( "%i ", array[i] );

   } else {

       for( i = 0; i <= 3; i++ )
       {
          if ( fixed == i )
          {
             fixed++;
             array[idx] = i;
             return generatearray( array, array_size, idx + 1, fixed );
          }
          array[idx] = i;
          generatearray( array, array_size, idx + 1, fixed );
       }
   }
}

int arr[3];
generatearray( arr, 3 );

The output, in this case, would be:

If 0 means blue and 2 means red, in Graph coloring, red-red-red is the same thing of blue-blue-blue. That's what my code do: it generates all possible different color combinations for a graph.

Now I need to improve my code, but I couldn't think of anything. I want it to generate arrays only with a given number of colors, because I'm using pthreads and I want each thread to deal with the graph with a number of colors.

For example: with 2 colors, the output would be:

0 0 1
0 1 0
0 1 1

And with 3 colors:

1 2 3

I don't need it to create arrays with less colors than the number set, as there's another threads doing this.

Could any of you guys help me with my code? Sorry if I didn't made myself clear at any point.

The best thing you can do for yourself, and for us as well, is to think about and produce the formulation of task for your phtread. That is, what exactly it means to "generate arrays with given number of colors". Your formulation will look something like this: We have N vertices and C colors. You continue. — ondrejdee, Jul 03 '13 at 08:56
Also it would be good to think about definition and representation of "coloring". In your example, I take it that "100" and "011" is the same coloring. Is it OK that the same coloring has different representations, or would you rather like to have a unique representation for a given coloring? (is coloring a set of same-colored vertices? that is, "100" or "011" or "122" you would represent as ((1), (2,3)), meaning first vertex has one color, vertices 2 and 3 have another color ) — ondrejdee, Jul 03 '13 at 09:10
When I set this function to generate arrays with 3 numbers (0 - 2), it would also create arrays with 1 and 2 numbers, as you can see. And I don't need it to happen, because each thread would generate all possible arrays for a number of colors. For example: thread #1 - 1 color thread #2 - 2 colors Then, when the thread #1 had finished, it would start to generate arrays with 3 colors, then thread #2 with 4 colors... till I find an array with the colors that would fit in my graph. — Alexandre Paiva, Jul 03 '13 at 17:59

score 1 · Accepted Answer · answered Jul 11 '13 at 13:14

so you need a systematic enumeration of all surjective mappings from the set V (#V = n) of vertices in your graph into a set of k elements representing k different colors along with the additional constraint that the map restricted to vertices with the least index among all other vertices associated with the same color must be strictly monotone (as you are not interested in the identity of the respective color).

let's assume the number of colors be fixed. choose the least indices of the color representatives first, i_1, ..., i_k. by definition, i_1 < ... < i_k. for any of remaining vertices v, i_j < v < i_(j+1), its color can be chosen freely from { 1, ..., j }.

this can be implemented by the following code:

/*
 * sample values
 *    K ist to be substituted with the number of colors to use and thus in actual usage scenarios will be a parameter of thread instantiation
 */
const   K = 4;
const   N = 10;

void
next_pattern ( int *out, int set_up_to, int *mins, int mins_seen ) {
    int i;
    int choice;

    /* in-place updating: only elements 1..set_up_to are valid */
    if (set_up_to < N) {
        if (set_up_to + 1 == mins[mins_seen+1]) {
            out[set_up_to + 1] = mins_seen+1;
            next_pattern ( out, set_up_to + 1, mins, mins_seen+1 );
        }
        else {
            for ( choice = 1; choice <= mins_seen; choice++ ) {
                out[set_up_to + 1] = choice;
                next_pattern ( out, set_up_to + 1, mins, mins_seen );
            }
        }
    }
    else {
        /* coloring complete */
        printf("[");
        for (i=1; i <= N; i++) {
            printf(" %u ", out[i]);
        }
        printf("];\n");
    }           
} /* next_pattern */

void
next_mindist ( int *mins, int issued, int *out ) {
    int lo;
    /* in-place updating: only elements 1..issued are valid */
    if (issued < K) {
        for ( lo = mins[issued] + 1; lo < N - issued; lo++ ) {
            mins[issued+1] = lo;
            next_mindist ( mins, issued+1, out );
        }
    }
    else {
        // min mapping complete
        next_pattern ( out, 0, mins, 0 );
    }
} /* next_mindist */


void main ( char **argv, int *argc ) {
    /* in-place arrays
     *  mins: minimum vertex index of color <index>
     *  out:  current mapping vertex -> color (mostly partial during processing)
     */
    int     *mins = (int *) calloc ( sizeof(int), K + 2 ); /* supporting indices 1 .. K and upper guard to avoid conditional statements */
    int     *out  = (int *) calloc ( sizeof(int), N + 1 ); /* supporting indices 1 .. N */

    next_mindist ( mins, 0, out );
}

caveat: the above code does compile and run, and its results appear to be correct. of course its far form being formally verified ... ;-).

All possible array combinations (parallel programming) - Optimal Graph Colouring

1 Answers1