0
$\begingroup$

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

enter image description here

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

[0][3][4][0][0]
[3][2][0][0][0]
[4][0][0][6][5]
[0][0][6][0][1]
[0][0][5][1][0]

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

row_ptr[]
col_ind[]
val[]

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

Similar question here


Edit:

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.

$\endgroup$
  • $\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.