Switch to an adjacency list storage of vertices.

[etiennedeg]

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.

[jirka-fink]

Let me emphasize that I use tuples in the adjacency lists only for demonstration purposes. My goal was to show that there should be a function which returns pairs of a neighbor and edge's weight of a given vertex. Furthermore, there should also be a function returning all edges with their weights.

I do not think there exists a best graph representation for all cases, so there should be more representation. The documentation can recommend one for users without theoretical background and advanced users can choose.

I do not understand why @etiennedeg needs to generate the weight matrix. A user choose one graph representation and keep it.

[etiennedeg]

In the API, the weights function return a weight matrix. This is used in a lot of place in the codebase and probably in a lot of users code. In the 2.0, we would like to revisit a bit how the weights are treated, so it might reduce the needs to use the weights function, but it will probably still matter.

[jirka-fink]

OK. So I would recommend to change the API so that a weight matrix is no longer needed and every representation of a weighted graph is required to provide functions for accessing weights.