Hacker News Reader

Comment by bee_rider | Hacker News Reader

Are the adjacency matrices in graph theory really usually dense?

For a powerful sparse adjacently matrix C library check out SuiteSparse GraphBLAS, there are binding for Python, Julia and Postgres.

https://github.com/DrTimothyAldenDavis/GraphBLAS

Same thing caught my eye. They are usually sparse.

Yep, for any decent sized graph, sparse is an absolute necessity, since a dense matrix will grow with the square of the node size, sparse matrices and sparse matrix multiplication is complex and there are multiple kernel approaches depending on density and other factors. SuiteSparse [1] handles these cases, has a kernel JIT compiler for different scenarios and graph operations, and supports CUDA as well. Worth checking out if you're into algebraic graph theory.

Using SuiteSparse and the standard GAP benchmarks, I've loaded graphs with 6 billion edges into 256GB of RAM, and can BFS that graph in under a second. [2]

[1] https://github.com/DrTimothyAldenDavis/GraphBLAS

[2] https://onesparse.com/

The article doesn't say "graphs are usually dense".

It just asserts that if you use an adjacency list, the graph is likely dense. Otherwise it makes little sense to use for a sparse graph.

An adjacency matrix seems like they gave the example most likely to irritate the mathematically inclined and confuse the outsider. Nested array access isn't that unusual.

Technically the article is saying the graphs are dense. Which might make sense, but using sparse matrices to represent sparse graphs is not unusual.

Reply on news.ycombinator.com