Graph.jl : How to interpret the output information returned by the shortest path algorithms?

Specific Domains Graphs
, , ,
1

Hi there,

I’d like to use Graph.jl package to run a shortest path algorithm. I have already read this page and am still not sure how to interpret the return traversal information of shortest path algorithm.
Let’s assume I’m interested in three of these algorithm; bellman_ford, dijkstra, and yen_k.

Here’s a small example. A Weighted digraph with 5 nodes and 5 edges :

using SimpleWeightedGraphs
using Graphs
using SplitApplyCombine
using SparseArrays




sources = [1,1,3,3,4]
destinations = [2, 3,4,5,5]
weight = [3, 0.5,1,2,1]
g = SimpleWeightedDiGraph(sources, destinations, weight)
edges(g)
weights(g)

blfs = Graphs.bellman_ford_shortest_paths(g,1)
dijk = Graphs.dijkstra_shortest_paths(g,1)


yen = Graphs.yen_k_shortest_paths(g, 1, 5, weights(g))
yen2 = Graphs.yen_k_shortest_paths(g, 1, 5, weights(g), 2)
yen2max = Graphs.yen_k_shortest_paths(g, 1, 5, weights(g), 2;maxdist=10) # there's clearly other path 1>3>4>5 with the total distance of 2.5
astar = Graphs.a_star(g, 1, 5, weights(g))

What I receive after running blfs = Graphs.bellman_ford_shortest_paths(g,1) is:

Graphs.BellmanFordState{Float64, Int64}([0, 1, 1, 3, 3], [0.0, 3.0, 0.5, 1.5, 2.5])

What information do these two lists contain? And why we have 0 in them (when there’s no nodes labeled by 0) ?

Same question for dijk = Graphs.dijkstra_shortest_paths(g,1). The return output is:

Graphs.DijkstraState{Float64, Int64}([0, 1, 1, 3, 3], [0.0, 3.0, 0.5, 1.5, 2.5], [Int64[], Int64[], Int64[], Int64[], Int64[]], [1.0, 1.0, 1.0, 1.0, 2.0], Int64[])

*----------------------------------------------------------------------------------------

According to documentation; the “yen_k” Perform Yen’s algorithm, computing k-shortest distances between source and target other vertices. Return contains distances and paths.

When I ran it, however, it does not return “K” different path but K copy of the same path. Why?
For instance:

yen2 = Graphs.yen_k_shortest_paths(g, 1, 5, weights(g), 2) returns:

Graphs.YenState{Float64, Int64}([2.5, 2.5], [[1, 3, 5], [1, 3, 5]])

Althogh there’s clearly other path 1>3>4>5 with the total distance of 2.5 also. Why it just returns 1>3>5 instead?

Also yen_k_shortest_paths, what exactly maxdist control? Is it to have a limit over the shortest distance? if so, why yen2max = Graphs.yen_k_shortest_paths(g, 1, 5, weights(g), 2;maxdist=10) does not consider 10 at all?

One more question:
How to run A* algorithm? I’ve tried different things (like astar = Graphs.a_star(g, 1, 5, weights(g))), all of which returned an error.

ERROR: MethodError: no method matching SimpleWeightedEdge{Int64, Float64}(::Int64, ::Int64)

a_star(g, s, t[, distmx][, heuristic][, edgetype_to_return])

Thanks very much,
F

2

Hi @F_A!

First of all, I agree that the documentation for shortest paths is insufficient (Insufficient documentation for shortest path functions · Issue #152 · JuliaGraphs/Graphs.jl · GitHub), I’ll try to add more details soon.

What Dijkstra and Bellman-Ford do is not just find one shortest path from a source to a target: they find the shortest paths from a source to all other vertices of the graph. This is easily stored as a shortest path tree spreading out from the source. All we need to remember is the parent of each vertex in the tree.

Let’s see how we can interpret the output thanks to the built-in REPL help mode:

julia> blfs = Graphs.bellman_ford_shortest_paths(g, 1)
Graphs.BellmanFordState{Float64, Int64}([0, 1, 1, 3, 3], [0.0, 3.0, 0.5, 1.5, 2.5])

help?> blfs
search: blfs blockfractions bellman_ford_shortest_paths enable_fzf GlobalRef

  No documentation found.

  blfs is of type Graphs.BellmanFordState{Float64, Int64}.

  Summary
  ≡≡≡≡≡≡≡≡≡

  struct Graphs.BellmanFordState{Float64, Int64}


  Fields
  ≡≡≡≡≡≡≡≡

  parents :: Vector{Int64}
  dists   :: Vector{Float64}


  Supertype Hierarchy
  ≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡

  Graphs.BellmanFordState{Float64, Int64} <: Graphs.AbstractPathState <: Any

So apparently the resulting object has two fields: parents and dists. The former gives you the predecessor of each vertex in the shortest path coming from the source, while the latter gives you the distance between said vertex and the source.

julia> blfs.parents
5-element Vector{Int64}:
 0
 1
 1
 3
 3

julia> blfs.dists
5-element Vector{Float64}:
 0.0
 3.0
 0.5
 1.5
 2.5

Since we picked 1 as the source, it has no parent (that’s what the 0 means) and the distance to it is also 0.0. Unfortunately, you need to work a little more to retrieve the actual path to a vertex v, for instance with a utility function like this one (maybe we should include it in Graphs.jl):

julia> function get_path(blfs::Graphs.BellmanFordState, v::Integer)
           u = v
           path = [u]
           while blfs.parents[u] != 0
               u = blfs.parents[u]
               pushfirst!(path, u)
           end
           return path
       end
get_path (generic function with 1 method)

julia> get_path(blfs, 1)
1-element Vector{Int64}:
 1

julia> get_path(blfs, 2)
2-element Vector{Int64}:
 1
 2

julia> get_path(blfs, 4)
3-element Vector{Int64}:
 1
 3
 4
2 Likes
3

Regarding Yen’s algorithm:

1 Like
4

Finally, for A*, the issue is that the output is a vector of edges, but SimpleWeightedGraphs does not know how to construct an edge based on source and destination alone, it also needs a weight. This has given rise to lengthy discussions (Fix A* implementation by gdalle · Pull Request #125 · JuliaGraphs/Graphs.jl · GitHub), and in the long term we probably need to change the way edges are handled by Graphs.jl as a whole (for instance with a get_edge(g, s, d) method. Feel free to contribute to the roadmap (Roadmap for Graphs.jl 2.0 · Issue #128 · JuliaGraphs/Graphs.jl · GitHub).
In the meantime, the solution is to tell a_star that it should return a vector of SimpleEdge instead, as detailed in the docs:

help?> a_star
search: a_star spectral_distance watts_strogatz spfa_shortest_paths make_edgestream

  a_star(g, s, t[, distmx][, heuristic][, edgetype_to_return])


  Compute a shortest path using the A* search algorithm
  (http://en.wikipedia.org/wiki/A%2A_search_algorithm).

  Arguments
  ≡≡≡≡≡≡≡≡≡≡≡

    •  g::AbstractGraph: the graph

    •  s::Integer: the source vertex

    •  t::Integer: the target vertex

    •  distmx::AbstractMatrix: an optional (possibly sparse) n × n matrix of
       edge weights. It is set to weights(g) by default (which itself falls
       back on Graphs.DefaultDistance).

    •  heuristic::Function: an optional function mapping each vertex to a
       lower estimate of the remaining distance from v to t. It is set to v
       -> 0 by default (which corresponds to Dijkstra's algorithm)

    •  edgetype_to_return::Type{E}: the eltype E<:AbstractEdge of the vector
       of edges returned. It is set to edgetype(g) by default. Note that the
       two-argument constructor E(u, v) must be defined, even for weighted
       edges: if it isn't, consider using E = Graphs.SimpleEdge.

And indeed, the following change works:

julia> distmx = weights(g);

julia> heuristic(v) = zero(eltype(distmx));

julia> edgetype_to_return = Graphs.SimpleEdge;

julia> astar = Graphs.a_star(g, 1, 5, distmx, heuristic, edgetype_to_return)
2-element Vector{Graphs.SimpleGraphs.SimpleEdge}:
 Edge 1 => 3
 Edge 3 => 5
1 Like
5

Hi @gdalle Many thanks for your time and Thank you very much for all the replies.

1 Like
6

Update: I just merged the first PR I mentioned, so the latest version of SimpleWeightedGraphs (1.3.0) should fix this.

1 Like
7

Hi again @gdalle Many thanks for following up on this.
Do you this one? JuliaGraphs/SimpleWeightedGraphs.jl · GitHub) which will soon be fixed thanks to a PR by @etienne_dg (rework of weighted graphs API, fixes #6 and Graphs#42 by etiennedeg · Pull Request #14 · JuliaGraphs/SimpleWeightedGraphs.jl · GitHub)

8

Yes exactly that one. The second one fixing the maxdist behavior is still under review

1 Like
9

Thanks a lot @gdalle Appreciate your time

10

No problem! Could you select one of my answers as the solution, so that this post shows up as resolved?

11

Done. Thanks again!

1 Like