I saw several questions discussion the benefits of adjacency lists over matrices to represent a sparse undirected graph. On the other hand, none of them discuss sparse matrix representations such as scipy's coo or csr formats.

Do adjacency lists still provide benefits in this case?

Definitions of the above:

  • Adjacency list: a graph is represented as a dictionary, where each vertex is associated to the list of its neighbors (and the value of the edge): {i: [(neigh_1, val1), (neigh2, val_2)]}. Suppose these lists are linked lists ;
  • coo format: the graph is represented as a dictionary of edges: (i,j) -> value.
  • csr format: the matrix is stored row-wise. For each non-zero row, we have 2 arrays: indices[i] and values[i]. Example: indices[i] = [neigh_1, neigh_2], values[i] = [neigh1, neigh2].

Related: When are adjacency lists or matrices the better choice? and https://stackoverflow.com/questions/2218322/what-is-better-adjacency-lists-or-adjacency-matrices-for-graph-problems-in-c/5419933#5419933

  • $\begingroup$ Not everybody is an expert on scipy. Perhaps you could explain what coo and csr are, as well as what you mean by adjacency lists? $\endgroup$ – Yuval Filmus Apr 21 '20 at 12:59
  • $\begingroup$ Right, thanks for the feedback. I added details on the data structures. $\endgroup$ – Geoffrey Negiar Apr 21 '20 at 13:07
  • 1
    $\begingroup$ The csr format seems equivalent to the adjacency list format. $\endgroup$ – Laakeri Apr 21 '20 at 13:24
  • $\begingroup$ Different usages of course! Non of them is better than the other one. Each is used in some situations. $\endgroup$ – amirali Apr 21 '20 at 13:24

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.