#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include "hyper.h"
#include "String.h"

int *sortcount;
Data *LabelSet;

int *caculate_leaf_count(Graph S) {
	int *count = new int[S.numEdge];
	int i,j,temp;

	for(i=0;i<S.numEdge;i++)
		count[i] = 0;

	for(i=0;i<S.numEdge;i++)
		for(j=0;j<S.numPath;j++) {
			temp = (int)S.content[j*S.numEdge+i] - 48;
			
			if(temp == 1)
				temp = 2;
			else if(temp == 2)
				temp = 1;

			count[i] = count[i]+temp;
		}

	return count;
}

int *handle_count(int *count,int len) {
	int *ccount = new int[len];
	int i,j;
	int index = 0;
	
	for(i=0;i<len;i++)
		for(j=i+1;j<len;j++) {
			if(count[i]==count[j])
				break;
			if(j==len-1) {
				ccount[index]=count[i];
				index++;
			}
		}

	return ccount;
}

int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}


Graph sort_edge(Graph S, int *count) {
	int i,j,k;
	Data *newEdge = newData();
	char *value;
	int *ccount = new int[S.numEdge];
	int *sortcount = new int[S.numEdge];
	char *content = new char[S.numEdge*S.numPath];

	for(i=0;i<S.numEdge;i++)
		ccount[i] = count[i];

	qsort(count,S.numEdge,sizeof(int),compare);

	for(i=0;i<S.numEdge;i++)
		sortcount[i] = count[S.numEdge-i-1];

	for(i=0;i<S.numEdge;i++)
		for(j=0;j<S.numEdge;j++) {
			if(sortcount[i]==ccount[j]) {
				value = search_string(S.Edge,j);
				newEdge = appendData(newEdge,value);

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

				break;
			}
		}

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

	delete count;
	delete sortcount;
	delete ccount;
	delete content;

    delete_data(S.Edge);
	S.Edge = newEdge;
	return S;
}

Data *create_C1(Graph S) {
	int i,j;
	Data *C1 = newData();
	char *value;

	for(i=0;i<S.numEdge;i++)
		for(j=0;j<S.numPath;j++) {
			if(S.content[j*S.numEdge+i]=='1') {
				value = search_string(S.Edge,i);
				C1 = appendData(C1,value);
				break;
			}
		}
	
	return C1;
}

Data *create_R1(Graph S) {
	Data *R1 = newData();
	int i,j;
	char *path;

	for(i=0;i<S.numPath;i++)
		for(j=0;j<S.numEdge;j++) {
			if(S.content[i*S.numEdge+j]=='1') {
				path = search_string(S.Path,i);
				R1 = appendData(R1,path);
				break;
			}
		}

	return R1;
}

Data *create_R11(Graph S, Data *R1) {
	int i,j,pos,len = DataLength(R1);
	bool is = true;
	Data *R11 = newData();

	for(i=0;i<len;i++) {
		pos = search_pos(S.Path,R1->value);
		
		for(j=0;j<S.numEdge;j++) {
			
			if(S.content[pos*S.numEdge+j]=='2') {
				is = false;
				break;
			}
			if(j==S.numEdge-1 && is)
				R11 = appendData(R11,R1->value);
		}

		is = true;
		R1 = R1->next;
	}
	return R11;
}


DataA *ResultA;
Data *extra_edges = newData();

void create_T1(Data *R2,Graph S,int whichone) {
	int i,j,pos,len = DataLength(R2);
	Data *sort;
	DataA *pointto;
	char *value;
	int no = -1;
	
	for(i=0;i<len;i++) {
		no = -1;
		sort = newData();
		pos = search_pos(S.Path,R2->value);
		for(j=0;j<S.numEdge;j++) {
			if(S.content[pos*S.numEdge+j]=='1' && no!=sortcount[j]) {				
				value = search_string(S.Edge,j);
				sort = appendData(sort,value);
				no = sortcount[j];
			}
		}
		
		pointto = locate_DataA(ResultA,pos);
		delete_data(pointto->row);
		pointto->row = copyData(sort);
		
		delete_data(sort);
		R2 = R2->next;
	}
}

void replace_node(tree T1,char *value,char *node) {
	int i,pos = search_pos(T1.edge,value);

	for(i=0;i<2*pos;i++) 
		T1.node = T1.node->next;
	
	T1.node->value = node;
}

tree Merge_Path(tree T1, int len) {
	Data *hresult;
	int l,i,j,pos;
	char *node;
	DataA *pointto;
	
	for(i=0;i<len;i++) {
		pointto = locate_DataA(ResultA,i);
		hresult = pointto->row;
		
		l = DataLength(hresult);
		for(j=0;j<l;j++) {
			
			if(j==0)
				node = hresult->value;
			
			pos = search_pos(T1.edge,hresult->value);
			if(pos==-1) {
				T1.edge = appendData(T1.edge,hresult->value);
				T1.node = appendData(T1.node,node);
				T1.node = appendData(T1.node,hresult->value);
			} else {
				if(j!=0) {
					replace_node(T1,hresult->value,node);
				}
			}

			node = hresult->value;
			hresult = hresult->next;
		}
	}
	return T1;
}

Data *find_root(tree T1) {
	int i,len = DataLength(T1.edge);
	Data *root = newData();
	
	for(i=0;i<len;i++) {
		if(strcmp(T1.node->value,T1.node->next->value)==0) 
			root = appendData(root,T1.node->value);
		
		T1.node = T1.node->next->next;
	}
	return root;
}

bool check_node(char *node, Graph S, Data *R11) {  // check if this node is in R11
	int pos = search_pos(S.Edge,node);
	int i,pos2;
	char *value;

	for(i=0;i<S.numPath;i++) {
		if(S.content[i*S.numEdge+pos]=='1') {
			value = search_string(S.Path,i);
			pos2 = search_pos(R11,value);
			if(pos2!=-1)
				return false;
		}
	}
	return true;
}

int *leaves_record;

Data *trace_path(tree T1, char *root, Data *PathSet,Graph S,Data *R11,char *previous) {
	int i,len = DataLength(T1.edge);
	int found = 0;
	Data *hnode = T1.node;
	char *oldp;

	for(i=0;i<len;i++) {
		if(strcmp(hnode->value,root)==0) {
			found = 1;
			
			PathSet = appendData(PathSet,hnode->value);
			PathSet = appendData(PathSet,hnode->next->value);
			PathSet = appendData(PathSet,"|");

			
			PathSet = appendData(PathSet,previous);
			PathSet = appendData(PathSet,hnode->value);
			PathSet = appendData(PathSet,hnode->next->value);
			PathSet = appendData(PathSet,"|");

			oldp = previous;
			previous = hnode->value;
			trace_path(T1,hnode->next->value,PathSet,S,R11,previous);
			previous = oldp;
		}
		hnode = hnode->next->next;
	}

	return PathSet;
}

bool check_1(int c1,int c2,Graph S) {
	int i,j;
	int check1,check2;
	check1 = check2 = 0;
	
	for(i=0;i<S.numPath;i++)
		if(S.content[i*S.numEdge+c1]=='1') {
			check1 = 1;
			break;
		}
	
	j = i;
	
	for(i=0;i<S.numPath;i++)
		if(S.content[i*S.numEdge+c2]=='1') {
			check2 = 1;
			break;
		}	
	
	if(check1==1 && check2==1 && i==j)
		return true;
	else
		return false;		
}

int find_ep(Graph S,int *sortcount,int i) {
	int j;
	int check = 0,check2 = 0;
	int previous = sortcount[0];
	for(j=0;j<S.numEdge;j++) {
		if(previous!=sortcount[j]) {
			if(check==0 && check2 ==2) {
				return sortcount[j-1];
			}
			check = 0;
			check2 = 0;
		}
		if(S.content[i*S.numEdge+j] == '1')
			check = 1;
		if(S.content[i*S.numEdge+j] == '2')
			check2 = 2;
			
		previous = sortcount[j];
	}
	
	if(check==0 && check2==2)
		return sortcount[j-1];
			
	return -1;
}

int check_indentical_column(Graph S,int path_index) {
	int i,j;
	
	int previous = -1;
	
	char *string1 = new char[S.numPath+1];
	char *string2 = new char[S.numPath+1];
	
	for(j=0;j<S.numEdge;j++) {	
		if(S.content[path_index*S.numEdge+j]!='1')
			continue;
			
		if(previous!=sortcount[j]) {
			for(i=0;i<S.numPath;i++) {				
				string1[i] = S.content[i*S.numEdge+j];
			}
		}	
		
		for(i=0;i<S.numPath;i++) {
			string2[i] = S.content[i*S.numEdge+j];
		}
		
		string1[i] = '\0';
		string2[i] = '\0';
		
		if(strcmp(string1,string2)!=0)
			return 0;
				
		previous = sortcount[j];
	}	
	
	return 1;
}

Data *add_2(tree T1, Graph S, Data *PathSet, Data *C1, int *check_i) {       // add node which value is 2
	int i,j;
	Data *temp,*htemp;
	char *value;
	int is,pos;
	int no2,no = -1;
	int haveone,havetwo;
	int prevpos;
	
	// handle C1 is empty
	if(DataLength(C1)==0) {
		
		for(i=0;i<S.numPath;i++) {
			no = 0;
			for(j=0;j<S.numEdge;j++) {
				if(S.content[i*S.numEdge+j]=='2') {
					char *value = search_string(S.Edge,j);
					PathSet = appendData(PathSet,value);	
					no++;
				}
			}
			if(no!=0) {
				PathSet = appendData(PathSet,"g0");
				PathSet = appendData(PathSet,"|");	
			}	
		}	
		return PathSet;
	}
	
	int ev,e;  
	// handle those '2' labels which has '1' in the same column
	for(i=0;i<S.numPath;i++) {
		temp = newData();
		is = 0;
		no = -1;
		no2 = -1;
		haveone = 0;
		havetwo = 0;
		ev = -1; // record ev
		e = -1; // record e
	
		for(j=0;j<S.numEdge;j++) {
			if(S.content[i*S.numEdge+j]=='2') {
				value = search_string(S.Edge,j);
				
				if(no!=sortcount[j] || !check_1(prevpos,j,S))  // avoid duplicate
					temp = appendData(temp,value);
				
				no = sortcount[j];
				prevpos = j;
					
				pos = search_pos(C1,value);
				if(pos!=-1) 
					is = 1;             // 2 value in C1
				havetwo = 1;
			} else if(S.content[i*S.numEdge+j]=='1') {
				if(no2!=sortcount[j]) {					
					haveone = 1;
					e = ev;
					ev = j;
				}
				no2 = sortcount[j];
			}
		}

		htemp = temp;
		if(haveone == 0)
			ev = -1;
			
		
		if(DataLength(temp)>0) {
			while(strcmp(temp->value,"END")!=0) {
				PathSet = appendData(PathSet,temp->value);
				temp = temp->next;
			}
			PathSet = appendData(PathSet,"|");
		}
		
		if(havetwo==1) {   
			char *cev,*ce,*ctwo;
			
			if(ev==-1)
				cev = "g0";
			else
				cev = search_string(S.Edge,ev);
				
			if(e!=-1)
				ce = search_string(S.Edge,e);
			
			//int max = find_ep(S,sortcount,i);
			//printf("max is %d\n",max);
			int max = -1;
			for(j=0;j<S.numEdge;j++) {
				if(S.content[i*S.numEdge+j]=='2') {
					if(max==-1 || max == sortcount[j]) {
						
						if(ev!=-1) {
							if(check_indentical_column(S,i)==0) {
								*check_i = 0;	
							}
						}
						
						ctwo = search_string(S.Edge,j);
						if(ev==-1) {	// no 1		
							PathSet = appendData(PathSet,"g0");
							PathSet = appendData(PathSet,ctwo);
							PathSet = appendData(PathSet,"|");
						} else if(e==-1) {
							PathSet = appendData(PathSet,"g0");
							PathSet = appendData(PathSet,cev);
							PathSet = appendData(PathSet,ctwo);
							PathSet = appendData(PathSet,"|");
							PathSet = appendData(PathSet,"g0");
							PathSet = appendData(PathSet,cev);
							PathSet = appendData(PathSet,"|");
							PathSet = appendData(PathSet,cev);
							PathSet = appendData(PathSet,ctwo);
							PathSet = appendData(PathSet,"|");
							
						} else {
							PathSet = appendData(PathSet,ce);
							PathSet = appendData(PathSet,cev);
							PathSet = appendData(PathSet,ctwo);
							PathSet = appendData(PathSet,"|");
							PathSet = appendData(PathSet,ce);
							PathSet = appendData(PathSet,cev);
							PathSet = appendData(PathSet,"|");
							PathSet = appendData(PathSet,cev);
							PathSet = appendData(PathSet,ctwo);
							PathSet = appendData(PathSet,"|");
						}
						break;
					} else {
						break;
					}
					max = sortcount[j];
				}		
			}
		}

		delete_data(htemp);
	}
	
	return PathSet;
}

Data *create_path(tree T1, Graph S,Data *R11,Data *C1,int *check_i) {
	Data *PathSet = newData();
	Data *root;
	char *previous = "g0";
	int i,pos;
	
	leaves_record = new int[S.numEdge];
	
	for(i=0;i<S.numEdge;i++)
		leaves_record[i] = -1;
	
	root = find_root(T1);
	int len = DataLength(root);

	extra_edges = appendData(extra_edges,"g0");
	for(i=0;i<len;i++) {		
		PathSet = appendData(PathSet,"g0");
		PathSet = appendData(PathSet,root->value);
		PathSet = appendData(PathSet,"|");

		pos = search_pos(S.Edge,root->value);
		leaves_record[pos] = 1;
		
		T1.node = truncatePair(T1.node,root->value,root->value);
		T1.edge = truncateData(T1.edge,root->value);
		
		PathSet = trace_path(T1,root->value,PathSet,S,R11,previous);
		root = root->next;
	}
	
	PathSet = add_2(T1,S,PathSet,C1,check_i);
	
	return PathSet;
}


Graph create_graph(Graph S,Data *PathSet) {
	Graph G;
	
	int i,len,pos,j=0;
	
	Data *path = newData();
	Data *hextra = extra_edges;

	len = DataLength(extra_edges);

	char *previous = " ";
	G.Edge = newData();
	while(strcmp(S.Edge->value,"END")!=0) {
		if(strcmp(S.Edge->value,previous)!=0)
			G.Edge = appendData(G.Edge,S.Edge->value);	
		previous = S.Edge->value;
		S.Edge = S.Edge->next;
	}
	
	for(i=0;i<len;i++) {
		G.Edge = appendData(G.Edge,hextra->value);
		hextra = hextra->next;
	}
	
	len = DataLength(G.Edge);
	G.numEdge = len;

	len = DataLength(PathSet);
	
	G.content = new char[G.numEdge * ((len/2)+1)];
	
	for(i=0;i<G.numEdge * ((len/2)+1);i++) 
		G.content[i] = '0';
		
	for(i=0;i<len;i++) {
		pos = search_pos(G.Edge,PathSet->value);
		
		if(pos!=-1) {  // not |
			G.content[j*G.numEdge+pos] = '1';
		}

		if(strcmp(PathSet->value,"|")==0) {
			char *temp = generate_node("p",j+1);
			path = appendData(path,temp);
			j++;
		}

		PathSet = PathSet->next;
	}

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

	G.Path = path;
	G.numPath = j;

	return G;
}

Graph sort_graph(Graph S, int *count) {
	int i,j,k;
	int *scount = new int[S.numEdge];
	sortcount = new int[S.numEdge];
	Graph G;
	char *value;
	
	G.content = new char[S.numEdge*S.numPath+1];
	G.numEdge = S.numEdge;
	G.numPath = S.numPath;
	G.Edge = newData();
	G.Path = newData();
		
	for(i=0;i<S.numEdge;i++)
		scount[i] = count[i];

	qsort(scount,S.numEdge,sizeof(int),compare);
	
	for(i=0;i<S.numEdge;i++) 
		sortcount[i] = scount[S.numEdge-i-1];
		
	G.Path = copyData(S.Path);
	
	for(i=0;i<S.numEdge;i++)
		for(j=0;j<S.numEdge;j++) {
			if(sortcount[i] == count[j]) {
				count[j] = -1;
				value = search_string(S.Edge,j);
				G.Edge = appendData(G.Edge,value);
				
				for(k=0;k<S.numPath;k++)
					G.content[k*S.numEdge+i] = S.content[k*S.numEdge+j]; 
				break;
			}
		}
		
	delete_graph(S);
	delete [] scount;
	return G;
}

Graph handle_duplicate(Graph S) {
	int i,j,k;
	int count;
	char *previous;
	
	Data *original = copyData(S.Edge);
	
	for(i=0;i<S.numPath;i++) {
		count = -1;	
		
		for(j=0;j<S.numEdge;j++) {
			if(S.content[i*S.numEdge+j]=='1') {
				if(sortcount[j]==count) {
					Data *hedge = S.Edge;
				
					k = 0;
					while(strcmp(hedge->value,"END")!=0) {
						
						if(sortcount[k]==count && S.content[i*S.numEdge+k]=='1') {	
							hedge->value = previous;
						}
							
						hedge = hedge->next;	
						k++;
					}
				}
				count = sortcount[j];
				previous = search_string(S.Edge,j);
			}
			
		}
	}
	
	Graph L;
	Data *he,*hEdge;
	int enumber = 0;
	char *value;

	// move same edges together
	L.numEdge = S.numEdge;
	L.numPath = S.numPath;
	L.Path = copyData(S.Path);
	L.Edge = newData();
	
	L.content = new char[L.numEdge*L.numPath];
	hEdge = S.Edge;
	
	for(i=0;i<S.numEdge;i++) {
		if(strcmp(hEdge->value,"cc")!=0) {
			value = hEdge->value;
			he = hEdge;			
			
			for(j=i;j<S.numEdge;j++) {
				if(strcmp(he->value,value)==0) {
					char *vv = search_string(original,j);
				
					LabelSet = appendData(LabelSet,vv);
					L.Edge = appendData(L.Edge,he->value);
					for(k=0;k<S.numPath;k++) {
						L.content[k*S.numEdge+enumber] = S.content[k*S.numEdge+j];
					}
					he->value = "cc";
					enumber++;
				}
				he = he->next;
			}
			LabelSet = appendData(LabelSet,"|");
		}	
		hEdge = hEdge->next;
	}
	
	L.content[L.numEdge*L.numPath] = '\0';
	
	delete_graph(S);
	return L;
}

Graph init(char *filename)
{
	Graph L;
	Data *phead,*ehead;
	FILE *fp;
	fp = fopen(filename,"r");
	int row,column,i,digit;
	float frow,fcolumn;
	char *temp;
	
	ehead = newData();
	phead = newData();
	
	if(fp==NULL) {
		printf("File does not exist\n");
		exit(1);
	}
		
	fscanf(fp,"%f",&frow);
	fscanf(fp,"%f",&fcolumn);
	
	row = (int)frow;
	column = (int)fcolumn;
	
	L.content = new char[row*column+1];

	for(i=1;i<=row;i++) {
		temp = generate_node("p",i);
		phead = appendData(phead,temp);
	}
	
	for(i=1;i<=column;i++) {
		temp = generate_node("e",i);
		ehead = appendData(ehead,temp);
	}

	int index = 0;
	while(fscanf(fp,"%d",&digit)!=EOF) {
		L.content[index] = (char)(digit+48);
		index++;
	}		
	L.content[index] = '\0';
			
	L.numEdge = DataLength(ehead);
	L.numPath = DataLength(phead);

	L.Edge = ehead;
	L.Path = phead;
	
	fclose(fp);
	return L;
}

void write_to_file(Data *PathSet,Graph S, Graph G, char *filename,char *vfilename,char *cvector) {
	FILE *fp;
	int i,len;
	Data *hedge,*hpath;
	char *title = "Paths: ";
	
	fp = fopen(filename,"w");
	
	fprintf(fp,"%s",title);
	
	len = DataLength(PathSet);
	for(i=0;i<len;i++) {
		fprintf(fp,"%s ",PathSet->value);
		PathSet = PathSet->next;
	}
	
	fprintf(fp,"\n\n");
	
	fprintf(fp,"Graph1:\n");
	fprintf(fp,"%d ",G.numEdge);
	fprintf(fp,"%d\n",G.numPath);
	hedge = G.Edge;
	
	for(i=0;i<G.numEdge;i++) {
		fprintf(fp,"%s ",hedge->value);
		hedge = hedge->next;
	}
	fprintf(fp,"\n");
	
	hpath = G.Path;
	
	for(i=0;i<G.numPath;i++) {
		fprintf(fp,"%s ",hpath->value);
		hpath = hpath->next;
	}
	fprintf(fp,"\n");
	
	fprintf(fp,"%s\n\n",G.content);
	
	////////////////////////////////////////////
	fprintf(fp,"Graph2:\n");
	fprintf(fp,"%d ",S.numEdge);
	fprintf(fp,"%d\n",S.numPath);
	hedge = S.Edge;
	
	for(i=0;i<S.numEdge;i++) {
		fprintf(fp,"%s ",hedge->value);
		hedge = hedge->next;
	}
	fprintf(fp,"\n");
	
	hpath = S.Path;
	
	for(i=0;i<S.numPath;i++) {
		fprintf(fp,"%s ",hpath->value);
		hpath = hpath->next;
	}
	fprintf(fp,"\n");
	
	fprintf(fp,"%s\n\n",S.content);
	
	fprintf(fp,"Vector:\n");
	fprintf(fp,"%s ",vfilename);
	fprintf(fp,"%s\n\n",cvector);
	
	fprintf(fp,"Labels: ");
	
	Data *hlabel = LabelSet;
	len = DataLength(LabelSet);
	for(i=0;i<len;i++) {
		fprintf(fp,"%s ",hlabel->value);
		hlabel = hlabel->next;
	}
	
	fprintf(fp,"\n\n");
	
	fclose(fp);
}

char *generate_default(char *cvector, Graph S) {
	int i,j;
	int one,zero;
	
	for(i=0;i<S.numEdge;i++) {
		one = 0;
		zero = 0;
		for(j=0;j<S.numPath;j++) {
			if(S.content[j*S.numEdge+i]=='1')
				one++;
			else if(S.content[j*S.numEdge+i]=='0')
				zero++;
		}
		if(zero >= one)
			cvector[i] = '0';
		else
			cvector[i] = '1';
	}
	cvector[i] = '\0';
	return cvector;
}

char *read_vector(char *cvector,char *filename, Graph S) {
	int num = S.numEdge;
	cvector = new char[num+1];
	FILE *fp;
	int i = 0;
	int tt;
	
	if(strcmp(filename,"d")!=0) {
		fp = fopen(filename,"r");
		
		for(i=0;i<num;i++) {	
			if(fscanf(fp,"%d",&tt)==EOF) {
				printf("vector information error!\n");
				exit(0);
			}
			cvector[i] = (char)tt+48;
		}
		cvector[i] = '\0';
		fclose(fp);
	} else {
		//cvector = generate_default(cvector,S);
		for(i=0;i<num;i++) 
			cvector[i] = '0';
		cvector[i] = '\0';
	}
	return cvector;
}

Graph convert_data(Graph S, char *vector) {
	int i,j;
	
	for(i=0;i<S.numEdge;i++) {
		if(vector[i] == '1') {
			for(j=0;j<S.numPath;j++) {
				if(S.content[j*S.numEdge+i]=='1')
					S.content[j*S.numEdge+i] = '0';
				else if(S.content[j*S.numEdge+i]=='0')
					S.content[j*S.numEdge+i] = '1';
			}
		}
	}
	
	return S;
}

int check_order(Graph S) {
	int i,j;
	int check = 0,check2 = 0;
	int previous = sortcount[0];
	int hasone = 0,hastwo =0,hasone_again=0;
	
	for(i=0;i<S.numPath;i++) {
		hasone = hastwo = hasone_again = 0;
		check = check2 = 0;
		for(j=0;j<S.numEdge;j++) {
			if(previous!=sortcount[j]) {
				if(check==1 && check2 ==2) {
					return 0;
				}
				check = 0;
				check2 = 0;
			}
			if(S.content[i*S.numEdge+j] == '1') {
				if(hastwo==1) {
					return 0;
				}
				check = 1;
			
				hasone = 1;
			}
			if(S.content[i*S.numEdge+j] == '2') {
				check2 = 2;
				hastwo = 1;
			}
			
			previous = sortcount[j];
		}	
		
		if(check==1 && check2==2) {
			return 0;
		}
			
	}
			
	return 1;
}

int check_identical(Graph S) {
	int i,j;
	int numone = 0,numtwo = 0,numzero = 0;
	int previous = -1;
	int fone,ftwo,fzero;
	
	for(j=0;j<S.numEdge;j++) {
		numone = numtwo = numzero = 0;
		if(previous!=sortcount[j]) {
			fone = ftwo = fzero = 0;
			for(i=0;i<S.numPath;i++) {
				if(S.content[i*S.numEdge+j] == '1')
					fone++;
				else if(S.content[i*S.numEdge+j] == '2')
					ftwo++;
				else
					fzero++;
			}
		}	
		
		for(i=0;i<S.numPath;i++) {
				if(S.content[i*S.numEdge+j] == '1')
					numone++;
				else if(S.content[i*S.numEdge+j] == '2')
					numtwo++;
				else
					numzero++;
		}
		
		if(fone!=numone || ftwo!=numtwo || fzero!=numzero)
			return 0;
				
		previous = sortcount[j];
	}	
		
	return 1;
}

int main(int argc, char *argv[])
{
	int i,len;
	Graph S;
	char *filename;
	int check ;
	
	if(argc==1) {
		printf("Usage: hypertree.out filename\n");
		exit(1);
	}
	
	//char fvector[50];
	char *cvector;
	FILE *fpp;
	fpp = fopen("cc","w");
	
	//printf("Please input the file name of the vector (enter \"d\" for default): ");
	//scanf("%s",fvector);
	
	char *fvector = "d";
	
	filename = stringcat(argv[1],'c');
	
	S = init(argv[1]);
	
	cvector = read_vector(cvector,fvector,S);
	S = convert_data(S,cvector);
	//show_graph_data(S);
	len = S.numEdge;
	Graph G;
	int *count = new int[S.numEdge];
	count = caculate_leaf_count(S);
	
	S = sort_graph(S,count); 
	//show_graph_data(S);
	check = check_order(S);
	//show_graph_data(S);
	if(check==0) {
		//fprintf("NO TREE!!\n");
		fprintf(fpp,"0");
		fclose(fpp);
		return 0;
	}		
	
	LabelSet = newData();
	S = handle_duplicate(S);
	
	
	Data *R1,*R11,*R2,*C1,*PathSet;
	tree T1;
	T1.edge = newData();
	T1.node = newData();

	ResultA = newDataA();
	for(i=0;i<S.numPath;i++) {
		ResultA = appendDataA(ResultA,"HEAD");
	}

	C1 = create_C1(S);
	R1 = create_R1(S);
	R11 = create_R11(S,R1);
	R2 = minusData(R1,R11);

	create_T1(R2,S,1);
	create_T1(R11,S,2);
		
	T1 = Merge_Path(T1,S.numPath);
	
	check = 1;
	PathSet = create_path(T1,S,R11,C1,&check);
	
	if(check==0) {
		//printf("NO TREE!!\n");
		fprintf(fpp,"0");
		fclose(fpp);
		return 0;
	}
	
	G = create_graph(S,PathSet);
	
	
	write_to_file(PathSet,S,G,filename,fvector,cvector);
	
	fprintf(fpp,"1");
	fclose(fpp);
	
	delete_graph(G);
	delete_data(PathSet);
	delete_data(extra_edges);
	delete_dataA(ResultA);
	delete_data(LabelSet);
	return 1;
}