JuliaGraphs / JuliaGraphs/Graphs.jl
[BUG] `enumerate_paths` does not give all paths
Nobody has claimed this yet.
- Dominant language
- Julia
- Stars
- 538
- Forks
- 128
- Avg merge
- 10h 25m
- Merged PRs (30d)
- 2
Description
the function enumerate_paths, when passed a DijkstraState, does not enumerate all paths as advertised.
below, I create a minimal example.
# construct graph
my_g = SimpleGraph(5)
add_edge!(my_g, 1, 2)
add_edge!(my_g, 3, 2)
add_edge!(my_g, 2, 4)
add_edge!(my_g, 3, 4)
add_edge!(my_g, 5, 4)
add_edge!(my_g, 5, 3)
# find all shortest paths from node 5 to other nodes
my_dsp = dijkstra_shortest_paths(my_g, 5, allpaths=true)
# enumerate paths from node 5 to 1
print(enumerate_paths(my_dsp, 1)) # only gives one path!
graphplot(my_g, nlabels=["$i" for i = 1:5])
Expected behavior
I expect enumerate_paths(my_dsp, 1) to give both:
[5, 3, 2, 1]
[5, 4, 2, 1]
but it only gives one of the paths.
Version information
Julia Version 1.12.2
Commit ca9b6662be4 (2025-11-20 16:25 UTC)
Build Info:
Official https://julialang.org release
Platform Info:
OS: macOS (arm64-apple-darwin24.0.0)
CPU: 8 × Apple M3
WORD_SIZE: 64
LLVM: libLLVM-18.1.7 (ORCJIT, apple-m3)
GC: Built with stock GC
Threads: 1 default, 1 interactive, 1 GC (on 4 virtual cores)
Status ~/.julia/environments/v1.12/Project.toml
[86223c79] Graphs v1.13.2
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with enumerate_paths and the DijkstraState produced by dijkstra_shortest_paths(..., allpaths=true), then reproduce the minimal five-node graph from the issue. Trace why enumerate_paths(my_dsp, 1) returns only one route; done means it returns both expected shortest paths, with the existing behavior verified against this example.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- julia
- Domain
- data
- Issue type
- Bug
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Active
- Clarity
- Clearly specified
- Newbie friendliness
- 72/100