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

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

K. Shiota
2005.6.2
*/

#define MAXORDER 256
#include "graph.h"

main()
{
	Graph g;		// 探索対象グラフ
	Graph tree;		// 探索木
	List parent;		// 親を登録するリスト
	List path;		// 道順（初期値は空）
	int startNode=0;	// 出発点	
	int goalNode;		// 目的地
	int i;
// テストデータ
	int maze[10][10] = {
               /* 0  1  2  3  4  5  6  7  8  9 */
    /* node0 */ { 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
    /* node1 */ { 1, 0, 1, 0, 1, 0, 0, 0, 0, 0},
    /* node2 */ { 0, 1, 0, 1, 0, 1, 0, 0, 0, 0},
    /* node3 */ { 0, 0, 1, 0, 0, 0, 0, 0, 0, 0},
    /* node4 */ { 0, 1, 0, 0, 0, 1, 0, 1, 1, 0},
    /* node5 */ { 0, 0, 1, 0, 1, 0, 1, 0, 1, 0},
    /* node6 */ { 0, 0, 0, 0, 0, 1, 0, 0, 0, 0},
    /* node7 */ { 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
    /* node8 */ { 0, 0, 0, 0, 1, 1, 0, 0, 0, 1},
    /* node9 */ { 0, 0, 0, 0, 0, 0, 0, 0, 1, 0}
		};

// 乱数の初期化
	srand(time(NULL));
	
// テストデータの場合
//	g=ArraytoGraph(10,maze);

// ランダムなグラフの場合
	g=RandomGraph(128,0.1);

// 標準入力からグラフを読み込む場合
//	g=ReadGraph();
	
	goalNode=g.ord-1;
	tree=DFSTree(g,startNode,&parent);
	printf("\nGraph :\n");
	WriteGraph(g);
	printf("\nDepth First Search Tree ( Root = 0 ) :\n");
	WriteGraph(tree);
	if(parent.mem[goalNode]!=-1){
		// goalNode に親がいれば道あり
		// goalNode から順に親をたどって道順 path を作る
		path=ParentPath(parent,startNode,goalNode);
		printf("\nSolution : ");		
		for(i=0;i<path.len;i++){
			if(i!=0) printf(" -> ");
			printf("%d",path.mem[i]);
		}
		printf("\n");
	}
	else printf("\nNo Solution\n");
	getchar();
	
	tree=WFSTree(g,startNode,&parent);
	printf("Width First Search Tree :\n");
	WriteGraph(tree);
	if(parent.mem[goalNode]!=-1){
		// goalNode に親がいれば迷路の解あり
		// goalNode から順に親をたどって道順 path を作る
		path=ParentPath(parent,startNode,goalNode);
		printf("\nSolution : ");
		for(i=0;i<path.len;i++){
			if(i!=0) printf(" -> ");
			printf("%d",path.mem[i]);
		}
		printf("\n");
	}
	else printf("\nNo Solution\n");
}