Let's say for the following weighted, undirected graph:

enter image description here

I am given the adjacency matrix A[5][5]:


What is a simple algorithm to convert the adjacency matrix A to a CSR (compressed sparse row) graph in the format of three lists:


And how about the other way around? (ie CSR to adjacency matrix)

Similar question here


Here's the CSR representation of the graph above: (and some explanation) enter image description here

Note that each value val[i] in the adjacency matrix is at the (x,y) coordinate(col_ind[i],index of row_ptr where row_ptr[index] equals i+1)of the adjacency matrix.

Additionally, the last element of row_ptr is equal to the number of edges+1.

  • $\begingroup$ Please add an explanation of CSR. Also, what is wrong with the answers to the stackoverflow question? Finally, this sounds like a programming question. Is there a non-trivial algorithm or data structure hiding here, which is required for implementing the conversion? $\endgroup$ – Yuval Filmus Apr 24 '16 at 5:52
  • $\begingroup$ Are you saying I should migrate this question to Stack Overflow?... also here's a CSR explanation: en.wikipedia.org/wiki/Sparse_matrix $\endgroup$ – Ibrahim Apr 29 '16 at 4:40

Your Answer

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

Browse other questions tagged or ask your own question.