/* blockdecomp.c
graph.h を同じディレクトリに download して用いよ

コンパイル命令と実行命令：
gcc blockdecomp.c -o blockdecomp
./blockdecomp

K. Shiota
2005.6.22
*/

#define MAXORDER 64
#include "graph.h"

main()
{
	Graph g;		// 探索対象グラフ（連結に限る）
	Graph h;		// ブロック表示用グラフ
	List o;			// ブロックの頂点数のリスト
	List s;			// ブロックの頂点数インデックスのリスト
	List v;			// ブロックの頂点のリスト
	int i,j,n,t,k;

// 乱数の初期化
	srand(time(NULL));

// ランダムなグラフの場合
	g=EmptyGraph(2);
	while(!ConnectedQ(g)) g=RandomGraph(8,0.2);
	printf("\nGraph :\n");
	WriteGraph(g);
	// getchar();
	k=BlockDecompose(g,&o,&s,&v);

	printf("\nBlock Decomposition :\n\n");
	for(i=0;i<k;i++){
		t=o.mem[i];
		n=s.mem[i];
		printf("%d-th component :",i);
		for(j=0;j<t;j++) printf(" %d",v.mem[n+j]);
		printf("\n");
		h=InducedSubGraph(g,SubList(v,n,n+t-1));
		WriteGraph(h);
		printf("\n");
		//getchar();
	}
}