/* chromatic.c
graph.h, graphpol.h, chromatic.h を同じディレクトリに download して用いよ
再帰命令でグラフを２個ずつ作ってゆくので、MAXORDER が大きいとメモり不足の
おそれあり

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

K. Shiota
2005.6.12
2005.6.14 version
*/

#define MAXORDER 16
#include "graph.h"
#include "graphpol.h"
#include "chromatic.h"

main()
{
	Graph g;
	int k;		// 彩色数
	int lf[16];	// 一次因子のべき指数
	int i;
	POL f;		// 彩色多項式
	POL ff;		// X-(k-1) までの一次因子を取り去った部分

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

	g=RandomGraph(9,0.5);		// ランダムなグラフ
//	g=CompleteGraph(9);		// 完全グラフ
//	g=CompleteBipartiteGraph(5,5);	// 完全二部グラフ
//	g=kDimensionalCubicGraph(3);	// 立方体グラフ
//	g=Cycle(5);			// 奇数長の閉路
//	g=Cycle(6);			// 偶数長の閉路
//	g=GraphSum(CompleteGraph(4),CompleteGraph(5));	// グラフの和
//	g=PetersenGraph();		// ピ−タースングラフ
//	g=EmptyGraph(2); while(!TreeQ(g)) g=RandomGraph(16,0.1);	// ランダムな木

	printf("\nGraph :\n\n");
	WriteGraph(g);
	k=ChromaticInformation(g,&f,&ff,lf);
	printf("\nChromatic Polynomial :\n\n");
	polwriteln(f);
	printf("\n=");
	for(i=0;i<k;i++){
		printf(" (");
		polwrite(linearfactor(i));
		printf(")");
		if(lf[i]>1) printf("^%d",lf[i]);
	}
	if(!poloneq(ff)){
		printf(" (");
		polwrite(ff);
		printf(")");
	}
	printf("\n\nChromatic Number = %d\n",k);
}