Insufficient documentation for shortest path functions

[linkhochon]

I've created a Simple Weighted DiGraph via the following commands:

using SimpleWeightedGraphs
using Graphs
g = SimpleWeightedDiGraph(start_node, end_node, distance; combine = +) 

The start_node, end_node are 42849-element Vector{Int64} and distance are 42849-element Vector{Float64}. Afetr this command I have an {28649, 42849} directed simple Int64 graph with Float64 weights

However, when I call the following I get an error:

# s is a single node   Int64
Graphs.bellman_ford_shortest_paths(g, s, distance)
# or
bellman_ford_shortest_paths(g, s, distance)
# or
SimpleWeightedDiGraph.bellman_ford_shortest_paths(g, s, distance)

My question is: Given a set of start nodes, end nodes and their associated weights, how one can construct a weighted digraph and then compute bellman ford shortest paths for a set of sources??

[gdalle]

When you construct a weighted graph, then you don't need to specify the distance when computing shortest paths: the default value of the argument distmx = weights(g) takes care of that. But if you want to specify it, it needs to be a (sparse) matrix and not a vector, hence the name distmx. Does that solve your problem?

[linkhochon]

Hi @gdalle Thanks a lot. Yes it seems to be resolved. However, what it returns is kind of strange!

Graphs.BellmanFordState{Float64, Int64}([0, 0, 0, 0, 0, 0, 0, 0, 0, 0 … 0, 0, 0, 0, 0, 0, 0, 0, 0, 23271], [Inf, Inf, Inf, Inf, Inf, Inf, Inf, Inf, Inf, Inf … Inf, Inf, Inf, Inf, Inf, Inf, Inf, Inf, Inf, 320.04055399000003])

[linkhochon]

@gdalle could you please give me a bit more of your knowledge on this packge? By any chance is there any function that I can recall to receive all nodes within some threshold? By that I mean very similar to BellmanFord, however, I'm interested in having ID of all nodes that are reachable within some threshlod.

[etiennedeg]

The first list is the list of parents, and the second list the list of dists. The last pair is (23271, 320.04055399000003). It means that the shortest path to the last vertex is of length 320.04055399000003, and the last parent encountered on this shortest path is the vertex 23271. If dist is Inf, it means that this vertex is unreachable from the source vertex.

By calling enumerate_paths(bfs::BellmanFordState), you get the list of shortest paths.

To get the vertices reachable under some treshold, you can do findall(bfs.dists .<= treshold)

I think we should have a better documentation on how to use the result of shortest paths, the docstrings are not very satisfying.

[linkhochon]

Hi @etiennedeg thank you so very much! it is really helpful for me :)

[gdalle]

Leaving this open but renaming it to hint at the missing documentation, if that's okay with you @linkhochon. Of course now that you know how it works, you're welcome to submit a small PR to help improve the docstrings 🙂

[gdalle]

See also #77

[linkhochon]

Sorry for asking too much trivial question. But this is the last one, I promis.

bellman_ford_shortest_paths(g, s, distmx=weights(g))
bellman_ford_shortest_paths(g, ss, distmx=weights(g))

Compute shortest paths between a source s (or list of sources ss) and all other nodes in graph g using the Bellman-Ford algorithm. Return a Graphs.BellmanFordState with relevant traversal information.

Is it possible to query the required amont of time from source s to another node like s' ?

[gdalle]

What do you mean by the amount of time? If it is the distance, you can find it within the BellmanFordState object by querying bfs.dists[s, s2]

[linkhochon]

Excellent!! You really helped me a lot! Thanks @gdalle I'm grateful :)

[gdalle]

Anytime! Besides, none of these questions would be necessary if the documentation was better, so that's on us 😉