Sparse matrices

Our algorithms typically take an adjacency matrix in a sparse CSR format as entry .

It is useful to understand how this format works in order to code basic graph routines:

Assume you have instanciated a csr_matrix A representing the adjacency of the graph G = (V, E) with the usual triplet of np.ndarray:

• row = np.array([...]) of length |E|,
• col = np.array([...]) of length |E|,
• data = np.array([...]) of length |E|,

such that for any k A[row[k], col[k]] = data[k].

The csr_matrix has instanciated three main attributes:

• indptr = np.array([...]) of length |V|+1,
• indices = np.array([...]) of length |E|,
• data = np.array([...]) of length |E|.

indices and data have the same elements as the arguments col and data but sorted such that:

• indices[indptr[i]:indptr[i+1]] are the neighbors of node i,
• data[indptr[i]:indptr[i+1]] are the weights of the corresponding edges.