# What does it mean when yen\_k shows only one route?
**URL:** https://discourse.julialang.org/t/what-does-it-mean-when-yen-k-shows-only-one-route/98132
**Category:** Geo
**Tags:** question, graphs, openstreetmapx
**Created:** [April 30, 2023, 5:09pm UTC](https://discourse.julialang.org/t/what-does-it-mean-when-yen-k-shows-only-one-route/98132 "2023-04-30T17:09:52Z")
**Posts on this page:** 12
**Page:** 1
### Author:  [@Yao\_Vang](https://discourse.julialang.org/u/Yao_Vang)
#### Post date: [April 30, 2023, 5:09pm UTC](https://discourse.julialang.org/t/what-does-it-mean-when-yen-k-shows-only-one-route/98132/1 "2023-04-30T17:09:52Z")
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:
```julia
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. 🤔 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:
```julia
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?
---
### Author:  [@gdalle](https://discourse.julialang.org/u/gdalle)
#### Post date: [April 30, 2023, 5:12pm UTC](https://discourse.julialang.org/t/what-does-it-mean-when-yen-k-shows-only-one-route/98132/2 "2023-04-30T17:12:42Z")
Hi!
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](https://github.com/JuliaGraphs/Graphs.jl/pull/183), I just have to merge it
---
### Author:  [@Yao\_Vang](https://discourse.julialang.org/u/Yao_Vang)
#### Post date: [April 30, 2023, 5:18pm UTC](https://discourse.julialang.org/t/what-does-it-mean-when-yen-k-shows-only-one-route/98132/3 "2023-04-30T17:18:14Z")
@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?
---
### Author:  [@Yao\_Vang](https://discourse.julialang.org/u/Yao_Vang)
#### Post date: [April 30, 2023, 5:58pm UTC](https://discourse.julialang.org/t/what-does-it-mean-when-yen-k-shows-only-one-route/98132/4 "2023-04-30T17:58:30Z")
@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:
```julia
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:
```julia
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:
```julia
aa = [n for n in routes[1]]
bb = [n for n in routes[1]]
aa==bb
```
It gives `true`
I’ve tried to visuliaze this from @pszufe tutorila [here] to see if there’s really one path??([OpenStreetMapX\_tutorial](https://pszufe.github.io/OpenStreetMapX_Tutorial/)), But it return a key error which I don’t know what does it mean here:
```julia
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
"*
"Length: $(length(routes[k])) nodes\n
" *
"From: $(routes[k][1]) $(round.((locs[1].lat, locs[1].lon),digits=4))\n
" *
"To: $(routes[k][end]) $(round.((locs[end].lat, locs[end].lon),digits=4))"
flm.PolyLine(
[(loc.lat, loc.lon) for loc in locs],
popup=info,
tooltip=info,
color="#$(hex(colrs[k]))"
).add_to(fm)
end
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)
fm.fit_bounds(MAP_BOUNDS)
fm
```
Key Error
```julia
KeyError: key 323 not found
Stacktrace:
[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
```
---
### Author:  [@gdalle](https://discourse.julialang.org/u/gdalle)
#### Post date: [April 30, 2023, 7:24pm UTC](https://discourse.julialang.org/t/what-does-it-mean-when-yen-k-shows-only-one-route/98132/5 "2023-04-30T19:24:49Z")
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](https://github.com/JuliaGraphs/Graphs.jl/issues/42)
Can you check what is the type of `m.g`? And also print the versions of the packages in your environment with `pkg> status`?
---
### Author:  [@Yao\_Vang](https://discourse.julialang.org/u/Yao_Vang)
#### Post date: [April 30, 2023, 9:24pm UTC](https://discourse.julialang.org/t/what-does-it-mean-when-yen-k-shows-only-one-route/98132/6 "2023-04-30T21:24:21Z")
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 😕
Do you know if there exist any alternative to `yen_k` so that I can use that instead?
And this is the status output:
```julia
[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.
```
---
### Author:  [@gdalle](https://discourse.julialang.org/u/gdalle)
#### Post date: [April 30, 2023, 9:27pm UTC](https://discourse.julialang.org/t/what-does-it-mean-when-yen-k-shows-only-one-route/98132/7 "2023-04-30T21:27:14Z")
Why do you have LightGraphs in your environment? You didn’t import it, did you?
---
### Author:  [@gdalle](https://discourse.julialang.org/u/gdalle)
#### Post date: [April 30, 2023, 9:32pm UTC](https://discourse.julialang.org/t/what-does-it-mean-when-yen-k-shows-only-one-route/98132/8 "2023-04-30T21:32:21Z")
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
---
### Author:  [@Yao\_Vang](https://discourse.julialang.org/u/Yao_Vang)
#### Post date: [April 30, 2023, 9:39pm UTC](https://discourse.julialang.org/t/what-does-it-mean-when-yen-k-shows-only-one-route/98132/9 "2023-04-30T21:39:04Z")
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?
---
### Author:  [@Yao\_Vang](https://discourse.julialang.org/u/Yao_Vang)
#### Post date: [April 30, 2023, 9:47pm UTC](https://discourse.julialang.org/t/what-does-it-mean-when-yen-k-shows-only-one-route/98132/10 "2023-04-30T21:47:45Z")
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://drive.google.com/file/d/1PX4sUJUab3_IacgO7xfNgRQBfxYtZQ5a/view?usp=share_link). ([https://www.openstreetmap.org/export#map=16/40.8152/-73.9009](https://www.openstreetmap.org/export#map=16/40.8152/-73.9009))). The visulization part gives a key error.
---
### Author:  [@pszufe](https://discourse.julialang.org/u/pszufe)
#### Post date: [May 1, 2023, 5:53pm UTC](https://discourse.julialang.org/t/what-does-it-mean-when-yen-k-shows-only-one-route/98132/11 "2023-05-01T17:53:47Z")
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?
---
### Author:  [@Yao\_Vang](https://discourse.julialang.org/u/Yao_Vang)
#### Post date: [May 1, 2023, 10:08pm UTC](https://discourse.julialang.org/t/what-does-it-mean-when-yen-k-shows-only-one-route/98132/12 "2023-05-01T22:08:31Z")
So many thanks for all your help @pszufe I’ll do that.