「アルゴリズム・データ構造演習 課題A1ソース」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
--------------------------------
プログラムリスト
--------------------------------
プログラムは仕様通りに作ったものと、多少関数化したり追加した
りして作りなおしたものと2つ組んだ。なので２つとも載せる。
その１ 仕様通り
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
typedef unsigned char boolean;
boolean **data;
boolean *Q;
boolean *Qmax;
/*----------------------------------------------------------
指定された頂点数と発生確率で隣接頂点行列を作成する関数(課題
a1で使用)
------------------------------------------------------------*/
void indata(double p,int v)
{
int i,j;
double ran;
for(i=0;i<v;i++)
{
for(j=i+1;j<v;j++)
{
ran = (double)rand()/RAND_MAX; /*ランダム関数を正規化して代入*/
if(ran<=p)
{
data[i][j]=1;data[j][i]=1; /*ランダム値がpより
高ければ隣接頂点*/
}
else
{
data[i][j]=0;data[j][i]=0;
}
}
}
for(i=0;i<v;i++)
data[i][i]=0; /*対角成分には隣接頂点とならない
*/
}
/*-----------------------------------------------------------
作成された隣接頂点行列をディスプレイに表示させる関数(課題a1
で使用)
-------------------------------------------------------------*/
void display(int v)
{
int i,j;
if(v<=20)
{
printf(" |");;
for(i=0;i<v;i++)
{
printf("%3d",i+1);
}
printf("¥n");
for(i=0;i<=v;i++)
{
printf("---");
}
printf("¥n");
for(i=0;i<v;i++)
{
printf("%2d|",i+1);
for(j=0;j<v;j++)
{
printf("%3d",data[i][j]);
}
printf("¥n");
}
printf("¥n");
}
}
/*---------------------------------------------------------------
探索する頂点が残っているかどうか判別する関数
-----------------------------------------------------------------*/
int check1(boolean *S,int v)
{
int i;
for(i=0;i<v;i++)
{
if(S[i]==1) return(1);
}
return(0);
}
/*---------------------------------------------------------------
今回は未使用の関数
int check2(boolean *S,int v)
{
int i,sum=0;
for(i=0;i<v;i++)
{
if(S[i]==1)return(i);
}
return(-1);
}
-----------------------------------------------------------------*/
/*----------------------------------------------------------------
頂点数を吐き出す関数
---------------------------------------------------------------*/
int Enumber(boolean *X,int v)
{
int i,sum=0;
for(i=0;i<v;i++)
{
if(X[i]==1)
sum++;
}
return(sum);
}
/*-----------------------------------------------------------------
再帰的に最大クリークを探し出す関数(今回の穴埋め部)
------------------------------------------------------------------*/
void Extend(boolean *S,int v)
{
int i,j,q;
static boolean *Sq;
Sq = (boolean*)malloc(sizeof(boolean)*v); /*Sqの領域確保*/
while(check1(S,v) != 0) /*すべての頂点を調べるま
で繰り返し*/
---------------------------------------------------------
穴埋めの部分
------------------------------------------------------
}
}
}
/*------------------------------------------------------------
ポインタの必要なメモリ領域を確保する関数
-------------------------------------------------------------*/
void ALLOCATE(int v)
{
int i;
data = (boolean**)malloc(sizeof(boolean*)*v);
for(i=0;i<v;i++)
{
data[i] = (boolean*)malloc(sizeof(boolean)*v);
}
Q = (boolean*)malloc(sizeof(boolean)*v);
Qmax = (boolean*)malloc(sizeof(boolean)*v);
}
/*-------------------------------------------------------------
確保したメモリを解放する関数
--------------------------------------------------------------*/
void FREE(int v)
{
int i;
for(i=0;i<v;i++)
{
free(data[i]);
}
free(data);
free(Q);
free(Qmax);
}
/*-------------------------------------------------------------
メイン部
--------------------------------------------------------------*/
int main(void)
{
int i,v;
double p,msec;
clock_t start,end;
long t;
char k;
boolean *V;
/* srand(time(NULL)); rand関数のシード値を初期
化。rand関数による出力を毎回変えたい場合はコメントアウ
トをはずす。*/
do
{
printf("DATA SIZE =");
scanf("%d",&v); /*DATA SIZEをコマンドライ
ンから読み込み*/
ALLOCATE(v);
V = (boolean*)malloc(sizeof(boolean)*v);
do
{
printf("prob of edges=");
scanf("%lf",&p); /*prob of edgesをコマンドラインか
ら読み込み*/
}while(p<0||1<p); /*入力が0から1に入るま
で繰り返し*/
indata(p,v);
display(v);
for(i=0;i<v;i++) /*頂点数,クリー
ク,最大クリークの初期化*/
{
V[i] = 1;
Q[i] = 0;
Qmax[i] = 0;
}
printf("ok¥n");
start = clock(); /*時間計測開始*/
Extend(V,v); /*最大クリーク抽出*/
end = clock(); /*時間計測終了*/
t = end - start;
msec = (t*1000)/CLOCKS_PER_SEC; /*単位をmsにす
るための計算*/
for(i=0;i<v;i++) /*最大クリーク出力その1*/
printf("%d",Qmax[i]);
printf("¥n");
for(i=0;i<v;i++) /*最大クリーク出力その2*/
{
if(Qmax[i]!=0)
printf("%d",i+1);
}
printf("¥n"); /*最大クリーク数出力*/
printf("size of maximum clique : %d ¥n¥n",Enumber(Qmax,v));
printf("%lf ms%d¥n",msec,t);
FREE(v); /*メモリ解放*/
free(V);
fflush(stdin);/*バッファに格納されてるデータを吐出し
2度目の入力に備える*/
printf("continue?(y or n)");
scanf("%c",&k);
printf("¥n¥n");
}while(k=='y'); /*countinue?に対してy
と答えている間は繰り返し*/
}
ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー
その２ 少々追加や変更して作りなおしたもの
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
#include<sys/time.h>
typedef unsigned char boolean;
boolean **data;
boolean *Q;
boolean *Qmax;
boolean *V;
const int RANDOM_MAX = 2147483647; /*2^31-1*/
int v;
double p;
/*----------------------------------------------------------
指定された頂点数と発生確率で隣接頂点行列を作成する関数(課題
a1で使用)
------------------------------------------------------------*/
void indata(double p,int v)
{
int i,j;
double ran;
for(i=0;i<v;i++)
{
for(j=i+1;j<v;j++)
{
ran = (double)random()/(double)RANDOM_MAX; /*ランダム関数
を正規化して代入*/
if(ran<=p)
{
data[i][j]=1;data[j][i]=1; /*ランダム値がpより
高ければ隣接頂点*/
}
else
{
data[i][j]=0;data[j][i]=0;
}
}
}
for(i=0;i<v;i++)
data[i][i]=0; /*対角成分には隣接頂点とならない
*/
}
/*-----------------------------------------------------------
作成された隣接頂点行列をディスプレイに表示させる関数(課題a1
で使用)
-------------------------------------------------------------*/
void display(int v)
{
int i,j;
if(v<=20)
{
printf(" |");;
for(i=0;i<v;i++)
{
printf("%3d",i+1);
}
printf("¥n");
for(i=0;i<=v;i++)
{
printf("---");
}
printf("¥n");
for(i=0;i<v;i++)
{
printf("%2d|",i+1);
for(j=0;j<v;j++)
{
printf("%3d",data[i][j]);
}
printf("¥n");
}
printf("¥n");
}
}
/*---------------------------------------------------------------
探索する頂点が残っているかどうか判別する関数
-----------------------------------------------------------------*/
int check1(boolean *S,int v)
{
int i;
for(i=0;i<v;i++)
{
if(S[i]==1) return(1);
}
return(0);
}
/*---------------------------------------------------------------
今回は未使用の関数
int check2(boolean *S,int v)
{
int i,sum=0;
for(i=0;i<v;i++)
{
if(S[i]==1)return(i);
}
return(-1);
}
-----------------------------------------------------------------*/
/*----------------------------------------------------------------
頂点数を吐き出す関数
---------------------------------------------------------------*/
int Enumber(boolean *X,int v)
{
int i,sum=0;
for(i=0;i<v;i++)
{
if(X[i]==1)
sum++;
}
return(sum);
}
/*-----------------------------------------------------------------
再帰的に最大クリークを探し出す関数(今回の穴埋め部)
------------------------------------------------------------------*/
void Extend(boolean *S,int v)
{
int i,j,q;
static boolean *Sq;
Sq = (boolean*)malloc(sizeof(boolean)*v); /*Sqの領域確保*/
while(check1(S,v) != 0) /*すべての頂点を調べるま
で繰り返し*/
{
for(i=0;i<v;i++)
{
if (S[i]==1)
{
for(q=0;q<v;q++) /*S[i]の隣接頂点集合作成部*/
{
if(S[q]==1 && data[i][q]==1)
Sq[q]=1;
else
Sq[q]=0;
}
Q[i]=1; /*Qに頂点iを加える*/
if(check1(Sq,v)!=0) /*Sqが空集合じゃない限り再帰*/
Extend(Sq,v);
else if(Enumber(Q,v) > Enumber(Qmax,v)) /*Qmax入れ替え部*/
{
for(j=0;j<v;j++)
Qmax[j] = Q[j];
}
S[i]=0; /*調べ終えた頂点を集合から取り除く*/
Q[i]=0;
}
}
}
}
/*------------------------------------------------------------
ポインタの必要なメモリ領域を確保する関数
-------------------------------------------------------------*/
void ALLOCATE(int v)
{
int i;
data = (boolean**)malloc(sizeof(boolean*)*v);
for(i=0;i<v;i++)
{
data[i] = (boolean*)malloc(sizeof(boolean)*v);
}
Q = (boolean*)malloc(sizeof(boolean)*v);
Qmax = (boolean*)malloc(sizeof(boolean)*v);
V = (boolean*)malloc(sizeof(boolean)*v);
}
/*-------------------------------------------------------------
確保したメモリを解放する関数
--------------------------------------------------------------*/
void FREE(int v)
{
int i;
for(i=0;i<v;i++)
{
free(data[i]);
}
free(data);
free(Q);
free(Qmax);
free(V);
}
/*-------------------------------------------------------------
結果を出力する関数(追加)
--------------------------------------------------------------*/
void result(int v,double msec)
{
int i;
for(i=0;i<v;i++) /*最大クリーク出力その1*/
printf("%d",Qmax[i]);
printf("¥n");
for(i=0;i<v;i++) /*最大クリーク出力その2*/
{
if(Qmax[i]!=0)
printf("%d",i+1);
}
printf("¥n"); /*最大クリーク数出力*/
printf("size of maximum clique : %d ¥n¥n",Enumber(Qmax,v));
printf("%10.6f ms¥n",msec);
}
/*-------------------------------------------------------------
頂点数入力のための関数(追加)
--------------------------------------------------------------*/
int inputv(int v)
{
do
{
printf("DATA SIZE =");
scanf("%d",&v);
if(v<0) /*入力が0以下の場合は警告を出して再入力
*/
fprintf(stderr,"DATA SIZE must be over 0!!");
}while(v<0);
return(v);
}
/*-------------------------------------------------------------
枝存在確率入力のための関数(追加)
--------------------------------------------------------------*/
double inputp(double p)
{
do
{
printf("prob of edges=");
scanf("%lf",&p);
if(p<0||1<p) /*入力が0から1じゃ
なかったから警告出して再入力*/
fprintf(stderr,"Prob of edges must be 0 to 1!!¥n");
}while(p<0||1<p);
return(p);
}
/*-------------------------------------------------------------
頂点数，クリーク，最大クリークの初期化(追加)
--------------------------------------------------------------*/
void initialization(int v)
{
int i;
for(i=0;i<v;i++)
{
V[i] = 1;
Q[i] = 0;
Qmax[i] = 0;
}
}
/*-------------------------------------------------------------
計測にかかった時間をms単位で返す関数(追加)
--------------------------------------------------------------*/
double counttime(double start,double end)
{
double msec;
msec = end - start;
msec = msec*1000;
return(msec);
}
/*-------------------------------------------------------------
処理を続けて行うかもうやめるかを選択させる関数(追加)
--------------------------------------------------------------*/
char again(void)
{
char k;
fflush(stdin); /*バッファに格納されてるデータを吐出し
2度目の入力に備える*/
printf("continue?(y or n)");
scanf("%c",&k);
printf("¥n¥n");
return(k);
}
/*-------------------------------------------------------------
gettimeofdayを使ったより正確な時間測定をする関数(追加)
--------------------------------------------------------------*/
double gettimeofday_sec()
{
struct timeval tv;
gettimeofday(&tv,NULL);
return tv.tv_sec + (double)tv.tv_usec*1e-6;
}
/*-------------------------------------------------------------
メイン部
--------------------------------------------------------------*/
int main(void)
{
int i;
double msec;
double start,end;
char k;
srandom(time(NULL)); /*random関数のシード値を初期化。random
関数による出力を毎回変えたい場合はコメントアウトをはずす。*/
do
{
v = inputv(v); /*頂点数入力*/
p = inputp(p); /*枝存在確率入力*/
ALLOCATE(v); /*メモリ領域確保*/
indata(p,v); /*グラフを作成*/
display(v); /*グラフをディスプレイに表示*/
initialization(v); /*各値を初期化*/
start = gettimeofday_sec(); /*時間計測開始*/
Extend(V,v); /*最大クリーク抽出*/
end = gettimeofday_sec(); /*時間計測終了*/
msec = counttime(start,end); /*入力された時間の単位を
msに直す*/
result(v,msec); /*結果出力*/
FREE(v); /*メモリ解放*/
k = again(); /*処理を続けるかやめるか*/
}while(k=='y'); /*countinue?に対してy
と答えている間は繰り返し*/
}
--------------------------------
プログラムの実行結果
--------------------------------
実行はコマンドラインから"maxclique"と入力することで実行
できるようにバイナリファイルにパスを通したの
で、"maxclique"と入力すれば実行できる。
実行すると、データサイズと枝存在確率を聞いてくるので、その値を
stdinで入力される。その後与えられるグラフから最大クリークを探
し、グラフ、最大クリーク、時間をstdoutで出力して終わる。
--------------------------------
プログラムリストの説明
--------------------------------
上記プログラムリストで逐次コメントアウトをして各処理がどのよ
うなことをやっているのかは書いているので、ここでは大まかにのべる。
まず、最初の状態でV={1,1,1,1,1}というようになっていて、
これがV={0,0,0,0,0}となるまで最大クリークを探し続ける、
というのが大まかな動作である。
最大クリークを見つけた場合は、それをQmaxにいれる。例え
ば最大クリークが1,2,4,5であったら、V={1,1,0,1,1}
のように表記される。これを最後に出力する。
--------------------------------
実行結果についての解説および考察
--------------------------------
これは4/25講義中に提出したレポートに載せているので割愛する。
ただし、プログラムを組む上で直した部分をここで述べようと思う。
１.rand関数
今回の場合はそこまで乱数がバラバラでなくてはいけないわけでは
ないのでrand関数でもかまわないのだが、rand関数は
あまり良くない関数として知られている。（最新版は多少改善され
たようではあるが。）一般的にはrand関数よりもバラツキの良い
random関数が使われるようだ。なので今回はrandom関数を用
いている。
rand関数は0からRAND_MAXという値までの中で無作為に
値を出す。RAND_MAXは環境によって違うらしいのだ
が、IEDの計算機ではRAND_MAX=32768であった。これに対し
random関数は、0から2^31-1までの値の中から無作為に
値を出す。なので、正規化する際はRANDOM_MAXという別の値
を用意して(RANDOM_MAX=2^31-1とした)、それを用いて
値を正規化した。
2.clock
時間を計測する関数なのだが、これも精度はあまり良いとは言えな
い関数であるようだ。なので、実際測定する際はgettimeofday
というものを使った。（このことはレポートにも触れてい
る。）clockが秒単位の精度であるのに対し
て、gettimeofdayはマイクロ秒の精度がある。普通の測定では
clock関数でも良いだろうが、今回は出力された時間が実行する度に
変わってしまっていたので、グラフを作る際10回の平均値を
とってプロットした。なので、より精度の良い平均値を出すには
clock関数では足りないのではないか、と思いgettimeofdayを
使用した。
3.関数化
メイン部を見てもらえば分かると思うのだが、メイン部は時間測定
以外は全て関数呼び出しのみになっている。「オブジェクト指向」
というの少し意識してみたのだが、これは少しやり過ぎたかもしれ
ない。しかし、こうすることでプログラムの可読性は増したのでは
ないかと思う。また、「実際に時間をmsに直して出力する、
という動作はDFT、FFTの課題でもどうやら用いるよう
だ。なので、このように他のプログラムでも用いられ得る部分は関
数化した方が良いのではないかと思った。
過去の課題レポートを添付しています.
ページ下部の「添付ファイル」を参照ください.
