Adjacency Matrix compression

general
,
1

Hi all,

I am currently working on some graph projects with a friend, and I would like to know if there is anyway to reduce the size taken by adjacency matrixes to save as many memory as possible.

I am assuming we need the Matrix representation as we need to compute flows and related stuf… But, maybe this can be done with adjacency list too…

If there’s any compression algorithm someone could point me out, I’d be very glad :slight_smile:

Thanks in advance,

Bruno

1 Like
2

Is you adjacency matrix sparse?

Not sure if you exactly want this, but you can look into page 86 and 87 of this book for some general solution. (Topic: Prufer code)

There may be ways to use bitfields and store only lower or upper triangle of adjacency matrix if graph is non-directional.

But I believe you want to handle really large data and are looking for quick retrieval.

1 Like
3

You are dealing with sparse matrix (as you mentioned saving memory), There are various representations of sparse matrices like Yale format, Compressed sparse row/Compressed sparse column, Band matrix…You can choose any of these as per your requirement.

1 Like
4

Thanks to both :slight_smile:

I will firstly try to use adjacency list representation and remove some unused vectors and also try to free some memory…

If that fails, I’ll try to use some compression scheme :smiley:

Thank you,

Bruno

1 Like