#include "graphProcessing.h"

//------------------------------------------------------------------------
// Create a new blank graph
//------------------------------------------------------------------------
graph* createGraph() {
	graph* g;

	g=(graph*)malloc(sizeof(graph));
	g->name			= NULL;
	g->mat2d		   = NULL;
	g->edgeLabels	= NULL;
	g->degree		= NULL;
	g->VERTEX		= NULL;
	g->vi			   = NULL;
	g->vertRoot    = NULL;
	g->vertData		= NULL;
	g->edgeRoot    = NULL;
	g->edgeData		= NULL;
	g->queryColors	= NULL;
	g->fltQuery		= NULL;
	g->strQuery		= NULL;
	g->numBin		= NULL;
	g->lodBin		= NULL;
	g->vertList		= NULL;
	g->vertColorList= NULL;
	g->vertPosn		= NULL;
	g->edgeList		= NULL;
	g->edgeList1d	= NULL;
	g->tl1d2		   = NULL;
   g->vertLabelAlias = 0;
	g->offset[0]=0;  g->offset[1]=0;  g->offset[2]=0;
	g->scale[0]=1.f; g->scale[1]=1.f; g->scale[2]=1.f;
	g->haloColorIdx=128;
	//g->haloColorIdx+=((3+1)*58)%255; //change default graph color
	return g;
}

//------------------------------------------------------------------------
// Create a shallow copy of the graph (warning: points to same data)
//------------------------------------------------------------------------
graph* sCopy(graph* g) {
	graph* h;
	h = (graph*)malloc(sizeof(graph));
	memcpy(h,g,sizeof(graph));
	return h;
}

//------------------------------------------------------------------------
// Create a copy of the graph
//------------------------------------------------------------------------
graph* copy(graph* g) {
	int i,size;
	char* extension;

	graph* h;
	h = sCopy(g);
	h->name			= NULL;
	h->mat2d		   = NULL;
	h->edgeLabels	= NULL;
	h->degree		= NULL;
	h->VERTEX		= NULL;
	h->vi		   	= NULL;
	h->vertRoot    = NULL;
	h->vertData		= NULL;
	h->vertColorList= NULL;
	h->edgeRoot     = NULL;
	h->edgeData		= NULL;
	h->queryColors	= NULL;
	h->fltQuery		= NULL;
	h->strQuery		= NULL;
	h->vertList		= NULL;
	h->edgeList		= NULL;
	h->edgeList1d	= NULL;
	h->tl1d2		   = NULL;

	//Hack: Read in file to save copying all the data
	h->name=(char*)malloc( (strlen(g->name)+1)*sizeof(char) );
	strcpy(h->name,g->name);
	//Assumes 3-letter extension convention
	extension=h->name+(strlen(h->name)-4);
	if(strcmp(extension,".ltm")==0)
		h->numVerts = readLTMDefaultWeighted2D(h->name, 0.0,1, h);
	else
		h->numVerts = readDefaultWeighted2D(h->name, 0.0, 1, h);

	// Copy display information
	for(i=0;i<3;i++) {
		h->scale[i] = g->scale[i];
		h->offset[i] = g->offset[i];
	}

	//Vertex information
	size=h->numDisplayVerts*sizeof(int);
	h->vertList = (int*)malloc(size);
	if(h->vertList==NULL) {perror("  copy(graph)"); exit(-1);}
	memcpy(h->vertList,g->vertList,size);

	size=3*h->numVerts*sizeof(int);
	h->vertPosn = (short int*)malloc(size);
	if(h->vertPosn==NULL) {perror("  copy(graph)"); exit(-1);}
	memcpy(h->vertPosn,g->vertPosn,size);

	size=h->numVerts*sizeof(int);
	h->vertColorList = (int*)malloc(size);
	if(h->vertColorList==NULL) {perror("  copy(graph)"); exit(-1);}
	memcpy(h->vertColorList,g->vertColorList,size);

	//Edge information
	size=2*h->numDisplayEdges*sizeof(int);
	h->edgeList = (unsigned short *)malloc(size);
	if(h->edgeList==NULL) {perror("  copy(graph)"); exit(-1);}
	memcpy(h->edgeList,g->edgeList,size);

	return h;
}

//------------------------------------------------------------------------
// Initialize the graph's edge count for each vertex
//------------------------------------------------------------------------
void initDegreeBase(graph* g, int** degree) {
	int i, j, edgeCount;

	if((*degree)!=NULL) free(*degree);
	(*degree)=(int*)malloc(g->numVerts*sizeof(int));
   if( (*degree)==NULL ) {
      perror("initDegreeBase(): degree[]");
      return;
   }
	for(i=0;i<g->numVerts;i++) {
		edgeCount=0;
		//Check row
		for(j=0;j<i;j++)
			if(g->mat2d[i][j]!=INAN)
				edgeCount++;
		//Check column
		for(j=i+1;j<g->numVerts;j++)
			if(g->mat2d[j][i]!=INAN)
				edgeCount++;

		(*degree)[i]=edgeCount;
	}
}

//------------------------------------------------------------------------
// Initialize the graph's edge count for each vertex and each threshold
//------------------------------------------------------------------------
void initDegreeAll(graph* g,float startThresh,float stopThresh,float stepThresh,int absVal) {
	int i, j, d, edgeCount, numSteps, realThresh;
   float t;
	clock_t startTime,endTime;

	numSteps=0; startTime=clock();
	for(t=startThresh;t<=(stopThresh+(1e-6));t+=stepThresh) numSteps++;
	g->degree=(int**)malloc(numSteps*sizeof(int*));
   if(g->degree==NULL) perror("initDegreeAll(): g->degree");
	g->degree[0]=NULL;
	printf("  Step %d...",numSteps);
	initDegreeBase(g,&(g->degree[0]));

	for(d=1;d<numSteps;d++) {
		printf("%d...",numSteps-d);
		realThresh=(int)(DENOM_THRESH*startThresh+d*stepThresh*DENOM_THRESH);
		g->degree[d]=(int*)malloc(g->numVerts*sizeof(int));
      if(g->degree==NULL) perror("initDegreeAll(): g->degree[]");
		if(absVal==0) {
			for(i=0;i<g->numVerts;i++) {
				edgeCount=0;
				if(g->degree[d-1][i]!=0) {//More restrictive threshold can't add edges
					//Check row
					for(j=0;j<i;j++)
						if(g->mat2d[i][j]>=realThresh)
							edgeCount++;
					//Check column
					for(j=i+1;j<g->numVerts;j++)
						if(g->mat2d[j][i]>=realThresh)
							edgeCount++;
				}
				g->degree[d][i]=edgeCount;
			}
		}
		else {
			for(i=0;i<g->numVerts;i++) {
				edgeCount=0;
				if(g->degree[d-1][i]!=0) {//More restrictive threshold can't add edges
					//Check row
					for(j=0;j<i;j++)
						if(g->mat2d[i][j]!=INAN)
							if (g->mat2d[i][j]>=realThresh || (-1*g->mat2d[i][j])>=realThresh)
								edgeCount++;
					//Check column
					for(j=i+1;j<g->numVerts;j++)
						if(g->mat2d[j][i]!=INAN)
							if (g->mat2d[j][i]>=realThresh || (-1*g->mat2d[j][i])>=realThresh)
								edgeCount++;
				}
				g->degree[d][i]=edgeCount;
			}
		}
	}
	endTime=clock();
	printf("(%d secs)\n",(endTime-startTime)/CLOCKS_PER_SEC);
}

//------------------------------------------------------------------------
// Finds the number of edges that connect to visible vertices
//------------------------------------------------------------------------
int initVisibleEdgeList(int target, graph* g) {
	int i, j, count;
   void* tmpRealloc;

	if(g->edgeList!=NULL) free(g->edgeList);
	g->edgeList=(unsigned short*)malloc(2*g->numEdges*sizeof(unsigned short));
   if(g->edgeList==NULL) perror("initVisibleEdgeList(): g->edgeList");
	count=0;
	for(i=0;i<g->numVerts;i++) {
		for(j=0;j<i;j++) {
			if (g->mat2d[i][j]!=INAN) {
				if ( (g->vertColorList[i]==target) &&
					 (g->vertColorList[j]==target) ) {
					g->edgeList[2*count+0]=i;
					g->edgeList[2*count+1]=j;
					count++;
				}
			}
		}
	}
   if(count>0) {
      tmpRealloc = realloc((void*)g->edgeList,2*count*sizeof(unsigned short));
      if(tmpRealloc==NULL) {
	      perror("initVisibleEdgeList() g->edgeList");  return -1;
      }
      if(g->edgeList != tmpRealloc) free(g->edgeList);
      g->edgeList = (unsigned short*)tmpRealloc;
   }
	else { free(g->edgeList); g->edgeList=NULL; }
	g->numDisplayEdges = count;
	return g->numDisplayEdges;
}

//------------------------------------------------------------------------
// Finds the number of edges that connect to visible vertices
//------------------------------------------------------------------------
int initVisibleEdgeListAll(graph* g) {
	int i, j, count;
   void* tmpRealloc;

   if(g->edgeList!=NULL) free(g->edgeList);
	g->edgeList=(unsigned short*)malloc(2*g->numEdges*sizeof(unsigned short));
   if(g->edgeList==NULL) {
      perror("initVisibleEdgeListAll() g->edgeList"); exit(-1);
   }
	count=0;
	for(i=0;i<g->numVerts;i++) {
		for(j=0;j<i;j++) {
			if (g->mat2d[i][j]!=INAN) {
				if ( (g->vertColorList[i]!=-1) &&
					 (g->vertColorList[j]!=-1) ) {
					g->edgeList[2*count+0]=i;
					g->edgeList[2*count+1]=j;
					count++;
				}
			}
		}
	}
   if(count>0) {
      tmpRealloc = realloc((void*)g->edgeList,2*count*sizeof(unsigned short));
      if(tmpRealloc==NULL) {
	      perror("initVisibleEdgeList() g->edgeList");  return -1;
      }
      if(g->edgeList != tmpRealloc) free(g->edgeList);
      g->edgeList = (unsigned short*)tmpRealloc;
   }
	else { free(g->edgeList); g->edgeList=NULL; }
	g->numDisplayEdges = count;
	return g->numDisplayEdges;
}

//------------------------------------------------------------------------
// Initializes and returns the number of edges in the current graph
//------------------------------------------------------------------------
int initNumEdges(graph* g) {
	int i,j,count;
	count=0;
	for(i=0;i<g->numVerts;i++) {
		for(j=0;j<i;j++) {
			if(g->mat2d[i][j]!=INAN) {
				count++;
			}
		}
	}
	
	g->numEdges = count;
	g->numDisplayEdges = count;
	return g->numEdges;
}

//------------------------------------------------------------------------
// Takes disconnected nodes (with no edges) out of the list
//------------------------------------------------------------------------
int filterDisconnectedVertsUsingDegree(graph* g, int index) {
	int i, count, numDisplayVerts;
   void* tmpRealloc;

	if(g->vertList==NULL) return(g->numDisplayVerts);
	count=0; numDisplayVerts=g->numDisplayVerts;
	for(i=0;i<g->numDisplayVerts;i++) {
		if(g->degree[index][g->vertList[i]]!=0) {
			g->vertList[count]=g->vertList[i];
			count++;
		}
	}
   numDisplayVerts=count;
	if(numDisplayVerts==0) { free(g->vertList); g->vertList=NULL; }
   else if (numDisplayVerts!=g->numDisplayVerts) {
      tmpRealloc = realloc((void*)g->vertList,numDisplayVerts*sizeof(int));
      if(tmpRealloc==NULL) {
	      perror("filterDisconnectedVertsUsingDegree() g->vertList"); return -1;
      }
      if(g->vertList != tmpRealloc) free(g->vertList);
      g->vertList = (int*)tmpRealloc;
   }
	g->numDisplayVerts=numDisplayVerts;
	return g->numDisplayVerts;
}

//------------------------------------------------------------------------
// Removes vertices from the current edgeList that have no edges
//------------------------------------------------------------------------
int filterVertsFailThresh(float thresh, int absVal, graph* g) {
	int i, j, count, numDisplayVerts, realThresh;
	int* tmp;
   void* tmpRealloc;
	short int flagDisconnected;
	clock_t startTime, endTime;

	startTime=clock();
	realThresh=(int)(DENOM_THRESH*thresh);
	numDisplayVerts=g->numDisplayVerts;
	if(g->vertList==NULL) return(g->numDisplayVerts);
	tmp=(int*)malloc(g->numDisplayVerts*sizeof(int));

	//printf("Vertices disconnected: ");
	count=0;
	if(absVal==0) {
		for(i=0;i<g->numDisplayVerts;i++) {
			flagDisconnected=1;
			//Check row
			for(j=0;j<g->vertList[i];j++)
				if(g->mat2d[g->vertList[i]][j]>=realThresh)
					flagDisconnected=0;
			//Check column
			for(j=g->vertList[i]+1;j<g->numVerts;j++)
				if(g->mat2d[j][g->vertList[i]]>=realThresh)
					flagDisconnected=0;

			//If disconnected, don't show it
			if(flagDisconnected==1) {
				//printf("%d with label %s,",i,g->edgeLabels->list[i]);
				numDisplayVerts--;
			}
			else {
				tmp[count]=g->vertList[i];
				count++;
			}
		}
	}
	else {
		for(i=0;i<g->numDisplayVerts;i++) {
			flagDisconnected=1;
			//Check row
			for(j=0;j<g->vertList[i];j++)
				if(g->mat2d[g->vertList[i]][j]!=INAN)
					if (g->mat2d[g->vertList[i]][j]>=realThresh || 
						(-1*g->mat2d[g->vertList[i]][j])>=realThresh)
						flagDisconnected=0;
			//Check column
			for(j=g->vertList[i]+1;j<g->numVerts;j++)
				if(g->mat2d[j][g->vertList[i]]!=INAN)
					if (g->mat2d[j][g->vertList[i]]>=realThresh || 
						(-1*g->mat2d[j][g->vertList[i]])>=realThresh)
						flagDisconnected=0;

			//If disconnected, don't show it
			if(flagDisconnected==1) {
				//printf("%d with label %s,",i,g->edgeLabels->list[i]);
				numDisplayVerts--;
			}
			else {
				tmp[count]=g->vertList[i];
				count++;
			}
		}
	}
	//printf("\n");
	if(numDisplayVerts>0) {
      tmpRealloc = realloc((void*)tmp,numDisplayVerts*sizeof(int));
      if(tmpRealloc==NULL) {
	      perror("filterVertsFailThresh() tmp");  return -1;
      }
      if(tmp != tmpRealloc) free(tmp);
		free(g->vertList);
		g->vertList=(int*)tmpRealloc;
	}
	else {free(g->vertList); g->vertList=NULL; free(tmp);}
	g->numDisplayVerts=numDisplayVerts;
	endTime=clock();
	VCB_INFO("  Verts-filterVertsFailThresh took %d ms\n",endTime-startTime);
	return g->numDisplayVerts;

}

//------------------------------------------------------------------------
// Removes edges from the current edgeList that fail the threshold
//------------------------------------------------------------------------
int filterEdgesFailThresh(float thresh, int absVal, graph* g) {
	int i, count, numDisplayEdges, realThresh;
	short int* tmp;
   void* tmpRealloc;

	realThresh=(int)(DENOM_THRESH*thresh);
	numDisplayEdges=g->numDisplayEdges;
	if(g->edgeList==NULL) return g->numDisplayEdges;
	tmp=(short int*)malloc(2*g->numDisplayEdges*sizeof(unsigned short));

	//printf("Vertices disconnected: ");
	count=0;
	if(absVal==0) {
		for(i=0;i<g->numDisplayEdges;i++)
			if(g->mat2d[g->edgeList[2*i]][g->edgeList[2*i+1]]>=realThresh) {
				tmp[2*count]=g->edgeList[2*i];
				tmp[2*count+1]=g->edgeList[2*i+1];
				count++;
			}
			else numDisplayEdges--;
	}
	else {
		for(i=0;i<g->numDisplayEdges;i++)
			if(g->mat2d[g->edgeList[2*i]][g->edgeList[2*i+1]]!=INAN)
				if(g->mat2d[g->edgeList[2*i]][g->edgeList[2*i+1]]>=realThresh 
					|| (-1*g->mat2d[g->edgeList[2*i]][g->edgeList[2*i+1]])>=realThresh) {
					tmp[2*count]=g->edgeList[2*i];
					tmp[2*count+1]=g->edgeList[2*i+1];
					count++;
				}
				else numDisplayEdges--;
	}
	//printf("\n");
	if(numDisplayEdges>0) {
      tmpRealloc = realloc((void*)tmp,2*numDisplayEdges*sizeof(unsigned short));
      if(tmpRealloc==NULL) {
	      perror("filterEdgesFailThresh() tmp");  return -1;
      }
      if(tmp != tmpRealloc) free(tmp);
		free(g->edgeList);
		g->edgeList=(unsigned short*)tmpRealloc;
	}
	else {free(g->edgeList); g->edgeList=NULL; free(tmp);}
	g->numDisplayEdges=numDisplayEdges;
	return g->numDisplayEdges;
}

//------------------------------------------------------------------------
// Filters the edgelist to contain only edges that connect to vertices
//   in the display list
//------------------------------------------------------------------------
int inducedSubgraph(float thresh, int absoluteValue, graph* g) {
	int i,j, idx,realThresh;
	unsigned short v1, v2;
   void* tmpRealloc;

	realThresh = (int)(DENOM_THRESH*thresh);

	//Not needed since realloc to smaller size
	if(g->edgeList!=NULL) free(g->edgeList);
	g->edgeList=(unsigned short*)malloc(2*g->numEdges*sizeof(unsigned short));
	idx=0;

	for(i=0;i<g->numDisplayVerts;i++) {
		v1=g->vertList[i];
		for(j=i+1;j<g->numDisplayVerts;j++) {
			v2=g->vertList[j];
			if(v1<v2) SWAP(v1,v2);
			if(g->mat2d[v1][v2]!=INAN) {
				if( g->mat2d[v1][v2]>realThresh ||
					(-1*g->mat2d[v1][v2]>realThresh && absoluteValue==1) ) {
					g->edgeList[2*idx]  = v1;
					g->edgeList[2*idx+1]= v2;
					printf("%d (%d,%d) = %d\n",idx,v1,v2,g->mat2d[v1][v2]);
					idx++;
				}
				else printf("rej (%d,%d) = %d\n",v1,v2,g->mat2d[v1][v2]);
			}
		}
	}

   if(idx>0) {
      tmpRealloc = realloc((void*)g->edgeList,2*idx*sizeof(unsigned short));
      if(tmpRealloc==NULL) {
	      perror("inducedSubgraph() g->edgeList");  return -1;
      }
      if(g->edgeList != tmpRealloc) free(g->edgeList);
		g->edgeList=(unsigned short*)tmpRealloc;
   }
	else { free(g->edgeList); g->edgeList=NULL; }
	g->numDisplayEdges = idx;
	return g->numDisplayEdges;
}

//------------------------------------------------------------------------
// Filters the edgelist to contain only edges that connect to vertices
//   with the same index of the given target
//------------------------------------------------------------------------
int filterInducedSubgraphShow(graph* g, int target) {
	int i, idx;
	unsigned short v1, v2;
   void* tmpRealloc;

	/*//Not needed since realloc to smaller size
	if(g->edgeList!=NULL) free(g->edgeList);
	g->edgeList=(unsigned short*)malloc(2*g->numEdges*sizeof(unsigned short));*/
	idx=0;
	for(i=0;i<g->numDisplayEdges;i++) {
		v1=g->edgeList[2*i]; v2=g->edgeList[2*i+1];
		if ( (g->vertColorList[v1]==target) &&
			 (g->vertColorList[v2]==target) ) {
			g->edgeList[2*idx]=v1;
			g->edgeList[2*idx+1]=v2;
			idx++;
		}//else don't count this data and replace it by the next edge that exists
	}
   if(idx>0) {
      tmpRealloc = realloc((void*)g->edgeList,2*idx*sizeof(unsigned short));
      if(tmpRealloc==NULL) {
	      perror("inducedSubgraph() g->edgeList");  return -1;
      }
      if(g->edgeList != tmpRealloc) free(g->edgeList);
		g->edgeList=(unsigned short*)tmpRealloc;
   }
	else { free(g->edgeList); g->edgeList=NULL; }
	g->numDisplayEdges = idx;
	return g->numDisplayEdges;
}

//------------------------------------------------------------------------
// Filters the edgelist to show edges that connect to any vertices
//   except those of the given color index
//------------------------------------------------------------------------
int filterInducedSubgraphAllButColor(graph* g, int turnOffColor) {
	int i, idx;
	unsigned short v1, v2;
   void* tmpRealloc;

	/*//Not needed since realloc to smaller size
	if(g->edgeList!=NULL) free(g->edgeList);
	g->edgeList=(unsigned short*)malloc(2*g->numEdges*sizeof(unsigned short));*/
	idx=0;
	for(i=0;i<g->numDisplayEdges;i++) {
		v1=g->edgeList[2*i]; v2=g->edgeList[2*i+1];
		if ( (g->vertColorList[v1]!=turnOffColor) &&
			 (g->vertColorList[v2]!=turnOffColor) ) {
			g->edgeList[2*idx]=v1;
			g->edgeList[2*idx+1]=v2;
			idx++;
		}//else don't count this data and replace it by the next edge that exists
	}
   if(idx>0) {
      tmpRealloc = realloc((void*)g->edgeList,2*idx*sizeof(unsigned short));
      if(tmpRealloc==NULL) {
	      perror("inducedSubgraph() g->edgeList");  return -1;
      }
      if(g->edgeList != tmpRealloc) free(g->edgeList);
		g->edgeList=(unsigned short*)tmpRealloc;
   }
	else { free(g->edgeList); g->edgeList=NULL; }
	g->numDisplayEdges = idx;
	return g->numDisplayEdges;
}

//------------------------------------------------------------------------
// For outputting the vertex equation to the screen
//------------------------------------------------------------------------
void getDisplayEquation(int numFeatures,float* fltHyp,char** strHyp){
	int i;
	
	char equation[2048]={0}; char tmp[2048]={0};
	sprintf(equation, "VQ(8): ", numFeatures);
	for(i=0;i<numFeatures;i++) {
		if (i!=0) strcat(equation," | ");
		sprintf(tmp,"F%d [%.0f,%.0f]", i, fltHyp[2*i],fltHyp[2*i+1]);
		strcat(equation,tmp);
	}
	if ((*strHyp)!=NULL) free(*strHyp);
	(*strHyp)=(char*)malloc((strlen(equation)+1)*sizeof(char));
	strcpy(*strHyp,equation);
}

//------------------------------------------------------------------------
// For getting the strings for all querying equations/hypotheses
//------------------------------------------------------------------------
void getAllDisplayEquations(int numQueries,int numFeatures,float** fltHyp,char*** strHyp){
	int i;
	for(i=0;i<numQueries;i++)
		getDisplayEquation(numFeatures,fltHyp[i],strHyp[i]);
}

//------------------------------------------------------------------------
// Get the minimum and maximum of the given feature
//------------------------------------------------------------------------
void getMinMax(graph* g, int featureNum, float* min, float* max) {
	int i, vertData;
	(*min)=FLT_MAX; (*max)=FLT_MIN;
   if(g->vertData==NULL) return;
	for(i=0;i<g->numVerts;i++) {
		vertData=(g->numVertFeatures+1)*i;
		//printf("VertData[%d]=%f\n",vertData+featureNum,g->vertData[vertData+featureNum]);
		if(g->vertData[vertData+featureNum]>(*max))
			(*max)=g->vertData[vertData+featureNum];
		if(g->vertData[vertData+featureNum]<(*min))
			(*min)=g->vertData[vertData+featureNum];
	}
	VCB_INFO("Min=%f,Max=%f\n",(*min),(*max));
}

//------------------------------------------------------------------------
// Print min/max weight of the graph
//------------------------------------------------------------------------
void printMinMaxWeight(graph* g, int absoluteValue) {
	int v1,v2;
	short int value,min,max;

	min=SHRT_MAX; max=SHRT_MIN;
	if(g->mat2d==NULL) {
		printf("  printMinMax(): Data doesn't exist\n");
		exit(-1);
	}

	for(v1=0;v1<g->numVerts;v1++) {
		for(v2=0;v2<g->numVerts;v2++) {
			if(v1<v2) value=g->mat2d[v2][v1];
			else if (v2>v1) value=g->mat2d[v1][v2];
			else value=INAN; //on diagonal

			if(value!=INAN) {
				if (value<0 && absoluteValue==1) value*=-1;
				if (value>max) max=value;
				if (value<min) min=value;
			}
		}
	}

	printf("  Min = %f, Max=%f\n",min/DENOM_THRESH,max/DENOM_THRESH);
}

//------------------------------------------------------------------------
// Shows all nodes using the given graph
//------------------------------------------------------------------------
int showAllVerts(graph* g) {
	int i;
	//clock_t startTime,endTime;
	//startTime=clock();
	if(g->vertList!=NULL) free(g->vertList);
	g->vertList=(int*)malloc(g->numVerts*sizeof(int));
	if(g->vertList==NULL) {
		perror("showAllVerts(): g->vertList"); exit(-1);
	}
	for(i=0;i<g->numVerts;i++) g->vertList[i]=i;
	g->numDisplayVerts=g->numVerts;
	//endTime=clock();
	//VCB_INFO("  Vert-ShowAll took %d ms\n",endTime-startTime);
	return g->numDisplayVerts;
}

//------------------------------------------------------------------------
// Shows all edges in the given graph
//------------------------------------------------------------------------
int showAllEdges(graph* g) {
	int i,j,index;
	//clock_t startTime,endTime;
	//startTime=clock();
	if(g->numEdges==0) return 0;

	if(g->edgeList!=NULL) free(g->edgeList);
	g->edgeList=(unsigned short*)malloc(2*g->numEdges*sizeof(unsigned short));
	if(g->edgeList == NULL) {
		perror("showAllEdges() edgeList"); exit(-1);
	}
	index=0;
	for(i=0;i<g->numVerts;i++) {
		for(j=0;j<i;j++) {
			if(g->mat2d[i][j]!=INAN) {
				g->edgeList[2*index]   = i;
				g->edgeList[2*index+1] = j;
				index++;
			}
		}
	}
	if(index != g->numEdges) {
		printf("  ShowAllEdges() error - mismatched sizes (%d!=%d)\n",index,g->numEdges);
		exit(-1);
	}
	g->numDisplayEdges=g->numEdges;
	//endTime=clock();
	//VCB_INFO("  Vert-ShowAll took %d ms\n",endTime-startTime);
	return g->numDisplayEdges;
}

//------------------------------------------------------------------------
// Shows the entire graph
//------------------------------------------------------------------------
void showAll(graph* g, int colorIndex) {
	int i,j,index;
	
	/*//Not necessary since vertColorList has constant maximum size
	if(g->vertColorList!=NULL) free(g->vertColorList);
	if((g->vertColorList=(int*)malloc(g->numVerts*sizeof(int))) == NULL) {
		perror("showAll() vertColorList"); exit(-1);
	}*/
	for(i=0;i<g->numVerts;i++) g->vertColorList[i]=colorIndex;

	if(g->vertList!=NULL) free(g->vertList);
	if(g->edgeList!=NULL) free(g->edgeList);

	if((g->vertList=(int*)malloc(g->numVerts*sizeof(int))) == NULL) {
		perror("showAll() vertList"); exit(-1);
	}
	for(i=0;i<g->numVerts;i++) g->vertList[i]=i;

	if((g->edgeList=(unsigned short*)malloc(2*g->numEdges*sizeof(unsigned short))) == NULL) {
		perror("showAll() edgeList"); exit(-1);
	}
	index=0;
	for(i=0;i<g->numVerts;i++) {
		for(j=0;j<i;j++) {
			if(g->mat2d[i][j]!=INAN) {
				g->edgeList[2*index]   = i;
				g->edgeList[2*index+1] = j;
				index++;
			}
		}
	}
	g->numDisplayVerts = g->numVerts;
	g->numDisplayEdges = g->numEdges;
}

//------------------------------------------------------------------------
// Shows only induced subgraph of the the largest connected component
//------------------------------------------------------------------------
/*int filterInducedSubgraphLCC(graph* g) {
	int i,j,v1,v2,count;

	if(g->edgeList!=NULL) free(g->edgeList);
	g->edgeList=(unsigned short*)malloc(2*g->numEdges*sizeof(unsigned short));
	if(g->edgeList==NULL) {perror("filterInducedSubgraphLCC()"); exit(-1);}

	count=0;
	for(i=0;i<g->numDisplayVerts;i++) {
		for(j=i+1;j<g->numDisplayVerts;j++) {
			v1=g->vertList[i];
			v2=g->vertList[j];
			if(g->vertColorList[v1]>0 && g->vertColorList[v2]>0) {
				g->edgeList[2*count]  = (unsigned short)v1;
				g->edgeList[2*count+1]= (unsigned short)v2;
				count++;
			}
		}
	}

	if(count>0) realloc(g->edgeList,2*count*sizeof(unsigned short));
	else {free(g->edgeList); g->edgeList=NULL;}
	g->numDisplayEdges = count;
	return count;
}*/

//------------------------------------------------------------------------
// Shows only nodes that constitute the largest connected component
//------------------------------------------------------------------------
int showLCC(float thresh, int absVal, graph* g) {
	int i, j, k, count, realThresh;
	short int currentLabel, maxLabel, maxCount, maxLCC;
	short int *nodeLabel, *labelCount;
   void* tmpRealloc;
	clock_t startTime, endTime;

	startTime=clock();
	currentLabel=1;
	nodeLabel=(short int*)malloc(g->numVerts*sizeof(short int));
	for(i=0;i<g->numVerts;i++) nodeLabel[i]=0;
	realThresh=(int)(DENOM_THRESH*thresh);

	if(absVal==0) {
		for(i=0;i<g->numVerts;i++)
			for(j=0;j<i;j++)
				if(g->mat2d[i][j]>=realThresh) {
					if(nodeLabel[i]==0 && nodeLabel[j]==0) {
						nodeLabel[i]=currentLabel;
						nodeLabel[j]=currentLabel;
						currentLabel++;
					}
					else if(nodeLabel[i]==0 && nodeLabel[j]!=0) {
						nodeLabel[i]=nodeLabel[j];
					}
					else if(nodeLabel[i]!=0 && nodeLabel[j]==0) {
						nodeLabel[j]=nodeLabel[i];
					}
					else if(nodeLabel[i]!=nodeLabel[j]) {
						for(k=0;k<g->numVerts;k++)
							if(nodeLabel[k]==nodeLabel[j])
								nodeLabel[k]=nodeLabel[i];
					}
					//else they're the same and non-zero, do nothing
				}
	}
	else {
		for(i=0;i<g->numVerts;i++)
			for(j=0;j<i;j++)
				if(g->mat2d[i][j]!=INAN) {
					if(g->mat2d[i][j]>=realThresh || (-1*g->mat2d[i][j])>=realThresh) {
						if(nodeLabel[i]==0 && nodeLabel[j]==0) {
							nodeLabel[i]=currentLabel;
							nodeLabel[j]=currentLabel;
							currentLabel++;
						}
						else if(nodeLabel[i]==0 && nodeLabel[j]!=0) {
							nodeLabel[i]=nodeLabel[j];
						}
						else if(nodeLabel[i]!=0 && nodeLabel[j]==0) {
							nodeLabel[j]=nodeLabel[i];
						}
						else if(nodeLabel[i]!=nodeLabel[j]) {
							for(k=0;k<g->numVerts;k++)
								if(nodeLabel[k]==nodeLabel[j])
									nodeLabel[k]=nodeLabel[i];
						}
						//else they're the same and non-zero, do nothing
					}
				}
	}

	maxLabel=currentLabel;
	currentLabel=maxCount=0;
	labelCount=(short int*)malloc(maxLabel*sizeof(short int));
	for(i=0;i<maxLabel;i++) labelCount[i]=0;

	for(i=0;i<g->numVerts;i++) labelCount[nodeLabel[i]]++;
	//for(i=0;i<maxLabel;i++) printf("  Cluster %d has %d\n",i,labelCount[i]);
	for(i=0;i<maxLabel;i++)
		if(labelCount[i]>maxCount && i!=0) {
			maxLCC=i;
			maxCount=labelCount[i];
		}
	//printf("  Cluster %d is LCC with %d vertices\n",maxLCC,maxCount);
	
	if(g->vertList!=NULL) free(g->vertList);
	g->vertList=(int*)malloc(g->numVerts*sizeof(int));
	count=0;
	for(i=0;i<g->numVerts;i++) {
		if(nodeLabel[i]==maxLCC) {
			g->vertList[count]=i;
			count++;
		}
	}
   if(count>0) {
      tmpRealloc = realloc((void*)g->vertList,count*sizeof(int));
      if(tmpRealloc==NULL) {
	      perror("showLCC() g->vertList");  return -1;
      }
		if(g->vertList != tmpRealloc) free(g->vertList);
		g->vertList=(int*)tmpRealloc;
   }
	else {free(g->vertList); g->vertList=NULL;}
	g->numDisplayVerts=maxCount;

	free(nodeLabel);
	free(labelCount);
	endTime=clock();
	VCB_INFO("  Vert-ShowLCC took %d ms\n",endTime-startTime);
	return g->numDisplayVerts;
}

//------------------------------------------------------------------------
// Makes all voxels in the voxel list visible
//------------------------------------------------------------------------
void updateVoxelVisibility(unsigned char** voxels, int failColor, graph* g) {
	int i;
	for(i=0;i<g->numVerts;i++)
		(*voxels)[i*10]=(unsigned char)failColor;
	for(i=0;i<g->numDisplayVerts;i++)
		(*voxels)[g->vertList[i]*10]=(unsigned char)g->vertColorList[g->vertList[i]];

	//Fixed this hack by assigning vertColorList to -1 for non-existent vertices
	/*for(i=0;i<g->numVerts;i++) {
		if( (*voxels)[i*10]!=(unsigned char)255 && 
			(*voxels)[i*10]!=(unsigned char)130 && 
			(*voxels)[i*10]!=(unsigned char)3)
		{
			(*voxels)[i*10]=(unsigned char)failColor;
		}
	}*/
}

//------------------------------------------------------------------------
//This function creates a 1D to 2D lookup for edges (to know its vertices)
//------------------------------------------------------------------------
void BuildLookup(graph* g) {
	int idx;
   unsigned short i, j;
   void* tmpRealloc;

	g->tl1d2=(unsigned short*)malloc(2*g->numEdges*sizeof(unsigned short));
   if(g->tl1d2==NULL) {
      perror("BuildLookup(): g->tl1d2"); return;
   }
   idx=0;
	for(i=0;i<g->numVerts;i++)
		for(j=0;j<i;j++)
			if(g->mat2d[i][j]!=INAN) {
				g->tl1d2[2*idx]=i;
				g->tl1d2[2*idx+1]=j;
				idx++;
			}

   tmpRealloc = realloc((void*)g->tl1d2,2*idx*sizeof(unsigned short));
   if(tmpRealloc==NULL) {
	   perror("BuildLookup() g->tl1d2");  return;
   }
	if(g->tl1d2 != tmpRealloc) free(g->tl1d2);
	g->tl1d2=(unsigned short*)tmpRealloc;
}

float* ReadFeatures(char* filename, int numElem, int* numFeat) {
	int i,j,idx,numFeatures,numElements;
	FILE* fp;
	float* data;
	
	fp = fopen(filename,"r");
	if(fp==NULL) {
		printf("Error: can't access %s.\n", filename);
		return NULL;
	}
	else { //we can open the file and proceed loading the data
		fscanf(fp,"%d %d",&(numElements),&(numFeatures));
		*numFeat = numFeatures;
		printf(" Reading %s, %d elements, %d features\n",filename,numElements,numFeatures);
		if(numElem!=numElements) {
			printf("  %s does not match expected number of data elements\n");
		}

		data = (float*) malloc (numElements*(numFeatures+1)*sizeof(float));
		if(data==NULL) { perror("ReadFeatures"); exit(-1);}
		idx=0;
		for(i=0;i<numElements;i++) {
			for(j=0;j<numFeatures;j++) {
				fscanf(fp,"%f ",&(data[idx]));
				idx++;
			}
			memcpy(&(data[idx]), &i, sizeof(int));
			idx++;
		}
	}
	fclose(fp);

	/*idx = 0;
	printf("Vert %d = {",idx);
	for(i=0;i<numFeatures;i++) printf("%f, ",data[idx*(numFeatures+1)+i]);
	memcpy(&idx,&(data[idx*(numFeatures+1)+numFeatures]),sizeof(int));
	printf("} = data[%d]=%d\n\n",idx*(numFeatures+1)+numFeatures,idx);
	idx = 1;
	printf("Vert %d = {",idx);
	for(i=0;i<numFeatures;i++) printf("%f, ",data[idx*(numFeatures+1)+i]);
	memcpy(&idx,&(data[idx*(numFeatures+1)+numFeatures]),sizeof(int));
	printf("} = data[%d]=%d\n\n",idx*(numFeatures+1)+numFeatures,idx);
	idx = numElements-1;
	printf("Vert %d = {",idx);
	for(i=0;i<numFeatures;i++) printf("%f, ",data[idx*(numFeatures+1)+i]);
	memcpy(&idx,&(data[idx*(numFeatures+1)+numFeatures]),sizeof(int));
	printf("} = data[%d]=%d\n\n",idx*(numFeatures+1)+numFeatures,idx);*/

	return data;
}

float* ReadFeaturesAndMap(char* filename, char* filemap, graph* g) {
	int i,j,map,idx,numFeatures,numElements,err;
	float* data;
	char key[1024];
	FILE *fp,*fp2;
	
	fp = fopen(filename,"r");
	fp2 = fopen(filemap,"r");
	if(fp==NULL) {
		printf("Error: can't access %s.\n", filename);
		return NULL;
	} else if(fp2==NULL) {
		printf("Error: can't access %s.\n", filemap);
		return NULL;
	} else { //we can open the file and proceed loading the data
		fscanf(fp,"%d %d",&(numElements),&(numFeatures));
		if(g->numVerts!=numElements) {
			printf("  %s doesn't match, %d!=%d\n",g->numVerts,numElements);
			return NULL;
		}
		g->numVertFeatures = numFeatures;
		printf(" Reading %s, %d elements, %d features...",filename,numElements,numFeatures);

		data = (float*) malloc (numElements*(numFeatures+1)*sizeof(float));
		if(data==NULL) { perror("ReadFeatures"); exit(-1);}
		idx=0;
		for(i=0;i<numElements;i++) {
			for(j=0;j<numFeatures;j++) {
				err=fscanf(fp,"%f ",&(data[idx]));
				idx++;
			}
			fscanf(fp2,"%s ",&key);
			map = (int)ll_getIndex(g->edgeLabels, key, &err);
			if(map==0 && err!=0) {printf(" Error %d: %s has unknown map\n",err,key); exit(-1);}
			memcpy(&(data[idx]), &map, sizeof(int));
			idx++;
		}
	}
	fclose(fp); fclose(fp2);
	printf("done\n");

	/*idx = 0;
	printf("Vert %d = {",idx);
	for(i=0;i<numFeatures;i++) printf("%f, ",data[idx*(numFeatures+1)+i]);
	memcpy(&idx,&(data[idx*(numFeatures+1)+numFeatures]),sizeof(int));
	printf("} = data[%d]=%d\n\n",idx*(numFeatures+1)+numFeatures,idx);
	idx = 1;
	printf("Vert %d = {",idx);
	for(i=0;i<numFeatures;i++) printf("%f, ",data[idx*(numFeatures+1)+i]);
	memcpy(&idx,&(data[idx*(numFeatures+1)+numFeatures]),sizeof(int));
	printf("} = data[%d]=%d\n\n",idx*(numFeatures+1)+numFeatures,idx);
	idx = numElements-1;
	printf("Vert %d = {",idx);
	for(i=0;i<numFeatures;i++) printf("%f, ",data[idx*(numFeatures+1)+i]);
	memcpy(&idx,&(data[idx*(numFeatures+1)+numFeatures]),sizeof(int));
	printf("} = data[%d]=%d\n\n",idx*(numFeatures+1)+numFeatures,idx);*/

	return data;
}

//------------------------------------------------------------------------
//This function loads data and creates the btree to be queried
//------------------------------------------------------------------------
void loadVertData(char* filename, graph* g) {
	int i, m, n;//, idx, edgeID;
	char *filenameMap, *filenameLabels;
   char key[1024];
   float* tmp;
	clock_t startTime,endTime;
   FILE* fp;

	startTime=clock();	m=4; n=3;

	filenameMap=(char*)malloc( (strlen(filename)+1)*sizeof(char) );
	strcpy(filenameMap,filename);
	strcpy(&filenameMap[strlen(filename)-4],".map");

	g->vertData = ReadFeaturesAndMap(filename, filenameMap, g);
   tmp=(float*)malloc(g->numVerts*(g->numVertFeatures+1)*sizeof(float));
   if(tmp==NULL) {
      perror("loadVertData(): tmp");
      return;
   }
   memcpy(tmp,g->vertData, g->numVerts*(g->numVertFeatures+1)*sizeof(float));

	//Build Vertex Tree
	printf("  Building Vert Tree (%d recs, %d feats)...",g->numVerts,g->numVertFeatures);
	g->vertRoot = (VCB_mntree)vcbBuildBtree(g->numVerts,g->numVertFeatures,(void*)g->vertData,m,n);
	endTime=clock();
	printf("built in %d ms\n",endTime-startTime);
   if(g->numVerts!=vcbMntreeStat(g->vertRoot)) {
      printf("ERROR: Search tree only contains %d of %d items\n",vcbMntreeStat(g->vertRoot),g->numVerts);
      printf("  Recommend changing m and n\n");
   }
   
   //Release sorted data and get original data back
   //free(g->vertData);
   g->vertData=tmp;

	//Check for new labels
	g->vertLabelAlias=0;
	filenameLabels=(char*)malloc((strlen(filenameMap)+8)*sizeof(char));
	if(filenameLabels==NULL) {
		perror("loadVertData() filenameLabels"); exit(-1);
	}
	strcpy(filenameLabels,filenameMap);
	strcpy(&(filenameLabels[strlen(filenameMap)-4]),"_labels.map");
   printf("  Custom labels at %s?",filenameLabels);
	fp=fopen(filenameLabels,"r");
	if(fp!=NULL) {
      printf(" Yes.\n");
      g->vertLabelAlias=1;
      g->vertLabels=(char**)malloc(g->numVerts*sizeof(char*));
      if(g->vertLabels==NULL) {
         perror("loadVertData() vertLabels"); exit(-1);
      }

      for(i=0;i<g->numVerts;i++) {
			fscanf(fp,"%s ",&key);
         g->vertLabels[i]=(char*)malloc((strlen(key)+1)*sizeof(char));
         if(g->vertLabels==NULL) {
            perror("loadVertData() vertLabels[]"); exit(-1);
         }
         strcpy(g->vertLabels[i],key);
      }

      fclose(fp);
	}
   else {
      printf(" No.\n");
   }

	/*
	//Build Edge Tree
	startTime=clock(); g->numEdgeFeatures=1; idx=edgeID=0;
	printf("  Building Edge Tree (%d recs, %d feats)...",g->numEdges,g->numEdgeFeatures);
	g->edgeData=(float*)malloc(g->numEdges*(g->numEdgeFeatures+1)*sizeof(float));
	for (j=0;j<g->numVerts;j++) {
		for(k=0;k<j;k++) {
			if(g->mat2d[j][k]!=INAN) {
				g->edgeData[idx]=(float)g->mat2d[j][k]/DENOM_THRESH;
				idx++;
				memcpy(&(g->edgeData[idx]), &edgeID, sizeof(int));
				idx++; edgeID++;
			}
		}
	}
	g->edgeRoot = (VCB_mntree)vcbBuildBtree(g->numEdges,g->numEdgeFeatures,(void*)g->edgeData,m,n);
	endTime=clock();
	printf("built in %d secs\n",(endTime-startTime)/CLOCKS_PER_SEC);
	*/
}

//------------------------------------------------------------------------
//This function creates the btree to be queried
//------------------------------------------------------------------------
void BuildTree(int numFeatures, graph* g) {
	int i, m, n;//, idx, edgeID;
   int min,max;
	//unsigned short j, k;
	clock_t startTime,endTime;

	startTime=clock();	m=4; n=3; g->numVertFeatures=numFeatures;
	//Build Vertex Tree
	printf("  Building Vert Tree (%d recs, %d feats)...",g->numVerts,g->numVertFeatures);
	//Allocate data space - +1 for the index (since using a tree)
	g->vertData=(float*)malloc(g->numVerts*(g->numVertFeatures+1)*sizeof(float));
   if(g->vertData==NULL) perror("BuildTree(): g->vertData");

   //If all values same (fully connected graph) then make all different
   getMinMaxiv(g->numVerts,g->degree[0],&min,&max);
   if( min==max) {
	   for (i=0;i<g->numVerts;i++) {
		   g->vertData[(g->numVertFeatures+1)*i]=(float)i;
		   memcpy(&(g->vertData[(g->numVertFeatures+1)*i+1]), &i, sizeof(int));
	   }   
   }
   //else just use degree of original graph
   else {
	   for (i=0;i<g->numVerts;i++) {
		   g->vertData[(g->numVertFeatures+1)*i]=(float)g->degree[0][i];
		   memcpy(&(g->vertData[(g->numVertFeatures+1)*i+1]), &i, sizeof(int));
	   }
   }
	g->vertRoot = (VCB_mntree)vcbBuildBtree(g->numVerts,g->numVertFeatures,(void*)g->vertData,m,n);
	endTime=clock();
	printf("built in %d ms\n",endTime-startTime);
   if(g->numVerts!=vcbMntreeStat(g->vertRoot)) {
      printf("ERROR: Search tree only contains %d of %d items\n",vcbMntreeStat(g->vertRoot),g->numVerts);
      printf("  Recommend changing m and n\n");
   }

   /*
	//Build Edge Tree
	startTime=clock(); g->numEdgeFeatures=1; idx=edgeID=0;
	printf("  Building Edge Tree (%d recs, %d feats)...",g->numEdges,g->numEdgeFeatures);
	g->edgeData=(float*)malloc(g->numEdges*(g->numEdgeFeatures+1)*sizeof(float));
	for (j=0;j<g->numVerts;j++) {
		for(k=0;k<j;k++) {
			if(g->mat2d[j][k]!=INAN) {
				g->edgeData[idx]=(float)g->mat2d[j][k]/DENOM_THRESH;
				idx++;
				memcpy(&(g->edgeData[idx]), &edgeID, sizeof(int));
				idx++; edgeID++;
			}
		}
	}
	g->edgeRoot = (VCB_mntree)vcbBuildBtree(g->numEdges,g->numEdgeFeatures,(void*)g->edgeData,m,n);
	endTime=clock();
	printf("built in %d secs\n",(endTime-startTime)/CLOCKS_PER_SEC);
	*/
}

//------------------------------------------------------------------------
//This function will run the b-tree query to see which vertices meet the criteria
//------------------------------------------------------------------------
int RunVertQuery(graph* g) {
	int i,j, queryNumResults,newCount;
   int *queryList, *vlist;
	float *lb, *ub;
	clock_t startTime,endTime;

	VCB_DEBUG_CODE {printf("Running b-tree query...\n");}
	startTime=clock();
	lb = (float*)malloc(g->numVertFeatures*sizeof(float));
	ub = (float*)malloc(g->numVertFeatures*sizeof(float));
   if(lb==NULL || ub==NULL) {
      perror("RunVertQuery(): lb/ub"); return -1;
   }

   //Use colorList as a hash for combining multi-query results
   for(i=0;i<g->numVerts;i++) {
      g->vertColorList[i]=-1;
   }

   //Give priority/coloring to top query
   for(i=g->numQueries-1;i>=0;i--) {
      for(j=0; j<g->numVertFeatures; j++) {
		    lb[j]=(float)(g->fltQuery[i][2*j]-(1e-4));//Min
		    ub[j]=(float)(g->fltQuery[i][2*j+1]+(1e-4));//Max
		    //printf("lb[%d]=%f,up[%d]=%f\n",j,lb[j],j,ub[j]);
		  }
      queryNumResults=vcbQueryBtree(g->vertRoot,lb,ub,&queryList);
      //printf("Results returned - %d\n",queryNumResults);

      for(j=0;j<queryNumResults;j++) {
         g->vertColorList[queryList[j]]=i;
      }
   }

   vlist=(int*)malloc(g->numVerts*sizeof(int));
   if(vlist==NULL) {
      perror("RunVertQuery(): vlist"); return -1;
   }

   //Calculate new query results
   newCount=0;
   for(i=0;i<g->numVerts;i++) {
      if(g->vertColorList[i]>-1) {
         vlist[newCount]=i;
         g->vertColorList[i]=g->queryColors[g->vertColorList[i]];
         newCount++;
      }
   }

   g->numDisplayVerts=newCount;
  	if(g->vertList!=NULL) free(g->vertList);
   g->vertList=(int*)malloc(newCount*sizeof(int));
   if(g->vertList==NULL) {
      perror("RunVertQuery(): g->vertList"); return -1;
   }
   memcpy(g->vertList,vlist,newCount*sizeof(int));

   /*
	//Clustering
	printf("Clustering %d items...\n",tree.numPass);
	if (tree.cluster != NULL) free(tree.cluster);
	tree.cluster = (int*)malloc(tree.numPass*sizeof(int));
    // gets the microseconds passed since app started
    gettimeofday(&startTime, NULL);
	tree.numClusters=Cluster((void **)tree.fiber, tree.cluster, tree.numPass, ClusterFunc,tree.clusterThresh);
	*/
	//View all results
	/*for(i=0;i<tree.numPass;i++)
		printf("%d=%d ",i,tree.cluster[i]);*/
	endTime=clock();
	VCB_INFO("  Vert Query took %d ms\n",endTime-startTime);
	free(lb); free(ub); free(vlist);
	return g->numDisplayVerts;
}

//------------------------------------------------------------------------
//This function will run the b-tree query to see which vertices meet the criteria
//------------------------------------------------------------------------
int RunVertQuery_deprecated(graph* g) {
	int i,j,k, alreadyExists,appendCount,newCount;
	int *appendList, *newList;  //Add to Vert display list (subsequent queries)
	float *lb, *ub;
	clock_t startTime,endTime;
	// struct for the time value
    //clock_t startTime, currentTime;

	VCB_DEBUG_CODE {printf("Running b-tree query...\n");}
	startTime=clock();
	lb = (float*)malloc(g->numVertFeatures*sizeof(float));
	ub = (float*)malloc(g->numVertFeatures*sizeof(float));

	//Testing/debug printout
	for(i=0; i<g->numVertFeatures; i++) {
		lb[i]=(float)(g->fltQuery[0][2*i]-(1e-4));//Min
		ub[i]=(float)(g->fltQuery[0][2*i+1]+(1e-4));//Max
		//printf("lb[%d]=%f,up[%d]=%f\n",i,lb[i],i,ub[i]);
	}

	if(g->vertList!=NULL) free(g->vertList);
	g->numDisplayVerts=vcbQueryBtree(g->vertRoot,lb,ub,&(g->vertList));
	VCB_INFO("  numVerts=%d, numPassed=%d\n",g->numVerts,g->numDisplayVerts);
	//View all results
	/*for(i=0;i<g->numDisplayVerts;i++)
		printf("%d ",g->vertList[i]);
	*/

	//Make all vertices invisible except those that match query 0
	for(i=0;i<g->numVerts;i++) {
		g->vertColorList[i]=-1;
	}
	for(i=0;i<g->numDisplayVerts;i++) {
		g->vertColorList[g->vertList[i]]=g->queryColors[0];
	}

	//RUN OTHER QUERIES AND APPEND NEW ITEMS
	//Memory allocation
	newCount=0;
	newList=NULL;
	appendCount=0;
	//assume worst case (a query may return all vertices in the graph)
	if((appendList=(int*)malloc(g->numVerts*sizeof(int))) == NULL) {
		perror("appendList allocation");
		exit(1);
	}

	//Run the other queries and store any new results
	for(j=1;j<g->numQueries;j++) {
		VCB_DEBUG_CODE {printf("Running b-tree query %d...\n",j);}
		if(newList!=NULL) free(newList);

		//Testing/debug printout
		for(i=0; i<g->numVertFeatures; i++) {
			lb[i]=(float)(g->fltQuery[j][2*i]-(1e-4));//Min
			ub[i]=(float)(g->fltQuery[j][2*i+1]+(1e-4));//Max
			//printf("lb[%d]=%f,up[%d]=%f\n",i,lb[i],i,ub[i]);
		}
		newCount=vcbQueryBtree(g->vertRoot,lb,ub,&(newList));

		//Find all new items
		for(i=0; i<newCount; i++) {

			//Is current vertex covered by first query?
			alreadyExists=0;
			for(k=0;k<g->numDisplayVerts;k++) {
				if(newList[i]==g->vertList[k]) {
					alreadyExists=1;
					break;
				}
			}

			//Is current vertex covered by another previous query
			if(alreadyExists==0) {
				for(k=0;k<appendCount;k++) {
					if(newList[i]==appendList[k]) {
						alreadyExists=1;
						break;
					}
				}
			}

			//If not, we need to change color appropriately and add to list
			if(alreadyExists==0) {
				g->vertColorList[newList[i]]=g->queryColors[j];
				appendList[appendCount]=newList[i];
				appendCount++;
			}
		}

		VCB_INFO("  numPassed=%d, newListSize=%d\n",newCount,g->numDisplayVerts+appendCount);
		if(newList!=NULL) free(newList);
		newList=NULL;
	}

	//Put all new items in our display list
	if((newList=(int*)malloc( (g->numDisplayVerts+appendCount)*sizeof(int))) == NULL) {
		perror("RunVertQuery() newList allocation"); exit(-1);
	}
	memcpy(newList,g->vertList,g->numDisplayVerts*sizeof(int)); //copy old list (query 0)
	memcpy(&(newList[g->numDisplayVerts]),appendList,appendCount*sizeof(int)); //append new list (queries 1+)
	g->numDisplayVerts+=appendCount;
	//printf("Error unless %d=%d after query\n",appendList[appendCount-1],newList[g->numDisplayVerts-1]);
	free(g->vertList);	free(appendList); //free old and new list, respectively
	g->vertList = newList;
	
	/*
	//Clustering
	printf("Clustering %d items...\n",tree.numPass);
	if (tree.cluster != NULL) free(tree.cluster);
	tree.cluster = (int*)malloc(tree.numPass*sizeof(int));
    // gets the microseconds passed since app started
    gettimeofday(&startTime, NULL);
	tree.numClusters=Cluster((void **)tree.fiber, tree.cluster, tree.numPass, ClusterFunc,tree.clusterThresh);
	gettimeofday(&currentTime, NULL);
	printf("  %d clusters in %d seconds\n",tree.numClusters,currentTime.tv_sec-startTime.tv_sec);
	*/
	//View all results
	/*for(i=0;i<tree.numPass;i++)
		printf("%d=%d ",i,tree.cluster[i]);*/
	endTime=clock();
	VCB_INFO("  Vert Query took %d ms\n",endTime-startTime);
	free(lb); free(ub);
	return g->numDisplayVerts;
}

//------------------------------------------------------------------------
//This function will run the b-tree query to see which edges meet the criteria
//------------------------------------------------------------------------
int RunEdgeQuery(float thresh, int absVal, graph* g) {
	int i, appendCount;
	float *lb, *ub;
	int *appendEdgeList,*newEdgeList;
	clock_t startTime,endTime;

	VCB_INFO("Running b-tree query...\n");
	startTime=clock();
	lb = (float*)malloc(g->numEdgeFeatures*sizeof(float));
	ub = (float*)malloc(g->numEdgeFeatures*sizeof(float));

	//Original Query
	for(i=0; i<g->numEdgeFeatures; i++) { lb[i]=thresh; ub[i]=1.f; }
	if(g->edgeList1d!=NULL) free(g->edgeList1d);
	g->numDisplayEdges=vcbQueryBtree(g->edgeRoot,lb,ub,&(g->edgeList1d));

	//Append query operations (assumes disjoint)
	if(absVal) {
		//Query
		for(i=0; i<g->numEdgeFeatures; i++) { lb[i]=-1.f; ub[i]=-thresh; }
		appendEdgeList=NULL;
		appendCount=vcbQueryBtree(g->edgeRoot,lb,ub,&(appendEdgeList));
		
		//Malloc and copy over since realloc won't work for this size
		newEdgeList=(int*)malloc((g->numDisplayEdges+appendCount)*sizeof(int));
		memcpy(newEdgeList,g->edgeList1d,g->numDisplayEdges*sizeof(int));
		memcpy(newEdgeList+g->numDisplayEdges,appendEdgeList,appendCount*sizeof(int));
		free(g->edgeList1d); free(appendEdgeList);
		g->edgeList1d=newEdgeList;
		g->numDisplayEdges+=appendCount;
	}

	//Convert 1d to 2D edgelist using table lookup
	if(g->edgeList!=NULL) free(g->edgeList);
	g->edgeList=(unsigned short*)malloc(2*g->numDisplayEdges*sizeof(unsigned short));
	for(i=0;i<g->numDisplayEdges;i++) {
		g->edgeList[2*i]=g->tl1d2[2*g->edgeList1d[i]];
		g->edgeList[2*i+1]=g->tl1d2[2*g->edgeList1d[i]+1];
	}

	VCB_INFO("  numEdges=%d, numPassed=%d\n",g->numEdges,g->numDisplayEdges);
	free(lb); free(ub);
	endTime=clock();
	VCB_INFO("  Edge Query took %d ms\n",endTime-startTime);

	return g->numDisplayEdges;
}

int strip(int key,int numValues,int* value) {
   int i,cnt;
   cnt=0;
   for(i=0;i<numValues;i++) {
      if(value[i]!=key) {
         value[cnt]=value[i];
         cnt++;
      }
   }
   return cnt;
}


int getNeighbors(graph* g, int* cnt, int** children) {
   int i,v1,v2,cnt2,size;
   int* inChildren;

   if(children==NULL) {
      printf("getNeighbors(): children not valid\n");
      return -1;
   }
   else if( (*children)==NULL ) {
      printf("getNeighbors(): children not valid\n");
      return -1;
   }
   else {
      size = (*cnt)*sizeof(int);
      inChildren=(int*)malloc(size);
      if(inChildren==NULL) {
         perror("getNeighbors(): inChildren");
         return -1;
      }
      memcpy((void*)inChildren,(const void*)(*children),size);
      for(i=0;i<g->numVerts;i++) (*children)[i]=-1;

      cnt2=0;
	   for(i=0;i<(*cnt);i++) {
         v1=inChildren[i];
		   for(v2=0;v2<v1;v2++) {
			   if(g->mat2d[v1][v2]!=INAN) {
				   (*children)[v2]=v2;
               cnt2++;
			   }
		   }
		   for(v2=v1+1;v2<g->numVerts;v2++) {
			   if(g->mat2d[v2][v1]!=INAN) {
				   (*children)[v2]=v2;
               cnt2++;
			   }
		   }
      }
      //cnt2 includes duplicates
      cnt2 = strip(-1,g->numVerts,(*children)); //cnt2 is uniques
      (*cnt)=cnt2;
      free(inChildren);
      return 0;
   }
}

int bigraph_bfs(graph* g, int root, int** visitLevel) {
   int i,j,idx,level,cnt,err;
   int* children;
   children=(int*)malloc(g->numVerts*sizeof(int));
   if( children==NULL ) {
      perror("graph_bfs(): children[]");
      return -1;
   }

   //initialization
   level = 0;
   (*visitLevel)[root]=level;
   cnt=1; children[0]=root;

   //breadth-first search
   while(cnt!=0) {
      err=getNeighbors(g, &cnt, &children);
      if(err!=0) return -1;
      level++;
      for(i=0;i<cnt;i++) {
         idx=children[i];
         if( (*visitLevel)[idx]==-1 ) { //unvisited
            (*visitLevel)[idx]=level;
         }
         else {
            //if connected within bigroup, not bipartite
            if ( (*visitLevel)[idx]%2 != level%2 ) {
               free(children);
               free((*visitLevel));
               (*visitLevel)=NULL;
               return 0;
            }
            else {
               for(j=i;j<cnt;j++) { //previously visited
                  children[j]=children[j+1];
               }
               cnt--;
            }
         }
      }
   }

   free(children);
   return 1;
}

int getIdx(int key, int numVals, int* values) {
   int i;
   for(i=numVals-1;i<=0; i--) {
      if(values[i]==key) return i;
   }
   return -1;
}

int getBiPartition(graph* g, int** partition) {
   int i,newIdx,isBipartite;

   if(g->numVerts<2) return 0; //bipartite must have 2 vertices
	(*partition)=(int*)malloc(g->numVerts*sizeof(int));
   if( (*partition)==NULL ) {
      perror("getBiPartition(): partition[]");
      return -1;
   }

   for(i=0;i<g->numVerts;i++) {
      (*partition)[i]=-1;
   }
   //start at last vertex for cache hits (loop through row)
   newIdx=g->numVerts-1;

   while(newIdx!=-1) {
      isBipartite = bigraph_bfs(g,newIdx,partition);
      if(isBipartite!=1) {
         printf("  Halting: graph not bipartite\n");
         return -1;
      }
      newIdx=getIdx(-1,g->numVerts,(*partition));
   }

   for(i=0;i<g->numVerts;i++) {
      (*partition)[i]= (*partition)[i]%2;
   }
   return 1;
}

int createBipartiteLayout(char* filename, graph* g) {
   int v1,isBipartite,x,y,z;
   int tmp,col,grpFirst,grpSecond,dimX,dimY,space;
   int* partition;
   FILE* fout;

   //initDegreeBase(g,&degree);
   isBipartite=getBiPartition(g,&partition);
   if(isBipartite!=1) {
      free(partition);
      return -1;
   }
   else {
      fout = fopen(filename,"w");
      if(fout==NULL) {
		   printf("Error: can't open %s for writing.\n", filename);
	   }
      else {
         grpFirst=grpSecond=0;
         dimX=dimY=20; space=20;
         fprintf(fout,"bipartite\t%d\t%d\t%d\n",dimX,dimY,space);
         fprintf(fout,"%d\t%d\n",g->numVerts,g->numEdges);

         //Layout computation
         for(v1=0;v1<g->numVerts;v1++) {
            if(partition[v1]==0) {
               tmp=grpFirst+1; col=0;
               while (tmp>0) {
                  tmp=tmp-dimX; col++;
               }
               x=col;
               y=grpFirst%dimY;
               z=grpFirst/(dimX*dimY);
               grpFirst++;
               fprintf(fout,"%d\t%d\t%d\t%d\n",0,x,y,z);
            }
            else {
               tmp=grpSecond+1; col=0;
               while (tmp>0) {
                  tmp=tmp-dimX; col++;
               }
               x=space+col;
               y=grpSecond%dimY;
               z=grpSecond/(dimX*dimY);
               grpSecond++;
               fprintf(fout,"%d\t%d\t%d\t%d\n",1,x,y,z);
            }
         }
      
      }
   }
	fclose(fout);
   return 1;
}
