From csr.UVic.CA!wendym Tue Jan  5 01:46:39 1993
Received: from sol.UVic.CA ([128.189.65.4]) by scapa.cs.ualberta.ca with SMTP id <42169>; Tue, 5 Jan 1993 01:46:33 -0700
Received: from csr.UVic.ca by sol.UVic.CA (4.1/SMI-4.0.3-UVic-2.38TMX)
	id AA13050; Tue, 5 Jan 93 00:46:20 PST
Received: from godot.cs by csr.UVic.ca (4.1/SMI-4.0)
	id AA09078; Tue, 5 Jan 93 00:46:18 PST
Date:	Tue, 5 Jan 1993 01:46:18 -0700
From:	wendym@csr.UVic.CA (Wendy  Myrvold)
Message-Id: <9301050846.AA09078@csr.UVic.ca>
To:	joe@cs.ualberta.ca
Subject: Routine for generating the graph (hopefully).
Status: OR


The terminal I have to work on at home is really druggy
so it is sometimes hard to edit. The routine for generating
the graph is below. Please excuse any messiness. 

If you send back a 90-colouring of this graph, I'd be VERY
happy. The vertex number (0-899) and colour would tell me all I need
to know, but printing the tuple for vertex i would be nice too.
For vertex i: print_tuple(tuples[i]);

Hope you find something!

   Wendy
-------------------- Cut here-------------- gen.c
#include <stdio.h>
#define MAX_N_VERTICES 900
main()
{
int n_tuple;
int tuples[MAX_N_VERTICES][4];

int G[MAX_N_VERTICES][MAX_N_VERTICES];
int nv;
int i, j;

   nv= 900;

/*  Start with graph with no edges. */

   for (i=0; i < nv; i++)
      for (j=0; j < nv; j++)
          G[i][j]=0;

   gen_tuples(&n_tuple, tuples);
   printf("Generation done.\n"); fflush(stdout);

/* Add edges where appropriate. */

   for (i=0; i < n_tuple; i++)
       for (j=i+1; j < n_tuple; j++)
      {
/*
          printf("%2d %2d:",i,j);
          print_tuple(tuples[i]);
          printf(" and ");
          print_tuple(tuples[j]);
          printf(" are ");
*/
          if (adjacent(tuples[i], tuples[j]))
          {
/*
              printf("DEFINITELY adjacent.\n");
*/
              G[i][j]=1;
              G[j][i]=1;
          }
/*
          else printf("NOT adjacent.\n");
*/
      }

      /* Start colouring here if graph matches your data 
          structures. Otherwise, make slight change in graph
          initialization above. */

}
int print_tuple(t)
int t[];
{
   printf("(%1d, %1d, %1d, %1d)",t[0], t[1], t[2],t[3]);
}
int gen_tuples(n_tuple, tuples)
int *n_tuple;
int tuples[][4];
{
    int c1, c2, p1, p2;

    *n_tuple=0;
    for (c1=0; c1 < 5; c1++)
       for (c2=c1+1; c2<5; c2++)
          for (p1=0; p1 < 10; p1++)
             for (p2=0; p2 < 10; p2++)
             {
                 if (p1 != p2)
                 { 
                    tuples[*n_tuple][0]= c1;
                    tuples[*n_tuple][1]= c2;
                    tuples[*n_tuple][2]= p1;
                    tuples[*n_tuple][3]= p2;
                    (*n_tuple)++;
                 }
             }
}
int adjacent(p1, p2)
int p1[], p2[];
{
   int i,j;

   if (p1[0] == p2[0] && p1[1] == p2[1]) return(1);

   for (i=0; i <2; i++)
      for (j=0; j <2; j++)
      { 
          if (p1[i] == p2[j])
          {
             if (p1[i+2]!= p2[j+2]) return(1);
          }
          else
             if (p1[i+2]== p2[j+2]) return(1);
      }
   return(0);
}