「教えて!ピックアップ」リリース!

複雑ネットワークの勉強をしている者です。
Cでバラバシモデルの作成を行っておりますが、Pajekを使いCで書いたプログラムを動かしたいのです。
しかし、最終頂点数が20を超えると動かなかったり、クラスター係数が出なくなったりします。
原因は、
(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;
}

A 回答 (1件)

> (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 なので,

// 辺の最大数 (辺番号の最大値+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] に0以外の値をセットし,辺を追加する.

・既に存在しているならば追加しない.
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!


人気Q&Aランキング