8
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.