What does it mean when yen_k shows only one route?

Hello everyone,

I’ve loaded a map via map = get_map_data(OSM_File_path, use_cache=false, trim_to_connected_graph=true) then randomly picked two nodeIDs to find out 5th shortest path between them. Since map.g stores a graph representation of the road network, I ran:

yen_k_shortest_paths(map.g, map.v[3786901729], map.v[9137045217], map.w, 5, maxdist=500.2).paths

No matter how much I increase the maxdist it always returns one path though. :thinking: This is happening almost for all nodeids that I have tried. Why?

On the other hand, when I build a non-real small graph with SimpleWeightedDiGraph(start, end, weight) and call yen_k it does give different path.

Is there anything special with real maps coming from osm? Or is it because I did use osmfilter?

My map was initially 400MB and then using osmfilter shrinks that to 14MB which seems to be normal. This is the filteration I ran:

osmfilter map.osm --keep="highway=motorway highway=motorway_link highway=primary highway=primary_link highway=secondary highway=secondary_link highway=tertiary highway=tertiary_link" -o=map.osm

Any idea? Or is there anything that I can do to ensure things are correct?

Sorry, it’s a longstanding bug in Graphs.jl. The fix exists in Solved bug in yen.jl by aurorarossi · Pull Request #183 · JuliaGraphs/Graphs.jl · GitHub, I just have to merge it

@gdalle it seems the issue that has mentioned at #183 says that the path given by yen_k are exceeding the threshold. right?
My issue is not that. The yen_k works fine, however, when I test it over a real map from openstreetmap, and feed it some nodes, it always return one shortest path. I’m wondering why always one?

@gdalle thanks for the link, I read it again. However, the issue is getting more strange now, if I don’t specify maxdist it copies the same routes n times. If I specify a maxdist it just gives back one!! For example:

using Graphs
using Random
using Parameters
using OpenStreetMapX
using Graphs
using PyCall
using Colors
const flm = pyimport("folium");
using OpenStreetMapXPlot

m = get_map_data(OSM_File_path, use_cache=false, trim_to_connected_graph=true );
println("The map contains $(length(m.nodes)) nodes")
println("The map boundary is  $((m.bounds)) nodes")

a,b = [point_to_nodes(generate_point_in_bounds(m), m) for _ in 1:2]
routes = Vector{Vector{Int}}()
route_times = Vector{Float64}()
route_times = yen_k_shortest_paths(m.g, m.v[a],m.v[b], m.w, 5).dists
routes = yen_k_shortest_paths(m.g, m.v[a],m.v[b], m.w, 5).paths

The output is:

5-element Vector{Vector{Int64}}:
 [323, 6886, 6887, 7219, 5051, 2439, 2440, 1379, 1371, 1401  …  904, 1012, 917, 916, 988, 2725, 924, 923, 922, 6881]
 [323, 6886, 6887, 7219, 5051, 2439, 2440, 1379, 1371, 1401  …  904, 1012, 917, 916, 988, 2725, 924, 923, 922, 6881]
 [323, 6886, 6887, 7219, 5051, 2439, 2440, 1379, 1371, 1401  …  904, 1012, 917, 916, 988, 2725, 924, 923, 922, 6881]
 [323, 6886, 6887, 7219, 5051, 2439, 2440, 1379, 1371, 1401  …  904, 1012, 917, 916, 988, 2725, 924, 923, 922, 6881]
 [323, 6886, 6887, 7219, 5051, 2439, 2440, 1379, 1371, 1401  …  904, 1012, 917, 916, 988, 2725, 924, 923, 922, 6881]

An they are all infact the samething. To check that, I ran:

aa = [n for n in routes[1]]
bb = [n for n in routes[1]]

It gives true

I’ve tried to visuliaze this from @pszufe tutorila [here] to see if there’s really one path??(OpenStreetMapX_tutorial), But it return a key error which I don’t know what does it mean here:

fm = flm.Map()
colrs = distinguishable_colors(10, [RGB(1,0.6,0.5)])
for k=1:5
    locs = [LLA(m.nodes[n],m.bounds) for n in routes[k]]
    info = "The route of Car $k\n<BR>"*
        "Length: $(length(routes[k])) nodes\n<br>" *
        "From: $(routes[k][1]) $(round.((locs[1].lat, locs[1].lon),digits=4))\n<br>" *
        "To: $(routes[k][end]) $(round.((locs[end].lat, locs[end].lon),digits=4))"
        [(loc.lat, loc.lon) for loc in locs ],

MAP_BOUNDS = [(m.bounds.min_y,m.bounds.min_x),(m.bounds.max_y,m.bounds.max_x)]
flm.Rectangle(MAP_BOUNDS, color="black",weight=6).add_to(fm)

Key Error

KeyError: key 323 not found

 [1] getindex(h::Dict{Int64, ENU}, key::Int64)
   @ Base .\dict.jl:498
 [2] (::var"#99#101")(n::Int64)
   @ Main .\none:0
 [3] iterate
   @ .\generator.jl:47 [inlined]
 [4] collect(itr::Base.Generator{Vector{Int64}, var"#99#101"})
   @ Base .\array.jl:787
 [5] top-level scope

There was another similar bug that might be relevant: [Port] [BUG] `yen_k_shortest_paths` with `k=2` returns same path twice · Issue #42 · JuliaGraphs/Graphs.jl · GitHub

Can you check what is the type of m.g? And also print the versions of the packages in your environment with pkg> status?

Thank you @gdalle I will read them carefully.
The type of m.g is showing SimpleDiGraph{Int64}. The odd thing is that if I creat a SimpleWeightedDiGraph of let’s say 10 nodes and 15 edges, and cal yen_k between any of the two nodes, it will return different paths. I don’t know whether to be suspect that there might be an issue with map.g from osmX or the yen_k itself. And unfortunaley the visulization was failed for an unknown reason to me :confused:

Do you know if there exist any alternative to yen_k so that I can use that instead?

And this is the status output:

[336ed68f] CSV v0.10.8 [5ae59095] Colors v0.12.10 [8f4d0f93] Conda v1.8.0 ⌃ [a93c6f00] DataFrames v1.4.4 [864edb3b] DataStructures v0.18.13 [a2cc645c] GraphPlot v0.5.2 [86223c79] Graphs v1.8.0  [093fc24a] LightGraphs v1.3.5 [626554b9] MetaGraphs v0.7.2 ⌃ [46757867] NetworkLayout v0.4.4 [86cd37e6] OpenStreetMapX v0.3.3 [d3d4fdd0] OpenStreetMapXPlot v0.1.4 [d96e819e] Parameters v0.12.3 [91a5bcdd] Plots v1.38.8 [438e738f] PyCall v1.95.1 [d330b81b] PyPlot v2.11.1 [47aef6b3] SimpleWeightedGraphs v1.3.0⌃ [fdbf4ff8] XLSX v0.8.4 [2f01184e] SparseArrays Info Packages marked with ⌃ have new versions available and may be upgradable.

Why do you have LightGraphs in your environment? You didn’t import it, did you?

Is this a fully reproducible example or do I need something else? I’ve reopened the issue on Graphs.jl, we’ll see if it’s still there once I merge the maxdist PR

I was working with one file from the OpenStreetMapX and in that it installed it. I don’t rembmer if I use LightGraph anywhere else.
Sould I unistall it?

Yes, it is. But there need to include a map.osm file (which I uploaded one-- sorry it was failed since it jsut allows image not *.osm but it’s this [area] an this is a small map. (https://www.openstreetmap.org/export#map=16/40.8152/-73.9009)). The visulization part gives a key error.

OpenStreetMapX migrated from LightGraphs.jl to Graphs.jl in version 0.3.0 in January 2022 and basically you should not use LightGraphs in your projects (and OpenStreetMapX will not require installing LightGraphs.jl).

Regarding the “key error” you could email me the osm file along with the source code to replicate it. But maybe this is just something regarding plotting custom routes in a map and some route has incomplete information?

1 Like

So many thanks for all your help @pszufe I’ll do that.