```
#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);
}

```