NOTE: graphs in this directory are stored in compressed incidence
matrix formats, with coordinate information appended to the representations
of geometric graphs.  The formats are as follows, with 
representing a carriage return character:

  0) random:
       0    (matrix type, mattype)
       size 
       density 
       bitmap   (integers of INT bits separated by spaces)
  1) geometric:
       1 
       size 
       max. distance 
       bitmap
       coordinate pairs

I append a C code fragment for reading graphs in this format,
including a macro "edge(x,y)" for telling whether there is an
edge between vertices x and y.

*******************************************

#define NMAX 1001	/* maximum number of vertices handles */
#define INT 32		/* computer word size */

#define edge(x,y) (bitmap[x][(y-1)/INT+1] & mask[y%INT])

unsigned mask[INT] =
   {
   1, 1<<31, 1<<30, 1<<29, 1<<28, 1<<27, 1<<26, 1<<25, 1<<24,
   1<<23, 1<<22, 1<<21, 1<<20, 1<<19, 1<<18, 1<<17, 1<<16,
   1<<15, 1<<14, 1<<13, 1<<12, 1<<11, 1<<10, 1<<9, 1<<8,
   1<<7, 1<<6, 1<<5, 1<<4, 1<<3, 1<<2, 1<<1
   };  /* CAUTION - assumes 32 bit machine */

int N;			/* number of vertices in graph */
int mattype;
unsigned bitmap[NMAX+1][(NMAX+1)/INT+1];
double x_coord[NMAX+1], y_coord[NMAX+1];
double dens, maxdist;
				
void readgraph(filename) 
FILE *filename;
{
   int i,j,width;

   width = N/INT + ((N%INT) != 0);

   fscanf(filename, "%d", &mattype);  /* first read matrix type */
   fscanf(filename, "%d", &N);     /* then size */
   width = N/INT + ((N%INT) != 0);  /* compute n & width */

   if (mattype == 0) {
      fscanf(filename, "%lf", &dens);
   }
   else if (mattype == 1) {
      fscanf(filename, "%lf", &maxdist);
   }

   for (i = 1; i <= N; i++)
      for (j = 1; j <= width; j++)
         fscanf(filename, "%u", &bitmap[i][j]);

   if (mattype == 1) {
	for (i = 1; i <= N; i++) {
		fscanf(filename, "%lf", &x_coord[i]);
		fscanf(filename, "%lf", &y_coord[i]);
	}
   }

}

Return to DIMACS Challenge page
Send us mail
Return to Main Page