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, withrepresenting 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