?? peg.c
字號:
/* FILENAME: peg.c AUTHOR: Tadashi Wadayama HOW TO MAKE: gcc -O2 -o peg peg.c*/#include <stdio.h>#include <stdlib.h>void visit_cnode(int c, int v, int l);int n;int m;int wc;int **H;int *rweight; /* row weight of H */int L;int *visited;int len;void new_column(){ int i,j; int min, mindex; for (i = 0; i <= m-1; i++) { H[i][n] = 0; } for (j = 1; j <= wc; j++) { min = 10000; for (i = 0; i <= m-1; i++) { if (rweight[i] < min) { min = rweight[i]; mindex = i; } } H[mindex][n] = 1; rweight[mindex]++; } n++;}void visit_vnode(int c, int v, int l){ int i,j; if (l > L) return; //for (i = 1; i <=l; i++) printf("\t"); //printf("visit_vnode: v = %d, l = %d\n",v,l); for (i = 0; i <= m-1; i++) { if (H[i][v] == 1) visit_cnode(i,v,l+1); }}void visit_cnode(int c, int v, int l){ int i,j; if (l > L) return; //for (i = 1; i <=l; i++) printf("\t"); //printf("visit_cnode: c = %d, l = %d\n",c,l); visited[c] = 1; for (i = 0; i <= n; i++) { if (H[c][i] == 1) visit_vnode(c,i,l+1); }}int peg_process(){ int i,j; int min, mindex; int sum; for (i = 0; i <= m-1; i++) { H[i][n] = 0; } for (i = 0; i <= m-1; i++) visited[i] = 0; for (j = 1; j <= wc; j++) { //printf("==================== j = %d\n",j); min = 10000; for (i = 0; i <= m-1; i++) { if ((rweight[i] < min)&&(visited[i] == 0)) { min = rweight[i]; mindex = i; } } H[mindex][n] = 1; rweight[mindex]++; for (i = 0; i <= m-1; i++) visited[i] = 0; visit_cnode(mindex,n,0); //printf("visited:"); //for (i = 0; i <= m-1; i++) printf("%d ",visited[i]); //printf("\n"); sum = 0; for (i = 0; i <= m-1; i++) sum += visited[i]; //printf("number of visited checknodes = %d\n",sum); if (sum == m) { fprintf(stderr,"PEG process stoped: n = %d\n",n); return -1; } } n++; }void print_H(){ int i,j; for (i = 0; i <= m-1; i++) { for (j = 0; j <= n-1; j++) { printf("%d ",H[i][j]); } printf("\n"); }}void init(){ int i,j; H = malloc(sizeof(int*)*m); rweight = malloc(sizeof(int)*m); visited = malloc(sizeof(int)*m); for (j = 0; j <= m-1; j++) { H[j] = malloc(sizeof(int)*5000); rweight[j] = 0; }}void output_spmat(){ int *row_w; int *col_w; int i,j; int w; int max_rw,max_cw; row_w = malloc(sizeof(int*)*m); col_w = malloc(sizeof(int*)*n); max_rw = 0; for (i = 0; i <= m-1; i++) { w = 0; for (j = 0; j <= n-1; j++) { w += H[i][j]; } row_w[i] = w; if (w > max_rw) max_rw = w; } max_cw = 0; for (j = 0; j <= n-1; j++) { w = 0; for (i = 0; i <= m-1; i++) { w += H[i][j]; } col_w[j] = w; if (w > max_cw) max_cw = w; } printf("%d %d\n",n,m); printf("%d %d\n",max_rw,max_cw); for (i = 0; i<=m-1; i++) printf("%d ",row_w[i]); printf("\n"); for (j = 0; j<=n-1; j++) printf("%d ",col_w[j]); printf("\n"); for (i = 0; i <= m-1; i++) { for (j = 0; j <= n-1; j++) { if (H[i][j] == 1) printf("%d ",j+1); } printf("\n"); }}int main(int argc,char **argv){ int i,j; int r; if (argc != 5) { fprintf(stderr,"usage : peg m wc girth len\n"); fprintf(stderr,"m: number of rows\n"); fprintf(stderr,"wc: column weight\n"); fprintf(stderr,"girth: girth of the bipartite graph\n"); fprintf(stderr,"len: code length\n"); exit(-1); } m = atoi(argv[1]); wc = atoi(argv[2]); L = atoi(argv[3])-2; len = atoi(argv[4]); if (L % 2 != 0) { fprintf(stderr,"girth must be a even number\n"); exit(-1); } //printf("m = %d\n",m); //printf("wc = %d\n",wc); n = 0; init(); while(1) { r = peg_process(); if (r == -1) break; if (n == len) break; fprintf(stderr,"n = %d\n",n); } //print_H(); output_spmat(); printf("# girth = %d\n",L+2);}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -