c
#include <stdio.h>#include <string.h>#include <stdlib.h> #define MAX_LEN 256 //ファイル名の最大値 //連結か調べるvoid visit( int v, int *yet, int N, int **adjacent ) { int w; yet[v] = 0; for ( w=0; w<N; w++ ) if ( adjacent[v][w] == 1 && yet[w] == 1 ) visit( w, yet, N, adjacent ); } int connect_check( int N, int **adjacent ) { int i, *YetToVisit, count = 0; YetToVisit = ( int * )malloc( sizeof( int ) * N ); for ( i=0; i<N; i++ ) YetToVisit[i] = 1; for ( i=0; i<N; i++ ) if ( YetToVisit[i] == 1 ) { count++; visit( i, YetToVisit, N, adjacent ); } free( YetToVisit ); return ( count ); } //累乗を計算int po(int x,int y){ int result = 1; int i; for(i=0;i<y;i++){ result = result * x; } return result;} int main(int argc, char *argv[]) { int i,j; int n1,n2; //点番号の一時保存 int N,M = 0; //点の数、辺の数 FILE *fp; //ファイルポインタ char fn[MAX_LEN]; //グラフファイル名 int **adjacent; //隣接行列 double dsum = 0; //次数の合計 double dave = 0; //次数の平均 int x,k,m; int val; //10進数表示 int delta = 100; //最小次数 int **Gdash; //(8-x)(8-x)の隣接行列 int v[8] = {}; //2進数表示 int count = 0; int check = 0; //実行時引数の数をチェック if(argc != 2){ fprintf(stderr, "Usage: %s graph_file\n", argv[0]); exit(1); } //ファイル名をコピー strcpy(fn, argv[1]); //ファイルオープン if((fp = fopen(fn, "r")) == NULL){ fprintf(stderr, "%s cannot found./n", fn); exit(1); } //1行目の読み込み fscanf(fp, "%d", &N); //隣接行列を動的に作成する N x N の2次元配列をmallocする adjacent = (int **)malloc(sizeof(int *) * N); for(i=0;i<N;i++){ adjacent[i] = (int *)malloc(sizeof(int) * N); for(j=0;j<N;j++){ adjacent[i][j] = 0; } } //2行目以降の読み込み while(fscanf(fp, "%d %d", &n1,&n2) != EOF){ M++; adjacent[n1][n2] = 1; adjacent[n2][n1] = 1; } fclose(fp); //隣接行列行列を表示 printf("N = %d, M = %d\n", N,M); for(i=0;i<N;i++){ for(j=0;j<N;j++){ printf("%d", adjacent[i][j]); } printf("\n"); } //各次数の計算 int d[N]; //次数を格納する for(i=0;i<N;i++){ d[i] = 0; } for(i=0;i<N;i++){ for(j=0;j<N;j++){ if(adjacent[i][j] == 1){ d[i]++; dsum++; } } if(delta > d[i]){ delta = d[i]; //最小次数の獲得 } } dave = dsum/N; //次数の平均の計算 //次数の表示 for(i=0;i<N;i++){ printf("v%d: %d ", i,d[i]); } printf("\n"); printf("average degree: %lf\n", dave); printf("delta = %d\n",delta);//最小次数の表示 for(x=1;x<delta;x++){ printf("*****x=%d*****\n",x); for(val=1;val<256;val++){ //Vx作成 for(i=0;i<8;i++){ v[i] = val % po(2,i+1) / po(2,i); //2進数の配列に変換 } //Vx内の要素数確認 count = 0; for(i=0;i<8;i++){ if(v[i] == 1) count++; } //(8-x)*(8-x)の配列をmalloc Gdash = (int **)malloc(sizeof(int*)*(8-x)); for(i=0;i<8;i++){ Gdash[i] = (int *)malloc(sizeof(int)*(8-x)); for(j=0;j<8;j++){ Gdash[i][j] = 0; } } //Gdash作成 k = m = 0; if(x == count){ for(i=0;i<8;i++){ m = 0; for(j=0;j<8;j++){ if(v[i] == 0 && v[j] == 0){ //v[i]が消す必要のない場合 if(adjacent[i][j] == 1){ //Gdashに1を代入 Gdash[k][m] = 1; } m++; } } if(v[i] == 0){ //v[i]が消す必要のない場合 k++; } } //Vxが分離集合の場合 if(connect_check(8-x,Gdash) != 1){ printf("("); for(i=0;i<8;i++){ if(v[i] == 1) printf(" %d",i); } printf(" ) Separated!!\n"); check++; break; }else{//分離集合ではなかった場合 printf("("); for(i=0;i<8;i++){ if(v[i] == 1) printf(" %d",i); } printf(" ) Connected\n"); } } //メモリの開放 for(i=0;i<8-x;i++){ free(Gdash[i]); } free(Gdash); } if(check == 1) break; } if(x != delta){ printf("\n"); printf("k(G) = %d\n", x); printf("Separating set = ("); for(i=0;i<8;i++){ if(v[i] == 1) printf(" %d",i); } printf(" )\n"); }else{ printf("\n"); printf("k(G) = %d (=mindegree)\n", x); } //メモリの開放 for(i=0;i<N;i++){ free(adjacent[i]); } free(adjacent); return 0;}
0 コメント