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

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

K. Shiota
2005.6.23
*/

#define MAXORDER 64
#define MAXFRAGMENTS 64
#define DRAW 1		// 描画法を出力するときは 1, そうでなければ 0
#include "graph.h"
#include "planar.h"

main()
{
	Graph g;		// 探索対象グラフ（連結に限る）

// テストデータ
	int a[8][8] = {
		{ 0, 1, 0, 0, 0, 0, 1, 0},
		{ 1, 0, 1, 1, 1, 0, 1, 0},
 		{ 0, 1, 0, 0, 1, 0, 0, 0},
 		{ 0, 1, 0, 0, 1, 0, 0, 0},
 		{ 0, 1, 1, 1, 0, 1, 1, 1},
		{ 0, 0, 0, 0, 1, 0, 1, 1},
		{ 1, 1, 0, 0, 1, 1, 0, 1},
		{ 0, 0, 0, 0, 1, 1, 1, 0}};
	int b[9][9] = {
		{ 0, 1, 0, 0, 0, 1, 0, 1, 1},
		{ 1, 0, 0, 0, 1, 0, 0, 1, 1},
		{ 0, 0, 0, 0, 0, 1, 0, 0, 1},
		{ 0, 0, 0, 0, 0, 1, 0, 0, 1},
		{ 0, 1, 0, 0, 0, 0, 0, 1, 0},
		{ 1, 0, 1, 1, 0, 0, 1, 1, 0},
		{ 0, 0, 0, 0, 0, 1, 0, 0, 1},
		{ 1, 1, 0, 0, 1, 1, 0, 0, 0},
		{ 1, 1, 1, 1, 0, 0, 1, 0, 0}};
	int c[15][15] = {
		{ 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0},
		{ 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{ 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0},
		{ 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0},
		{ 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
		{ 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0},
		{ 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0},
		{ 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0},
		{ 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
		{ 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
		{ 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1},
		{ 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1},
		{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1},
		{ 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1},
		{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0}};

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

// テストデータの場合
//	g=ArraytoGraph(8,a);
//	g=ArraytoGraph(9,b);
	g=ArraytoGraph(15,c);

// ランダムなグラフの場合
//	g=EmptyGraph(2); while(!ConnectedQ(g)) g=RandomGraph(24,0.05);
//	g=EmptyGraph(2); while(!ConnectedQ(g)) g=RandomGraph(16,0.2);

//	g=CompleteGraph(5);
//	g=CompleteBipartiteGraph(3,3);
//	g=CompleteBipartiteGraph(2,5);
//	g=PetersenGraph();
	g=WheelGraph(8);
//	g=PlatonicGraph6();
//	g=PlatonicGraph8();
//	g=PlatonicGraph12();
//	g=PlatonicGraph20();

	printf("\nGraph :\n");
	WriteGraph(g);
	printf("\n");
	if(PlanarQ(g)) printf("G  is planar.\n");
	else printf("G  is not planar.\n");
}