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

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

K. Shiota
2005.6.14
*/

#define MAXORDER 256
#include "graph.h"

main()
{
	Graph g;		// 探索対象グラフ
	Graph mf;		// 最大フロー
	int startNode=0;	// 出発点	
	int goalNode;		// 目的地
	int v;
	int n;

// テストデータ
	int maze[5][5] = {
		{ 0, 4, 3, 1, 0},
		{ 0, 0, 0, 1, 2},
		{ 0, 4, 0, 2, 0},
		{ 0, 2, 0, 0, 4},
		{ 0, 0, 0, 0, 0}
	};

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

// テストデータの場合
//	n=5; goalNode=n-1; g=ArraytoGraph(5,maze); 

	
// ランダムなネットワーク
	n=16; goalNode=n-1; g=RandomNetwork(n,startNode,goalNode,0.5,9);
	printf("\nNetwork :\n");
	WriteGraph(g);
	v=MaxFlow(g,startNode,goalNode,&mf);
	printf("\nMaximum Flow ( %d -> %d ) :\n",startNode,goalNode);
	WriteGraph(mf);
	printf("\nValue of the Flow = %d\n",v);
}