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 が赤の場合、グラフの色付けでは、赤-赤-赤は青-青-青と同じです。それが私のコードが行うことです: グラフのすべての可能な異なる色の組み合わせを生成します。

今、コードを改善する必要がありますが、何も考えられませんでした。私は 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 );
}

警告: 上記のコードはコンパイルおよび実行され、その結果は正しいように見えます。もちろん、その far 形式は正式に検証されています ... ;-)。

于 2013-07-11T13:14:22.837 に答える