#include <EWS/graph.h>

int iscomplete(nbl) ULONG *nbl;
{
	ULONG knoten = nbl[0]-1;
	if (nbl[knoten] == (knoten + 1 + knoten * (knoten -1))) return TRUE;
	return FALSE;

}

int compint(a,b) ULONG *a,*b;
{ 
	return *a - *b; 
}

verschmelze_knoten(pnbl,i,j)  ULONG i,j; 
ULONG **pnbl;
{
	ULONG *nbl = *pnbl, *nn;
	int k,l,ll,m,beide;
	ULONG knoten_nn, knoten_nbl;

	knoten_nbl=nbl[0]-1;
	knoten_nn=knoten_nbl-1;
	if (i>j) { 
		k=i;
		i=j;
		j=k;
	}
	m=knoten_nbl;
	nn = (ULONG *)EWS_malloc(nbl[nbl[0]-1] * sizeof(ULONG));
	for (k=0;k<knoten_nbl;k++)
		qsort(nbl+nbl[k],nbl[k+1]-nbl[k], sizeof(ULONG),compint);

	for (k=0;k<i;k++)
	{
		nn[k]=m; 
		beide=0;
		for (l=nbl[k];l<nbl[k+1];l++)
		{
			if ((nbl[l] == j) && (beide == 1)) continue;
			if (nbl[l]==i) beide=1;
			if (nbl[l]==j)
				nn[m++]=i;
			else
				nn[m++]=(nbl[l]>j?nbl[l]-1:nbl[l]);
		}
	}
	/* knoten i */
	{
		nn[i]=m;
		l = nbl[i]; 
		ll=nbl[j];
		while (l<nbl[i+1] && ll<nbl[j+1])
		{
			if (nbl[l] < nbl[ll])
			{
				nn[m++]=(nbl[l]>j?nbl[l]-1:nbl[l]);
				l++;
			}
			else if (nbl[ll] < nbl[l])
			{
				nn[m++]=(nbl[ll]>j?nbl[ll]-1:nbl[ll]);
				ll++;
			}
			else 
			{
				nn[m++]=(nbl[ll]>j?nbl[ll]-1:nbl[ll]);
				ll++;
				l++;
			}
		}
		while (l<nbl[i+1])
		{
			nn[m++]=(nbl[l]>j?nbl[l]-1:nbl[l]);
			l++;
		}
		while (ll<nbl[j+1])
		{
			nn[m++]=(nbl[ll]>j?nbl[ll]-1:nbl[ll]);
			ll++;
		}
	}
	for (k=i+1;k<j;k++)
	{
		nn[k]=m; 
		beide=0;
		for (l=nbl[k];l<nbl[k+1];l++)
		{
			if ((nbl[l] == j) && (beide == 1)) continue;
			if (nbl[l]==i) beide=1;
			if (nbl[l]==j)
				nn[m++]=i;
			else
				nn[m++]=(nbl[l]>j?nbl[l]-1:nbl[l]);
		}
	}
	/* knoten j wird ausgelassen */
	for (k=j+1;k<knoten_nbl;k++)
	{
		nn[k-1]=m; 
		beide=0;
		for (l=nbl[k];l<nbl[k+1];l++)
		{
			if ((nbl[l] == j) && (beide == 1)) continue;
			if (nbl[l]==i) beide=1;
			if (nbl[l]==j)
				nn[m++]=i;
			else
				nn[m++]=(nbl[l]>j?nbl[l]-1:nbl[l]);
		}
	}
	nn[knoten_nn]=m;
	EWS_free(nbl);
	*pnbl=nn;
}

faerbe(pnbl,farben,anz) ULONG **pnbl; 
int ***farben;
int *anz;
{
	ULONG knoten, *new_nbl;
	ULONG *nbl = *pnbl;
	int **new_farben;
	int new_anz;
	int i,j,k,l,m;
	*farben = (int **) NULL;
	knoten=nbl[0]-1;
	if (iscomplete(nbl) == TRUE)
	{
		*farben = (int **)EWS_malloc(sizeof (int *));
		(*farben)[0] = (int *)EWS_malloc(knoten * sizeof(int));
		for (i=0;i<knoten;i++)
			((*farben)[0])[i]=i+1;
		*anz =1 ;
		return;
	}
	/* such ein paar von knoten, die nicht verknuepft sind */
	for (i=0;i<knoten;i++)
		if (nbl[i+1]-nbl[i] < (knoten -1)) /* dann fehlt ein knoten */
		{
			qsort(nbl+nbl[i],nbl[i+1]-nbl[i],sizeof(ULONG),compint); /* sortiert */
			for (j=0;j<nbl[i+1]-nbl[i];j++)
			{
				if (j<i) {
					if (nbl[nbl[i]+j] >j ) /* paar gefunden */ goto aaa;
				}
				else if (j>=i) {
					if (nbl[nbl[i]+j] >(j+1) ) /* paar gefunden */ 
					{
						j++;
						goto aaa;
					}
				}
			}
			/* die ersten nbl[i+1]-nbl[i] kanten sind da */
			if (i<=j) j++;
			goto aaa;
		}
aaa:	/* die kanten (i,j) fehlt */

	fuege_kante_ein(pnbl,i,j);
	faerbe(pnbl,farben,anz);
	loesche_kante(pnbl,i,j);
	/* farbe gefunden */
	/* nun mit verschmelzen probieren */
	nbl=*pnbl;
	new_nbl = (ULONG*)EWS_malloc(nbl[nbl[0]-1] * sizeof (ULONG));
	memcpy(new_nbl,nbl, nbl[nbl[0]-1] * sizeof (ULONG));
	verschmelze_knoten(&new_nbl,i,j);
	faerbe(&new_nbl,&new_farben,&new_anz);
	EWS_free(new_nbl);
	if (new_anz > 0) {
		*anz = *anz+new_anz;
		*farben = (int **) realloc(*farben,*anz * sizeof(int *));
		for (k=0;k<new_anz;k++)
		{
			(*farben)[*anz-k-1] = (int *)EWS_malloc(knoten * sizeof(int));
			for (l=0;l<knoten;l++)
			{
				if (l==j)
					((*farben)[*anz-k-1])[l]=new_farben[k][i];
				else if (l<j)
					((*farben)[*anz-k-1])[l]=new_farben[k][l];
				else
					((*farben)[*anz-k-1])[l]=new_farben[k][l-1];
			}
			EWS_free(new_farben[k]);
		}
		EWS_free(new_farben);
	}
}


main()
{
	ULONG *nbl;
	int **f,i,j;
	nbl=random_nbl_einfach(6);
	/*
	scan_nachbarschafts_liste_ulong(&nbl);
*/
	print_nachbarschafts_liste_ulong(nbl);
	faerbe(&nbl,&f,&j);
	for (;j>0;j--)
	{
		for (i=0;i<nbl[0]-1;i++) printf(" %d ",(f[j-1])[i]);
		EWS_free(f[j-1]);
		printf("\n");
	}
	EWS_free(nbl);
	EWS_free(f);
}