graphlib - a low-level graph library in C

This library is intended for experimenting with different low-level representations of undirected graphs, especially for Markov chain Monte Carlo algorithms, where the critical factor is being able to flip an edge as quickly as possible. It should also be useful for other applications involving simulations of random processes on graphs, although for applications in which the nodes carry state information, it will be necessary to add another software layer to represent this.

It currently includes three implementations, each having an identical interface. Thus, by simply changing an include file, you can see the effect of a different implementation. All versions have O(1) edge lookup time, but hash is roughly 5 times slower than char_array and bitmatrix.

• char_array - the full adjacency matrix is stored as an array of arrays of chars. Uses 8 times as much storage as bitmatrix, but has faster lookup. Good for small, dense graphs
• bitmatrix - one bit per edge; the bits are packed into arrays of bytes. The full adjacency matrix stored as an array of such bit vectors. Good for medium size, dense graphs
• hash - stores edge information in a hash table. Currently about 5 times slower than the first two implementations, but can handle much larger graphs. Good for large, sparse graphs. (needs glib)

The hash and bitmatrix graph types automatically keep track of the node degrees.

html documentation is included in the package.