/*
 * This code was downloaded from  
 * ftp://dimacs.rutgers.edu/pub/netflow/matching/weighted/solver-1
 * and is presumed to be in the public domain
 */

#include "graphtypes.h"
#include <stdlib.h>
#include <stdio.h>
#include <math.h>

void AddEdge (Graph g, int n, int m, int label)
{	Edge edge1,edge2;

	edge1 = (Edge) malloc(2*sizeof(struct edge_ent));
	edge2 = edge1 + 1;

	edge1->label = label;
	edge1->endpoint = m;
	edge1->otheredge = edge2;
	edge1->prevedge = NULL;
	edge1->nextedge = g[n].adj_list;
	if (edge1->nextedge != NULL)
		edge1->nextedge->prevedge = edge1;
	g[n].adj_list = edge1;
	g[n].degree++;

	edge2->label = label;
	edge2->endpoint = n;
	edge2->otheredge = edge1;
	edge2->prevedge = NULL;
	edge2->nextedge = g[m].adj_list;
	if (edge2->nextedge != NULL)
		edge2->nextedge->prevedge = edge2;
	g[m].adj_list = edge2;
	g[m].degree++;
}

Edge FindEdge(Graph graph, int i, int j)
{	Edge edge;

	edge = graph[i].adj_list;
	while (edge!=NULL && edge->endpoint!=j)
		edge = edge->nextedge;
	if (edge==NULL) return(NULL);
	else return(edge);
}

int RemoveEdge(Graph graph, Edge edge)
{	Edge other;
	int i,j;

	if (edge==NULL) return(0);
	other = edge->otheredge;
	i = other->endpoint;
	j = edge->endpoint;
	graph[i].degree--; graph[j].degree--;
	if (edge->prevedge == NULL) {
		graph[i].adj_list = edge->nextedge;
		if (edge->nextedge != NULL)
			edge->nextedge->prevedge = NULL;
		}
	else if (edge->nextedge == NULL)
        	(edge->prevedge)->nextedge = NULL;
	else {
		(edge->nextedge)->prevedge = edge->prevedge;
		(edge->prevedge)->nextedge = edge->nextedge;
		}
	if (other->prevedge == NULL) {
		graph[j].adj_list = other->nextedge;
		if (other->nextedge != NULL)
			other->nextedge->prevedge = NULL;
		}
	else if (other->nextedge == NULL)
		(other->prevedge)->nextedge = NULL;
	else {
		(other->nextedge)->prevedge = other->prevedge;
		(other->prevedge)->nextedge = other->nextedge;
		}
	free((edge < other) ? edge : other);
	return(1);
}

int NumEdges(Graph g)
{	int i,size,edges;

	edges = 0;
	size = Degree(g,0);
	for (i=1; i<=size; i++)
		edges += Degree(g,i);
	edges /= 2;
	return(edges);
}

Graph NewGraph(int size)
{	Graph tmp;
	int i;

	tmp = (Graph) malloc((size+1)*sizeof(struct node_entry));
	for (i=1; i<=size; i++) {
		Degree(tmp,i) = 0;
		FirstEdge(tmp,i) = NULL;
		NLabel(tmp,i) = i;
		}
	Degree(tmp,0) = size;
	return(tmp);
}

EuclidGraph NewEuclid(int size)
{
	EuclidGraph xy;

	xy = (EuclidGraph) malloc((size+1)*2*sizeof(int));
	xy[0][0] = size;
	return(xy);
}

MatrixGraph NewMatrix(int size)
{
	MatrixGraph graph;
	int i;

	graph = (MatrixGraph) malloc((size*(size+1)+1)*sizeof(int));
	graph[0] = size;

	for (i=1; i<=size; i++)		/* zero the diagonal */
		graph[i*(size+1)] = 0;

	return(graph);
}

Graph CopyGraph(Graph g)
{	int i,j,size;
	Edge edge;
	Graph cp;

	size = Degree(g,0);
	cp = NewGraph(size);
	for (i=1; i<=size; i++) {
		Xcoord(cp,i) = Xcoord(g,i);
		Ycoord(cp,i) = Ycoord(g,i);
		edge = FirstEdge(g,i);
		for (j=1; j<=Degree(g,i); j++) {
			if (i < EndPoint(edge))
				AddEdge(cp,i,EndPoint(edge),ELabel(edge));
			edge = NextEdge(edge);
			}
		}
	return (cp);
}

/* Graph I/O routines */

Graph ReadGraph (int *size, char *file)
{	Graph graph;
	FILE *fp;
 	char c;
	int edges, degree, vlabel, elabel, adj_node, i, j;
	int xcoord, ycoord;

	if (file[0] == '\0') fp = stdin;
	else fp = fopen(file,"r");
	if (fp==NULL) {
		printf("ReadGraph: file %s can't be opened\n",file);
		exit(0);
		}
	fscanf(fp,"%d%d %c",size,&edges,&c);
	if (c !='U' && c!='u') {
		printf("ReadGraph: file %s does not contain an undirected graph\n",file);
		exit(0);
		}
	while (getc(fp)!='\n') ;

	graph = NewGraph(*size);
	for (i = 1; i <= *size; ++i) {
		fscanf(fp,"%d%d%d%d",&degree,&vlabel,&xcoord,&ycoord);
		NLabel(graph,i) = vlabel;
		Xcoord(graph,i) = xcoord;
		Ycoord(graph,i) = ycoord;
		while (getc(fp)!='\n') ;
		for (j = 1; j <= degree; ++j) {
			fscanf(fp,"%d%d", &adj_node, &elabel);
			while (getc(fp)!='\n') ;
			if (i<adj_node)
				AddEdge (graph,i,adj_node,elabel);
			}
		}
	fclose(fp);
	return(graph);
}

void WriteGraph (Graph graph, char *file)
{	FILE *fp;
	int size, i,j,edges;
	Edge p;

	if (file[0] == '\0') fp = stdout;
	else fp = fopen(file,"w");
	if (fp==NULL) {
		printf("WriteGraph: file %s can't be opened\n",file);
		exit(0);
		}
	size = Degree(graph,0);
	edges = NumEdges(graph);
	fprintf(fp,"%d %d U\n",size,edges);

	for (i = 1; i <= size; i++) {
		fprintf(fp,"%d %d %d %d L\n",Degree(graph,i),NLabel(graph,i),
					   Xcoord(graph,i),Ycoord(graph,i));
		p = FirstEdge(graph,i);
		for (j = 1; j <= Degree(graph,i); ++j) {
			fprintf(fp,"%d %d L\n",EndPoint(p),ELabel(p));
			p = NextEdge(p);
			}
		}
	fclose(fp);
}

EuclidGraph ReadEuclid(int *size, char *file)
{	EuclidGraph graph;
	FILE *fp;
	char c;
	int i,xcoord, ycoord;

	if (file[0]=='\0') fp=stdin;
	else fp = fopen(file,"r");
	if (fp==NULL) {
		printf("ReadEuclid: file %s can't be opened\n",file);
		exit(0);
		}
	fscanf(fp,"%d %c",size,&c);
	if (c!='E' && c!='e') {
		printf("ReadEuclid: file %s isn't Euclidean\n",file);
		exit(0);
		}
	while (getc(fp)!='\n');
	graph = NewEuclid(*size);

	for (i=1; i<=*size; ++i) {
		fscanf(fp,"%d%d",&xcoord,&ycoord);
		while (getc(fp)!='\n') ;
		graph[i][0] = xcoord;
		graph[i][1] = ycoord;
		}
	fclose(fp);
	return (graph);
}

void WriteEuclid(EuclidGraph graph, char *file)
{	FILE *fp;
	int size, i;

	if (file[0] == '\0') fp = stdout;
	else fp = fopen(file,"w");
	if (fp==NULL) {
		printf("WriteEuclid: file %s can't be opened\n",file);
		exit(0);
		}
	size = graph[0][0];
	fprintf(fp,"%d E\n",size);
	for (i = 1; i <= size; i++) 
		fprintf(fp,"%d %d\n",graph[i][0],graph[i][1]);
	fclose(fp);
}

MatrixGraph ReadMatrix(int *size, char *file)
{	MatrixGraph graph;
	FILE *fp;
	char c;
	int i,j,k;

	if (file[0]=='\0') fp=stdin;
	else fp = fopen(file,"r");
	if (fp==NULL) {
		printf("ReadMatrix: file %s can't be opened\n",file);
		exit(0);
		}
	fscanf(fp,"%d %c",size,&c);
	if (c!='M' && c!='m') {
		printf("ReadMatrix: file %s isn't a distance matrix\n",file);
		exit(0);
		}
	while (getc(fp)!='\n');
	graph = NewMatrix(*size);

	for (i=1; i<*size; i++) {
		for (j=i+1; j<=*size; j++) {
			fscanf(fp,"%d",&k);
			graph[i*(*size)+j] = graph[j*(*size)+i] = k;
			}
		while (getc(fp)!='\n');
		}
	fclose(fp);
	return(graph);
}

void WriteMatrix(MatrixGraph graph, char *file)
{	FILE *fp;
	int size, i, j;

	if (file[0] == '\0') fp = stdout;
	else fp = fopen(file,"w");
	if (fp==NULL) {
		printf("WriteMatrix: file %s can't be opened\n",file);
		exit(0);
		}
	size = graph[0];
	fprintf(fp,"%d M\n",size);
	for (i = 1; i < size; i++) {
		for (j=i+1; j<=size; j++)
			fprintf(fp,"%d ",graph[i*size+j]);
		fprintf(fp,"\n");
		}
	fclose(fp);
}

/* Euclidean distance routines */

int eucdist (EuclidGraph graph, int i, int j) /* Find the distance between two points */
			/* 10K x 10K unit square */
                  
        
{	int dv,dh;
	register int k, l;

	dv = graph[i][0]-graph[j][0];
	dh = graph[i][1]-graph[j][1];
	k = dv*dv + dh*dh;
	if (k==0) return(0);
	if (dv<0) dv = -dv;
	if (dh<0) dh = -dh;
	l = dv + dh;
	l = (l + k/l)>>1;
	l = (l + k/l)>>1;
	l = (l + k/l)>>1;
	l = (l + k/l)>>1;
	return ((l*l<k) ? ++l : l);
}


int eucdist2 (EuclidGraph graph, int i, int j) /* Find the distance between two points */
			/* 1M x 1M unit square */
                  
        
{	double dv,dh,d;
	int l;

	dv = (double) graph[i][0]-graph[j][0];
	dh = (double) graph[i][1]-graph[j][1];
	d  = sqrt(dv*dv + dh*dh);
	l  = (int) d;
	return((d-l > .000000001) ? l+1 : l);
}


int eucdistsq(EuclidGraph graph, int i, int j) /* Find the square of the dist between two points */
                  
        
{
	register int dv,dh;

	dv = graph[i][0]-graph[j][0];
	dh = graph[i][1]-graph[j][1];
	return(dv*dv+dh*dh);
}