How row-major-matrix format would have a better run-time performance?


#1

Hi, I’m interested in the Dijkstra algorithm to find the shortest path. http://juliagraphs.github.io/LightGraphs.jl/latest/pathing.html#LightGraphs.dijkstra_shortest_paths When I was reading the documentation, I found that it has mentioned
" Use a matrix type for distmx that is implemented in row-major matrix format for better run-time." Why row-major matrix implementation would give a better performance then?


#2

Because they wrote their algorithm in a way that iterates down rows instead of columns. It should just be switched and there would be no performance difference if the algorithm is correctly changed. Indexing is all an abstraction over linear memory.


#3

@ChrisRackauckas, I’m not sure I understand that

“there would be no performance difference if the algorithm is correctly changed”

Moreover, the distmx is a symmetric matrix in this case. So, are there anything which can be done with respect to this?


#4

The distmx is only symmetric for undirected graphs.

To answer your original question, the documentation isn’t quite accurate. The distance matrix is a matrix A such that A[i, j] is the weight associated with the edge from i to j. We will correct the documentation so that it’s clearer.

(That said, have a look at https://github.com/JuliaGraphs/LightGraphs.jl/pull/920 for some history.)


#5

@sbromberger, I’m just saying I do not quite understand why using a row major matrix format would be more efficient. I did not see the logic, and got very confused. Thank you so much for your kindness.


#6

No worries. You would likely get better answers in the slack channel, though. I admit this question threw me for a loop since I didn’t recall why we made the decision we did.


#7

Ref: https://github.com/JuliaGraphs/LightGraphs.jl/pull/1120