/* planar.h
平面性判定関数

描画法の出力が必要なときは main で
#define DRAW 1
を宣言せよ。必要でないときは）
#define DRAW 0

K. Shiota
2005.6.23-24
2005.6.24 描画法をわかりやすく修正
2007.6.13 extending path のバグを修正
2008.6.17-18 extending path のバグを更に修正
*/

#ifndef MAXFRAGMENTS
#define MAXFRAGMENTS 64
#endif

/* ブロック g の、2-連結な平面部分グラフ h に関する fragment を求める
   vh は h に関与する頂点のリスト
   返り値は fragment の個数 */
/* Reference: 
   Chartrand-Oellermann,
   Applied and Algorithmic Graph Theory, Alg.9.1 */
int FragmentDecompose(Graph g, Graph h, List vh, Graph *f)
{
	Graph sc=RemoveEdges(g,h);		// 辺の scan 済み判定用グラフ
	Graph t[MAXFRAGMENTS];			// 探索木を登録するリスト
	List pr[MAXFRAGMENTS];			// 親を登録するリスト
	List l=ListInitialize(g.ord,0);		// ラベルを登録するリスト
	List pv=ListInitialize(g.ord,0);	// 頂点が以前に root になったか否か
	int j=1;	// ラベルの値
	int k=0;	// 最終的に fragment の個数
	int c;		// current vertex
	int r;		// root
	int i;

	Fragment_Step2:
	for(i=0;i<g.ord;i++)
		if(ListMemberQ(i,vh) && pv.mem[i]==0) break;
	if(i>=g.ord) return k;
	else{
		pv.mem[i]=1;
		r=i;
		c=i;
		l.mem[c]=j;
		t[k]=EmptyGraph(g.ord);
		f[k]=EmptyGraph(g.ord);
	}
	
	Fragment_Step3:
	j++;
	
	Fragment_Step4:
	if(c==r && CountEdge(t[k])==0){
		for(i=0;i<g.ord;i++) if(i!=c && sc.adj[c][i]>0) break;
		if(i<g.ord){
			t[k]=AddEdge(t[k],c,i);
			f[k]=AddEdge(f[k],c,i);
			sc=RemoveEdge(sc,c,i);
			l.mem[i]=j;
			pr[k].mem[i]=c;
			c=i;
			goto Fragment_Step3;
		}
		else goto Fragment_Step2;
	}
	
	Fragment_Step5:
	if(c==r && CountEdge(t[k])>0){
		k++;
		t[k]=EmptyGraph(g.ord);
		f[k]=EmptyGraph(g.ord);
		l.mem[c]=j;
		goto Fragment_Step3;
	}
	
	Fragment_Step6:
	if(ListMemberQ(c,vh)){
		c=pr[k].mem[c];
		goto Fragment_Step4;
	}
	
	Fragment_Step7:
	for(i=0;i<g.ord;i++) if(i!=c && sc.adj[c][i]>0) break;
	if(i<g.ord){
		sc=RemoveEdge(sc,c,i);
		f[k]=AddEdge(f[k],c,i);
		if(l.mem[i]<l.mem[r]){
			pr[k].mem[i]=c;
			l.mem[i]=j;
			t[k]=AddEdge(t[k],c,i);
			c=i;
			goto Fragment_Step3;
		}
		else goto Fragment_Step7;
	}
	c=pr[k].mem[c];
	goto Fragment_Step3;
}

/* 頂点数 3 以上のブロック g の平面性を判定する */
/* Reference: 
   Chartrand-Oellermann,
   Applied and Algorithmic Graph Theory, Alg.9.2 */
int BlockPlanarQ(Graph g)
{
	int q=CountEdge(g);	// g の辺数
	int qq;			// 描画済みの辺数
	List cl;
	List fv,hv,cmn;
	List p;
	Graph h;
	Graph sc;		// 辺の scan 済み判定用グラフ
	Graph f[MAXFRAGMENTS];	// planarq
	List r[MAXFRAGMENTS];	// regions
	int i;			// region の個数
	int m;			// planarq の個数
	int j,k,j0,w,jj,kk;
	int u,v,iu,iv;
	int z;

	BlockPlanarQ_Step1:
	if(g.ord<5) return 1;		// 頂点数 < 5 なら平面的
	if(q>(3*g.ord-6)) return 0;	// 辺数 > 3*頂点数-6 なら非平面的

	BlockPlanarQ_Step2:
	cl=FindCycle(g);		// 閉路をひとつみつける
	h=ListtoCycle(g.ord,cl);	// 平面に描けている部分グラフ
	r[0]=cl;			// 閉路によって平面を２つの領域に分ける
	r[1]=ListReverse(cl);		// 領域は境界（時計回り）で表現
	i=2;				// 現在の領域の個数
	sc=RemoveEdges(g,h);		// 平面に描けた辺を除去
	qq=cl.len-1;			// 平面に描けた辺の本数
	
	BlockPlanarQ_Step3:
	if(DRAW){
		printf("Current picture :\n");
		WriteGraph(h);
		printf("\n");
		printf("Regions :\n");
		for(j=0;j<i;j++){ 
			printf("R[%d] : ",j);
			WriteList(r[j]);
		}
		printf("\n");
	}
	if(q==qq) return 1;		// 全ての辺が平面に描けていれば終了

	BlockPlanarQ_Step4:
	hv=PosDegVertices(h);		// 平面に描けた辺の接続点
	m=FragmentDecompose(g,h,hv,f);	// fragment の計算
	
	BlockPlanarQ_Step5Step6:
	kk=-1;
	for(k=m-1;k>=0;k--){
		fv=PosDegVertices(f[k]);	// fragment f[k] に属する頂点
		w=0;
		for(j=i-1;j>=0;j--)
			if(ListIncludedQ(ListCommon(fv,hv),r[j])){
				w++;
				j0=j;
			}
		// fv と hv の共通部分を全て含む領域がなければ非平面的
		if(w==0) return 0;
		// あれば fragment f[kk] と領域 r[jj] を登録
		if(w==1){
			kk=k;
			jj=j0;
		}
	}
		
	BlockPlanarQ_Step7:	
	if(kk==-1){
		kk=0;
		jj=j0;
	}
	
	BlockPlanarQ_Step8:	
	fv=PosDegVertices(f[kk]);
	cmn=ListCommon(fv,hv);
	u=cmn.mem[0];
	v=cmn.mem[1];
	iu=ListPosition(u,r[jj]);
	iv=ListPosition(v,r[jj]);
	/* These lines must be placed below. ( 2008.6.17 )
	if(iu>iv){
		w=u;  u=v;   v=w;
		w=iu; iu=iv; iv=w;
	}
	*/
	p=FindPath(f[kk],u,v);	// fragment f[kk] の中で u から v への道を探索
	z=1;
	while(!ListMemberQ(p.mem[z],cmn)) z++;
	p=SubList(p,0,z);	// 途中で境界に達していたらそこまでで道を cut し
	v=p.mem[z];			// v と
	iv=ListPosition(v,r[jj]);	// iv を修正（2007.6.13 debugged）
	if(iu>iv){
		w=u;  u=v;   v=w;
		w=iu; iu=iv; iv=w;
		p=ListReverse(p);	// 修正 (2008.6.18)
	}
	if(DRAW){
		printf("Extending path in R[%d] :\n",jj);
		WriteList(p);
		printf("\n");
	}
	r[i]=ListAdd(SubList(r[jj],iu,iv-1),ListReverse(p));
	r[jj]=ListReplace(r[jj],p,iu,iv);
	i++;
	qq+=(p.len-1);
	for(j=0;j<p.len-1;j++){
		sc=RemoveEdge(sc,p.mem[j],p.mem[j+1]);
		h=AddEdge(h,p.mem[j],p.mem[j+1]);
	}
	goto BlockPlanarQ_Step3;
}

/* 単純無向グラフ g の平面性を判定する */
int PlanarQ(Graph g)
{
	Graph b;	// ブロック表示用グラフ
	List o;		// ブロックの頂点数のリスト
	List s;		// ブロックの頂点数インデックスのリスト
	List v;		// ブロックの頂点のリスト
	List sl;
	int i,j,n,t,k;

	k=BlockDecompose(g,&o,&s,&v);
	for(i=0;i<k;i++){
		t=o.mem[i];
		n=s.mem[i];
		sl=SubList(v,n,n+t-1);
		b=InducedSubGraph(g,sl);
		if(b.ord>2){
			if(DRAW){
				printf("%d-th block with vertices  ",i);
				WriteList(sl);
				printf("\n"); 
				WriteGraph(b);
				printf("\n");
			}
			if(!BlockPlanarQ(b)) return 0;
		}
	}
	return  1;
}