[BUG] `enumerate_paths` does not give all paths

[SimonEnsemble]

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

[Krastanov]

Thank you for reporting this! A volunteer maintainer will probably not be able to tackle this in the near term (we are stretch rather thin), but if you are interested in debugging and submitting a fix, I would be happy to help along.

[Kiwy3]

Hello,

If possible, I would be interested in working on this issue. I looked into it briefly, and it seems that the bug comes from using the same enumerate_paths for both Bellman–Ford and Dijkstra, although Bellman–Ford does not store predecessors or path counts, which are now needed to enumerate all paths.

I was thinking of writing a new enumerate_paths method with dispatch based on DijkstraState, but there may be a better way to handle this.

[henrik-wolf]

Given that most other enumerate_paths methods seem to be dispatching on the AbstractPathState, I think that adding a dispatch for the DijkstraState would (probably) be the right way to go. The main thing that I am worried with this is that the whole enumerate_paths api seems to (implicitly) assume that each path is uniquely identified by an o-d pair, as reflected by the return types:

enumerate_paths(my_dsp)::Vector{Vector{Int}}  # vector of paths, one for each vertex
enumerate_paths(my_dsp, 1)::Vector{Int}  # one path, for one destination
enumerate_paths(my_dsp, [1,2,3])::Vector{Vector{Int}}  # vector of paths, one for each index in [1,2,3]

Changing the return types would be very breaking, changing the return types based on the runtime value of my_dsp will lead to type instability, and will add another layer to the already somewhat convoluted story of what exactly enumerate_paths will return for any given input... (I would also consider this approach mildly breaking, as the current behaviour is (not very clearly) stated in the documentation, but also not really what you would expect if you just call enumerate_paths on a path state that is supposed to hold all paths)

I feel having a function that lets you get all paths, including alternates, seems nonetheless like a valuable thing to have. I would rather suggest adding another function like collect_paths_with_alternatives or collect_all_paths (maybe enumerate_all_paths, but I am not sure why is says "enumerate" in the name, as there is clearly no enumeration going on) and put a warning/explanation into the docstring for enumerate_paths.

[SimonEnsemble]

FWIW, here is my implementation for my project:

"""
find ALL shortest paths starting from a source node.
"""
function find_all_shortest_paths(
    g::SimpleGraph, src::Int; ℓ_max::Int=typemax(Int)
)::Vector{Vector{Int}}
    @assert is_connected(g)

    sps = Vector{Vector{Int}}()
	# find all (src, ..., dst) paths for ∀ dst
	dsp = dijkstra_shortest_paths(g, src, allpaths=true)

	for dst = 1:nv(g)
		#=
		construct all (src, ..., dst) paths
		=#
		all_paths = Vector{Vector{Int}}()

		stack = [(dst, Int[])]
		while ! isempty(stack)
			current_node, current_path = pop!(stack)

			# append current node (building backward: dst → ... → src)
			new_path = push!(copy(current_path), current_node)

			if current_node == src # finished!
				push!(all_paths, reverse(new_path))
				continue
			end

			for pred in dsp.predecessors[current_node] # not finished.
				push!(stack, (pred, new_path))
			end
		end

		@assert length(all_paths) == Int(dsp.pathcounts[dst])

		#=
		store paths we found
		=#
		for path in all_paths
			# length (# hops = # edges)
			if length(path) - 1 > ℓ_max
				continue # do not store
			end

			push!(sps, path)
		end
	end

    return sps
end

[Krastanov]

@Kiwy3 , thanks for volunteering on this, pardon the slow engagement. If you can contribute fixes, rework suggestions, and help with improving the API, that would be certainly greatly appreciated (and do not hesitate to "bump" issues on which you do not get engagement -- we are struggling to get enough volunteers to help with maintenance, so bumps are certainly appreciated.)

@SimonEnsemble , could you consider submitting this as a PR. On this particular issue it would be nice to get a solution and thankfully we have a few more involved parties than usual. Be warned, there will probably be some bikeshedding over naming conventions and API design.

@henrik-wolf , I personally do not perceive much difference between "collect" and "enumerate". I guess "enumerate" implies some implicit order is available, but as long as the data structure returned implements and iterate I perceive "enumerate" as reasonable enough. To keep names consistent with (potentially imperfect) status quo, and more importantly to keep them simple, how about we go with your enumerate_all_paths?

[henrik-wolf]

@Krastanov this is of course all a bit of bikeshedding... I am fine with enumerate_all_paths just to keep consistency. We should maybe just put a pin in for whenever Graphs 2.0 will (maybe...) happen. (Just mentioning #146 for the crossref)

The main problem I have with both enumerate and collect is that they have some meaning within julia via enumerate(iter) and collect(iter), where the former returns an iterator with elements (index, value) and the latter puts all elements in iter into an Array, which is closer to what the enumerate_paths is doing.

(A long time ago, I started looking into making an interator version for the path states in #221, which may be an interesting consideration as well.)