The Compressed Adjacency Matrix Data Structure

To save the code and input files without insertion of strange characters, try right clicking on the file names and using the "Save as" option.

The code as shown in class:

  1. bit.h
  2. main.c
  3. io.c

Compile with either:

gcc *.c

g++ *.c

Some input files in adjacency list format:

  1. ik4me: K4 minus one edge.
  2. idodec: The dodecahedron.
  3. i_icos: An icosahedron (the dual graph of the dodecahedron).
  4. c060: The C60 fullerenes.

To run on the dodecahedron:

Unix:

a.out < idodec > ododec

DOS:

./a.exe < idodec > ododec

BUG FIX: on Feb. 4: In bit.h, I changed: 

long bit[] = {020000000000,010000000000,04000000000,02000000000,01000000000,
              0400000000,0200000000,0100000000,040000000,020000000,010000000,
              04000000,02000000,01000000,0400000,0200000,0100000,040000,020000,
              010000,04000,02000,01000,0400,0200,0100,040,020,010,04,02,01};
to be: 
int bit[] = {020000000000,010000000000,04000000000,02000000000,01000000000,
              0400000000,0200000000,0100000000,040000000,020000000,010000000,
              04000000,02000000,01000000,0400000,0200000,0100000,040000,020000,
              010000,04000,02000,01000,0400,0200,0100,040,020,010,04,02,01};

The previous version will run fine on machines where a long and an int both have the same number of bits (on my machine, I have 32 bits for both) but may not run correctly if the long integers have more bits than the integers.