Switch to an adjacency list storage of vertices.

See this conversation

This seems to be mostly equivalent to a sparse matrix (I mentioned slower access of weights, but using binary search, I think it should be same complexity than for a sparse matrix)
You can get back the sparse matrix by simply:

• collecting the weights in the order found in the adjacency list
• concatenating the outneighbors adjacency lists
• computing the cumulative degrees of the vertices.

As shown in the discussion, the benefit obtained by iterating simultaneously weights and vertices can be also achieved with the sparse matrix implementation, although it seems a bit slower.

The proposed implementation is by storing tuples in the adjacency lists, but it might be better to store in some aside adjacency list to avoid the penalty cost of accessing tuple when considering only neighbors. (we can still zip through both lists at the same time).

At this point, I think the bigger drawback will be the linear cost for generating the weight matrix, all other computations should be asymptotically equivalent.
I think we need some benchmarking to find the best implementation, by considering both the access of a single weight and the access of weights when iterating neighbors.

Start with the linked Discourse conversation and examine the current sparse-matrix representation, adjacency lists, outneighbor access, and weight lookup behavior. Benchmark single-weight access and iteration over neighbors, then compare the proposed adjacency-list designs; done means selecting and implementing the best-supported storage approach.