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.
The hash and bitmatrix graph types automatically keep track of the node degrees.
html documentation is included in the package.