0

我再次进行了优化图形着色的工作，因此，我需要为图形生成所有可能的颜色组合（数组代表每个节点的颜色）。正如您在这个问题中看到的那样，我在这里得到了很多帮助：

在 C 中生成所有可能的数组组合 - 最佳图形着色

现在，我的代码是：

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

在这种情况下，输出将是：

0 0 0
0 0 1
0 1 0
0 1 1
0 1 2

如果 0 表示蓝色，2 表示红色，在 Graph 着色中，red-red-red 与 blue-blue-blue 相同。这就是我的代码所做的：它为图形生成所有可能的不同颜色组合。

现在我需要改进我的代码，但我什么都想不出来。我希望它只生成具有给定颜色数量的数组，因为我使用的是 pthreads，并且我希望每个线程处理具有多种颜色的图形。

例如：使用 2 种颜色，输出​​将是：

0 0 1
0 1 0
0 1 1

并有 3 种颜色：

1 2 3

我不需要它来创建颜色少于数字集的数组，因为还有另一个线程在做这件事。

你们中的任何人都可以帮我写代码吗？对不起，如果我没有在任何时候说清楚。

4

1 回答 1

1

因此，您需要系统地枚举从V (#V = n)图形中的一组顶点到一组k表示不同颜色的元素的所有满射映射，k以及该映射限制为与相同颜色关联的所有其他顶点中索引最小的顶点的附加约束必须严格单调（因为您对相应颜色的身份不感兴趣）。

让我们假设颜色的数量是固定的。首先选择颜色代表的最小索引，i_1, ..., i_k。根据定义，i_1 < ... < i_k. 对于任何剩余的顶点v, i_j < v < i_(j+1)，其颜色可以从 中自由选择{ 1, ..., j }。

这可以通过以下代码实现：

/*
 * 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 );
}

警告：上面的代码确实编译并运行，其结果似乎是正确的。当然，它的远形式正在被正式验证...... ;-)。

于 2013-07-11T13:14:22.837 回答