Matrix representation
There are many formats to represent matrices.
| Format | Adjacency matrix | COO(Edge list(Array)) | Edge list(linked list) | Adjacency list | CSR/CSC |
|---|---|---|---|---|---|
| Space | $O (\left\vert V \right\vert^2)$ | $O(\left\vert E \right\vert)$ | $O(\left\vert E \right\vert)$ | $O(\left\vert V \right\vert + \left\vert E \right\vert)$ | $O(\left\vert V \right\vert + \left\vert E \right\vert)$ |
| Read edge | $O (1)$ | $O(log \left\vert E \right\vert)$ | $O(\left\vert E \right\vert)$ | $O(deg(v))$ | $O(deg(v))$ |
| Add edge | $O (1)$ | $O(\left\vert E \right\vert)$ | $O(\left\vert E \right\vert)$ | $O(deg(v))$ | $O(\left\vert V \right\vert + \left\vert E \right\vert)$ |
| Delete edge | $O (1)$ | $O(\left\vert E \right\vert)$ | $O(\left\vert E \right\vert)$ | $O(deg(v))$ | $O(\left\vert V \right\vert + \left\vert E \right\vert)$ |
| Read neighbors | $O (\left\vert V \right\vert)$ | $O(log \left\vert E \right\vert + deg(v))$ | $O(\left\vert E \right\vert)$ | $O(deg(v))$ | $O(deg(v))$ |
| Get degree | $O (\left\vert V \right\vert)$ | $O(log \left\vert E \right\vert + deg(v))$ | $O(\left\vert E \right\vert)$ | $O(deg(v))$ | $O(1)$ |
The adjacency matrix is a straightforward 2D-array representation that stores every entry.
The edge list (COO) represents edges as an array or linked list; a specific edge can be found by binary search.
The adjacency list represents edges as a per-vertex list, keeping an array of vertex pointers.
CSR/CSC is a compact array-based representation similar to the adjacency matrix.
CSR/CSC uses a row_ptr/col_ptr array to indicate the start and end index of each row’s or column’s edges, along with arrays of column/row indices and values.
Each format has its own trade-offs. However, several formats are rarely used in modern scientific computing because real-world matrices are typically sparse. Therefore, the adjacency matrix is usually avoided. Linked-list-based edge lists and adjacency lists are also rarely used due to poor cache performance from pointer chasing.
COO is occasionally used, but CSR/CSC is the standard format because it is slightly more memory-efficient. CSR/CSC uses $\left\vert V \right\vert + 2\left\vert E \right\vert$ memory, while COO uses $3\left\vert E \right\vert$.