/* digraph.h : 有向グラフアルゴリズム関数定義部

K. Shiota
2005.6.13-
*/

/*********** 有向グラフ操作関数定義部 **********/

/* 有向グラフ g の弧 uv を除去した有向グラフを返す */
/* 多重弧の場合は1本のみ除去 */
Graph RemoveArc(Graph g, int u, int v)
{
	Graph h=g;
	h.adj[u][v]--;
	return h;
}

/* 有向グラフ g に弧 uv を付加した有向グラフを返す */
Graph AddArc(Graph g, int u, int v)
{
	Graph h=g;
	h.adj[u][v]++;
	return h;
}

/* 有向グラフ g の弧 uv を縮約した有向グラフを返す */
Graph ContractArc(Graph g, int u, int v)
{
	Graph h=g;
	int i,j,t;
	for(i=0;i<h.ord;i++)
		if(i!=u && i!=v)
			h.adj[u][i]=g.adj[u][i]+g.adj[v][i];
	for(i=0;i<h.ord;i++)
		if(i!=u && i!=v)
			h.adj[i][u]=g.adj[i][u]+g.adj[i][v];
	h.adj[u][u]=0;
	h=RemoveVertex(h,v);
	return h;
}

/* 頂点数 = n の有向閉路を返す */
Graph DirectedCycle(int n)
{
	Graph g=EmptyGraph(n);
	int i;
	for(i=0;i<n;i++) g.adj[i][(i+1)%n]=1;
	return g;	
}

/* ランダムな単純有向グラフを返す */
/* 頂点数 = n, 弧の割合 = rate */
Graph RandomDiGraph(int n, float rate)
{
	Graph g;
	int i,j;
	float r;

	g.ord=n;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++){
			r=((float)(rand()%10000))/10000;
			if(r<=rate) g.adj[i][j]=1;
			else g.adj[i][j]=0;
		}
	return g;	
}

/* ランダムな単純重みつき有向グラフを返す */
/* 頂点数 = n, 弧の割合 = rate, 最大重み = m */
/* m<=255 に限定 */
Graph RandomWeightedDiGraph(int n, float rate, int m)
{
	Graph g;
	int i,j;
	float r;

	if(m>255){
		printf("最大重みは 255 までにしてください。\n");
		exit(1);
	}
	g.ord=n;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			if(i==j) g.adj[i][i]=0;
			else{
				r=((float)(rand()%10000))/10000;
				if(r<=rate) g.adj[i][j]=rand()%m+1;
				else g.adj[i][j]=0;
			}
	return g;	
}

/* 有向グラフ g を根 r から深さ優先探索する */
/* p : 親を登録するリスト */
/* 返り値は深さ優先探索木 */
Graph DFSDirectedTree(Graph g, int r, List *p)
{
	Graph t;	// 最終的に深さ優先探索木を格納して返り値にする
	List cl={0,{}};	// 探索の終わった点のリスト ( closed list )
	int c=r;	// 現在の探索点 ( current node )
	int b;		// 探索木をバックトラック ( backtrack ) するか否か
	int f;		// 連結成分を探索し終わったか否か ( finish )
	int i,j;
	
	t=EmptyGraph(g.ord); 			// 木の初期化
	*p=ListInitialize(g.ord,-1);		// 親が居ないと -1
	cl.mem[cl.len++]=r;			// 根 r は探索済み
	do{
		b=1;
		f=0;
		for(i=0;i<g.ord;i++){
			if(i!=c && g.adj[c][i]>0 && !ListMemberQ(i,cl)){
				// 現在の探索点の隣接点で未探索の点を探し見つかれば
				p->mem[i]=c;		// 親を登録
				t.adj[c][i]=1;		// 探索木の弧を登録
				cl.mem[cl.len++]=i;	// 探索済みリストに登録
				c=i;			// 現在点を i に進める
				b=0;			// バックトラックは不要
				break;
			}
		}
		if(b){
			// バックトラックが必要なとき
			// 現在点が r ならこれ以上の探索は不可能
			// そうでなければ探索点の親へ戻る
			if(c==r) f=1;	
			else c=p->mem[c];	
		}
	}while(cl.len!=g.ord && !f);	// 全ての点を探索し終わったか、探索続行不可能で終了
	return t;
}

/* 有向グラフ g を根 r から広さ優先探索する */
/* p : 親 ( parent ) を登録するリスト */
/* 返り値は広さ優先探索木 */
Graph WFSDirectedTree(Graph g, int r, List *p)
{
	Graph t;	// 最終的に広さ優先探索木を格納して返り値にする
	List ll;	// 各 node のレベルを登録するリスト
	int c;		// 現在の探索点 ( current node )
	int f;		// 連結成分を探索し終わったか否か ( finish )
	int l=0;	// 現在のレベル
	int i,j;
	
	t=EmptyGraph(g.ord); 			// 木の初期化
	*p=ListInitialize(g.ord,-1);		// 親が居ないと -1
	ll=ListInitialize(g.ord,-1);		// r 以外の点のレベルの初期値は -1
	ll.mem[r]=l;
	do{
		f=1;
		for(c=0;c<g.ord;c++){
			if(ll.mem[c]==l){	// レベル l の点が全て探索点
				for(i=0;i<g.ord;i++){
					if(i!=c && g.adj[c][i]>0 && ll.mem[i]==-1){
					// 現在の探索点の隣接点で未探索の点を探し見つかれば
						p->mem[i]=c;		// 親を登録
						t.adj[c][i]=1;		// 探索木の弧を登録
						ll.mem[i]=l+1;		// レベルを l+1 に設定
						f=0;			// 探索続行可能
					}
				}
			}
		}
		l++;				// レベルを +1
	}while(ListMemberQ(-1,ll) && !f);	// 全ての点を探索し終わったか、探索続行不可能で終了
	return t;
}

/* 有向グラフ g から多重弧とループを取り去った有向グラフを返す */
Graph SimplifiedDiGraph(Graph g)
{
	Graph h=g;
	int i,j;

	for(i=0;i<h.ord;i++){
		h.adj[i][i]=0;
		for(j=0;j<h.ord;j++)
			if(g.adj[i][j]>0) h.adj[i][j]=1;
	}
	return h;
}

/* 有向グラフ g を単純無向化したグラフを返す */
Graph SimplifiedUndirectedGraph(Graph g)
{
	Graph h=g;
	int i,j;

	for(i=0;i<h.ord;i++){
		h.adj[i][i]=0;
		for(j=i+1;j<h.ord;j++){
			if(g.adj[i][j]>0 || g.adj[j][i]>0){
				h.adj[i][j]=1;
				h.adj[j][i]=1;
			}
		}
	}
	return h;
}

/* 有向グラフ g が弱連結か否か判定する */
int WeakConnectedQ(Graph g)
{
	return ConnectedQ(SimplifiedUndirectedGraph(g));
}

/* 頂点 u の入次数 */
int InDegree(Graph g, int u)
{
	int i,d=0;
	for(i=0;i<g.ord;i++) d+=g.adj[i][u];
	return d;
}

/* 頂点 u の出次数 */
int OutDegree(Graph g, int u)
{
	int i,d=0;
	for(i=0;i<g.ord;i++) d+=g.adj[u][i];
	return d;
}

/* 有向グラフ g がオイラー有向グラフであるか否かを判定する */
int EulerianDiGraphQ(Graph g)
{
	int i;
	
	// 弱連結でなければ偽
	if(!WeakConnectedQ(g)) return 0;		
	// 入出次数の異なる点があれば偽
	for(i=0;i<g.ord;i++)
		if(InDegree(g,i)!=OutDegree(g,i)) return 0;	
	return 1;
}


/* 有向グラフ g の弧数を返す */
int CountArc(Graph g)
{
	int i,j,s=0;
	for(i=0;i<g.ord;i++) for(j=0;j<g.ord;j++) s+=g.adj[i][j];
	return s;
}

/* 有向グラフ g の弧 uv が橋であるか否かを判定する */
int DirectedBridgeQ(Graph g, int u, int v)
{
	Graph t;
	List p;
	t=WFSTree(SimplifiedUndirectedGraph(RemoveArc(g,u,v)),u,&p);	
	// g から uv を除去し無向化したグラフで u を根とする wfs を実行し
	// v に親がいなければ uv は橋
	return (p.mem[v]==-1);			
}

/* オイラー有向グラフ g のオイラーサイクルを配列で返す */
/* 返り値は g のサイズ */
/* Fleury のアルゴリズム */
int EulerianCircuitDirected(Graph g, int *ec)
{
	int m=CountArc(g);	// g のサイズ
	int c=0;		// 現在位置
	Graph h=g,hh;
	int i,k=0,r,t,b;
	
	r=m;
	ec[k++]=c;
	while(r>0){
		t=-1;				// 橋による隣接点登録用変数
		b=0;				// 橋以外の隣接点があれば 1
		for(i=0;i<g.ord;i++){
			if(h.adj[c][i]>0){
				if(c==i){	// ループは先に回ろう	
					h=RemoveArc(h,c,i);
					r--;
					ec[k++]=c;	// サーキットに c を登録
					b=1;		// 橋以外の隣接点があった
					break;
				}
				// ci が橋でなければ i へ進む
				if(!DirectedBridgeQ(h,c,i)){	
					h=RemoveArc(h,c,i);
					r--;
					ec[k++]=i;	// サーキットに i を登録
					c=i;		// 現在位置を i に更新
					b=1;		// 橋以外の隣接点があった
					break;
				}			
				else{
					if(t==-1) t=i;	// ci が橋のときは t=i を仮登録
				}
			}
		}
		if(b==0){
			h=RemoveArc(h,c,t);
			r--;
			ec[k++]=t;	// サーキットに t を登録
			c=t;		// 現在位置を t に更新
		}
	}
	return m;
}