ＣでＢＡモデルを作りたいのですが

質問

複雑ネットワークの勉強をしている者です。
Ｃでバラバシモデルの作成を行っておりますが、Pajekを使いＣで書いたプログラムを動かしたいのです。
しかし、最終頂点数が２０を超えると動かなかったり、クラスター係数が出なくなったりします。
原因は、
(1)i,jの値が重なっている
(2)同じ組み合わせが出現する
ことだと思われます。
(1)(2)が出なくなるプログラムにする方法を教えてください。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void ba_model(int N, int m0, int m);
int sum(int *data, int n);

int main(int argc, char *argv[])
{
int N;
int m0=atoi(argv[1]);
int m=atoi(argv[2]);
char filename[18]="ba_model.net";
FILE *fp;

if(argc == NULL) exit(0);

printf("Input Vertex Size: ");
scanf("%d", &N);

printf("Vertex Size: %d\n",N);
printf("Initial Vertex: %d\n",m0);
printf("Edge Number: %d\n",m);

fp=fopen(filename, "w");
fprintf(fp, "*Vertices %d\n", N);
fprintf(fp, "*Edges\n");
fclose(fp);
ba_model(N, m0, m);

return 0;

}

void ba_model(int N, int m0, int m) {

int i, j, n;
int output_degree[100];
int edge_number;
double p;

char filename[18]="bamodel.net";
FILE *fp;
fp=fopen(filename, "a");
if(fp==NULL) {
printf("Error FileOpen\n");
} else {
printf("FileOpen OK:%s\n",filename);
}

srand(time(NULL));
printf("乱数初期化OK\n");

printf("N=%d, m0=%d, m=%d\n",N,m0,m);

for(i=0; i<N; i++) {
edge_number=0;
for(j=m0; j<N; j++) {
p=(double)(output_degree[j]+1)/(double)sum(output_degree, i);
printf("p(%d)=%lf\n",j,p);
if(p > (double)rand()/RAND_MAX) {
output_degree[i]++;
output_degree[j]++;
edge_number++;

if((i+1)!=(j+1)) {
printf("%d %d 1\n", i+1, j+1);
}else{
break;
}
}
if( m < edge_number )
break;
}
}
fclose(fp);
}

int sum(int *data, int n) {

int k;
int sum=0;

printf("In Sum: n=%d\n",n);

if(n==0) {
sum = 1;
}

for(k=0; k<n; k++) {
printf("k=0 n=0\n");
sum = sum + data[k] + 1;
}
return sum;
}

回答No.1

noocyte

> (1)(2)が出なくなるプログラムにする方法を教えてください。

> (1)i,jの値が重なっている

自己ループを含まない無向グラフでよければ，i＜j となるように制限する．

> (2)同じ組み合わせが出現する

どの辺を生成したかを覚えておく必要がある．
自己ループを含まない無向グラフにおいて，頂点 i，j (0 ≦ i ＜ j ＜ N)
の間に辺があれば，その辺番号を次の関数で定義する．

int EdgeID(int i, int j)
{
return j * (j - 1) / 2 + i;
}

辺番号の範囲は 0 ～ EdgeID(N-2, N-1) - 1 なので，

// 辺の最大数 (辺番号の最大値＋１)
int maxEdges = EdgeID(N - 2, N - 1) + 1;

// 辺が存在するか否かを示すフラグの配列
char *EdgeExists = calloc(1, (size_t)maxEdges);

とする．辺 (i, j) を追加しようとしたとき，
まず eid = EdgeId(i, j) を計算し，

・まだその辺が存在しない (EdgeExists[eid] == 0) ならば
　EdgeExists[eid] に０以外の値をセットし，辺を追加する．

・既に存在しているならば追加しない．