I’ve been using the SimpleWeightedDiGraph from the SimpleWeightedGraphs package for creating directed weighted graphs. Recently, I encountered a problem related to weight retrieval of edges.
When initializing a SimpleWeightedDiGraph with a predefined adjacency matrix, retrieving the weight of a specific edge using weights indexing returns an incorrect value, while using the get_weight function provides the correct weight.
test_matrix = [0.0 1.0 0.0;
0.0 0.0 1.0;
1.0 0.0 0.0]
test_graph = SimpleWeightedDiGraph(test_matrix)
println("Outneighbors of node 1: ", outneighbors(test_graph, 1))
test_graph.weights[1,2] # it really seems there is a bug there...
get_weight(test_graph, 1, 2)
If I initialise the directed graph using the transpose of the adjency matrix, then the test_graph.weights matches my matrix, but then the get_weight and the outneighbors function do not match anymore…so it seems the stored adjency matrix in the directed graph is the tranposed of what it should be.
You figured it out, that’s exactly what happens under the hood!
This transposed storage was chosen for performance reasons. Since (sparse) matrices in Julia are column-major, it is very fast to query all the nonzero coefficients in the column j. Usually, for directed graphs, we want outneighbors to be fast, so we need the out-neighbors of vertex j to be stored in the same column… which means we should work with the transpose of the adjacency matrix.
I agree that it is not very well documented at the moment, but there is a clue in the docstring for SimpleWeightedDiGraph:
help?> SimpleWeightedDiGraph
search: SimpleWeightedDiGraph SimpleWeightedDiGraphEdge SimpleWeightedEdge
SimpleWeightedDiGraph{T,U}
A type representing a directed weighted graph with vertices of type T and
edge weights of type U.
Fields
≡≡≡≡≡≡
• weights::SparseMatrixCSC{U,T}: weighted adjacency matrix, indexed
by (dst, src)
Right at the end, it says "indexed by (dst, src), i.e. (destination, source) of each edge. You’re welcome to submit a pull request improving this documentatin
