<p><a href="http://people.csail.mit.edu/jfineman/csb.pdf">Buluç et al.</a> (2009) propose a storage format called <em>compressed sparse blocks</em> 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)$.</p>

CC BY-SA 2.5
2011-02-01T13:59:39.410Z
2011-02-01T13:59:39.410Z
Marcus Ritt
<p>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 <a href="http://en.wikipedia.org/wiki/Petri_net#Formulation_in_terms_of_vectors_and_matrices" rel="nofollow">state-equation</a> approach - which would presumably require me to use sparse matrices. </p>

<p>Which led me to wonder - are there are any implementations of sparse matrices providing fast enumeration in both rows <em>and</em> 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?</p>

<p>FWIW - By 'efficiently', in this case, I mean fast at enumerating the <a href="http://en.wikipedia.org/wiki/Petri_net#Formal_definition_and_basic_terminology" rel="nofollow">arcs</a> 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.</p>

<p>TIA</p>

<ds.data-structures><functional-programming><sparse-matrix>
Functional Sparse-Matrix with good performance?
Andrew Matthews
# Functional Sparse-Matrix with good performance?

(Asked by: username_0 on 2011-01-31)

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](http://en.wikipedia.org/wiki/Petri_net#Formulation_in_terms_of_vectors_and_matrices) 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](http://en.wikipedia.org/wiki/Petri_net#Formal_definition_and_basic_terminology) 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

**Tags:** ds.data-structures, functional-programming, sparse-matrix

---

## 1 answers

### Answer by username_1 on 2011-02-01. Score: 5 | Accepted answer

[Buluç et al.](http://people.csail.mit.edu/jfineman/csb.pdf) (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)$.


---

