// This code is written by Albert Chung
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include "String.h"
#include "hyper.h"
#include "reduction.h"
#include "hypertree.h"

void init(char *filename,Graph *L, Graph *S, Data **PathSet, Data **Label,char **vfilename, char **cvector) {
	FILE *fp;
	char *title;
	int edge_num,path_num,i;
	
	title = new char[10];
	fp = fopen(filename,"r");
	*PathSet = newData();
	*Label = newData();
	L->Edge = newData();
	L->Path = newData();
	S->Edge = newData();
	S->Path = newData();
	
	if(fp==NULL) {
		printf("File not exit\n");
		exit(1);
	}
	
	fscanf(fp,"%s",title);
	if(strcmp(title,"Paths:")!=0) {
		printf("File format is not correct. Maybe open the wrong file\n");
		exit(1);
	}
	
	while(strcmp(title,"Graph1:")!=0) {
		title = new char[10];
		fscanf(fp,"%s",title);
		
		if(strcmp(title,"Graph1:")!=0) {			
			*PathSet = appendData(*PathSet,title);	
		}
	}
	
	// scan graph1
	fscanf(fp,"%d",&edge_num);
	fscanf(fp,"%d",&path_num);
	
	for(i=0;i<edge_num;i++) {
		title = new char[10];
		fscanf(fp,"%s",title);
		L->Edge = appendData(L->Edge,title);
	}
	for(i=0;i<path_num;i++) {
		title = new char[10];
		fscanf(fp,"%s",title);
		L->Path = appendData(L->Path,title);
	}
	title = new char[edge_num*path_num];
	fscanf(fp,"%s",title);
	L->content = title;
	L->numEdge = edge_num;
	L->numPath = path_num;
	
	// scan for graph 2
	title = new char[10];
	fscanf(fp,"%s",title);
	
	fscanf(fp,"%d",&edge_num);
	fscanf(fp,"%d",&path_num);
	for(i=0;i<edge_num;i++) {
		title = new char[10];
		fscanf(fp,"%s",title);
		S->Edge = appendData(S->Edge,title);
	}
	for(i=0;i<path_num;i++) {
		title = new char[10];
		fscanf(fp,"%s",title);
		S->Path = appendData(S->Path,title);
	}
	title = new char[edge_num*path_num];
	fscanf(fp,"%s",title);
	S->content = title;
	S->numEdge = edge_num;
	S->numPath = path_num;
	
	// scan for vector
	title = new char[10];
	*vfilename = new char[50];
	*cvector = new char[S->numEdge];
	fscanf(fp,"%s",title);
	fscanf(fp,"%s%s",*vfilename,*cvector);
	
	// scan for labels
	title = new char[10];
	fscanf(fp,"%s",title);
	
	title = new char[10];
	while(fscanf(fp,"%s",title)!=EOF) {
		*Label = appendData(*Label,title);
		title = new char[10];	
	}

	fclose(fp);
}

bool check_incident(Graph L) { // check if p has more than two incident edges
	int i,j,row_count,column_count;
	row_count = column_count = 0;

	for(i=0;i<L.numPath;i++) {
		int amount = 0;
		for(j=0;j<L.numEdge;j++) {
			if(L.content[i*L.numEdge+j]=='1') 
				amount++;				
		}
		if(amount>2) 
			return true;
	}
	return false;
}

tree Ti;
node *cTi;
int edge_no = 1;

void create_star(Graph L,char *preroot) {
	//show_graph_data(L);
	int i;
	tree star;
	char *center;
	//star.edge = newData();
	star.node = newData();
	star.edge = copyData(L.Edge);

	center = generate_node("n",edge_no);
	edge_no++;

	int len = DataLength(star.edge);
	for(i=0;i<len;i++) {
		star.node = appendData(star.node,generate_node("n",edge_no));
		edge_no++;
		star.node = appendData(star.node,center);
	}
	
	Ti = star;
}

// find a list of Pe correspond to e
Data *findPe(Graph L, char *e) {
	Data *Pe = newData();

	int i;
	int ie = search_pos(L.Edge,e);
	char *temp;

	for(i=0;i<L.numPath;i++) {
		if(L.content[i*L.numEdge+ie] == '1') {
			temp = search_string(L.Path,i);
			Pe = appendData(Pe,temp);
		}
	}
	return Pe;
}

Graph setL(Graph L, Data *E, Data *P)
{
	Graph subL;
	int i,j,m,n;
	int k = 0;

	int lenP = DataLength(P);
	int lenE = DataLength(E);
	Data *headE = E;

	//temp = new char[lenP*lenE];
	subL.Edge = copyData(E);
	subL.Path = copyData(P);
	subL.numEdge = lenE;
	subL.numPath = lenP;
	subL.content = new char[lenE*lenP+1];

	for(i=0;i<subL.numPath;i++) {
		for(j=0;j<subL.numEdge;j++) {
			//show_Data(L.Path);
			m = search_pos(L.Path,P->value);
			//printf("%d\n",m);
			n = search_pos(L.Edge,E->value);
			//printf("%d\n",n);
			subL.content[k] = L.content[m*L.numEdge+n];
			//printf("%d %d %s ",m,n,P->value);
			//printf("%s %c\n",E->value,temp[k]);
			k++;
			E = E->next;
		}
		P = P->next;
		E = headE;
	}
	subL.content[k] = '\0';
	
	return subL;
}

Data *findSe(Graph L)
{
	int i,j;
	Data *Se = newData();

	if(L.numPath==0) {
		delete Se;
		Se = copyData(L.Edge);
		return Se;
	}
	for(i=0;i<L.numEdge;i++)  {
		for(j=0;j<L.numPath;j++)  {
			//printf("%c ",L.content[j*strlen(L.Edge)+i]);
			if(L.content[j*L.numEdge+i]=='1')
				break;
			if(j==(L.numPath-1))   // search to the end of the array
				Se = appendData(Se,L.Edge->value);
		}
		L.Edge = L.Edge->next;
	}	
	return Se;
}

Data *Path;
char *Previous;

Graph depth_first_search(Graph L,int x,int y,CComponent *CC,Data *record,char *parent)
{
	int i;
	int *edge,*path;
	int index = 0;

	edge = new int[L.numEdge+L.numPath];
	path = new int[L.numEdge+L.numPath];

	L.content[y*L.numEdge+x] = '0';

	for(i=0;i<L.numEdge;i++) {
		if(L.content[y*L.numEdge+i]=='1') { // x-axis
			
			edge[index] = i;
			path[index] = y;
			index++;
			
			char *item = search_string(L.Edge,i);
		
			if(search_pos(record,item)==-1) {
				CC->G.numEdge++;
				CC->G.Edge = appendData(CC->G.Edge,item);
				record = appendData(record,item);		
				Path = appendData(Path,parent);			
				Path = appendData(Path,item);
			}
			
		}
	}

	for(i=0;i<L.numPath;i++) {
		if(L.content[i*L.numEdge+x]=='1') { // y-axis
			edge[index] = x;
			path[index] = i;
			index++;	

			char *item = search_string(L.Path,i);
			
			if(search_pos(record,item)==-1) {
				CC->G.numPath++;
				CC->G.Path = appendData(CC->G.Path,item);
				record = appendData(record,item);
			}
		}
	}

	char *pp;

	for(i=0;i<index;i++) {
		pp = search_string(L.Edge,edge[i]);
		L = depth_first_search(L,edge[i],path[i],CC,record,pp);
	}

	delete [] edge;
	delete [] path;
	return L;
}

void show_CComponent(CComponent *head)
{
	CComponent *temp;	
    temp = head;
	while(temp->G.numEdge>0) {
	  //printf("%s %s\n",temp->G.Edge,temp->G.Path);
	  show_Data(temp->G.Edge);
	  show_Data(temp->G.Path);
      temp = temp->next ;
   }

}

CComponent *findCComponent(Graph L, CComponent *head, Data *Se)
{
	int i,j;
	int num_CC = 0;
	char *evalue,*pvalue;
	Path = newData();
	
	for(i=0;i<L.numPath;i++) {
		for(j=0;j<L.numEdge;j++) {
			if(L.content[i*L.numEdge+j]=='1') {
				// create a new ccomponent
				CComponent *temp;
				Data *hEdge,*hPath,*record;
				temp = new CComponent();
				Graph tempG;
				tempG.numEdge = tempG.numPath = 1;
				
				hEdge = newData();
				hPath = newData();
				record = newData();
				
				evalue = search_string(L.Edge,j);
				pvalue = search_string(L.Path,i);

				hEdge = appendData(hEdge,evalue);
				hPath = appendData(hPath,pvalue);
				
				tempG.Edge = hEdge;
				tempG.Path = hPath;

				temp->next = head;
				temp->G = tempG;
				head = temp;
				num_CC++;

				record = appendData(record,evalue);
				record = appendData(record,pvalue);
				
				L = depth_first_search(L,j,i,head,record,evalue);
				
				delete_data(record);
			}
		}
	}
		
	head->number = num_CC;
	return head;
}

Data *findCoEi(Graph L, Data *eip)
{
 int i,j,k,index;
 Data *CoEip = newData();
 char *content = new char[L.numEdge*L.numPath+1];

 for(i=0;i<L.numEdge*L.numPath;i++)
	 content[i] = L.content[i];

 int leneip = DataLength(eip);
 for(i=0;i<leneip;i++) {
	 for(j=0;j<L.numPath;j++) {
		 char *eipi = search_string(eip,i);
		 index = search_pos(L.Edge, eipi);
		 if(content[j*L.numEdge+index]=='1') {
			 char *pathj = search_string(L.Path,j);
			 CoEip = appendData(CoEip,pathj);
			 for(k=0;k<L.numEdge;k++)
				 content[j*L.numEdge+k] = '0';
				 // avoid duplication
		 }
	 }
 }
 delete [] content;
 return CoEip;
}

Data *pA,*pB;

bool test_bipartite(Graph L)
{
	int i,j;
	pA = newData();
	pB = newData();

	if(L.numPath == 0) {
		for(i=0;i<L.numEdge;i++) {
			pA = appendData(pA,L.Edge->value);
			L.Edge  =L.Edge->next;
		}
		return true;
	}

    CComponent *head = new CComponent();
	Path = newData();  // record the path of depth first search
	Data *tPath = Path;

	int num_CC = 0;
	char *evalue,*pvalue;
	char *temp = new char[L.numEdge*L.numPath];

	for(i=0;i<L.numEdge*L.numPath;i++)
		temp[i] = L.content[i];

	for(i=0;i<L.numPath;i++) {
		for(j=0;j<L.numEdge;j++) {
			if(L.content[i*L.numEdge+j]=='1') {
				// create a new ccomponent
				CComponent *temp;
				Data *hEdge,*hPath,*record;
				temp = new CComponent();
				Graph tempG;
				tempG.numEdge = tempG.numPath = 1;
				hEdge = newData();
				hPath = newData();
				record = newData();
				
				//tempG.Edge = stringcat(tempG.Edge,L.Edge[j]);
				evalue = search_string(L.Edge,j);
				pvalue = search_string(L.Path,i);
				
				hEdge = appendData(hEdge,evalue);
				hPath = appendData(hPath,pvalue);

				tempG.Edge = hEdge;
				tempG.Path = hPath;

				temp->next = head;
				temp->G = tempG;
				head = temp;
				
				Previous = temp->G.Edge->value;
				num_CC++;

				record = appendData(record,evalue);
				record = appendData(record,pvalue);

				L = depth_first_search(L,j,i,head,record,evalue);
				Path = appendData(Path,Previous);
				Path = appendData(Path,"end");
			}
		}
	}

	int len;
	int pos1,pos2;

	for(i=0;i<L.numEdge*L.numPath;i++)
		L.content[i] = temp[i];

	for(i=0;i<num_CC;i++) {	
		len = DataLength(head->G.Edge);
		
		Data *hhp = Path;
		int slen = 0;
		while(strcmp(hhp->value,"end")!=0) {
			slen++;
			hhp = hhp->next;
		}
		len = (slen+1)/2;
		
		pA = appendData(pA,Path->value);   // set first element

		for(j=0;j<len-1;j++) {
			pos1 = search_pos(pA,Path->value);
			pos2 = search_pos(pB,Path->value);
			if(pos1*pos2<=0) {   // in either pa or pb
				if(pos1!=-1) {   // in pa
					pos1  =search_pos(pB,Path->next->value);
					if(pos1==-1)
						pB = appendData(pB,Path->next->value);
					else
						return false;
				}
				else if(pos2!=-1) {   // in pb
					pos2  =search_pos(pA,Path->next->value);
					if(pos2==-1)
						pA = appendData(pA,Path->next->value);
					else
						return false;
				}
				else {
					printf("Biaprtite Error!!\n");
					return false;
				}
			}
			Path = Path->next->next;
		}
		Path = Path->next->next;
	}

	Data *remain = minusData(L.Edge,pA);
	remain = minusData(remain,pB);
	Data *hremain = remain;

	len = DataLength(remain);
	for(i=0;i<len;i++) {
		if((i%2)==0)
			pA = appendData(pA,remain->value);
		else
			pB = appendData(pB,remain->value);
		remain = remain->next;
	}

	delete_data(tPath);
	delete_data(hremain);
	
	return true;
}

Data *Old,*Stack,*CorEqClass;
DataA *EqResult;
 
int COUNT,ENUMBER;
int *DFNUMBER,*LOW;

Data *searchLV(Data *Vc, Data *Ec, char *v) {
	Data *LV = newData();

	int len = DataLength(Ec);
	int i;
	for(i=0;i<len;i++) {
		if( Ec->value==v && ((i%2)==0) ) 
			LV = appendData(LV,Ec->next->value);
		Ec = Ec->next;
	}

	return LV;
}

char *popData(int EQNUMBER) {
	char *x;
	int i;
	Data *duStack = Stack;
	DataA *pointto;
	
	int len = DataLength(Stack);
	
	x = search_string(Stack,len-1);

	for(i=0;i<len-1;i++) 
		duStack = duStack->next;
	duStack->value = "END";
	Stack->len--;
	delete duStack->next;
	
	pointto = locate_DataA(EqResult,EQNUMBER);
	pointto->row = appendData(pointto->row,x);
	
	return x;
}

int SEARCHB(Data *Vc, Data *Ec, char *v, int EQNUMBER,int ccc) {
	int i,len1,pos;
	
	Old = appendData2(Old,v);
	
	int vpos = search_pos(Vc,v);
	Data *LV,*hLV;
	char *x;

	DFNUMBER[vpos] = COUNT;
	DFNUMBER[vpos] = ccc;
	COUNT = COUNT+1;
	ccc++;
	LOW[vpos] = DFNUMBER[vpos];

	Stack = appendData(Stack,v);
	
	LV = searchLV(Vc,Ec,v);
	hLV = LV;
	len1 = DataLength(LV);
	
	for(i=0;i<len1;i++) {
		pos = search_pos(Old,LV->value);
		
		if(pos == -1) {      // w is new
			EQNUMBER = SEARCHB(Vc,Ec,LV->value,EQNUMBER,ccc);
			pos = search_pos(Vc,LV->value);
			if(LOW[vpos] >= LOW[pos]) 
				LOW[vpos] = LOW[pos];
							
		} else {
			pos = search_pos(Vc,LV->value);
			int spos = search_pos(Stack, LV->value);
			if(DFNUMBER[pos]<DFNUMBER[vpos] && spos!=-1)
				if(LOW[vpos]>DFNUMBER[pos])
					LOW[vpos]=DFNUMBER[pos];			
		}
		LV = LV->next;
	}
	
	if(LOW[vpos] == DFNUMBER[vpos]) {
		do {
			x = popData(EQNUMBER);
		} while (strcmp(x,v)!=0);
	
		EQNUMBER++;
	}
	delete_data(hLV);
	return EQNUMBER;
}

void Find_Equivalence_Class(Data *Vc,Data *Ec) {
	int i,pos;

	ENUMBER = 0;
	int EQNUMBER = 0;
	Old = newData();
	Stack = newData();

	int elen = DataLength(Ec);
	
	EqResult = newDataA();

	for(i=0;i<elen;i++) {
		//EqResult[i] = newData();
		EqResult = appendDataA(EqResult,"HEAD");
	}

	Data *hVc = Vc;

	int len = DataLength(Vc);
	DFNUMBER = new int[len];
	LOW = new int[len];
	COUNT = 1;
                     
	for(i=0;i<len;i++) {
		pos = search_pos(Old,Vc->value);
	
		if(pos==-1) {
			EQNUMBER = SEARCHB(hVc,Ec,Vc->value,EQNUMBER,1);
		}
		Vc = Vc->next;
	}

	ENUMBER = EQNUMBER;
	
	delete [] LOW;
	delete [] DFNUMBER;
	delete_data(Stack);
	delete_data(Old);
}

int *SetMTI(Data *Vc, Data *Ec) {
	int i,j,count;
	int len1 = DataLength(Vc);
	int len2 = DataLength(Ec);
	Data *hEc = Ec;
	int *mti = new int[len1];

	for(i=0;i<len1;i++) {
		count = 0;
		for(j=0;j<(len2/2);j++) {
			if(strcmp(Vc->value,Ec->value)==0)
				count++;
			 Ec = Ec->next->next;
		}
		mti[i] = count;
		Vc = Vc->next;
		Ec = hEc;
	}

	return mti;
}

Data *Replace_ECLASS(Data *Vc,Data *Ec,Data *Vbc,Data *Ebc,Data *Vpc,Data *Epc) {
	int i,k,index=0;
	DataA *pointto,*pointResult;
	
	Data *finalE = newData();
	
	int Vpclen = DataLength(Vpc);
	
	DataA *TEdge = newDataA();

	int pos,len1,len2,j;
	
	// create a path with corrosponding eq class nodes
	for(i=0;i<Vpclen;i++) {
		pos = search_pos(Vc,Vpc->value);
		pointResult = locate_DataA(EqResult,pos);
		len2 = DataLength(pointResult->row);
		Data *tempA = pointResult->row;
		
		for(j=0;j<len2-1;j++) {		
			TEdge = appendDataA(TEdge,"HEAD");
			pointto = locate_DataA(TEdge,index);
			
			pointto->row = appendData(pointto->row,tempA->value);
			pointto->row = appendData(pointto->row,tempA->next->value);
			
			finalE = appendData(finalE,tempA->value);
			finalE = appendData(finalE,tempA->next->value);
			tempA = tempA->next;
		}
		
		if(len2 == 1)  {// no corresponding eq class
			TEdge = appendDataA(TEdge,"HEAD");
			pointto = locate_DataA(TEdge,index);
			pointto->row = appendData(pointto->row,pointResult->row->value);
		}

		index++;
		
		Vpc = Vpc->next;
	}

	len1 = DataLength(Epc);
	len2 = DataLength(Ec);
	Data *hEc = Ec;
	char *tt;
	int len;

	// stick all above path 
	for(i=0;i<(len1/2);i++) {
		for(j=0;j<(len2/2);j++) {
			if(strcmp(Epc->value,Ec->value)==0 && strcmp(Epc->next->value,Ec->next->value)==0) {
				tt = search_string(CorEqClass,2*j);
				
				for(k=0;k<index;k++) {
					pointto = locate_DataA(TEdge,k);
					pos = search_pos(pointto->row,tt);
					if(pos!=-1)
						break;
				}

				len = DataLength(pointto->row);   // find the last element
				tt = search_string(pointto->row,len-1);
				
				finalE = appendData(finalE,tt);
				
				tt = search_string(CorEqClass,2*j+1);
				for(k=0;k<index;k++) {
					pointto = locate_DataA(TEdge,k);
					pos = search_pos(pointto->row,tt);
					if(pos!=-1)
						break;
				}
				
				tt = pointto->row->value;
				finalE = appendData(finalE,tt);
			}
			Ec = Ec->next->next;
		}
		Ec = hEc;
		Epc = Epc->next->next;
	}

	delete_dataA(TEdge);
	return finalE;
}

tree Replace_V_to_E(Data *Vbc,Data *E) {
	tree T;
	T.node = copyData(E);
	T.edge = newData();

	int i;
	int len = DataLength(E);
	for(i=0;i<(len/2);i++) {
		T.edge = appendData(T.edge,E->value);
		E = E->next->next;
	}
	return T;
}

tree create_bipartite_tree(Data *C, char *e, char *y, DataA *Pie, int Ke, Data *si)
{
	Data *Vbc;
	Data *Ebc = newData();
	Data *Ec = newData();
	DataA *pointto1,*pointto2,*pointResult;

	int i,j;
	Vbc = appendData2(C, e);
	int len = DataLength(C);

	Data *h1C = C;
	Data *h2C = C;
	int m,n;

	tree Tbar;

	for(i=0;i<len;i++) {                     // line 17
		for(j=0;j<len;j++) {
			if(strcmp(h1C->value,h2C->value)!=0) {   // si not equal sj
				m = search_pos(si,h1C->value);
				n = search_pos(si,h2C->value);

				pointto1 = locate_DataA(Pie,m);
				pointto2 = locate_DataA(Pie,n);
				
				Data *intersect = intersection(pointto1->row,pointto2->row);
				bool is = isEqual(pointto1->row,intersect);
				
				if(is && y[m*Ke+n]=='0') {
					Ebc = appendData(Ebc,h1C->value);
					Ebc = appendData(Ebc,h2C->value);
				}
		
				delete_data(intersect);
			}
			h1C = h1C->next;
		}
		h1C = C;
		h2C = h2C->next;
	}

	for(i=0;i<len;i++) {
		Ebc = appendData(Ebc,C->value);
		Ebc = appendData(Ebc,e);
		C = C->next;
	}

	Data *dEbc = Ebc;

	Find_Equivalence_Class(Vbc,Ebc);

	Data *cEbc = Ebc;
	Data *Vc = newData();

	for(i=0;i<ENUMBER;i++) {
		char *temp = "t";    
		char tp = (char)(i+49);
		temp = stringcat(temp,tp);
		Vc = appendData(Vc,temp);
	}

	// find new e
	for(i=0;i<ENUMBER;i++) {
		pointResult = locate_DataA(EqResult,i);
		int pp = search_pos(pointResult->row,e);
		if(pp!=-1)
			break;
	}
	char *te = search_string(Vc,i);

	// shrink E bar c into Ec
	len = DataLength(Ebc);
	int pos1,pos2;

	CorEqClass = newData();

	for(i=0;i<(len/2);i++) {
		
		for(j=0;j<ENUMBER;j++) {
			pointResult = locate_DataA(EqResult,j);
			
			if(search_pos(pointResult->row,Ebc->value)!=-1)
				pos1 = j;
			if(search_pos(pointResult->row,Ebc->next->value)!=-1)
				pos2 = j;
		}
		
		if(pos1!=pos2) {   // ebc and ebc next not in the same eq class
			char *temp = "t",*temp1,*temp2;    
			char tp = (char)(pos1+49);
			temp1 = stringcat(temp,tp);

			tp = (char)(pos2+49);
			temp2 = stringcat(temp,tp);

			if(NoDuplicateData(Ec,temp1,temp2)) {
				Ec = appendData(Ec,temp1);
				Ec = appendData(Ec,temp2);
				CorEqClass = appendData(CorEqClass,Ebc->value);
				CorEqClass = appendData(CorEqClass,Ebc->next->value);
			}
		}
		Ebc = Ebc->next->next;
	}

	////////////////////////
	//printf("Equivalence class\n");
	//show_Data(Vc);
	//show_Data(Ec);

	Data *Vpc = newData();     // setup v prime c
	Vpc = appendData(Vpc,te);

	int len1 = DataLength(Vc);
	int tlen,pos;

	DataA *fti = newDataA();
	DataA *pointto;
	
	for(i=0;i<len1;i++) {
		fti = appendDataA(fti,"HEAD");
	}

	int *mti = SetMTI(Vc,Ec);

	for(i=0;i<len1;i++) {
		mti[i]--;	
		pointto = locate_DataA(fti,i);
		pointto->row = appendData(pointto->row,te);
		//pointto->row->value = te;			
	}

	Data *Epc = newData();
	
	while(1) {
		Data *temp = minusData(Vc,Vpc);
		Data *htemp = temp;
		tlen = DataLength(temp);
		//show_Data(temp);
		if(tlen==0)
			break;

		for(i=0;i<tlen;i++) {
			pos = search_pos(Vc,htemp->value);
		
			if(mti[pos]==0) {

				Epc = appendData(Epc,htemp->value);								
				pointto = locate_DataA(fti,pos);
				Epc = appendData(Epc,pointto->row->value);
				Vpc = appendData(Vpc,htemp->value);
	
				for(j=0;j<tlen;j++) {
					if(i!=j) {
						char *string = search_string(temp,j);
						
						bool check = check_pair(Ec,string,htemp->value);
						
						if(check) {
							pos = search_pos(Vc,string);
							pointto = locate_DataA(fti,pos);
							
							mti[pos]--;						
							pointto->row->value = htemp->value;
						}						 
					}
				}  // end for
				break;
			}  // end if
			//printf("%d\n",i);
			htemp = htemp->next;
		}  // end for
		delete_data(temp);
	}

	delete_dataA(fti);
	Data *tempE;
	
	tempE = Replace_ECLASS(Vc,Ec,Vbc,cEbc,Vpc,Epc);
	
	delete_data(CorEqClass);

	Tbar = Replace_V_to_E(Vbc,tempE);
	
	delete_data(Vc);
	delete_data(Ec);
	delete_data(Vpc);
	delete_data(Epc);
	delete_data(Vbc);
	delete_data(dEbc);
	delete_data(tempE);
	
	return Tbar;
}

tree Merge_A_and_B(tree TbarA,tree TbarB,char *e) {
	int len,i;
	char *newe1 = stringcat(e,'p');
	char *newe2 = stringcat(e,'q');
	
	Data *hAnode = TbarA.node;

	len = DataLength(TbarA.node);
	for(i=0;i<len;i++) {
		if(strcmp(hAnode->value,e)==0) 
			hAnode->value = newe1;
		hAnode = hAnode->next;
	}

	len = DataLength(TbarB.edge);
	for(i=0;i<len;i++) {	
		TbarA.edge = appendData(TbarA.edge,TbarB.edge->value);
		TbarB.edge = TbarB.edge->next;
	}

	len = DataLength(TbarB.node);
	for(i=0;i<len;i++) {
		if(strcmp(TbarB.node->value,e)==0)
			TbarA.node = appendData(TbarA.node,newe2);
		else
			TbarA.node = appendData(TbarA.node,TbarB.node->value);
		TbarB.node = TbarB.node->next;
	}

	TbarA.edge = appendData(TbarA.edge,e);
	TbarA.node = appendData(TbarA.node,newe1);
	TbarA.node = appendData(TbarA.node,newe2);

	return TbarA;
}

void reverse_nodes(tree tip, char *root, Data *old) {
	int i;
	int len = DataLength(tip.node);
	Data *hnode = tip.node;
	char *temp,*value;
	
	for(i=0;i<len;i++) {
		if(strcmp(hnode->value,root)==0) {
			value = search_string(tip.edge,i/2);
			if(i%2==0 && search_pos(old,value)==-1) {
				old = appendData(old,value);
				temp = hnode->value;
				hnode->value = hnode->next->value;
				hnode->next->value = temp;
				reverse_nodes(tip,hnode->value,old);	
			}
		}
		hnode = hnode->next;	
	}	
}

tree create_Tip_tree(tree Ti, char *e) {	
	tree tip;

	Data *tempNode = newData();
	char *node1,*node2;
	int i,pos,len = DataLength(Ti.edge);

	pos = search_pos(Ti.edge,e);

	Ti.edge = truncateData2(Ti.edge,e);
	tip.edge = copyData(Ti.edge);

	node1 = search_string(Ti.node,2*pos);
	node2 = search_string(Ti.node,2*pos+1);

	len = DataLength(Ti.node);
	
	for(i=0;i<(len/2);i++) {
		int c1 = strcmp(Ti.node->value,node1);
		int c2 = strcmp(Ti.node->next->value,node2);	
		if(c1!=0 || c2!=0) {
			 tempNode = appendData(tempNode,Ti.node->value);
			 tempNode = appendData(tempNode,Ti.node->next->value);			
		}
		Ti.node = Ti.node->next->next;
	}

	tip.node = tempNode;

	len = DataLength(tempNode);
	for(i=0;i<len;i++) {
		if(strcmp(tempNode->value,node1)==0 || strcmp(tempNode->value,node2)==0)
			tempNode->value = "dd";
		tempNode = tempNode->next;
	}
	delete_tree(Ti);
	
	Data *old = newData();
	reverse_nodes(tip,"dd",old);
	
	return tip;
}

char *find_uj(tree tip,char *root,Data *E,int length) {
	int len = DataLength(tip.node);
	int i;
	Data *hnode = tip.node;
	Data *previous;
	char *value,*value2;
	
	for(i=0;i<len;i++) {
		if(strcmp(hnode->value,root)==0) {
			value = search_string(tip.edge,i/2);
			if(search_pos(E,value)!=-1) {
				E = truncateData2(E,value);
				if(i%2==0) {
					char *temp = hnode->next->value;
					hnode->next->value = "cc";
					hnode->value = "cc";
					value2 = find_uj(tip,temp,E,length);
					if(strcmp(value2," ")!=0)
						return value2;
					else
						return temp;
				}
					//printf("vv: %s %s %s\n",value,hnode->value,hnode->next->value);
				else {
					char *temp = previous->value;
					previous->value = "cc";
					hnode->value = "cc";
					value2 = find_uj(tip,temp,E,length);
					if(strcmp(value2," ")!=0)
						return value2;
					else
						return temp;
				}
					
					//printf("vv: %s %s %s\n",value,previous,hnode->value);
			} 
		}
		previous = hnode;
		hnode = hnode->next;
	}	
	return " ";
}

char *stick_si(Graph L,Data *pie,tree tip) {
	int pos;
	int i,j;
	int len = DataLength(pie);
	char *value;
	
	for(j=0;j<len;j++) {
		pos = search_pos(L.Path,pie->value);
		Data *CoE = newData();
		
		tree ctip;
		ctip.edge = copyData(tip.edge);
		ctip.node = copyData(tip.node);
	
		for(i=0;i<L.numEdge;i++) {
			if(L.content[pos*L.numEdge+i]=='1') { 
				value = search_string(L.Edge,i);
				CoE = appendData(CoE,value);				
			}
		}
	
		value = find_uj(ctip,"dd",CoE,CoE->len);
		delete_data(ctip.edge);
		delete_data(ctip.node);
		
		if(strcmp(value," ")!=0)
			break;
		pie = pie->next;
	}
	return value;
}

char ETH(Data *UH,tree T,Graph L,Data **root,char *preroot)
{
	bool B = false;
	int num_UH,k,Ke;
	char *e,temp;
	Data *Pe,*E,*P,*Se,*dSe,*Ei,*CoEip,*coEi,*Pi,*UHie;
	DataA *Pie = newDataA();
	DataA *pointto;
	Graph subL;
	GraphList *Li = newGraph();
	
	CComponent *head;
	int i,j;
	tree Tbar;
	treeList *Tip = newTree();
	Data *tempP;
	
	while(!B) {
		num_UH = DataLength(UH);
		if(num_UH==0) {   // UH is empty set
			if(check_incident(L)) {
				//printf("Some edge has more than two incident edges\n");
				return '0';
			} else {
				create_star(L,preroot);
				return '1';
			}
		} else {
			e = UH->value;		
			*root = appendData(*root,e);	
			
			Pe = findPe(L,e);
			
			UH = truncateData2(UH,e);
			Data *tempE = copyData(L.Edge);
                        E = truncateData(tempE,e);    // E-e

			tempP = copyData(L.Path);
			P = truncateDatas(tempP,Pe);   // P-Pe
			delete_data(tempE);
			delete_data(tempP);

			subL = setL(L,E,P);
			Se = findSe(subL);
			dSe = Se;

			head = new CComponent();
			head->number = -1;
			head = findCComponent(subL,head,Se);
			CComponent *hhead = head;
				
			delete_graph(subL);
			delete_data(E);
			delete_data(P);
			
			k = head->number;
			Ke = k + DataLength(Se);
		
			if(Ke>1) {
				B = true;
				char *resultSet="";
				Data *si = newData();

				for(i=0;i<k;i++) {
						Ei = appendData2(head->G.Edge,e);
						CoEip = findCoEi(L,head->G.Edge);
						
						Pie = appendDataA(Pie,"HEAD");
						pointto = locate_DataA(Pie,i);
						pointto->row = intersection(Pe,CoEip);

						coEi = findCoEi(L,Ei);
						
						Data *icoEi = intersection(pointto->row,coEi);
						
						Pi = unions(head->G.Path,icoEi);
						UHie = intersection(UH,head->G.Edge);				
						
						Graph G = setL(L,Ei,Pi);
						Li = appendGraph(Li,G);
						
						temp = ETH(UHie,T,G,root,e);
						
						if(temp!='0') {
							tree tip;
							tip = create_Tip_tree(Ti,e);
							Tip = appendTree(Tip,tip);
						} else
							return '0';

						resultSet = stringcat(resultSet,temp);
						head = head->next;

						char *tpstring = "s";    // set S1...Sk
						char tpk = (char)(i+49);
						tpstring = stringcat(tpstring,tpk);
						si = appendData(si,tpstring);

						delete_data(Ei);
						delete_data(coEi);
						delete_data(icoEi);
						delete_data(CoEip);
						delete_data(Pi);
				}
							
								
				for(i=k;i<Ke;i++) {  // Put Se into connected component
					Data *tempSe = newData();  // construct temp Se
					tempSe = appendData(tempSe,Se->value);
					
					si = appendData(si,Se->value);  // set sk...ske
					Ei = appendData2(tempSe,e);
					CoEip = findCoEi(L,tempSe);
					//Pie[i] = intersection(Pe,CoEip);

					Pie = appendDataA(Pie,"HEAD");
					pointto = locate_DataA(Pie,i);
					pointto->row = intersection(Pe,CoEip);
                                                              
					coEi = findCoEi(L,Ei);				
					Data *icoEi = intersection(pointto->row,coEi);
					Pi = unions(tempSe,icoEi);
					Graph G = setL(L,Ei,Pi);
					Li = appendGraph(Li,G);
					
					Se = Se->next;
				
					delete_data(Ei);
					delete_data(coEi);
					delete_data(icoEi);
					delete_data(CoEip);
					delete_data(Pi);
					delete_data(tempSe);
				}
			
				delete_data(Pe); 
				delete_data(UH);		
				delete_data(Se);
				
				if(searchc(resultSet,'0')!=-1) {
						printf("Some CComponent has no graph, exit e= %s\n",e);
						return '0';
				}

				
				DataA *X = newDataA();

				for(i=0;i<Ke;i++) {
					X = appendDataA(X,"HEAD");
				}

				for(i=0;i<L.numEdge;i++) {
						Data *plus = newData();

						for(j=0;j<L.numPath;j++) {  //line 11
							char *lpathj = search_string(L.Path,j);
							if(L.content[j*L.numEdge+i]=='1')
								plus = appendData(plus,lpathj);
						}
						
						for(j=0;j<Ke;j++) {   // line 12
							
							pointto = locate_DataA(Pie,j);
							Data *tempis = intersection(pointto->row,plus);
							
							int l1 = DataLength(pointto->row);
							int l3 = DataLength(tempis);

							delete_data(tempis);
							if(l3>0 && l3!=l1) {	
							
									char *ledgei = search_string(L.Edge,i);
								
									pointto = locate_DataA(X,j);
									pointto->row = appendData(pointto->row,ledgei);
							}
						}
						delete_data(plus);
				}  // end for
			
			
				char *y;
				y = new char[Ke*Ke+1];
				y[Ke*Ke]='\0';

				GraphList *gl;
				
				for(i=0;i<Ke;i++) {
					for(j=0;j<Ke;j++) {
						Data *xeo;
						pointto = locate_DataA(X,i);
						gl = locate_Graph(Li,j);
						xeo = intersection(pointto->row,gl->gg.Edge);
											
						int lenxeo = DataLength(xeo);
					
						if(lenxeo>0)
							y[i*Ke+j]='1';
						else
							y[i*Ke+j]='0';
					
						delete_data(xeo);
					}
				}

				delete_dataA(X);
		
				Data *pG = newData();
	
				bool is;
				Graph G;
				int path_index = 0; // record which path now

				G.Edge = si;
				G.numEdge = DataLength(si);
				G.content = new char[G.numEdge*Ke*(Ke-1)];

				for(i=0;i<G.numEdge*Ke*(Ke-1);i++)
					G.content[i] = '0';
			
				// branch conditions
				for(i=0;i<Ke;i++)
					for(j=0;j<Ke;j++) {
						if(i!=j) {
							
							Data *temp1,*temp4,*temp5;
							int len1,len4,len5;
							
							// branch 1

							DataA *pointto1 = locate_DataA(Pie,i);
							DataA *pointto2 = locate_DataA(Pie,j);
							
							temp1 = intersection(pointto1->row,pointto2->row);
							len1 = DataLength(temp1);

							temp4 = minusData(pointto1->row,pointto2->row);
							len4 = DataLength(temp4);
							temp5 = minusData(pointto2->row,pointto1->row);
							len5 = DataLength(temp5);
							
							if(len1>0 && len4>0 && len5>0) {
								
									char *tpstring = "p";    
									char tpk = (char)(path_index+49);
									tpstring = stringcat(tpstring,tpk);
									pG = appendData(pG,tpstring);
									G.content[path_index*G.numEdge+i] = '1';
									G.content[path_index*G.numEdge+j] = '1';
								
									path_index++;
								
								continue;
							}
							

							// branch 2
							is = isEqual(temp1,pointto1->row);
							int ll = DataLength(pointto2->row);

							if(len1>0 && is && ll!=len1 && y[i*Ke+j]=='1') {
								
									char *tpstring = "p";    
									char tpk = (char)(path_index+49);
									tpstring = stringcat(tpstring,tpk);
									pG = appendData(pG,tpstring);

									G.content[path_index*G.numEdge+i] = '1';
									G.content[path_index*G.numEdge+j] = '1';
									path_index++;
								
								continue;
							}

							// branch 3
							
							is = isEqual(pointto1->row,pointto2->row);
							
							if(is && y[i*Ke+j]=='1' && y[j*Ke+i]=='1') {
								
									char *tpstring = "p";    
									char tpk = (char)(path_index+49);
									tpstring = stringcat(tpstring,tpk);
									pG = appendData(pG,tpstring);

									G.content[path_index*G.numEdge+i] = '1';
									G.content[path_index*G.numEdge+j] = '1';
									path_index++;
								
								continue;
							}

							delete_data(temp1);
							delete_data(temp4);
							delete_data(temp5);
						}					
					}  // end for

					// construct graph G
					G.Path = pG;
					G.numPath = DataLength(pG);

					for(i=0;i<G.numEdge*G.numPath;i++) {
						if(G.content[i]!='1')
							G.content[i] = '0';
					}

					G.content[G.numEdge*G.numPath] = '\0';

					if(!test_bipartite(G)) {  // test if G is bipartite
						printf("Not Bipartite!, exit e= %s\n",e);
						return '0';
					} 

					tree TbarA,TbarB;

					if(DataLength(pA)!=0)
						TbarA = create_bipartite_tree(pA,e,y,Pie,Ke,si);
					else {
						TbarA.edge = newData();
						TbarA.node = newData();
					}
					
					if(DataLength(pB)!=0)
						TbarB = create_bipartite_tree(pB,e,y,Pie,Ke,si);
					else {
						TbarB.edge = newData();
						TbarB.node = newData();
					}

					delete_data(pA);
					delete_data(pB);
					
					Tbar = Merge_A_and_B(TbarA,TbarB,e);

					if(k==0) {   // did not call eth, so no tip tree
						Ti = Tbar;
						return '1';
					}						

					char *eti,*sip,*sipp,*previous,*esi;
					int pos,len,m,later;
					treeList *pointTree;
					DataA *pie;
					
					for(i=0;i<k;i++) {   // replace si
						eti = generate_node("s",i+1);
						later = 0;

						pointTree = locate_Tree(Tip,i);
						
						
						pos = search_pos(Tbar.edge,eti);
						sip = search_string(Tbar.node,2*pos);
						sipp = search_string(Tbar.node,2*pos+1);
						
						// stick si to sj
						Data *hbar_node = Tbar.node;
						len = DataLength(hbar_node);
						char *rv;
						
						for(j=0;j<len;j++) {
							if(strcmp(hbar_node->value,sip)==0) {  // find si
								esi = search_string(Tbar.edge,j/2);
								if(strcmp(esi,eti)!=0) {   // not himself
									pos = search_pos(si,esi);
									pie = locate_DataA(Pie,pos);
									
									if(DataLength(pie->row)==0) {
										//stick any node
										rv = pointTree->tt.node->value;
									} else {
									
										rv = stick_si(L,pie->row,pointTree->tt);
									}
									
									Data *nodes = Tbar.node;
									
									pos = search_pos(Tbar.edge,esi);
									for(m=0;m<pos;m++)
										nodes = nodes->next->next;
									if(strcmp(nodes->value,sip)==0)
										nodes->value = rv;
									else
										nodes->next->value = rv;
									
								}	
							}
							previous = hbar_node->value;
							hbar_node = hbar_node->next;
						}
						
						// stick vi on si''
						Data *htree_node = pointTree->tt.node;
						while(strcmp(htree_node->value,"END")!=0) {
							if(strcmp(htree_node->value,"dd")==0)
								htree_node->value = sipp;
							htree_node = htree_node->next;							
						}
						///end
						
						Data *htree_edge = pointTree->tt.edge;
						htree_node = pointTree->tt.node;
						
						// copy edge and node of Tip to Tbar
						Tbar.edge = truncateData2(Tbar.edge,eti);
						Tbar.node = truncatePair(Tbar.node,sip,sipp);
						
						while(strcmp(htree_edge->value,"END")!=0) {
							Tbar.edge = appendData(Tbar.edge,htree_edge->value);
							Tbar.node = appendData(Tbar.node,htree_node->value);
							Tbar.node = appendData(Tbar.node,htree_node->next->value);
							htree_edge = htree_edge->next;
							htree_node = htree_node->next->next;	
						}
					}

					delete_graph(G);

					delete_dataA(Pie);
					delete_GraphList(Li);
					delete_treeList(Tip);

					Ti = Tbar;
					return '1';
			}  //if ke>1
			delete_ccomponent(hhead);
		} //else if num_uh != 0		
	} // while

	return '1';
}

char *another=" ";

Data *search_again(tree Ti, Data *EdgeSet, char *value,int debug) {
	int len = 0;
	char *edge,*previous;
	int pos;
	previous = Ti.node->value;
	Data *ht = Ti.node;
	
	if(strcmp(EdgeSet->value,"END")==0)
		return EdgeSet;
		
	while(strcmp(ht->value,"END")!=0) {
		if(strcmp(ht->value,value)==0) {
			edge = search_string(Ti.edge,len/2);
			
			pos = search_pos(EdgeSet,edge);
						
			int elen = DataLength(EdgeSet);
		
			if(elen==0) {
				if(len%2==0)
					another = ht->next->value;
				else
					another = previous;
				return EdgeSet;
			}
			
			if(pos!=-1) {
				EdgeSet = truncateData2(EdgeSet,edge);
				
				if(debug==2)
					printf("%s ",value);
				
				if(DataLength(EdgeSet)==0) {
					if(len%2==0)
						another = ht->next->value;
					else
						another = previous;
						
					return EdgeSet;
				}
				
				if(len%2==0)
					EdgeSet = search_again(Ti,EdgeSet,ht->next->value,debug);
				else
					EdgeSet = search_again(Ti,EdgeSet,previous,debug);
				if(DataLength(EdgeSet)==0) 
					return EdgeSet;
			}
		}	
		previous = ht->value;
		ht = ht->next;
		len++;
	}	
	another = value;
	EdgeSet = newData();	
	return EdgeSet;
}

char *find_path(tree Ti, Data *EdgeSet, char *terminal,int debug) {	
	another = " ";
	
	search_again(Ti,EdgeSet,terminal,debug);
	
	if(strcmp(another," ")==0) {
		another = terminal;
	}
		
	return another;
}

tree find_leaves(Graph S, tree Ti) {
	int i,j,pos,len,pos1;
	char *row,*column,*node1,*node2,*rnode1,*rnode2,*pathname;
	Data *EdgeSet,*cEdgeSet;
	Data *ledge = newData();
	Data *lnode = newData();
	Data *oneSet = newData();
	
	for(i=0;i<S.numPath;i++) {
		EdgeSet = newData();
		oneSet = newData();
		pathname = search_string(S.Path,i);
		
		for(j=S.numEdge-1;j>=0;j--) {
			if(S.content[i*S.numEdge+j]=='2') {
				row = search_string(S.Path,i);
				column = search_string(S.Edge,j);
				if(search_pos(EdgeSet,column)==-1)
					EdgeSet = appendData(EdgeSet,column);			
			}
			
			if(S.content[i*S.numEdge+j]=='1') 
				oneSet = appendData(oneSet,"one");
		}
		
		char *p1 = stringcat(pathname,'a');
		char *p2 = stringcat(pathname,'b');
			
		cEdgeSet = copyData(EdgeSet);
		
		if(DataLength(EdgeSet)!=0) {
			pos = search_pos(Ti.edge,EdgeSet->value);
			
			node1 = search_string(Ti.node,2*pos);
			node2 = search_string(Ti.node,2*pos+1);
			
			EdgeSet = truncateData2(EdgeSet,EdgeSet->value);
			rnode1 = find_path(Ti, EdgeSet, node1,1);
		
			cEdgeSet = truncateData2(cEdgeSet,cEdgeSet->value);
			
			rnode2 = find_path(Ti , cEdgeSet, node2,1);
			
			ledge = appendData(ledge,p1);
			ledge = appendData(ledge,p2);
			lnode = appendData(lnode,"leaves");
			lnode = appendData(lnode,rnode1);
			
			// add leaves
			
			lnode = appendData(lnode,"leaves");
			lnode = appendData(lnode,rnode2);
		} else {
			if(DataLength(oneSet)!=0) {					
			for(j=S.numEdge-1;j>=0;j--) 
				if(S.content[i*S.numEdge+j]=='1') {
					pos1 = j;
					break; 	
				}
						
			row = search_string(S.Path,i);
			column = search_string(S.Edge,j);
			
			pos = search_pos(Ti.edge,column);
			node1 = search_string(Ti.node, 2*pos);
			node2 = search_string(Ti.node, 2*pos+1);
			len = DataLength(Ti.node);
			
			ledge = appendData(ledge,p1);
			lnode = appendData(lnode,"leaves");
			lnode = appendData(lnode,node1);
			
			ledge = appendData(ledge,p2);		
			lnode = appendData(lnode,"leaves");
			lnode = appendData(lnode,node1);
			}
		}
		
		delete_data(oneSet);
	}
	
	
	Data *hledge = ledge;
	Data *hlnode = lnode;
	
	while(strcmp(hledge->value,"END")!=0) {
		Ti.edge = appendData(Ti.edge,hledge->value);
		Ti.node = appendData(Ti.node,hlnode->value);
		Ti.node = appendData(Ti.node,hlnode->next->value);
		hledge = hledge->next;
		hlnode = hlnode->next->next;
	}
	
	return Ti;
}

tree extract_tree(tree T) {
	int i,j,len,len2,tlen;
	len = DataLength(T.edge);
	Data *hedge = T.edge;
	char *node1,*node2,*value;
	Data *dedge = newData();
	Data *dnode = newData();
	Data *hnode2;
	len2 = DataLength(T.node);
		
	for(i=0;i<len;i++) {
		tlen = strlen(hedge->value);
		if(hedge->value[tlen-1]=='g') {
			node1 = search_string(T.node,2*i);
			node2 = search_string(T.node,2*i+1);
			value = hedge->value;
			
			dedge = appendData(dedge,value);
			dnode = appendData(dnode,node1);
			dnode = appendData(dnode,node2);
			
			hnode2 = T.node;
			for(j=0;j<len2;j++) {
				if(strcmp(hnode2->value,node1)==0 && j%2==1) {
					hnode2->value = node2;
				}
				hnode2 = hnode2->next;
			}
		}	
		hedge = hedge->next;
	}
	
	len = DataLength(dedge);
	Data *hdedge = dedge;
	Data *hdnode = dnode;
	
	for(i=0;i<len;i++) {
		
		T.edge = truncateData2(T.edge,hdedge->value);
		T.node = truncatePair(T.node,hdnode->value,hdnode->next->value);
		
		hdedge = hdedge->next;
		hdnode = hdnode->next->next;	
	}
	
	delete_data(dedge);
	delete_data(dnode);
	return T;
}

int getnumber(char *value,int len) {
	char str[10];
	int m=0,j,row;
	len = strlen(value);
	for(j=1;j<len;j++) {
		str[m] = value[j];
		m++;
	}
	str[m] = '\0';
				
	row = atoi(str);
	return row-1;
}

stack traverse_tree(FILE *fp, tree T, stack s, char *root, char *output,int width,Data *label) {
	int i,row,column,clen,l,j,pos;
	int len = DataLength(T.edge);
	Data *hnode = T.node;
	Data *hedge = T.edge;
	int stringlen;
	char aorb;
	
	for(i=0;i<len;i++) {
		if(strcmp(hnode->next->value,root)==0) {
			if(strcmp(hnode->value,"leaves")==0) {
				fprintf(fp," ( e %s ) ",hedge->value);
					
				stringlen = strlen(hedge->value);
				aorb = hedge->value[stringlen-1];
				
				row = getnumber(hedge->value,stringlen-1); // get row number of path
				
				Data *hcontent = s.content;
				clen = DataLength(s.content);
				
				for(l=0;l<clen;l++) {
					stringlen = strlen(hcontent->value);
					column = getnumber(hcontent->value,stringlen);
					
					if(aorb == 'a')
						output[2*row*width+column] = '1';
					else
						output[(2*row+1)*width+column] = '1';
					hcontent = hcontent->next;
				}
			} else {
				s = push(s,hedge->value);
				fprintf(fp,"( %s ",hedge->value);
				
				Data *hlabel = label;
				pos = search_pos(label,hedge->value);
				for(j=0;j<pos+1;j++)
					hlabel = hlabel->next;
					
				while(strcmp(hlabel->value,"|")!=0 && strcmp(hlabel->value,"END")!=0) {
					fprintf(fp," %s ",hlabel->value);
					hlabel = hlabel->next;
				}
				
				s = traverse_tree(fp,T,s,hnode->value,output,width,label);
				fprintf(fp,") ");
				s = pop(s);
			}
			
		}
		
		hedge = hedge->next;
		hnode = hnode->next->next;
	}
	
	
	
	return s;
}

char *create_map(char *filename, tree T, Data *Label, int numEdge, int numPath) {
	stack s;
	int i,j,len,index,stringlen,row;
	char *output = new char[2*numEdge*numPath+1];
	FILE *fp = fopen(filename,"w");
	
	for(i=0;i<2*numEdge*numPath;i++)
		output[i] = '0';
	output[i] = '\0';
	
	s.content = newData();
	
	fprintf(fp,"( ");
	traverse_tree(fp,T,s,"dd",output,numEdge,Label);
	
	// handle same labels
	len = DataLength(Label);
	Data *hlabel = Label;
	
	index = -1;
	for(i=0;i<len;i++) {
		if(strcmp(hlabel->value,"|")==0) {
			index = -1;
		} else {
			stringlen = strlen(hlabel->value);
			row = getnumber(hlabel->value,stringlen);
			if(index==-1)
				index = row;
			else {
				//printf("%d %d\n",row,index);
				for(j=0;j<2*numPath;j++)
					output[j*numEdge+row] = output[j*numEdge+index];
			}
		}
		hlabel = hlabel->next;			
	}
	
	fprintf(fp," )\n");
	fclose(fp);
	return output;
}

void write_to_file(char *filename,char *output,int numEdge,int numPath) {
	FILE *fp;
	int i,j;
	char c;
	
	fp = fopen(filename,"w");
	
	fprintf(fp,"%d ",2*numPath);
	fprintf(fp,"%d\n",numEdge);
	
	for(i=0;i<2*numPath;i++) {
		for(j=0;j<numEdge;j++) {
			c = (char)output[i*numEdge+j];
			fprintf(fp,"%c ",c);
		}
		fprintf(fp,"\n");
	}
	
	fclose(fp);
}

void write_tree_to_file(char *filename,tree T,Data *PathSet) {
	FILE *fp;
	int i,len;
	Data *hedge,*hnode,*hpath;
	fp = fopen(filename,"w");
	
	hedge = T.edge;
	hnode = T.node;
	hpath = PathSet;
	
	len = DataLength(T.edge);
	fprintf(fp,"%d ",len);
	
	for(i=0;i<len;i++) {
		fprintf(fp,"%s ",hedge->value);
		hedge = hedge->next;
	}
	fprintf(fp,"\n");
	
	len = DataLength(T.node);
	fprintf(fp,"%d ",len);
	
	for(i=0;i<len;i++) {
		fprintf(fp,"%s ",hnode->value);
		hnode = hnode->next;
	}
	
	fprintf(fp,"\n");
	
	len = DataLength(PathSet);
	fprintf(fp,"%d ",len);
	
	for(i=0;i<len;i++) {
		fprintf(fp,"%s ",hpath->value);
		hpath = hpath->next;
	}
	
	fprintf(fp,"\n");
	fclose(fp);
}

char *convert_graph(char *output,int column,int row,char *cvector) {
	int i,j;
	row = row*2;
	for(i=0;i<column;i++) {
		if(cvector[i]=='1') {
			for(j=0;j<row;j++) {
				if(output[j*column+i]=='0')
					output[j*column+i] = '1';
				else if(output[j*column+i]=='1')
					output[j*column+i] = '0';
			}
		}
	}
	return output;
}

int main(int argc, char *argv[])
{
	Graph L;
	Graph sortS;
	Data *PathSet;
	Data *Label;
	
	char *filename,*filename1,*output,*filename2;
	char *vfilename,*cvector;
	
	Data *UH;
	Data *root = newData();
	tree tree;
	char result;
	int havetree;
	FILE *fpp;
	fpp = fopen("cc","w");
	
	init(argv[1],&L,&sortS,&PathSet,&Label,&vfilename,&cvector);

	UH = copyData(L.Edge);
   
        result = ETH(UH,tree,L,&root,UH->value);
	
	if(result=='1') {
		filename1 = stringcat(argv[1],'u');
		
		write_tree_to_file(filename1,Ti,PathSet); // for checking uniqueness
		
		Ti = create_Tip_tree(Ti,"g0");
		Ti = extract_tree(Ti);
		Ti = find_leaves(sortS,Ti);
		
		filename2 = stringcat(argv[1],'t');
		output = create_map(filename2,Ti,Label,sortS.numEdge,sortS.numPath);
		output = convert_graph(output,sortS.numEdge,sortS.numPath,cvector);
		filename = stringcat(argv[1],'o');
		write_to_file(filename,output,sortS.numEdge,sortS.numPath);
		havetree = 1;
		//printf("Have tree!!\n");
		fprintf(fpp,"1");
	}
	else {
		//printf("No Tree!!\n");
		havetree = 0;
		fprintf(fpp,"0");	
	}
	fclose(fpp);
	delete_graph(sortS);
	delete_graph(L);
	delete_data(PathSet);
	delete_data(Label);
	
	return havetree;
}