enumerate paths should support DijkstraState all paths.

[bicycle1885]

The following graph is a diamond-shaped graph with two paths between 1st and 4th vertices:

using LightGraphs

g = DiGraph(4)
add_edge!(g, 1 => 2)
add_edge!(g, 2 => 4)
add_edge!(g, 1 => 3)
add_edge!(g, 3 => 4)
for path in enumerate_paths(dijkstra_shortest_paths(g, 1, allpaths=true))
    @show path
end

Apparently, there is a path 1 => 3 => 4 in the graph but it is not printed:

path = Int64[]
path = [1,2]
path = [1,3]
path = [1,2,4]

I naively thought that allpaths=true would enumerate all paths but it doesn't. Is this a bug or an intended behavior?

[sbromberger]

The graph you created only has four vertices so there cannot be an edge to vertex 5....

ETA: if you mean "the path 1->3->4", then the answer is that enumerate_paths does not (currently) treat an allpaths DijkstraState any differently than a non-allpaths. We should probably change this.

[CarloLucibello]

probably @bicycle1885 meant 1->3->4. Should not the output look like this?

path = [1]
path = [1,2]
path = [1,3]
path = [1,2,4]
path = [1,3,4]

[sbromberger]

@CarloLucibello yes - ideally. enumerate_paths was not designed to handle all_paths dijkstra states though. I'll make this an enhancement.

[bicycle1885]

if you mean "the path 1->3->4"

Sorry, I made a mistake. I meant "1 -> 3 -> 4" as you said. Edited the original post.

[sbromberger]

PS @bicycle1885 - this might make a nice easy PR if you've got some time :) I'm out of pocket for a week or two.

[bicycle1885]

It would be suitable for an exercise of a graph theory 101 class :)
Okay, I'll make a pull request later.

[sbromberger]

Yes, I didn't mean to imply it would be a challenge for you - just that if you wanted a fix quickly, it might be best for you to create the PR since I'm on vacation :)

[sbromberger]

I've given this some thought lately, and I'm not sure I want to do this after all. It's recursive and will only really work for small graphs. Please feel free to continue the discussion but I'll close this out until someone can persuade me this is generally useful.