
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>

#include "glut.h"
#include "glui.h"

#include "graph.h"

#define PI 3.14159
#define TWO_PI 6.2832

extern float brightness;
extern int com_rd_mode;
extern int text_or_box;
extern int color_by_route;
extern int publication;
extern int draw_window_paths;
extern int changes_only;

int univs [6][12][32];
float pcolors[128][3];

int nodesSame(Path *p1, Path *p2) {

	int i;
	int same = 1;
	if (p1->length == p2->length) {
		for (i=0;i<p1->length;i++) {
			if (p1->nodeArray[i]!=p2->nodeArray[i]) same = 0;
		}
		return same;
	} else {
		return 0;
	}

}

void set_univs() {
	int year, leap, i,j,k,d;
	int current = 0;
	for (i=0;i<6;i++) {
		year = i + UNIVSTARTYEAR;
		if (year%400==0) {
			leap = 1;
		} else if (year%100==0) {
			leap = 0;
		} else if (year%4==0) {
			leap = 1;
		} else {
			leap = 0;
		}
		for (j=0;j<12;j++) {
			if ((j==8)||(j==3)||(j==5)||(j==10)) {
				d = 30;
			} else if (j==1) {
				if (leap) {
					d = 29;
				} else {
					d = 28;
				}
			} else {
				d = 31;
			}
			for (k=0;k<d;k++) {
				univs[i][j][k] = current;
				current++;
			}
		}
	}
	// TEOH set publication colors
	pcolors[0][0] = 1.0; pcolors[0][1] = 0.0; pcolors[0][2] = 0.0;
	pcolors[1][0] = 1.0; pcolors[1][1] = 0.5; pcolors[1][2] = 0.0;
	pcolors[2][0] = 1.0; pcolors[2][1] = 0.0; pcolors[2][2] = 1.0;
	pcolors[3][0] = 0.0; pcolors[3][1] = 1.0; pcolors[3][2] = 0.0;
	pcolors[4][0] = 0.0; pcolors[4][1] = 0.0; pcolors[4][2] = 1.0;
	pcolors[5][0] = 0.0; pcolors[5][1] = 1.0; pcolors[5][2] = 1.0;
	pcolors[6][0] = 0.5; pcolors[6][1] = 0.5; pcolors[6][2] = 0.5;
	pcolors[7][0] = 0.2; pcolors[7][1] = 0.8; pcolors[7][2] = 0.5;
	pcolors[8][0] = 0.5; pcolors[8][1] = 0.2; pcolors[8][2] = 0.8;
	pcolors[9][0] = 0.8; pcolors[9][1] = 0.5; pcolors[9][2] = 0.2;
	srand(5);
	for (i=10;i<128;i++) {
		pcolors[i][0] = (float)(rand()%256)/256.0;
		pcolors[i][1] = (float)(rand()%256)/256.0;
		pcolors[i][2] = (float)(rand()%256)/256.0;
	}

}

void Path::Print() {
	int i;
	printf("path date %d %d %d %d %d univ %d\n", year, month, day, hour, min, univtime);
	for (i=0; i<length; i++) {
		printf("%d ", nodeArray[i]);
	}
	printf("\n");
}

int Path::FindNode(int n) {

	int i;
	for (i=0; i<length; i++) {
		if (nodeArray[i] == n) return 1;
	}
	return 0;

}


int Path::FindLink(int a, int b) {

	int i;
	for (i=1; i<length; i++) {
		if ((nodeArray[i-1] == a) && (nodeArray[i] == b)) return 1;
	}
	return 0;

}



void Node::AddLink(Node *n) {
	int i;
	int dont = 0;
	for (i=0;i<nlinks;i++) {
		if (links[i] == n) dont = 1;
	}
	if (!dont) {
		links[nlinks] = n;
		nlinks++;
	}
}

void Node::AddTempLink(Node *n) {
	templink = n;
}

void Node::RemoveTempLink() {
	templink = NULL;
}

void Node::PermanizeLink() {
	
	if (templink != NULL) {
		AddLink(templink);
		//printf("pernamize link %d %d\n", AS, templink->AS);
		templink = NULL;
	}
	
}

void Node::Print() {
	int i;
	if (dfsflag == 1) return;
	dfsflag = 1;
	printf("nlinks %d x %d level %d maxlevel %d\n", nlinks, xcoord, level, maxlevel);
	for (i=0;i<nlinks;i++) {
		printf("%d %d\n", AS, links[i]->AS);
	}
	for (i=0;i<nlinks;i++) {
		links[i]->Print();
	}
}

int Node::SetLevel(int n) {
	int i;
	if (level<n) {
		maxlevel = level = n;
		for (i=0;i<nlinks;i++) {
			if (links[i]->SetLevel(n+1) > maxlevel) {
				maxlevel = links[i]->SetLevel(n+1);
			}
		}
	}
	return maxlevel;
}


int Node::NumInLevel(int n) {
	int i, r;
	r = 0;
	if ((level==n) && (countedlevel==0)) { r = 1; countedlevel = 1; }
	for (i=0;i<nlinks;i++) r += links[i]->NumInLevel(n);
	return r;
}

void Node::SetLinearX(int *next) {

	int i;
	if (linearX < 0) {
		linearX = next[level+1];
		printf("AS %d level %d set to %d\n", AS, level, linearX);
		next[level+1] = next[level+1] + 1;
	}
	for (i=0;i<nlinks;i++) {
		links[i]->SetLinearX(next);
	}
	
}

void Node::DrawYourself(int n) {

	float off;

	off = ((float)n * 1.5)/100.0;
	glColor3f(1.0,1.0,1.0);
	glPointSize(n+2);
	glBegin(GL_POINTS);
	glVertex2f(off+xcoord,off+(float)level);
	glEnd();
}

void Node::Draw() {
	int i;
	char asstr[8];
	if (dfsflag == 1) return;
	dfsflag = 1;
	if (publication) {
		glColor3f(1.0-brightness,1.0-brightness,1.0-brightness);
	} else {
		glColor3f(brightness,0.0,0.0);
	}
	glPointSize(5);
	glBegin(GL_POINTS);
	glVertex2f(xcoord,(float)level);
	glEnd();
	if (publication) {
		glColor3f(1.0-brightness,1.0-brightness,1.0-brightness);
	} else {
		glColor3f(brightness,brightness,brightness);
	}

	sprintf(asstr,"%d",AS);
	for (i=0;i<strlen(asstr);i++) {
		glRasterPos3f(0.1+xcoord+0.2*i,level+0.1,-0.1);
		glutBitmapCharacter(GLUT_BITMAP_TIMES_ROMAN_10,asstr[i]);
	}


	for (i=0;i<nlinks;i++) {
		if (publication) {
			glColor3f(1.0-brightness,1.0-brightness,1.0-brightness);
		} else {
			glColor3f(brightness,brightness,brightness);
		}
		glLineWidth(1);
		glBegin(GL_LINES);
		glVertex3f(xcoord,(float)level,-0.1);	
		glVertex3f(links[i]->xcoord,(float)links[i]->level,-0.1);

		glEnd();
		links[i]->Draw();
	}
}


int Node::DetectCycle() {
	int i;
	if (dfsflag) {
		return 1;
	} else {
		dfsflag = 1;
		for (i=0;i<nlinks;i++) {
			if (links[i]->DetectCycle()) {
				return 1;
			}
		}
		if (templink != NULL) {
			if (templink->DetectCycle()) {
				return 1;
			}
		}
		dfsflag = 0;
		return 0;
	}
}

void Node::InitDFS() {
	int i;
	if (dfsflag==0) {
		return;
	} else {
		dfsflag = 0;
		for (i=0;i<nlinks;i++) {
			links[i]->InitDFS();
		}
		if (templink!=NULL) templink->InitDFS();
	}
}

Graph::Graph() {
	int i;
	npaths = 0;
	for (i=0;i<MAX_N_NODES_IN_GRAPH;i++) {
		nodes[i] = NULL;
	}
	selectedPoint = -1;
	peer1 = peer2 = peer3 = -1;
	highlightedpath = -1;
	shadowpath = -1;
	for (i=0;i<N_SHADOW;i++) shadowpaths[i] = -1;
	sep_fac = 1.0;

	orthograph = NULL;

	linearNodeColors[0][0] = 1.0; linearNodeColors[0][1] = 0.0; linearNodeColors[0][2] = 0.0;
	linearNodeColors[1][0] = 0.0; linearNodeColors[1][1] = 1.0; linearNodeColors[1][2] = 0.0;
	linearNodeColors[2][0] = 0.0; linearNodeColors[2][1] = 0.0; linearNodeColors[2][2] = 1.0;
	linearNodeColors[3][0] = 1.0; linearNodeColors[3][1] = 1.0; linearNodeColors[3][2] = 0.0;
	linearNodeColors[4][0] = 1.0; linearNodeColors[4][1] = 0.0; linearNodeColors[4][2] = 1.0;
	linearNodeColors[5][0] = 1.0; linearNodeColors[5][1] = 1.0; linearNodeColors[5][2] = 1.0;
	linearNodeColors[6][0] = 0.0; linearNodeColors[6][1] = 1.0; linearNodeColors[6][2] = 1.0;


}


void Graph::readMRT(char *fname) {

	FILE *fptr;
	char buf[512];
	char str[512];
	char as[16];
	char temp[8];
	int i, j, k, p, a;
	int asn, asn1;
	int incremented;
	int found, keepgoing;
	int curind, prevind;

	struct tm *timeobj;
	int itimestamp;
	unsigned long longtime;

	fptr = fopen(fname,"rt");
	npaths = 0;
	ndistinctpaths = 0;

	//root = 12654;
	root = 0;

	p = 0;

	// *************** PART I : READ IN ALL THE PATHS ******************


	// for each path
	while (!feof(fptr)) {
		fgets(buf,256,fptr);
		i = 0;
		paths[p] = new Path();
		// read header BGP4MP
		while (buf[i]!='|') {
			str[i] = buf[i];
			i++;
		}
		i++;
		// read time stamp
		for (j=0;buf[i]!='|';j++,i++) {
			temp[j] = buf[i];
		}
		temp[j] = '\0';
		sscanf(temp,"%d",&itimestamp);
		longtime = (unsigned long)itimestamp;

		timeobj = localtime((const time_t*)(&longtime));
		timeobj->tm_year+=1900;
		timeobj->tm_mon++;

		paths[p]->timestamp = itimestamp;
		paths[p]->year = timeobj->tm_year;
		paths[p]->month = timeobj->tm_mon;
		paths[p]->day = timeobj->tm_mday;
		paths[p]->hour = timeobj->tm_hour;
		paths[p]->min = timeobj->tm_min;

		i++;

		// read whether announcement or withdraw
		while (buf[i]!='|') {
			str[i] = buf[i];
			i++;
		}
		i++;

		// read peer ip
		j = 0;
		while (buf[i]!='|') {
			paths[p]->attributes[0][j] = buf[i];
			i++; j++;
		}
		paths[p]->attributes[0][j] = '\0';
		i++;

		// skip peer as
		while (buf[i]!='|') {
			str[i] = buf[i];
			i++;
		}
		i++;


		// skip prefix
		while (buf[i]!='|') {
			str[i] = buf[i];
			i++;
		}
		i++;

		k = i;

		// read as path
		while (buf[i]!='|') {
			str[i] = buf[i];
			i++;
		}
		str[i] = '\0';
		i++;

		a = 0;
		while (k < strlen(str)) {
			// read AS
			j = 0;
			while ((str[k]>='0') && (str[k]<='9')) {
				as[j] = buf[k];
				k++; j++;
			}
			as[j] = '\0';
			paths[p]->nodeArray[a] = atoi(as);
			a++;
			paths[p]->length = a;
			// read white space
			while ((buf[k]!='\0')&&((buf[k]<'0') || (buf[k]>'9'))) k++;
			if (a >= MAX_N_NODES) {
				printf("a exceeded\n");
			}
		}

		// read 4 other attributes
		for (k=1;k<5;k++) {
			j = 0;
			while (buf[i]!='|') {
				paths[p]->attributes[k][j] = buf[i];
				i++; j++;
			}
			paths[p]->attributes[k][j] = '\0';
			i++;
		}


		// finished reading this path, now do some accounting

		p++;
		if (p >= MAX_N_PATHS) {
			printf("p exceeded\n");
		}
		npaths = p;

		// set unique path
		found = 0;
		for (i=0;((i<ndistinctpaths)&(!found));i++) {
			if (distinctpaths[i].length==paths[p-1]->length) {
				keepgoing = 1;
				for (j=0;((j<distinctpaths[i].length)&&(keepgoing));j++) {
					if (distinctpaths[i].nodeArray[j] !=
						paths[p-1]->nodeArray[j]) {
						keepgoing = 0;
					}
				}
				if (keepgoing) {
					found = 1;
					paths[p-1]->dpid = i;
				}
			}
		}
		if (found==0) {
			// create new unique path
			for (i=0;i<paths[p-1]->length;i++) {
				distinctpaths[ndistinctpaths].nodeArray[i] = paths[p-1]->nodeArray[i];
			}
			distinctpaths[ndistinctpaths].length = paths[p-1]->length;
			paths[p-1]->dpid = ndistinctpaths;
			ndistinctpaths++;
		}



	}



	printf("distinct paths\n");
	for (i=0;i<ndistinctpaths;i++) {
		printf("path ");
		for (j=0;j<distinctpaths[i].length;j++) {
			printf("%d ", distinctpaths[i].nodeArray[j]);
		}
		printf("\n");
	}
	printf("end distinct paths\n");

	ConstructGraph();

  
	// *************** PART V : SET TIME LINE ***************************

	// convert all path times to univ time
	set_univs();
	for (p=0;p<npaths;p++) {
		paths[p]->univtime = 0;
		paths[p]->univtime += univs[paths[p]->year-UNIVSTARTYEAR][paths[p]->month-1][paths[p]->day-1] * 24 * 60;
		paths[p]->univtime -= univs[paths[0]->year-UNIVSTARTYEAR][paths[0]->month-1][paths[0]->day-1] * 24 * 60;
		paths[p]->univtime += (paths[p]->hour - paths[0]->hour) * 60;
		paths[p]->univtime += (paths[p]->min - paths[0]->min);
	}
	// set num announcements for each time period
	tinter = paths[npaths-1]->univtime / 511;
	for (i=0;i<512;i++) numanns[i] = 0;
	for (p=0;p<npaths;p++) numanns[paths[p]->univtime/tinter]++;
	maxnumanns = 0;
	for (i=0;i<512;i++) {
		if (maxnumanns < numanns[i]) maxnumanns = numanns[i];
	}
	// set indices from the 512 boxes back to the paths

	pindices[0] = 0;
	for (i=1;i<512;i++) {
		pindices[i] = pindices[i-1] + numanns[i-1];
	}

	// set flags for unique paths in each time period
	for (i=0;i<512;i++) { allpaths[i] = 0; allpaths2[i] = 0; }
	curind = prevind = 0;
	for (p=0;p<npaths;p++) {
		curind = paths[p]->univtime/tinter;
		if (curind<0) curind = 0;
		if (curind>=512) curind = 511;
		if (paths[p]->dpid<32) {
			allpaths[curind] |= (1<<paths[p]->dpid);
		} else {
			allpaths2[curind] |= (1<<(paths[p]->dpid-32));
		}
		if (curind-prevind>1) {
			for (i=prevind+1;i<curind;i++) {
				if (paths[p-1]->dpid<32) {
					allpaths[i] |= (1<<paths[p-1]->dpid);
				} else {
					allpaths2[i] |= (1<<(paths[p-1]->dpid-32));
				}
			}
		}
		prevind = curind;
	}


  
}


void Graph::MakeGraph(char *fname) {

	FILE *fptr;
	char buf[256];
	char str[64];
	char as[16];
	char temp[8];
	int i, j, p, a;
	int asn, asn1;
	int incremented;
	int found, keepgoing;
	int curind, prevind;

	fptr = fopen(fname,"rt");
	npaths = 0;
	ndistinctpaths = 0;

	//root = 12654;
	root = 0;

	p = 0;

	// *************** PART I : READ IN ALL THE PATHS ******************


	// for each path
	while (!feof(fptr)) {
		fgets(buf,256,fptr);
		i = 0;
		paths[p] = new Path();
		// read header
		while (buf[i]!='.') {
			str[i] = buf[i];
			i++;
		}
		i++;
		for (j=0;j<4;j++,i++) {
			temp[j] = buf[i];
		}
		temp[4] = '\0';
		paths[p]->year = atoi(temp);
		for (j=0;j<2;j++,i++) {
			temp[j] = buf[i];
		}
		temp[2] = '\0';
		paths[p]->month = atoi(temp);
		for (j=0;j<2;j++,i++) {
			temp[j] = buf[i];
		}
		temp[2] = '\0';
		paths[p]->day = atoi(temp);
		i++;
		for (j=0;j<2;j++,i++) {
			temp[j] = buf[i];
		}
		temp[2] = '\0';
		paths[p]->hour = atoi(temp);
		for (j=0;j<2;j++,i++) {
			temp[j] = buf[i];
		}
		temp[2] = '\0';
		paths[p]->min = atoi(temp);
		while ((buf[i]!=' ')&&(buf[i]!='\t')) {
			str[i] = buf[i];
			i++;
		}
		str[i] = '\0';
		// read white space
		while ((buf[i]==' ') || (buf[i]=='\t')) i++;
		// read ip address
		j = 0;
		while ((buf[i]!=' ') && (buf[i]!='\t') && (buf[i]!='\n')) {
			ipadd[j] = buf[i];
			i++; j++;
		}
		ipadd[j] = '\0';
		// read white space
		while ((buf[i]<'0') || (buf[i]>'9')) i++;
		// for each AS
		a = 0;
		while (i < strlen(buf)) {
			// read AS
			j = 0;
			while ((buf[i]>='0') && (buf[i]<='9')) {
				as[j] = buf[i];
				i++; j++;
			}
			as[j] = '\0';
			paths[p]->nodeArray[a] = atoi(as);
			a++;
			paths[p]->length = a;
			// read white space
			while ((buf[i]<'0') || (buf[i]>'9')) i++;
			if (a >= MAX_N_NODES) {
				printf("a exceeded\n");
			}
		}
		//printf("p is %d\n", p);
		p++;
		if (p >= MAX_N_PATHS) {
			printf("p exceeded\n");
		}
		npaths = p;

		// set unique path
		found = 0;
		for (i=0;((i<ndistinctpaths)&(!found));i++) {
			if (distinctpaths[i].length==paths[p-1]->length) {
				keepgoing = 1;
				for (j=0;((j<distinctpaths[i].length)&&(keepgoing));j++) {
					if (distinctpaths[i].nodeArray[j] !=
						paths[p-1]->nodeArray[j]) {
						keepgoing = 0;
					}
				}
				if (keepgoing) {
					found = 1;
					paths[p-1]->dpid = i;
				}
			}
		}
		if (found==0) {
			// create new unique path
			for (i=0;i<paths[p-1]->length;i++) {
				distinctpaths[ndistinctpaths].nodeArray[i] = paths[p-1]->nodeArray[i];
			}
			distinctpaths[ndistinctpaths].length = paths[p-1]->length;
			paths[p-1]->dpid = ndistinctpaths;
			ndistinctpaths++;
		}

	}

	printf("distinct paths\n");
	for (i=0;i<ndistinctpaths;i++) {
		printf("path ");
		for (j=0;j<distinctpaths[i].length;j++) {
			printf("%d ", distinctpaths[i].nodeArray[j]);
		}
		printf("\n");
	}
	printf("end distinct paths\n");

	ConstructGraph();

  
	// *************** PART V : SET TIME LINE ***************************

	// convert all path times to univ time
	set_univs();
	for (p=0;p<npaths;p++) {
		paths[p]->univtime = 0;
		paths[p]->univtime += univs[paths[p]->year-UNIVSTARTYEAR][paths[p]->month-1][paths[p]->day-1] * 24 * 60;
		paths[p]->univtime -= univs[paths[0]->year-UNIVSTARTYEAR][paths[0]->month-1][paths[0]->day-1] * 24 * 60;
		paths[p]->univtime += (paths[p]->hour - paths[0]->hour) * 60;
		paths[p]->univtime += (paths[p]->min - paths[0]->min);
	}
	// set num announcements for each time period
	tinter = paths[npaths-1]->univtime / 511;
	for (i=0;i<512;i++) numanns[i] = 0;
	for (p=0;p<npaths;p++) numanns[paths[p]->univtime/tinter]++;
	maxnumanns = 0;
	for (i=0;i<512;i++) {
		if (maxnumanns < numanns[i]) maxnumanns = numanns[i];
	}
	// set indices from the 512 boxes back to the paths

	pindices[0] = 0;
	for (i=1;i<512;i++) {
		pindices[i] = pindices[i-1] + numanns[i-1];
	}

	// set flags for unique paths in each time period
	for (i=0;i<512;i++) { allpaths[i] = 0; allpaths2[i] = 0; }
	curind = prevind = 0;
	for (p=0;p<npaths;p++) {
		curind = paths[p]->univtime/tinter;
		if (curind<0) curind = 0;
		if (curind>=512) curind = 511;
		if (paths[p]->dpid<32) {
			allpaths[curind] |= (1<<paths[p]->dpid);
		} else {
			allpaths2[curind] |= (1<<(paths[p]->dpid-32));
		}
		if (curind-prevind>1) {
			for (i=prevind+1;i<curind;i++) {
				if (paths[p-1]->dpid<32) {
					allpaths[i] |= (1<<paths[p-1]->dpid);
				} else {
					allpaths2[i] |= (1<<(paths[p-1]->dpid-32));
				}
			}
		}
		prevind = curind;
	}

	

}

void Graph::AddGraph(Graph *gptr) {

	
	int i, j, n, keepgoing, found;

	for (n=0;n<gptr->ndistinctpaths;n++) {

		// set unique path
		found = 0;
		for (i=0;((i<ndistinctpaths)&(!found));i++) {
			if (distinctpaths[i].length==gptr->distinctpaths[n].length) {
				keepgoing = 1;
				for (j=0;((j<distinctpaths[i].length)&&(keepgoing));j++) {
					if (distinctpaths[i].nodeArray[j] !=
						gptr->distinctpaths[n].nodeArray[j]) {
						keepgoing = 0;
					}
				}
				if (keepgoing) {
					found = 1;
					//paths[p-1]->dpid = i;
				}
			}
		}
		if (found==0) {
			// create new unique path
			for (i=0;i<gptr->distinctpaths[n].length;i++) {
				distinctpaths[ndistinctpaths].nodeArray[i] = gptr->distinctpaths[n].nodeArray[i];
			}
			distinctpaths[ndistinctpaths].length = gptr->distinctpaths[n].length;
			//paths[p-1]->dpid = ndistinctpaths;
			ndistinctpaths++;
		}

	}

	printf("distinct paths\n");
	for (i=0;i<ndistinctpaths;i++) {
		printf("path ");
		for (j=0;j<distinctpaths[i].length;j++) {
			printf("%d ", distinctpaths[i].nodeArray[j]);
		}
		printf("\n");
	}
	printf("end distinct paths\n");

}

void Graph::ConstructGraph() {

	int p;
	int asn1, a, asn, incremented, i, curind, prevind;
	int *next;
	int tempx, tempy;

	// **************** PART II : CONSTRUCT THE GRAPH *******************


	for (i=0;i<MAX_N_NODES_IN_GRAPH ;i++) {
		if ((nodes[i]) != NULL) {
			delete nodes[i];
			nodes[i] = NULL;
		}
	}


	nodes[root] = new Node(root);
	for (p=0;p<ndistinctpaths;p++) {

		if ((distinctpaths[p].length)>0) {
			asn1 = distinctpaths[p].nodeArray[0];
			if ((nodes[asn1])==NULL) nodes[asn1] = new Node(asn1);
			nodes[root]->AddLink(nodes[asn1]);
		}
		
		for (a=0;a<distinctpaths[p].length-1;a++) {
			asn1 = distinctpaths[p].nodeArray[a];
			asn = distinctpaths[p].nodeArray[a+1];
			if ((nodes[asn])==NULL) {
				nodes[asn] = new Node(asn);
				nodes[asn1]->AddLink(nodes[asn]);
			} else {
				nodes[asn1]->AddTempLink(nodes[asn]);
			}
		}

		if (DetectCycle()) {
			for (a=0;a<distinctpaths[p].length-1;a++) {
				asn1 = distinctpaths[p].nodeArray[a];
				nodes[asn1]->RemoveTempLink();
			}
			distinctpaths[p].addlater = 1;
		} else {
			for (a=0;a<distinctpaths[p].length-1;a++) {
				asn1 = distinctpaths[p].nodeArray[a];
				nodes[asn1]->PermanizeLink();
			}
		}
	}
	



	// *************** PART III : SET LEVEL AND LINEARX OF NODES ********************

	y = nodes[root]->SetLevel(0);

	next = new int[y+3];
	printf("y is %d\n", y);
	for (i=-1; i<=y; i++) {
		next[i+1] = nodes[root]->NumInLevel(i);
		printf("level %d has %d nodes\n", i, next[i+1]);
	}
	for (i=0; i<=y; i++) {
		next[i+1] += next[i];
	}
	for (i=y+2;i>0;i--) {
		next[i] = next[i-1];
	}
	maxlinearx = next[y+2];
	nodes[root]->SetLinearX(next);
	delete [] next;



	for (p=0;p<ndistinctpaths;p++) {
		if (distinctpaths[p].addlater==1) {
			for (a=0;a<distinctpaths[p].length-1;a++) {
				asn1 = distinctpaths[p].nodeArray[a];
				asn = distinctpaths[p].nodeArray[a+1];
				if ((nodes[asn1])==NULL) nodes[asn1] = new Node(asn1);
				if ((nodes[asn])==NULL) nodes[asn] = new Node(asn);
				nodes[asn1]->AddLink(nodes[asn]);
			}
			distinctpaths[p].addlater = 0;
		}
	}


	// *************** PART IV : SET X COORDINATES OF NODES *************
	
	x = 0;
	for (p=0;p<ndistinctpaths;p++) {
		incremented = 0;
		for (a=0;a<distinctpaths[p].length;a++) {
			asn1 = distinctpaths[p].nodeArray[a];
			if (nodes[asn1]->xcoord<0) {
				nodes[asn1]->xcoord = (float)x;
				printf("xcoord set %f on level %d as %d\n", nodes[asn1]->xcoord, nodes[asn1]->level, nodes[asn1]->AS);
				if (!incremented) {
					incremented = 1;
				}
			}
		}
		if (incremented) x++;
	}
	nodes[root]->xcoord = 0.5*(float)x;


	// *************** PART V : SET ORTHOGONAL GRID ************************

	orthox = x+1;
	orthoy = y+1;
 	orthogonal_grid = new char[orthox*orthoy];
	orthogonal_grid_AS = new int[orthox*orthoy];
	for (i=0; i<orthox*orthoy; i++) {
		orthogonal_grid[i] = 0;
	}
	for (p=0;p<ndistinctpaths;p++) {
		for (a=0;a<distinctpaths[p].length;a++) {
			asn1 = distinctpaths[p].nodeArray[a];
			tempx = (int)(nodes[asn1]->xcoord + 0.1);
			tempy = nodes[asn1]->level;
			orthogonal_grid[tempx + tempy * orthox] = 1;
			orthogonal_grid_AS[tempx + tempy * orthox] = asn1;
		}
	}



}


void Graph::PrintPaths() {
}

void Graph::PrintGraph() {
}

void Graph::Draw() {

	nodes[root]->InitDFS();
	nodes[root]->Draw();

}

void Graph::DrawTimeLine(int t) {

	int i;
	glLineWidth(1);
	glBegin(GL_LINES);
	for (i=0;i<512;i++) {
		if ((t>=0)&&(paths[t]->univtime/tinter==i)) {
			glColor3f(brightness*0.5,brightness*0.1,0.0);
		} else {
			if (publication) {
				glColor3f(0.1,0.1,0.1);
			} else {
				glColor3f(0.8,0.8,0.8);
			}
		}
		glVertex2i(i,numanns[i]);
		glVertex2i(i,0);
	}
	glEnd();

}

void Graph::DrawBackground(float st, float ft) {
	glColor3f(0.1,0.1,0.1);
	glBegin(GL_QUADS);
	glVertex3f(st,0.0,-0.5);
	glVertex3f(st,1.0,-0.5);
	glVertex3f(ft,1.0,-0.5);
	glVertex3f(ft,0.0,-0.5);
	glEnd();

}

void Graph::DrawTimeDistinctPaths(int t) {

	int i,j;
	glPointSize(2);
	glBegin(GL_POINTS);
	for (i=0;i<512;i++) {
		for (j=0;(j<ndistinctpaths) && (j<32);j++) {
			if ((allpaths[i]>>j & 1)!= 0) {
				glColor3f(pcolors[j][0],pcolors[j][1],pcolors[j][2]);
				glVertex2i(i,j*2);
			}
		}
		for (j=32; j<ndistinctpaths ;j++) {
			if ((allpaths2[i]>>(j-32) & 1)!= 0) {
				glColor3f(pcolors[j][0],pcolors[j][1],pcolors[j][2]);
				glVertex2i(i,j*2);
			}
		}
	}
	glEnd();
	
	if (t>=0) {
		glColor3f(0.3,0.3,0.3);
		glBegin(GL_LINES);
		glVertex2i(paths[t]->univtime/tinter,ndistinctpaths*2);
		glVertex2i(paths[t]->univtime/tinter,0);
		glEnd();
	}	

}


void Graph::DrawWindowDistinctPaths(int w, int p, int t) {
	int p1;
	int up;
	float t1,t2;
	p1 = p;
	//printf("draw window path %d %d %d\n", w, p, t);
	glLineWidth(2);
	while ((paths[p1]->univtime>(t-w/2))&&(p1>0)) {
		up = 2*paths[p1-1]->dpid;
		glColor3f(pcolors[up][0],pcolors[up][1],pcolors[up][2]);
		t1 = (float)((float)paths[p1-1]->univtime-(float)(t-w/2));
		t2 = 512.0*t1/(float)w;
		glBegin(GL_LINES);
		if (t2<0.0) {
			glVertex2f(0.0,(float)up);
		} else {
			glVertex2f(t2,(float)up);
		}
		glVertex2f(512.0*(float)(paths[p1]->univtime-(t-w/2))/(float)w,up);
		glEnd();
		p1--;
	}
	p1 = p;
	glLineWidth(2);
	while ((paths[p1]->univtime<(t+w/2))&&(p1>0)) {
		up = 2*paths[p1]->dpid;
		glColor3f(pcolors[up][0],pcolors[up][1],pcolors[up][2]);
		t1 = (float)((float)paths[p1]->univtime-(float)(t-w/2));
		t2 = 512.0*t1/(float)w;
		glBegin(GL_LINES);
		if (t2<0.0) {
			glVertex2f(0.0,(float)up);
		} else {
			glVertex2f(t2,(float)up);
		}
		glVertex2f(512.0*(float)(paths[p1+1]->univtime-(t-w/2))/(float)w,up);
		glEnd();
		//printf("drawing path %d %d %d %f %f %f\n", paths[p1]->univtime, paths[p1+1]->univtime, up,
		//	t1,
		//	512.0*t1/(float)w,
		//	512.0*(float)(paths[p1+1]->univtime-(t-w/2))/(float)w);
		p1++;
	}
	//printf("end draw window path\n");

}


void Graph::DrawNewWinDistinctPaths(int s, int e) {

	int spi;
	int epi;
	int up;
	float t1,t2;
	float t, w; // start univ time, window univ time
	int i;

	spi = pindices[s];
	if (e<511) {
		epi = pindices[e+1];
	} else {
		epi = npaths;
	}

	//t = (float)paths[spi]->univtime;
	t = (float)(s*tinter) + (float)paths[0]->univtime; // starting time of the window
	//w = (float)paths[epi]->univtime - (float)paths[spi]->univtime;
	w = (e - s + 1) * tinter;

	glLineWidth(2);
	for (i=spi;i<epi;i++) {
		if (i>0) {
			t1 = (float)((float)paths[i-1]->univtime-t);
			up = paths[i-1]->dpid;
		} else {
			t1 = 0.0;
			up = paths[i]->dpid;
		}
		glColor3f(pcolors[up][0],pcolors[up][1],pcolors[up][2]);
		t2 = 512.0*t1/w;
		glBegin(GL_LINES);
		if (t2<0.0) {
			glVertex2f(0.0,2.0*(float)up);
		} else {
			glVertex2f(t2,2.0*(float)up);
		}
		glVertex2f(512.0*(float)(paths[i]->univtime-t)/w,2.0*(float)up);
		glEnd();
	}

}

void Graph::DrawBoxPath(int i, int n, float st, float frac, int vert) {

	int j;

	j = paths[i]->dpid;

	if (publication) {
		glColor3f(0.8,0.8,0.8);
	} else {
		glColor3f(0.2,0.2,0.2);
	}

	if (com_rd_mode==0) {			
		glBegin(GL_QUADS);
		glVertex3f(15.0,45.0-1.25*(float)n,-0.1);
		glVertex3f(15.0+(float)ndistinctpaths,45.0-1.25*(float)n,-0.1);
		glVertex3f(15.0+(float)ndistinctpaths,46.0-1.25*(float)n,-0.1);
		glVertex3f(15.0,46.0-1.25*(float)n,-0.1);
		glEnd();
		glColor3f(pcolors[j][0],pcolors[j][1],pcolors[j][2]);
		glBegin(GL_QUADS);
		glVertex3f(15.0+(float)j,45.0-1.25*(float)n,0.0);
		glVertex3f(16.0+(float)j,45.0-1.25*(float)n,0.0);
		glVertex3f(16.0+(float)j,46.0-1.25*(float)n,0.0);
		glVertex3f(15.0+(float)j,46.0-1.25*(float)n,0.0);
		glEnd();
	} else if (com_rd_mode==1) {
		glBegin(GL_QUADS);
		glVertex3f(15.0,45.0 - frac*((float)paths[i]->univtime-(float)st),-0.1);
		glVertex3f(16.0+(float)ndistinctpaths,45.0 - frac*((float)paths[i]->univtime-(float)st),-0.1);
		glVertex3f(16.0+(float)ndistinctpaths,46.0 - frac*((float)paths[i]->univtime-(float)st),-0.1);
		glVertex3f(15.0,46.0 - frac*((float)paths[i]->univtime-(float)st),-0.1);
		glEnd();
		glColor3f(pcolors[j][0],pcolors[j][1],pcolors[j][2]);
		glBegin(GL_QUADS);
		glVertex3f(15.0+(float)j,45.0 - frac*((float)paths[i]->univtime-(float)st),0.0);
		glVertex3f(16.0+(float)j,45.0 - frac*((float)paths[i]->univtime-(float)st),0.0);
		glVertex3f(16.0+(float)j,46.0 - frac*((float)paths[i]->univtime-(float)st),0.0);
		glVertex3f(15.0+(float)j,46.0 - frac*((float)paths[i]->univtime-(float)st),0.0);
		glEnd();
	} else if (com_rd_mode==2) {
		glBegin(GL_QUADS);
		glVertex3f(15.0,45.1 - frac*((float)paths[i]->univtime-(float)st), 0.0); //sep_fac*(float)vert);
		glVertex3f(15.0+(float)ndistinctpaths,45.1 - frac*((float)paths[i]->univtime-(float)st), 0.0); //sep_fac*(float)vert);
		glVertex3f(15.0+(float)ndistinctpaths,45.1 - frac*((float)paths[i]->univtime-(float)st), sep_fac*(1.0+(float)vert));
		glVertex3f(15.0,45.1 - frac*((float)paths[i]->univtime-(float)st), sep_fac*(1.0+(float)vert));
		glEnd();
		glColor3f(pcolors[j][0],pcolors[j][1],pcolors[j][2]);
		glBegin(GL_QUADS);
		glVertex3f(15.0+(float)j,45.0 - frac*((float)paths[i]->univtime-(float)st), sep_fac*(float)vert);
		glVertex3f(16.0+(float)j,45.0 - frac*((float)paths[i]->univtime-(float)st), sep_fac*(float)vert);
		glVertex3f(16.0+(float)j,45.0 - frac*((float)paths[i]->univtime-(float)st), sep_fac*(1.0+(float)vert));
		glVertex3f(15.0+(float)j,45.0 - frac*((float)paths[i]->univtime-(float)st), sep_fac*(1.0+(float)vert));
		glEnd();
	}



	glBegin(GL_LINES);
	if (com_rd_mode==0) {
		glVertex2f(15.0, 45.0-1.25*(float)n);
	} else if (com_rd_mode==1) {
		glVertex2f(15.0, 45.0 - frac*((float)paths[i]->univtime-(float)st));
	} else if (com_rd_mode==2) {
		glVertex3f(15.0, 45.0 - frac*((float)paths[i]->univtime-(float)st), sep_fac*(float)vert);
	}
	glVertex2f(5.0, 45.0 - frac*((float)paths[i]->univtime-(float)st));
	glEnd();


}

void Graph::WritePath(int i, int n, float st, float frac, int vert) {

	
	int j;
	char tempas[128];
	char tempaslist[256];
	char str[16];
	int slot;
	int up;
	int sd;


	// write the time-stamp

	sprintf(tempaslist,"%d.%d.%d:%d.%d\0", paths[i]->year, paths[i]->month,
		paths[i]->day, paths[i]->hour, paths[i]->min);
	

	glColor3f(0.1,0.8,0.7);
	
	if (color_by_route) {
		up = paths[i]->dpid;
		glColor3f(pcolors[up][0],pcolors[up][1],pcolors[up][2]);
	}

	for (j=0;j<strlen(tempaslist);j++) {
		if (com_rd_mode==0) {
			glRasterPos2f(15.0+(float)j,45.0-1.25*(float)n);
		} else if (com_rd_mode==1) {
			glRasterPos2f(15.0+(float)j,45.0 - frac*((float)paths[i]->univtime-(float)st));
		} else if (com_rd_mode==2) {
			glRasterPos3f(15.0+(float)j,45.0 - frac*((float)paths[i]->univtime-(float)st), (float)vert);
		}
		glutBitmapCharacter(GLUT_BITMAP_TIMES_ROMAN_10,tempaslist[j]);
	}


	// write the AS list

	tempaslist[0] = '\0';
	for (j=0;j<paths[i]->length;j++) {
		sprintf(tempas, "%d ", paths[i]->nodeArray[j]);
		strcat(tempaslist, tempas);
	}

	for (j=0;j<paths[i]->length;j++) {
		printf("%d ", paths[i]->nodeArray[j]);
	}
	printf("\n");
	
	for (j=0;j<paths[i]->length;j++) {
		printf("%d ", nodes[paths[i]->nodeArray[j]]->linearX);
	}
	printf("\n");


	if (show_attrs) {
		sprintf(tempas," %s %s %s %s %s\0",
		paths[i]->attributes[0], paths[i]->attributes[1], paths[i]->attributes[2], 
		paths[i]->attributes[3], paths[i]->attributes[4]);
		strcat(tempaslist, tempas);
	}


	glColor3f(0.1,0.8,0.3);
		
	if (color_by_route) {
		up = paths[i]->dpid;
		glColor3f(pcolors[up][0],pcolors[up][1],pcolors[up][2]);
	}
	
	for (sd=0; sd<N_SHADOW;sd++) {
		if (shadowpaths[sd]==i) {
			if (publication) {
				glColor3f(0.0,0.0,0.0);				
			} else {
				glColor3f(1.0,1.0,1.0);
			}
		}
	}


	for (j=0;j<strlen(tempaslist);j++) {
		if (com_rd_mode==0) {
			glRasterPos2f(33.0+(float)j,45.0-1.25*(float)n);
		} else if (com_rd_mode==1) {
			glRasterPos2f(33.0+(float)j,45.0 - frac*((float)paths[i]->univtime-(float)st));
		} else if (com_rd_mode==2) {
			glRasterPos3f(33.0+(float)j,45.0 - frac*((float)paths[i]->univtime-(float)st), sep_fac*(float)vert);
		}
		glutBitmapCharacter(GLUT_BITMAP_TIMES_ROMAN_10,tempaslist[j]);
	}

	if (paths[i]->length==0) {
		glColor3f(0.9,0.3,0.1);
		if (com_rd_mode==0) {
			glRasterPos2f(33.0,45.0-1.25*(float)n);
		} else if (com_rd_mode==1) {
			glRasterPos2f(33.0,45.0 - frac*((float)paths[i]->univtime-(float)st));
		} else if (com_rd_mode==2) {
			glRasterPos3f(33.0,45.0 - frac*((float)paths[i]->univtime-(float)st), sep_fac*(float)vert);
		}
		glutBitmapCharacter(GLUT_BITMAP_TIMES_ROMAN_10,'W');
		if (com_rd_mode==0) {
			glRasterPos2f(34.0,45.0-1.25*(float)n);
		} else if (com_rd_mode==1) {
			glRasterPos2f(34.0,45.0 - frac*((float)paths[i]->univtime-(float)st));
		} else if (com_rd_mode==2) {
			glRasterPos3f(34.0,45.0 - frac*((float)paths[i]->univtime-(float)st), sep_fac*(float)vert);
		}
		glutBitmapCharacter(GLUT_BITMAP_TIMES_ROMAN_10,'D');
	}

	// draw the line from the time line to the text

	glBegin(GL_LINES);
	if (com_rd_mode==0) {
		glVertex2f(15.0, 45.0-1.25*(float)n);
	} else if (com_rd_mode==1) {
		glVertex2f(15.0, 45.0 - frac*((float)paths[i]->univtime-(float)st));
	} else if (com_rd_mode==2) {
		glVertex3f(15.0, 45.0 - frac*((float)paths[i]->univtime-(float)st), sep_fac*(float)vert);
	}
	glVertex2f(5.0, 45.0 - frac*((float)paths[i]->univtime-(float)st));
	glEnd();

}


void Graph::WriteDetailPaths(int tstart, int twin) {

	int st, et, i, j, n;
	char tempas[8];
	char tempaslist[128];
	char str[16];
	float frac;
	int slot;
	int up;
	int sd;
	int inseries;

	glColor3f(0.1,0.2,0.9);
	sprintf(str,"%d min", twin);
		
	for (i=0;i<strlen(str);i++) {
		glRasterPos2f(5.0+(float)i,1.0);
		glutBitmapCharacter(GLUT_BITMAP_TIMES_ROMAN_10,str[i]);
	}

	glBegin(GL_LINES);
	glVertex3f(5.0,5.0,0.0);
	glVertex3f(5.0,45.0,0.0);
	glEnd();

	
	st = tstart; // starting time of the window
	et = tstart + twin;

	n = 0;

	frac = 40.0/(float)twin;

	slot = 0;
	i = pindices[slot];
	while ((slot<511)&&(paths[i]->univtime < st)) {
		i = pindices[slot];
		slot++;
	}
	if (slot > 0) slot--;
	i = pindices[slot];

	while ((i<npaths)&&(paths[i]->univtime < st)) { 
		i++;
	}

	firstwritepath = i;

	inseries = 0;
	while ((i<npaths)&&(paths[i]->univtime < et)) {
		if (inseries==0) {
			for (j=i;((j<npaths)&&(paths[j]->univtime < et)&&((paths[j+1]->univtime-paths[j]->univtime)<sep_thres));j++) {
				inseries++;
			}
		}
		if (text_or_box) {
			DrawBoxPath(i,n,st,frac,inseries);
		} else {
			WritePath(i,n,st,frac,inseries);
		}
		i++; n++;
		if (inseries>0) inseries--;
	}

}


void Graph::WritePaths(int slot, int t) {

	int spi, st, et, i, j, n;
	char tempas[8];
	char tempaslist[128];
	char str[16];
	float frac;
	int up;
	int sd;
	int inseries;

	glColor3f(0.1,0.2,0.9);
	sprintf(str,"%d min", t);
		
	for (i=0;i<strlen(str);i++) {
		glRasterPos2f(5.0+(float)i,1.0);
		glutBitmapCharacter(GLUT_BITMAP_TIMES_ROMAN_10,str[i]);
	}

	glBegin(GL_LINES);
	glVertex3f(5.0,5.0,0.0);
	glVertex3f(5.0,45.0,0.0);
	glEnd();

	spi = pindices[slot];
	
	st = (float)(slot*tinter) + (float)paths[0]->univtime; // starting time of the window
	et = st + t;

	i = spi;

	n = 0;

	frac = 40.0/(float)t;


	firstwritepath = i;

	inseries = 0;
	while ((i<npaths)&&(paths[i]->univtime < et)) {
		if (inseries==0) {
			for (j=i;((j<npaths)&&(paths[j]->univtime < et)&&((paths[j+1]->univtime-paths[j]->univtime)<sep_thres));j++) {
				inseries++;
			}
		}
		if (text_or_box) {
			DrawBoxPath(i,n,st,frac,inseries*2);
		} else {
			WritePath(i,n,st,frac,inseries*2);
		}
		i++; n++;
		if (inseries>0) inseries--;
	}


}

void Graph::DrawPathLengths(int s, int e) {

	int spi;
	int epi;
	float t2,t3;
	float t, w; // start univ time, window univ time
	int i;
	int up;

	spi = pindices[s];
	if (e<511) {
		epi = pindices[e+1];
	} else {
		epi = npaths;
	}

	//t = (float)paths[spi]->univtime;
	t = (float)(s*tinter) + (float)paths[0]->univtime; // starting time of the window
	//w = (float)paths[epi]->univtime - (float)paths[spi]->univtime;
	w = (e - s + 1) * tinter;

	glLineWidth(2);
	for (i=spi;i<epi;i++) {
		if (i>0) {
			up = paths[i-1]->dpid;
			glColor3f(pcolors[up][0],pcolors[up][1],pcolors[up][2]);
			t2 = 512.0*(float)(paths[i-1]->univtime-t)/w;
			if (t2<0.0) t2 = 0.0;
			t3 = 512.0*(float)(paths[i]->univtime-t)/w;
			glBegin(GL_QUADS);
			glVertex2f(t2,0.0);
			glVertex2f(t2,(float)paths[i-1]->length);
			glVertex2f(t3,(float)paths[i-1]->length);
			glVertex2f(t3,0.0);
			glEnd();
		}
	}

}




void Graph::DrawDiagonal(int p, int n) {

	Path *pptr;
	int i;
	int n1, n2;
	int fromx, fromy, tox, toy;
	int obstacle_left;
	int obstacle_right;
	int obstacle_upper;
	int obstacle_lower;
	int temp;
	float off;
	float poff;
	int r, xdiff, ydiff;

	pptr = paths[p];


	poff = (float)n/10.0;

	if (poff<0.2) {
		glColor3f(1.0,poff*5.0,0.0);
	} else if (poff<0.4) {
		glColor3f(1.0-5.0*(poff-0.2),1.0,0.0);
	} else if (poff<0.6) {
		glColor3f(0.0,1.0,5.0*(poff-0.4));
	} else if (poff<0.8) {
		glColor3f(0.0,1.0-5.0*(poff-0.6),1.0);
	} else {
		glColor3f(5.0*(poff-0.8),0.0,1.0);
	}

	poff = poff * 0.3;

	if (pptr->length > 0) {	
		n1 = root;
		n2 = pptr->nodeArray[0];

		fromx = (int)(nodes[n1]->xcoord + 0.1);
		fromy = nodes[n1]->level;
		tox = (int)(nodes[n2]->xcoord + 0.1);
		toy = nodes[n2]->level;

		ydiff = fromy-toy;
		xdiff = fromx-tox;
		if (ydiff < 0) ydiff = -ydiff;
		if (xdiff < 0) xdiff = -xdiff;
		if (ydiff < xdiff) {
			if (ydiff != 0) r = xdiff % ydiff;
		} else {
			if (xdiff != 0) r = ydiff % xdiff;
		}


		obstacle_left = obstacle_right = obstacle_upper = obstacle_lower = 0;
		for (temp = fromx + 1; temp < tox; temp++) {
			if (orthogonal_grid[temp + fromy * orthox] != 0) obstacle_lower = 1;
			if (orthogonal_grid[temp + toy * orthox] != 0) obstacle_upper = 1;
		}
		for (temp = fromy + 1; temp < toy; temp++) {
			if (orthogonal_grid[fromx + temp * orthox] != 0) obstacle_left = 1;
			if (orthogonal_grid[tox + temp * orthox] != 0) obstacle_right = 1;
		}
		for (temp = tox + 1; temp < fromx; temp++) {
			if (orthogonal_grid[temp + fromy * orthox] != 0) obstacle_lower = 1;
			if (orthogonal_grid[temp + toy * orthox] != 0) obstacle_upper = 1;
		}
		for (temp = toy + 1; temp < fromy; temp++) {
			if (orthogonal_grid[fromx + temp * orthox] != 0) obstacle_left = 1;
			if (orthogonal_grid[tox + temp * orthox] != 0) obstacle_right = 1;
		}

		glLineWidth(1);
		glBegin(GL_LINE_STRIP);

		if ((fromy == toy + 1) || (fromy == toy - 1)) { // case 0A
			glVertex3f(nodes[n1]->xcoord+poff,(float)nodes[n1]->level,0.0);
			glVertex3f(nodes[n2]->xcoord+poff,(float)nodes[n2]->level,0.0);
		} else if ((fromx == tox + 1) || (fromx == tox - 1)) { // case 0B
			glVertex3f(nodes[n1]->xcoord,(float)nodes[n1]->level+poff,0.0);
			glVertex3f(nodes[n2]->xcoord,(float)nodes[n2]->level+poff,0.0);
		} else if (fromx == tox) {
			if (obstacle_left==0) { // case 0A
				glVertex3f(nodes[n1]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
				glVertex3f(nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
			} else { // case JumpA
				glVertex3f(nodes[n1]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
				glVertex3f(0.5+nodes[n1]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
				glVertex3f(0.5+nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
				glVertex3f(nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
			}
		} else if (fromy == toy) {
			if (obstacle_lower==0) { // case 0B
				glVertex3f(nodes[n1]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
				glVertex3f(nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
			} else { // case JumpB
				glVertex3f(nodes[n1]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
				glVertex3f(nodes[n1]->xcoord+poff,0.5+(float)nodes[n1]->level+poff,0.0);
				glVertex3f(nodes[n2]->xcoord+poff,0.5+(float)nodes[n2]->level+poff,0.0);
				glVertex3f(nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
			}
		} else if (r) { 
			
			glVertex3f(nodes[n1]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
			glVertex3f(nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
			
		} else { // case 3Bends
			if (nodes[n1]->xcoord > nodes[n2]->xcoord) {
				off = 0.5; 
			} else {
				off = -0.5;
			}
			glVertex3f(nodes[n1]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
			glVertex3f(nodes[n1]->xcoord+poff,0.5+(float)nodes[n1]->level+poff,0.0);
			if (xdiff > 3) glVertex3f(off+nodes[n2]->xcoord+poff,0.5+(float)nodes[n1]->level+poff,0.0);
			glVertex3f(off+nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
			glVertex3f(nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
		}

		glEnd();

	}

	for (i=0; i < pptr->length - 1; i++) {
		n1 = pptr->nodeArray[i];
		n2 = pptr->nodeArray[i+1];
		fromx = (int)(nodes[n1]->xcoord + 0.1);
		fromy = nodes[n1]->level;
		tox = (int)(nodes[n2]->xcoord + 0.1);
		toy = nodes[n2]->level;

		ydiff = fromy-toy;
		xdiff = fromx-tox;
		if (ydiff < 0) ydiff = -ydiff;
		if (xdiff < 0) xdiff = -xdiff;
		if (ydiff < xdiff) {
			if (ydiff != 0) r = xdiff % ydiff;
		} else {
			if (xdiff != 0) r = ydiff % xdiff;
		}


		obstacle_left = obstacle_right = obstacle_upper = obstacle_lower = 0;
		for (temp = fromx + 1; temp < tox; temp++) {
			if (orthogonal_grid[temp + fromy * orthox] != 0) obstacle_lower = 1;
			if (orthogonal_grid[temp + toy * orthox] != 0) obstacle_upper = 1;
		}
		for (temp = fromy + 1; temp < toy; temp++) {
			if (orthogonal_grid[fromx + temp * orthox] != 0) obstacle_left = 1;
			if (orthogonal_grid[tox + temp * orthox] != 0) obstacle_right = 1;
		}
		for (temp = tox + 1; temp < fromx; temp++) {
			if (orthogonal_grid[temp + fromy * orthox] != 0) obstacle_lower = 1;
			if (orthogonal_grid[temp + toy * orthox] != 0) obstacle_upper = 1;
		}
		for (temp = toy + 1; temp < fromy; temp++) {
			if (orthogonal_grid[fromx + temp * orthox] != 0) obstacle_left = 1;
			if (orthogonal_grid[tox + temp * orthox] != 0) obstacle_right = 1;
		}

		glLineWidth(1);
		glBegin(GL_LINE_STRIP);

		if ((fromy == toy + 1) || (fromy == toy - 1)) { // case 0A
			glVertex3f(nodes[n1]->xcoord+poff,(float)nodes[n1]->level,0.0);
			glVertex3f(nodes[n2]->xcoord+poff,(float)nodes[n2]->level,0.0);
		} else if ((fromx == tox + 1) || (fromx == tox - 1)) { // case 0B
			glVertex3f(nodes[n1]->xcoord,(float)nodes[n1]->level+poff,0.0);
			glVertex3f(nodes[n2]->xcoord,(float)nodes[n2]->level+poff,0.0);
		} else if (fromx == tox) {
			if (obstacle_left==0) { // case 0A
				glVertex3f(nodes[n1]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
				glVertex3f(nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
			} else { // case JumpA
				glVertex3f(nodes[n1]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
				glVertex3f(0.5+nodes[n1]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
				glVertex3f(0.5+nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
				glVertex3f(nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
			}
		} else if (fromy == toy) {
			if (obstacle_lower==0) { // case 0B
				glVertex3f(nodes[n1]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
				glVertex3f(nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
			} else { // case JumpB
				glVertex3f(nodes[n1]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
				glVertex3f(nodes[n1]->xcoord+poff,0.5+(float)nodes[n1]->level+poff,0.0);
				glVertex3f(nodes[n2]->xcoord+poff,0.5+(float)nodes[n2]->level+poff,0.0);
				glVertex3f(nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
			}
		} else if (r) { 
			
			glVertex3f(nodes[n1]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
			glVertex3f(nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
			
		} else { // case 3Bends
			if (nodes[n1]->xcoord > nodes[n2]->xcoord) {
				off = 0.5; 
			} else {
				off = -0.5;
			}
			glVertex3f(nodes[n1]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
			glVertex3f(nodes[n1]->xcoord+poff,0.5+(float)nodes[n1]->level+poff,0.0);
			if (xdiff > 3) glVertex3f(off+nodes[n2]->xcoord+poff,0.5+(float)nodes[n1]->level+poff,0.0);
			glVertex3f(off+nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
			glVertex3f(nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
		}

		glEnd();	
	
	}



}


void Graph::DrawOrthogonal(int p, int n) {

	Path *pptr;
	int i;
	int n1, n2;
	int fromx, fromy, tox, toy;
	int obstacle_left;
	int obstacle_right;
	int obstacle_upper;
	int obstacle_lower;
	int temp;
	float off;
	float poff;

	pptr = paths[p];


	poff = (float)n/10.0;

	if (poff<0.2) {
		glColor3f(1.0,poff*5.0,0.0);
	} else if (poff<0.4) {
		glColor3f(1.0-5.0*(poff-0.2),1.0,0.0);
	} else if (poff<0.6) {
		glColor3f(0.0,1.0,5.0*(poff-0.4));
	} else if (poff<0.8) {
		glColor3f(0.0,1.0-5.0*(poff-0.6),1.0);
	} else {
		glColor3f(5.0*(poff-0.8),0.0,1.0);
	}

	poff = poff * 0.3;

	if (pptr->length > 0) {	
		n1 = root;
		n2 = pptr->nodeArray[0];

		fromx = (int)(nodes[n1]->xcoord + 0.1);
		fromy = nodes[n1]->level;
		tox = (int)(nodes[n2]->xcoord + 0.1);
		toy = nodes[n2]->level;

		obstacle_left = obstacle_right = obstacle_upper = obstacle_lower = 0;
		for (temp = fromx + 1; temp < tox; temp++) {
			if (orthogonal_grid[temp + fromy * orthox] != 0) obstacle_lower = 1;
			if (orthogonal_grid[temp + toy * orthox] != 0) obstacle_upper = 1;
		}
		for (temp = fromy + 1; temp < toy; temp++) {
			if (orthogonal_grid[fromx + temp * orthox] != 0) obstacle_left = 1;
			if (orthogonal_grid[tox + temp * orthox] != 0) obstacle_right = 1;
		}
		for (temp = tox + 1; temp < fromx; temp++) {
			if (orthogonal_grid[temp + fromy * orthox] != 0) obstacle_lower = 1;
			if (orthogonal_grid[temp + toy * orthox] != 0) obstacle_upper = 1;
		}
		for (temp = toy + 1; temp < fromy; temp++) {
			if (orthogonal_grid[fromx + temp * orthox] != 0) obstacle_left = 1;
			if (orthogonal_grid[tox + temp * orthox] != 0) obstacle_right = 1;
		}

		glLineWidth(1);
		glBegin(GL_LINE_STRIP);


		if ((fromx == tox) && ((fromy == toy + 1) || (fromy == toy - 1))) { // case 0A
			glVertex3f(nodes[n1]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
			glVertex3f(nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
		} else if ((fromy == toy) && ((fromx == tox + 1) || (fromx == tox - 1))) { // case 0B
			glVertex3f(nodes[n1]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
			glVertex3f(nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
		} else if (fromx == tox) {
			if (obstacle_left==0) { // case 0A
				glVertex3f(nodes[n1]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
				glVertex3f(nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
				for (temp = toy; temp <= fromy; temp++) {
					if (orthogonal_grid[fromx + temp * orthox] == 0) orthogonal_grid[fromx + temp * orthox] = 2;
				}
				for (temp = fromy; temp <= toy; temp++) {
					if (orthogonal_grid[fromx + temp * orthox] == 0) orthogonal_grid[fromx + temp * orthox] = 2;
				}
			} else { // case JumpA
				glVertex3f(nodes[n1]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
				glVertex3f(0.5+nodes[n1]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
				glVertex3f(0.5+nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
				glVertex3f(nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
			}
		} else if (fromy == toy) {
			if (obstacle_lower==0) { // case 0B
				glVertex3f(nodes[n1]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
				glVertex3f(nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
				for (temp = tox; temp <= fromx; temp++) {
					if (orthogonal_grid[temp + fromy * orthox] == 0) orthogonal_grid[temp + fromy * orthox] = 2;
				}
				for (temp = fromx; temp <= tox; temp++) {
					if (orthogonal_grid[temp + fromy * orthox] == 0) orthogonal_grid[temp + fromy * orthox] = 2;
				}
			} else { // case JumpB
				glVertex3f(nodes[n1]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
				glVertex3f(nodes[n1]->xcoord+poff,0.5+(float)nodes[n1]->level+poff,0.0);
				glVertex3f(nodes[n2]->xcoord+poff,0.5+(float)nodes[n2]->level+poff,0.0);
				glVertex3f(nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
			}
		} else if ((obstacle_left==0) && (obstacle_upper==0)) { // case 1A
			glVertex3f(nodes[n1]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
			glVertex3f(nodes[n1]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
			glVertex3f(nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
			for (temp = tox; temp <= fromx; temp++) {
				if (orthogonal_grid[temp + toy * orthox] == 0) orthogonal_grid[temp + toy * orthox] = 2;
			}
			for (temp = fromx; temp <= tox; temp++) {
				if (orthogonal_grid[temp + toy * orthox] == 0) orthogonal_grid[temp + toy * orthox] = 2;
			}
			for (temp = toy; temp <= fromy; temp++) {
				if (orthogonal_grid[fromx + temp * orthox] == 0) orthogonal_grid[fromx + temp * orthox] = 2;
			}
			for (temp = fromy; temp <= toy; temp++) {
				if (orthogonal_grid[fromx + temp * orthox] == 0) orthogonal_grid[fromx + temp * orthox] = 2;
			}
		} else if ((obstacle_right==0) && (obstacle_lower==0)) { // case 1B
			glVertex3f(nodes[n1]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
			glVertex3f(nodes[n2]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
			glVertex3f(nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
			for (temp = tox; temp <= fromx; temp++) {
				if (orthogonal_grid[temp + fromy * orthox] == 0) orthogonal_grid[temp + fromy * orthox] = 2;
			}
			for (temp = fromx; temp <= tox; temp++) {
				if (orthogonal_grid[temp + fromy * orthox] == 0) orthogonal_grid[temp + fromy * orthox] = 2;
			}
			for (temp = toy; temp <= fromy; temp++) {
				if (orthogonal_grid[tox + temp * orthox] == 0) orthogonal_grid[tox + temp * orthox] = 2;
			}
			for (temp = fromy; temp <= toy; temp++) {
				if (orthogonal_grid[tox + temp * orthox] == 0) orthogonal_grid[tox + temp * orthox] = 2;
			}
		} else { // case 3Bends
			if (nodes[n1]->xcoord > nodes[n2]->xcoord) {
				off = 0.5; 
			} else {
				off = -0.5;
			}
			glVertex3f(nodes[n1]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
			glVertex3f(nodes[n1]->xcoord+poff,0.5+(float)nodes[n1]->level+poff,0.0);
			glVertex3f(off+nodes[n2]->xcoord+poff,0.5+(float)nodes[n1]->level+poff,0.0);
			glVertex3f(off+nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
			glVertex3f(nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
		}

		glEnd();



	}
	for (i=0; i < pptr->length - 1; i++) {
		n1 = pptr->nodeArray[i];
		n2 = pptr->nodeArray[i+1];

		fromx = (int)(nodes[n1]->xcoord + 0.1);
		fromy = nodes[n1]->level;
		tox = (int)(nodes[n2]->xcoord + 0.1);
		toy = nodes[n2]->level;

		obstacle_left = obstacle_right = obstacle_upper = obstacle_lower = 0;
		for (temp = fromx + 1; temp < tox; temp++) {
			if (orthogonal_grid[temp + fromy * orthox] != 0) obstacle_lower = 1;
			if (orthogonal_grid[temp + toy * orthox] != 0) obstacle_upper = 1;
		}
		for (temp = fromy + 1; temp < toy; temp++) {
			if (orthogonal_grid[fromx + temp * orthox] != 0) obstacle_left = 1;
			if (orthogonal_grid[tox + temp * orthox] != 0) obstacle_right = 1;
		}
		for (temp = tox + 1; temp < fromx; temp++) {
			if (orthogonal_grid[temp + fromy * orthox] != 0) obstacle_lower = 1;
			if (orthogonal_grid[temp + toy * orthox] != 0) obstacle_upper = 1;
		}
		for (temp = toy + 1; temp < fromy; temp++) {
			if (orthogonal_grid[fromx + temp * orthox] != 0) obstacle_left = 1;
			if (orthogonal_grid[tox + temp * orthox] != 0) obstacle_right = 1;
		}

		glBegin(GL_LINE_STRIP);

		if ((fromx == tox) && ((fromy == toy + 1) || (fromy == toy - 1))) { // case 0A
			glVertex3f(nodes[n1]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
			glVertex3f(nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
		} else if ((fromy == toy) && ((fromx == tox + 1) || (fromx == tox - 1))) { // case 0B
			glVertex3f(nodes[n1]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
			glVertex3f(nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
		} else if (fromx == tox) {
			if (obstacle_left==0) { // case 0A
				glVertex3f(nodes[n1]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
				glVertex3f(nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
				for (temp = toy; temp <= fromy; temp++) {
					if (orthogonal_grid[fromx + temp * orthox] == 0) orthogonal_grid[fromx + temp * orthox] = 2;
				}
				for (temp = fromy; temp <= toy; temp++) {
					if (orthogonal_grid[fromx + temp * orthox] == 0) orthogonal_grid[fromx + temp * orthox] = 2;
				}
			} else { // case JumpA
				glVertex3f(nodes[n1]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
				glVertex3f(0.5+nodes[n1]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
				glVertex3f(0.5+nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
				glVertex3f(nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
			}
		} else if (fromy == toy) {
			if (obstacle_lower==0) { // case 0B
				glVertex3f(nodes[n1]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
				glVertex3f(nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
				for (temp = tox; temp <= fromx; temp++) {
					if (orthogonal_grid[temp + fromy * orthox] == 0) orthogonal_grid[temp + fromy * orthox] = 2;
				}
				for (temp = fromx; temp <= tox; temp++) {
					if (orthogonal_grid[temp + fromy * orthox] == 0) orthogonal_grid[temp + fromy * orthox] = 2;
				}
			} else { // case JumpB
				glVertex3f(nodes[n1]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
				glVertex3f(nodes[n1]->xcoord+poff,0.5+(float)nodes[n1]->level+poff,0.0);
				glVertex3f(nodes[n2]->xcoord+poff,0.5+(float)nodes[n2]->level+poff,0.0);
				glVertex3f(nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
			}
		} else if ((obstacle_left==0) && (obstacle_upper==0)) { // case 1A
			glVertex3f(nodes[n1]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
			glVertex3f(nodes[n1]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
			glVertex3f(nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
			for (temp = tox; temp <= fromx; temp++) {
				if (orthogonal_grid[temp + toy * orthox] == 0) orthogonal_grid[temp + toy * orthox] = 2;
			}
			for (temp = fromx; temp <= tox; temp++) {
				if (orthogonal_grid[temp + toy * orthox] == 0) orthogonal_grid[temp + toy * orthox] = 2;
			}
			for (temp = toy; temp <= fromy; temp++) {
				if (orthogonal_grid[fromx + temp * orthox] == 0) orthogonal_grid[fromx + temp * orthox] = 2;
			}
			for (temp = fromy; temp <= toy; temp++) {
				if (orthogonal_grid[fromx + temp * orthox] == 0) orthogonal_grid[fromx + temp * orthox] = 2;
			}
		} else if ((obstacle_right==0) && (obstacle_lower==0)) { // case 1B
			glVertex3f(nodes[n1]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
			glVertex3f(nodes[n2]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
			glVertex3f(nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
			for (temp = tox; temp <= fromx; temp++) {
				if (orthogonal_grid[temp + fromy * orthox] == 0) orthogonal_grid[temp + fromy * orthox] = 2;
			}
			for (temp = fromx; temp <= tox; temp++) {
				if (orthogonal_grid[temp + fromy * orthox] == 0) orthogonal_grid[temp + fromy * orthox] = 2;
			}
			for (temp = toy; temp <= fromy; temp++) {
				if (orthogonal_grid[tox + temp * orthox] == 0) orthogonal_grid[tox + temp * orthox] = 2;
			}
			for (temp = fromy; temp <= toy; temp++) {
				if (orthogonal_grid[tox + temp * orthox] == 0) orthogonal_grid[tox + temp * orthox] = 2;
			}
		} else { // case 3Bends
			if (nodes[n1]->xcoord > nodes[n2]->xcoord) {
				off = 0.5; 
			} else {
				off = -0.5;
			}
			glVertex3f(nodes[n1]->xcoord+poff,(float)nodes[n1]->level+poff,0.0);
			glVertex3f(nodes[n1]->xcoord+poff,0.5+(float)nodes[n1]->level+poff,0.0);
			glVertex3f(off+nodes[n2]->xcoord+poff,0.5+(float)nodes[n1]->level+poff,0.0);
			glVertex3f(off+nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
			glVertex3f(nodes[n2]->xcoord+poff,(float)nodes[n2]->level+poff,0.0);
		}

		glEnd();



	}


	for (i=0;i<orthox*orthoy;i++) {
		if (orthogonal_grid[i] == 2) orthogonal_grid[i] = 0;
	}

}


// draw between x = 0 and x = 10,
// draw between y = 0 and y = 1,
// draw between z = 0 and z = 1.
// in between time periods s and e inclusive
// draw all announcements.
void Graph::DrawAnnPaths(int s, int e) {

	
	int spi;
	int epi;
	float t2,t3;
	float t, w; // start univ time, window univ time
	int i, j, n1, n2;
	int up;
	Path *pptr;

	spi = pindices[s];
	if (e<511) {
		epi = pindices[e+1];
	} else {
		epi = npaths;
	}

	//t = (float)paths[spi]->univtime; // starting time of the window
	t = (float)(s*tinter) + (float)paths[0]->univtime; // starting time of the window
	//w = (float)paths[epi]->univtime - (float)paths[spi]->univtime; 
	w = (e - s + 1) * tinter;
	// window size in terms of time

	for (i=spi;i<epi;i++) {

		t2 = (float)(paths[i]->univtime-t)/w;
		if (publication) {
			if (t2<0.5) {
				glColor3f(2.0*(0.5-t2),t2,0.0);
			} else {
				glColor3f(0.0,1.0-t2,t2-0.5);
			}
		} else {
			if (t2<0.5) {
				glColor3f(1.0,2.0*(0.5-t2),0.0);
			} else {
				glColor3f(1.0-2.0*(t2-0.5),0.0,2.0*(t2-0.5));
			}
		}

		if (color_by_route) {
			up = paths[i]->dpid;
			glColor3f(pcolors[up][0],pcolors[up][1],pcolors[up][2]);
		}


		t2 = 10.0 * t2;

		pptr = paths[i];
		if (pptr->length > 0) {	
			n1 = root;
			n2 = pptr->nodeArray[0];
			glLineWidth(1);
			glBegin(GL_LINES);
			glVertex3f(t2,(float)nodes[n1]->level,nodes[n1]->xcoord);
			glVertex3f(t2,(float)nodes[n2]->level,nodes[n2]->xcoord);
			glEnd();
		}
		for (j=0; j < pptr->length - 1; j++) {
			n1 = pptr->nodeArray[j];
			n2 = pptr->nodeArray[j+1];
			glLineWidth(1);
			glBegin(GL_LINES);
			glVertex3f(t2,(float)nodes[n1]->level,nodes[n1]->xcoord);
			glVertex3f(t2,(float)nodes[n2]->level,nodes[n2]->xcoord);
			glEnd();	
		}
		if (i<epi-1) {
			t3 = 10.0*(float)(paths[i+1]->univtime-t)/w;
		} else {
			t3 = t2;
		}
		up = paths[i]->dpid;
		glColor3f(pcolors[up][0],pcolors[up][1],pcolors[up][2]);
		glBegin(GL_QUADS);
		glVertex3f(t2,-1.0,0.0);
		glVertex3f(t2,-1.0,10.0);
		glVertex3f(t3,-1.0,10.0);
		glVertex3f(t3,-1.0,0.0);
		glEnd();

		if (paths[i]->length == 0) {

			glColor3f(1.0,1.0,1.0);
			glBegin(GL_QUADS);
			glVertex3f(t2,-1.0,0.0);
			glVertex3f(t2,-1.0,10.0);
			glVertex3f(t2,-2.0,10.0);
			glVertex3f(t2,-2.0,0.0);
			glEnd();
			glColor3f(0.5,0.5,0.5);
			glBegin(GL_QUADS);
			glVertex3f(t2,-1.0,0.0);
			glVertex3f(t3,-1.0,0.0);
			glVertex3f(t3,-2.0,0.0);
			glVertex3f(t2,-2.0,0.0);
			glEnd();
			glBegin(GL_QUADS);
			glVertex3f(t2,-1.0,10.0);
			glVertex3f(t3,-1.0,10.0);
			glVertex3f(t3,-2.0,10.0);
			glVertex3f(t2,-2.0,10.0);
			glEnd();

		}

	}


}

void Graph::DrawNodes(int n) {

	int i, j, k;
	float off;
	char as_str[16];

	off = ((float)n  * 1.5)/100.0;
	glColor3f(1.0,1.0,1.0);
	glPointSize(n+2);
	glBegin(GL_POINTS);
	for (i=0;i<orthox;i++) {
		for (j=0;j<orthoy;j++) {
			if (orthogonal_grid[i+j*orthox]==1) {
				glVertex3f(off+(float)i,off+(float)j,-0.1);
			}
		}
	}
	glEnd();
	glColor3f(brightness,brightness,brightness);
	for (i=0;i<orthox;i++) {
		for (j=0;j<orthoy;j++) {
			if (orthogonal_grid[i+j*orthox]==1) {
				sprintf(as_str,"%d",orthogonal_grid_AS[i+j*orthox]);
				for (k=0;k<strlen(as_str);k++) {
					glRasterPos3f(off+0.1+(float)i+0.1*(float)k,off+(float)j,-0.1);
					glutBitmapCharacter(GLUT_BITMAP_TIMES_ROMAN_10,as_str[k]);
				}
			}
		}
	}

}

void Graph::DrawCustomHighlightTopology() {

	int i, j, k, p, sd;
	int found, keepgoing;

	if (orthograph!=NULL) delete orthograph;

	orthograph = new Graph();

	// ****** begin make orthograph

	orthograph->npaths = 0;
	orthograph->ndistinctpaths = 0;
	orthograph->root = 0;

	p = 0;

	for (sd=0; sd<N_SHADOW; sd++) {

		i = shadowpaths[sd];

		if ((i < npaths) && (i >= 0)) {

			orthograph->paths[p] = new Path();
			
			orthograph->paths[p]->timestamp = paths[i]->timestamp;
			orthograph->paths[p]->year = paths[i]->year;
			orthograph->paths[p]->month = paths[i]->month;
			orthograph->paths[p]->day = paths[i]->day;
			orthograph->paths[p]->hour = paths[i]->hour;
			orthograph->paths[p]->min = paths[i]->min;

			for (j=0; j<paths[i]->length; j++) {
				orthograph->paths[p]->nodeArray[j] = paths[i]->nodeArray[j];
			}
		
			orthograph->paths[p]->length = paths[i]->length;
			orthograph->npaths++;
			p++;

			// set unique path
			found = 0;
			for (k=0;((k<orthograph->ndistinctpaths)&(!found));k++) {
				if (orthograph->distinctpaths[k].length==orthograph->paths[p-1]->length) {
					keepgoing = 1;
					for (j=0;((j<orthograph->distinctpaths[k].length)&&(keepgoing));j++) {
						if (orthograph->distinctpaths[k].nodeArray[j] !=
							orthograph->paths[p-1]->nodeArray[j]) {
							keepgoing = 0;
						}
					}
					if (keepgoing) {
						found = 1;
						orthograph->paths[p-1]->dpid = k;
					}
				}
			}
			if (found==0) {
				// create new unique path
				for (j=0;j<orthograph->paths[p-1]->length;j++) {
					orthograph->distinctpaths[orthograph->ndistinctpaths].nodeArray[j] = 
						orthograph->paths[p-1]->nodeArray[j];
				}
				orthograph->distinctpaths[orthograph->ndistinctpaths].length = orthograph->paths[p-1]->length;
				orthograph->paths[p-1]->dpid = orthograph->ndistinctpaths;
				orthograph->ndistinctpaths++;
			}	
		}
	}

	j = 0;
	for (sd=0; sd<N_SHADOW; sd++) {
		i = shadowpaths[sd];
		if ((i < npaths) && (i >= 0)) j++;
	}

	if (j > 0) {
		orthograph->ConstructGraph();
		orthograph->DrawNodes(j);
		orthograph->nodes[orthograph->root]->DrawYourself(j);
	}

	
	// ****** end make orthograph



	for (sd=0; sd<N_SHADOW; sd++) {

		i = shadowpaths[sd];

		if ((i < npaths) && (i >= 0)) orthograph->DrawDiagonal(sd,sd);
		//if ((i < npaths) && (i >= 0)) orthograph->DrawOrthogonal(sd,sd);

	}

}


void Graph::DrawPathsInSlots(int s, int e) {


	int spi;
	int epi;
	float t2,t3;
	float t, w; // start univ time, window univ time
	int i, j, n1, n2, sd, p;
	int up;
	Path *pptr;

	spi = pindices[s];
	if (e<511) {
		epi = pindices[e+1];
	} else {
		epi = npaths;
	}

	printf("highlighted path is %d\n", highlightedpath + firstwritepath);

	t = (float)paths[spi]->univtime; // starting time of the window
	w = (float)paths[epi]->univtime - (float)paths[spi]->univtime; 
	// window size in terms of time

	for (i=spi;(i<epi && draw_window_paths);i++) {
		
		t2 = (float)(paths[i]->univtime-t)/w;	

		if (publication) {
			if (t2<0.5) {
				glColor3f(2.0*(0.5-t2),t2,0.0);
			} else {
				glColor3f(0.0,1.0-t2,t2-0.5);
			}
			glLineWidth(2);
		} else {
			if (t2<0.5) {
				glColor3f(1.0,2.0*(0.5-t2),0.0);
			} else {
				glColor3f(1.0-2.0*(t2-0.5),0.0,2.0*(t2-0.5));
			}
			glLineWidth(1);
		}
		pptr = paths[i];
		if (pptr->length > 0) {	
			n1 = root;
			n2 = pptr->nodeArray[0];
			glBegin(GL_LINES);
			glVertex3f(nodes[n1]->xcoord,(float)nodes[n1]->level,0.1);
			glVertex3f(nodes[n2]->xcoord,(float)nodes[n2]->level,0.1);
			glEnd();
		}
		for (j=0; j < pptr->length - 1; j++) {
			n1 = pptr->nodeArray[j];
			n2 = pptr->nodeArray[j+1];
			glBegin(GL_LINES);
			glVertex3f(nodes[n1]->xcoord,(float)nodes[n1]->level,0.1);
			glVertex3f(nodes[n2]->xcoord,(float)nodes[n2]->level,0.1);
			glEnd();
		}

	}


	// ***** draw highlighted path *************************************



	for (sd=0; sd<N_SHADOW; sd++) {

		i = shadowpaths[sd];
		
		if ((i < npaths) && (i >= 0)){
			glColor3f(pcolors[sd][0], pcolors[sd][1], pcolors[sd][2]);
			glLineWidth(2+2*sd);
			pptr = paths[i];
			if (pptr->length > 0) {	
				n1 = root;
				n2 = pptr->nodeArray[0];
				glBegin(GL_LINES);
				glVertex3f(nodes[n1]->xcoord,(float)nodes[n1]->level,0.5-0.01*(float)sd);
				glVertex3f(nodes[n2]->xcoord,(float)nodes[n2]->level,0.5-0.01*(float)sd);
				glEnd();
			}
			for (j=0; j < pptr->length - 1; j++) {
				n1 = pptr->nodeArray[j];
				n2 = pptr->nodeArray[j+1];
				glBegin(GL_LINES);
				glVertex3f(nodes[n1]->xcoord,(float)nodes[n1]->level,0.5-0.01*(float)sd);
				glVertex3f(nodes[n2]->xcoord,(float)nodes[n2]->level,0.5-0.01*(float)sd);
				glEnd();
			}
			glLineWidth(1);
		}
		
	}

}

void Graph::DrawCircleSegment(float x1, float x2, float y, int cind1, int cind2) {

	float ang1, ang2;
	float midx, midy;
	float theta, theta1, theta2;
	float r;
	float cx, cy;
	float len;
	float frac;

	if (x2 < x1 + 0.01) return;

	midx = 0.5 * (x1 + x2);
	midy = y + 0.25;

	ang1 = atan((midx-x1)/(midy-y));
	ang2 = PI - 2.0 * ang1;

	len = (midx-x1)/tan(ang2);
	r = len + (midy - y);
	cx = midx;
	cy = y - len;

	theta1 = atan(len/(x2-midx));
	theta2 = PI - theta1;

	glBegin(GL_LINE_STRIP);
	for (theta = theta1; theta <= theta2; theta += 0.001) {
		frac = (theta-theta1)/(theta2-theta1);
		if (changes_only) {
			glColor3f(0.0,0.0,1.0);
		} else {
			glColor3f(((1.0-frac)*linearNodeColors[cind2][0])+(frac*linearNodeColors[cind1][0]),
				((1.0-frac)*linearNodeColors[cind2][1])+(frac*linearNodeColors[cind1][1]),
				((1.0-frac)*linearNodeColors[cind2][2])+(frac*linearNodeColors[cind1][2]));
		}
		glVertex3f(cx + r * cos(theta),cy + r * sin(theta),0.0);
	}
	glEnd();

}

void Graph::DrawCrescent(float x1, float x2, float y, float h1, float h2) {

	float ang1, ang2;
	float midx, midy;
	float theta, theta1, theta2;
	float r;
	float cx, cy;
	float len;

	if (x2 < x1 + 0.01) return;

	midx = 0.5 * (x1 + x2);
	midy = y + h1;

	ang1 = atan((midx-x1)/(midy-y));
	ang2 = PI - 2.0 * ang1;

	len = (midx-x1)/tan(ang2);
	r = len + (midy - y);
	cx = midx;
	cy = y - len;

	theta1 = atan(len/(x2-midx));
	theta2 = PI - theta1;

	for (theta = theta1; theta < theta2; theta += 0.001) {
		glBegin(GL_QUADS);
		glColor3f(0.0,0.0,1.0);
		glVertex3f(cx + r * cos(theta),cy + r * sin(theta),0.0);
		glColor3f(0.0,0.0,0.0);
		glVertex3f(cx + r * cos(theta),cy + r * sin(theta) + (h2-h1),0.0);
		glColor3f(0.0,0.0,0.0);
		glVertex3f(cx + r * cos(theta+0.001),cy + r * sin(theta+0.001) + (h2-h1),0.0);
		glColor3f(0.0,0.0,1.0);
		glVertex3f(cx + r * cos(theta+0.001),cy + r * sin(theta+0.001),0.0);
		glEnd();
	}

}

void Graph::DrawCylinder(float x1, float x2, float y) {

	float ang1, ang2;
	float midx, midy;
	float theta, theta1, theta2;
	float r;
	float cx, cy;
	float len;

	if (x2 < x1 + 0.01) return;

	midx = 0.5 * (x1 + x2);
	midy = y + 0.25;

	ang1 = atan((midx-x1)/(midy-y));
	ang2 = PI - 2.0 * ang1;

	len = (midx-x1)/tan(ang2);
	r = len + (midy - y);
	cx = midx;
	cy = y - len;

	theta1 = atan(len/(x2-midx));
	theta2 = PI - theta1;

	glColor3f(0.0,0.0,1.0);
	for (theta = theta1; theta < theta2; theta += 0.001) {
		glBegin(GL_QUADS);
		glVertex3f(cx + r * cos(theta),cy + r * sin(theta),0.0);
		glVertex3f(cx + r * cos(theta),cy + r * sin(theta) - 1.0,0.0);
		glVertex3f(cx + r * cos(theta+0.001),cy + r * sin(theta+0.001) - 1.0,0.0);
		glVertex3f(cx + r * cos(theta+0.001),cy + r * sin(theta+0.001),0.0);
		glEnd();
	}

}

void Graph::DrawLinear() {

	int i, j, k, cind1, cind2, sd;
	Path *pptr;
	int n1, n2;
	char as_str[16];

	// ***** draw highlighted path *************************************

	for (sd=0; sd<N_SHADOW; sd++) {

		i = shadowpaths[sd];
		if ((i < npaths) && (i >= 0)){
			glLineWidth(2);
			pptr = paths[i];
			if (pptr->length > 0) {	
				n1 = root;
				n2 = pptr->nodeArray[0];
				cind1 = nodes[n1]->linearX % 7;
				cind2 = nodes[n2]->linearX % 7;
				glPointSize(5);
				glBegin(GL_POINTS);
				if (!changes_only) {
					glColor3f(linearNodeColors[cind1][0],linearNodeColors[cind1][1],linearNodeColors[cind1][2]);
				} else {
					glColor3f(1.0,1.0,1.0);
				}
				glVertex3f((float)nodes[n1]->linearX,(float)sd,0.1);
				if (!changes_only) {
					glColor3f(linearNodeColors[cind2][0],linearNodeColors[cind2][1],linearNodeColors[cind2][2]);
				} else {
					glColor3f(1.0,1.0,1.0);
				}
				glVertex3f((float)nodes[n2]->linearX,(float)sd,0.1);
				glEnd();

				
				if (changes_only) {
					glLineWidth(5);
					glBegin(GL_LINE_STRIP);
					glColor3f(0.0,0.0,1.0);
					if ((sd+1 < N_SHADOW) && (shadowpaths[sd+1] < npaths) && (shadowpaths[sd+1] >= 0)) {
						glVertex3f((float)nodes[n1]->linearX,(float)sd+1.0,0.0);
					}
					glVertex3f((float)nodes[n1]->linearX,(float)sd,0.0);
					if (sd > 0) glVertex3f((float)nodes[n1]->linearX,(float)sd-1.0,0.0);
					glEnd();
				}

				if (changes_only) {
					glLineWidth(5);
					glBegin(GL_LINE_STRIP);
					if ((sd+1 < N_SHADOW) && (shadowpaths[sd+1] < npaths) && (shadowpaths[sd+1] >= 0)) {
						if (paths[shadowpaths[sd+1]]->FindNode(n2)) {
							glColor3f(0.0,0.0,1.0);
							glVertex3f((float)nodes[n2]->linearX,(float)sd+1.0,0.0);
						} else {
							glColor3f(0.0,0.0,0.0);
							glVertex3f((float)nodes[n2]->linearX,(float)sd+0.5,0.0);
						}
					}
					glColor3f(0.0,0.0,1.0);
					glVertex3f((float)nodes[n2]->linearX,(float)sd,0.0);
					if (sd > 0) { 
						if (paths[shadowpaths[sd-1]]->FindNode(n2)) {
							glColor3f(1.0,0.0,1.0);
							glVertex3f((float)nodes[n2]->linearX,(float)sd-1.0,0.0);
						} else {
							glColor3f(0.0,0.0,0.0);
							glVertex3f((float)nodes[n2]->linearX,(float)sd-0.5,0.0);
						}
					}
					glEnd();
				}

				DrawCircleSegment((float)nodes[n1]->linearX,(float)nodes[n2]->linearX,(float)sd,cind1,cind2);

				if (changes_only) {

					if ((sd+1 < N_SHADOW) && (shadowpaths[sd+1] < npaths) && (shadowpaths[sd+1] >= 0)) {
						if (paths[shadowpaths[sd+1]]->FindNode(n2)) {
						} else {
							DrawCrescent((float)nodes[n1]->linearX,(float)nodes[n2]->linearX,(float)sd,0.25,0.5);
						}
					}
					if (sd > 0) { 
						if (paths[shadowpaths[sd-1]]->FindNode(n2)) {
							DrawCylinder((float)nodes[n1]->linearX,(float)nodes[n2]->linearX,(float)sd);
						} else {
							DrawCrescent((float)nodes[n1]->linearX,(float)nodes[n2]->linearX,(float)sd,0.25,0.0);
						}
					}

				}

				if (!changes_only) {
					glColor3f(linearNodeColors[cind1][0]*brightness,
						linearNodeColors[cind1][1]*brightness,
						linearNodeColors[cind1][2]*brightness);
				} else {
					glColor3f(1.0,1.0,1.0);
				}

				sprintf(as_str,"%d", n1);
				for (j=0;j<strlen(as_str);j++) {
					glRasterPos3f(0.2 + (float)nodes[n1]->linearX + 0.2*(float)j,(float)sd-0.2,0.1);
					glutBitmapCharacter(GLUT_BITMAP_TIMES_ROMAN_10,as_str[j]);
				}
				if (!changes_only) {
					glColor3f(linearNodeColors[cind2][0]*brightness,
						linearNodeColors[cind2][1]*brightness,
						linearNodeColors[cind2][2]*brightness);
				} else {
					glColor3f(1.0,1.0,1.0);
				}
				sprintf(as_str,"%d", n2);
				for (j=0;j<strlen(as_str);j++) {
					glRasterPos3f(0.2 + (float)nodes[n2]->linearX + 0.2*(float)j,(float)sd-0.2,0.1);
					glutBitmapCharacter(GLUT_BITMAP_TIMES_ROMAN_10,as_str[j]);
				}
			
			
			
			}
			for (j=0; j < pptr->length - 1; j++) {

				n1 = pptr->nodeArray[j];
				n2 = pptr->nodeArray[j+1];
				cind1 = nodes[n1]->linearX % 7;
				cind2 = nodes[n2]->linearX % 7;

				glPointSize(5);
				glBegin(GL_POINTS);
				if (!changes_only) {
					glColor3f(linearNodeColors[cind2][0],linearNodeColors[cind2][1],linearNodeColors[cind2][2]);
				} else {
					glColor3f(1.0,1.0,1.0);
				}
				glVertex3f((float)nodes[n2]->linearX,(float)sd,0.1);
				glEnd();
				
				if (changes_only) {
					glLineWidth(5);
					glBegin(GL_LINE_STRIP);
					if ((sd+1 < N_SHADOW) && (shadowpaths[sd+1] < npaths) && (shadowpaths[sd+1] >= 0)) {
						if (paths[shadowpaths[sd+1]]->FindNode(n2)) {
							glColor3f(0.0,0.0,1.0);
							glVertex3f((float)nodes[n2]->linearX,(float)sd+1.0,0.0);
						} else {
							glColor3f(0.0,0.0,0.0);
							glVertex3f((float)nodes[n2]->linearX,(float)sd+0.5,0.0);
						}
					}
					glColor3f(0.0,0.0,1.0);
					glVertex3f((float)nodes[n2]->linearX,(float)sd,0.0);
					if (sd > 0) { 
						if (paths[shadowpaths[sd-1]]->FindNode(n2)) {
							glColor3f(0.0,0.0,1.0);
							glVertex3f((float)nodes[n2]->linearX,(float)sd-1.0,0.0);
						} else {
							glColor3f(0.0,0.0,0.0);
							glVertex3f((float)nodes[n2]->linearX,(float)sd-0.5,0.0);
						}
					}
					glEnd();
				}
				
				glLineWidth(2);

				DrawCircleSegment((float)nodes[n1]->linearX,(float)nodes[n2]->linearX,(float)sd,cind1,cind2);

				if (changes_only) {

					if ((sd+1 < N_SHADOW) && (shadowpaths[sd+1] < npaths) && (shadowpaths[sd+1] >= 0)) {
						if (paths[shadowpaths[sd+1]]->FindLink(n1,n2)) {
						} else {
							DrawCrescent((float)nodes[n1]->linearX,(float)nodes[n2]->linearX,(float)sd,0.25,0.5);
						}
					}
					if (sd > 0) { 
						if (paths[shadowpaths[sd-1]]->FindLink(n1,n2)) {
							DrawCylinder((float)nodes[n1]->linearX,(float)nodes[n2]->linearX,(float)sd);
						} else {
							DrawCrescent((float)nodes[n1]->linearX,(float)nodes[n2]->linearX,(float)sd,0.25,0.0);
						}
					}

				}

				if (!changes_only) {
					glColor3f(linearNodeColors[cind2][0]*brightness,
						linearNodeColors[cind2][1]*brightness,
						linearNodeColors[cind2][2]*brightness);
				} else {
					glColor3f(1.0,1.0,1.0);
				}
				sprintf(as_str,"%d", n2);
				for (k=0;k<strlen(as_str);k++) {
					glRasterPos3f(0.2 + (float)nodes[n2]->linearX + 0.2*(float)k,(float)sd-0.2,0.1);
					glutBitmapCharacter(GLUT_BITMAP_TIMES_ROMAN_10,as_str[k]);
				}


			}
			glLineWidth(1);
		}

	
	
	
	
	
	
	}



}


void Graph::DrawOtherPathsInSlots(int s, int e, Graph *gptr, int id) {


	int spi;
	int epi;
	float t2,t3;
	float t, w; // start univ time, window univ time
	int i, j, n1, n2;
	int up;
	Path *pptr;

	spi = gptr->pindices[s];
	if (e<511) {
		epi = gptr->pindices[e+1];
	} else {
		epi = gptr->npaths;
	}

	t = (float)gptr->paths[spi]->univtime; // starting time of the window
	w = (float)gptr->paths[epi]->univtime - (float)gptr->paths[spi]->univtime; 
	// window size in terms of time

	for (i=spi;i<epi;i++) {
		
		t2 = (float)(gptr->paths[i]->univtime-t)/w;	

		if (publication) {
			glColor3f(pcolors[id][0],pcolors[id][1],pcolors[id][2]);
			glLineWidth(2);
		} else {
			glColor3f(pcolors[id][0],pcolors[id][1],pcolors[id][2]);
			glLineWidth(1);
		}
		pptr = gptr->paths[i];
		if (pptr->length > 0) {	
			n1 = root;
			n2 = pptr->nodeArray[0];
			glBegin(GL_LINES);
			glVertex3f(nodes[n1]->xcoord,(float)nodes[n1]->level,0.1);
			glVertex3f(nodes[n2]->xcoord,(float)nodes[n2]->level,0.1);
			glEnd();
		}
		for (j=0; j < pptr->length - 1; j++) {
			n1 = pptr->nodeArray[j];
			n2 = pptr->nodeArray[j+1];
			glBegin(GL_LINES);
			glVertex3f(nodes[n1]->xcoord,(float)nodes[n1]->level,0.1);
			glVertex3f(nodes[n2]->xcoord,(float)nodes[n2]->level,0.1);
			glEnd();
		}

	}

	if (publication) {
		glColor3f(pcolors[id][0],pcolors[id][1],pcolors[id][2]);
	} else {
		glColor3f(pcolors[id][0],pcolors[id][1],pcolors[id][2]);
	}
	glLineWidth(3);
	i = gptr->shadowpath;
	if ((i < gptr->npaths) && (i >= 0)){
		pptr = gptr->paths[i];
		if (pptr->length > 0) {	
			n1 = root;
			n2 = pptr->nodeArray[0];
			glBegin(GL_LINES);
			glVertex3f(nodes[n1]->xcoord,(float)nodes[n1]->level,0.2);
			glVertex3f(nodes[n2]->xcoord,(float)nodes[n2]->level,0.2);
			glEnd();
		}
		for (j=0; j < pptr->length - 1; j++) {
			n1 = pptr->nodeArray[j];
			n2 = pptr->nodeArray[j+1];
			glBegin(GL_LINES);
			glVertex3f(nodes[n1]->xcoord,(float)nodes[n1]->level,0.2);
			glVertex3f(nodes[n2]->xcoord,(float)nodes[n2]->level,0.2);
			glEnd();
		}
	}
	glLineWidth(1);


}


void Graph::DrawPath(int p) {
	Path *pptr;
	int i, n1, n2;
	pptr = paths[p];
	//printf("draw path %d\n",p);
	if (pptr->length > 0) {	
		n1 = root;
		n2 = pptr->nodeArray[0];
		glColor3f(1.0,1.0,0.0);
		glLineWidth(3);
		glBegin(GL_LINES);
		glVertex2f(nodes[n1]->xcoord,(float)nodes[n1]->level);
		glVertex2f(nodes[n2]->xcoord,(float)nodes[n2]->level);
		glEnd();
	}
	for (i=0; i < pptr->length - 1; i++) {
		n1 = pptr->nodeArray[i];
		n2 = pptr->nodeArray[i+1];
		glColor3f(1.0,1.0,0.0);
		glLineWidth(3);
		glVertex2f(nodes[n1]->xcoord,(float)nodes[n1]->level);
		glVertex2f(nodes[n2]->xcoord,(float)nodes[n2]->level);
		glEnd();
	}
}

void Graph::DrawPrevPath(int p, float m) {
	Path *pptr;
	int i, n1, n2;
	pptr = paths[p];
	//printf("draw path %d\n",p);
	if (pptr->length > 0) {	
		n1 = root;
		n2 = pptr->nodeArray[0];
		//glColor3f(0.8*m,0.2*m,0.0);
		glColor3f(0.0,1.0,0.0);
		glLineWidth(3);
		glBegin(GL_LINES);
		glVertex2f(nodes[n1]->xcoord,(float)nodes[n1]->level);
		glVertex2f(nodes[n2]->xcoord,(float)nodes[n2]->level);
		glEnd();
	}
	for (i=0; i < pptr->length - 1; i++) {
		n1 = pptr->nodeArray[i];
		n2 = pptr->nodeArray[i+1];
		//glColor3f(0.8*m,0.2*m,0.0);
		glColor3f(0.0,1.0,0.0);
		glLineWidth(3);
		glBegin(GL_LINES);
		glVertex2f(nodes[n1]->xcoord,(float)nodes[n1]->level);
		glVertex2f(nodes[n2]->xcoord,(float)nodes[n2]->level);
		glEnd();
	}
}

void Graph::DrawPathPtr(Path *pptr) {
	int i, n1, n2;
	if (pptr->length > 0) {	
		n1 = root;
		n2 = pptr->nodeArray[0];
		glColor3f(0.0,0.0,0.6);
		glLineWidth(3);
		glBegin(GL_LINES);
		glVertex2f(nodes[n1]->xcoord,(float)nodes[n1]->level);
		glVertex2f(nodes[n2]->xcoord,(float)nodes[n2]->level);
		glEnd();
	}
	for (i=0; i < pptr->length - 1; i++) {
		n1 = pptr->nodeArray[i];
		n2 = pptr->nodeArray[i+1];
		glColor3f(0.0,0.0,1.0);
		glLineWidth(3);
		glBegin(GL_LINES);
		glVertex2f(nodes[n1]->xcoord,(float)nodes[n1]->level);
		glVertex2f(nodes[n2]->xcoord,(float)nodes[n2]->level);
		glEnd();
	}
}


int Graph::DetectCycle() {

	nodes[root]->InitDFS();
	return nodes[root]->DetectCycle();

}

void Graph::Init() {

	int i;
	for (i=0;i<npaths;i++) {
		delete paths[i];
	}
	npaths = 0;
	for (i=0;i<MAX_N_NODES_IN_GRAPH;i++) {
		if (nodes[i]!=NULL) {
			delete nodes[i];
			nodes[i] = NULL;
		}
	}
	selectedPoint = -1;
	peer1 = peer2 = peer3 = -1;
}

void Graph::SelectPoint(int i, int j) {
	int n;
	int set = 0;
	printf("select point called %d %d\n", i, j);
	for (n=0;(n<MAX_N_NODES_IN_GRAPH)&&(!set);n++) {
		if ((nodes[n]!=NULL) && (nodes[n]->xcoord == i) && (nodes[n]->level == j)) {
			selectedPoint = n;
			set = 1;
		}
	}
	if (!set) {
		selectedPoint = -1;
	}
	printf("selected point %d\n", selectedPoint);
}

void Graph::MovePoint(int i, int j) {
	if (selectedPoint >= 0) {
		nodes[selectedPoint]->xcoord = i;
		nodes[selectedPoint]->level = j;
	}
}

void Graph::AdvanceTime(int &t) {
	int p;
	int a;
	int n;
	Path *pptr;
	if ((peer1<0)&&(peer2<0)&&(peer3<0)) {
		t++;
		return;
	} else {
		for (p = t+1; p<npaths; p++) {
			pptr = paths[p];
			for (a = 0; a<pptr->length; a++) {
				n = pptr->nodeArray[a];
				if ((n==peer1)||(n==peer2)||(n==peer3)) {
					t = p;
					return;
				}
			}
		}
	}
	t++;
	return;
}







