[BUG] enumerate_paths does not give all paths #478

Activity

1. SimonEnsemble

   added

   bugSomething isn't workingSomething isn't working

   on Dec 14, 2025
2. Krastanov commented on Dec 14, 2025

   

   Krastanov

   on Dec 14, 2025

   Member

   More actions

   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.
3. Kiwy3 commented on Jan 9, 2026

   

   Kiwy3

   on Jan 9, 2026

   More actions

   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.
4. henrik-wolf commented on Jan 9, 2026

   

   henrik-wolf

   on Jan 9, 2026

   Contributor

   More actions

   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.
5. SimonEnsemble commented on Feb 25, 2026

   

   SimonEnsemble

   on Feb 25, 2026

   Author

   More actions

   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
6. Krastanov commented on Feb 25, 2026

   

   Krastanov

   on Feb 25, 2026

   Last edited by Krastanov

   Member

   More actions

   @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?
7. henrik-wolf commented on Feb 26, 2026

   

   henrik-wolf

   on Feb 26, 2026

   Contributor

   More actions

   @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.)
8. simsurace commented on Sep 15, 2026

   

   simsurace

   on Sep 15, 2026

   Member

   More actions

   Anyone still working on this?

   👎React with 👎1Reacted by Cory Simon