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

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

K. Shiota
2005.6.16
*/

#define MAXORDER 256
#include "graph.h"

main()
{
	Graph g;	// オイラーでない半オイラーグラフ
	Graph h;	// g を単純化したグラフ
	int u,v;	// 奇数次数の２点
	int ew[1024];	// h の半オイラー歩道
	List path;	// v-u 最短道	
	int l;		// v-u 最短距離
	int i;
	int m;		// h の辺数
	int w;		// g の重み合計

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

// ランダムな重み付き半オイラーグラフを生成
// 引数は頂点数、辺の割合、最大重み
	g=EmptyGraph(2); while(!SemiEulerianGraphQ(SimplifiedGraph(g),&u,&v)) g=RandomWeightedGraph(6,0.5,5);

	printf("Graph  G :\n");
	WriteGraph(g);
	printf("\n");
	h=SimplifiedGraph(g);
	if(SemiEulerianGraphQ(h,&u,&v)){
		m=SemiEulerianWalk(h,u,v,ew);
		printf("u = %d\n",u);
		printf("v = %d\n\n",v);
		printf("Semi-Eulerian Walk from u to v :\n");
		for(i=0;i<=m;i++){
			if(i!=0) printf(" -> ");
			printf("%d",ew[i]);
		}
		printf("\n\n");
		l=Dijkstra(g,v,u,&path);
		printf("Minimum Path from v to u :\n");
		for(i=0;i<path.len;i++){
			if(i!=0) printf(" -> ");
			printf("%d",path.mem[i]);
		}
		printf("\n\n");

		printf("Total Walk :\n",l);
		for(i=0;i<m;i++){
			if(i!=0) printf(" -> ");
			printf("%d",ew[i]);
		}
		for(i=0;i<path.len;i++)
			printf(" -> %d",path.mem[i]);
		printf("\n\n");
		printf("Length = %d\n",l+CountEdge(g));
	}
	else{
		printf("G  is Eulerian or is not Semi-Eulerian.\n");
	}
}