Redesign floyd_warshall_shortest_paths? about lightgraphs.jl HOT 14 CLOSED

all shortest paths algorithms have _shortest_paths at the end. I'm reluctant to change the name just to make it shorter. The reason is that Dijkstra has a bunch of stuff associated with him, and we may need to disambiguate at some point.

As far as the state, I think that's ok but we need to make sure that it doesn't have some unintended consequence. Matrices are memory-expensive compared with other sparse structures - it's one of the reasons we don't use them for adjacency / distance. I'm not sure it makes a difference in shortest-path state objects, though, so if you'd like to create a PR and do some testing with very large graphs, I'm totally ok with changing it. We'll want to do the same for the other shortest-path algorithms too.

from lightgraphs.jl.

Oh, I didn't realize there were other shortest path algorithms implemented. I should've checked

Matrices are memory-expensive compared with other sparse structures - it's one of the reasons we don't use them for adjacency / distance.

Note Floyd-Warshall already uses dense matrices internally for the computation here, then performs a memory copy into a vector of vectors. I don't understand the point of this conversion. The advantage of being able to do linear algebra on the answer is quite substantial (to me, at least).

If the graph has a single connected component, then the computed distance matrix will be completely dense, and so there is absolutely no benefit in using a sparse representation. If there are N connected components, then the distance matrix will be block diagonal with N completely dense subblocks. In the latter case using a SparseMatrixCSC is still quite practicable, and still preferable IMO to a vector of vectors.

from lightgraphs.jl.

We've got Dijkstra and Bellman-Ford as well :)

Anyway - since F-W computes all-vector shortest paths (unlike the others where source vertices may be specified), I think you're right on - and I'm 100% in favor of returning a matrix. Sparse or dense, it's still n^2 since distances between unconnected components should be Inf, not 0.0 (if I'm thinking about this correctly).

Would you mind filing a PR that passes tests and I'll merge ASAP?

from lightgraphs.jl.

from lightgraphs.jl.

@sbromberger is correct; the block diagonal structure is buried in a matrix of default value Inf instead of 0, so the sparsity can only be captured with a custom sparse matrix type with a customizable default implied value (see JuliaLang/julia#10410 JuliaLang/julia#7010).

from lightgraphs.jl.

For reference, what are you doing with the results of F-W? What types of graphs and what application? It's good to have a catalog of use cases for library development.

from lightgraphs.jl.

Like I said in the OP, the distance matrix is an input to the stress majorization algorithm in GraphLayout.jl (layout_stressmajorize_adj).

from lightgraphs.jl.

In a sparse matrix a structural 0 can mean no path and an entry that is 0 can indicate path of length 0. Otherwise you put in a dense matrix and it uses inf to represent no path.

This will break things since we currently use "0" to mean "default edge weight" and explicitly pass in an empty sparse graph when a distance matrix isn't supplied. Lots of re-coding will be required here and I'm wary of making a distinction between structural 0 and explicit 0 for sparse matrices. These will fail if they ever get transformed to a dense data structure and then re-sparsed, for example. The distinction seems to be something that shouldn't be relied on.

from lightgraphs.jl.

I don't think Floyd-Warshall is worth retooling to also handle sparse matrices, since graphs with multiple disconnected components don't show up often for distance computations. If we did, the right way to do so would be a custom sparse matrix type that returned Inf for nonstored values.

from lightgraphs.jl.

If we're settled on dense matrices for F-W, the only remaining issue to resolve is parameterized types. I've still got reservations about non-Float distance matrices. Are there real use cases for rational or bigint distances, and how would we test for "not connected"? BigInt doesn't have typemax():

julia> typeof(one(BigInt))
Base.GMP.BigInt

julia> typemax(ans)
ERROR: MethodError: `typemax` has no method matching typemax(::Type{Base.GMP.BigInt})

from lightgraphs.jl.

BigInt doesn't have typemax defined because each BigInt can have a differently sized bit representation. See JuliaLang/julia#7501.

from lightgraphs.jl.

I can't comment on whether there use cases for rational distances, but again the point I'm trying to make is that the implementation of FW does not require Float64 distances, but rather it will work on any distance matrix with element types that have a maximal element and allow a (min, +) tropical algebra to be defined.

from lightgraphs.jl.

BigInt doesn't have typemax defined because each BigInt can have a differently sized bit representation.

How would you suggest we define "no edge" with BigInt distance matrices? (I note that BigFloat supports typemax() so there's no problem there.)

the implementation of FW does not require Float64 distances, but rather it will work on any distance matrix with element types that have a maximal element and allow a (min, +) tropical algebra to be defined.

Point taken. We should move forward with implementation via #38 (pending the resolution of details under discussion there).

from lightgraphs.jl.

I think we can close this out given the new features of #59. Let me know if there's anything outstanding and I'll be happy to reopen.

from lightgraphs.jl.