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

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

K. Shiota
2005.6.14
2007.7.4 テストデータ変更
*/

#define MAXORDER 256
#include "graph.h"

main()
{
	Graph g;		// 探索対象グラフ
	Graph mf;		// 最大フロー
	int startNode=0;	// 入口は 0
	int goalNode;		// 出口
	int v;
	int n;

// テストデータ
// 頂点数 6
// 入口はノード 0 ( 第 0 列成分が全て 0 )
// 出口はノード 5 ( 第 5 行成分が全て 0 )
	int m[6][6] = {
		{ 0, 4, 2, 5, 0, 0},
		{ 0, 0, 2, 1, 1, 0},
		{ 0, 1, 0, 2, 1, 0},
		{ 0, 0, 1, 2, 4, 3},
		{ 0, 0, 0, 2, 2, 7},
		{ 0, 0, 0, 0, 0, 0}
	};

// テストデータの場合
// n は頂点数（ = 隣接行列のサイズ）
// goalNode は出口
// ArraytoGraph は n 次行列 m を隣接行列に持つグラフを返す関数
	n=6; goalNode=5; g=ArraytoGraph(n,m); 

// ランダムなネットワーク
	srand(time(NULL));	// 乱数の初期化
//	n= 16; goalNode=n-1; g=RandomNetwork(n,startNode,goalNode,0.5,9);
//	n= 32; goalNode=n-1; g=RandomNetwork(n,startNode,goalNode,0.3,9);
//	n= 64; goalNode=n-1; g=RandomNetwork(n,startNode,goalNode,0.2,9);
//	n=128; goalNode=n-1; g=RandomNetwork(n,startNode,goalNode,0.2,9);
//	n=256; goalNode=n-1; g=RandomNetwork(n,startNode,goalNode,0.2,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);
}