Functional Sparse-Matrix with good performance?

Question

While writing a Petri Net program, I was faced with a choice about data structures to represent the graph. Adjacency lists (i.e. lists enumerating the arcs into and out of individual places or transitions) are easy to implement, but while I was studying the theory of petri nets, I was taken with the beauty of the matrix-based state-equation approach - which would presumably require me to use sparse matrices.

Which led me to wonder - are there are any implementations of sparse matrices providing fast enumeration in both rows and columns? If not, are there alternatives that would allow me to construct and efficiently traverse a bipartite graph in a functional language such as Erlang?

FWIW - By 'efficiently', in this case, I mean fast at enumerating the arcs incident on a given transition or place. I'd be happier to trade space for time if there are trade-offs to be made. Since the graph will not be modified after construction, it need not be particularly efficient for insertions or updates.

TIA

Answer 1

Buluç et al. (2009) propose a storage format called compressed sparse blocks which does not favour rows or columns. A $n\times n$-matrix is subdivided into $\beta\times\beta$ blocks and the list of nonzero elements in each block is stored in Z-Morton order. To list the nonzeros in a row or column you can process the $n/\beta$ blocks containing it, recursively finding the nonzeros in each block in $O(\beta)$.