Problem with a function computing paths

[elchiconuevo]

I used some code online to output a set of paths between a source and target.

function enumerate_paths!(
  graph::LightGraphs.AbstractGraph,
  paths::Vector{Vector{Int64}},
  visited::Vector{Int64},
  target::Int64)

  nodes = LightGraphs.outneighbors(graph, visited[end])

  for i in nodes
    if i in visited
      continue
    end

    if i == target
      push!(visited, i)
      push!(paths, visited)
      println(visited)
      pop!(visited)
      break
    end
  end

  for i in nodes
    if i in visited || i == target
      continue
    end
    push!(visited, i)
    enumerate_paths!(graph, paths, visited, target)
    pop!(visited)
  end
end

function all_simple_paths(
  graph::LightGraphs.AbstractGraph,
  source::Int64,
  target::Int64)

  visited = [source]
  paths = Vector{Int64}[]

  enumerate_paths!(graph, paths, visited, target)

  return paths
end

It seems pretty strange that the function is able to print the paths accurately whereas the set of paths doesn't reflect the same. Any guesses as to what is happening here?

[jpfairbanks]

Can you show the input you provide and the output both what you got and what you expect?

[elchiconuevo]

% Input

G = DiGraph(5)
add_edge!(G, 1, 2)
add_edge!(G, 2, 3)
add_edge!(G, 3, 4)
add_edge!(G, 4, 1)
add_edge!(G, 1, 5)
add_edge!(G, 5, 2)

% Output when I run all_simple_paths(G, 1, 4)

[1, 2, 3, 4]
[1, 5, 2, 3, 4]
2-element Array{Array{Int64,1},1}:
 [1]
 [1]

What I expect is a vector containing all the paths i.e.,

 [[1, 2, 3, 4],
[1, 5, 2, 3, 4]]

[jpfairbanks]

Does filter(x->length(x)>0 && x[end]==4, enumerate_paths(bellman_ford_shortest_paths(G, 1))) get you the result you want?

I get the right answer:

julia> G = DiGraph(5)
{5, 0} directed simple Int64 graph

julia> add_edge!(G, 1, 2)
true

julia> add_edge!(G, 2, 3)
true

julia> add_edge!(G, 3, 4)
true

julia> add_edge!(G, 4, 1)
true

julia> add_edge!(G, 1, 5)
true

julia> add_edge!(G, 5, 2)
true

julia> G
{5, 6} directed simple Int64 graph

julia> bellman_ford_shortest_paths(G, 1)
LightGraphs.BellmanFordState{Int64,Int64}([0, 1, 2, 3, 1], [0, 1, 2, 3, 1])

julia> enumerate_paths(bellman_ford_shortest_paths(G, 1))
5-element Array{Array{Int64,1},1}:
 []          
 [1, 2]      
 [1, 2, 3]   
 [1, 2, 3, 4]
 [1, 5]     


julia> filter(x->length(x)>0 && x[end]==4, enumerate_paths(bellman_ford_shortest_paths(G, 1)))
1-element Array{Array{Int64,1},1}:
 [1, 2, 3, 4]

[jpfairbanks]

I think this is the reason you get different output printed than returned.

   if i == target
     push!(visited, i)
     push!(paths, visited)
     println(visited)
     pop!(visited)
     break
   end

Everything that is printed is immediately popped so nothing that is printed will be in the final result.

[elchiconuevo]

I was about to reply to your previous comment but you were faster :). So, how can I correct the code so that the final result returns the set of paths?

[jpfairbanks]

You could remove the pop!?

[elchiconuevo]

A quick update: The function now correctly outputs the paths between a source and target node. Additionally, it has an option to stop the search when the length of the paths exceed the cut-off limit.

function enumerate_paths!(
  graph::LightGraphs.AbstractGraph,
  paths::Vector{Array{Any,N} where N},
  visited::Vector{Int64},
  target::Int64,
  cutoff::Int64)

  nodes = LightGraphs.outneighbors(graph, visited[end])

  for i in nodes
    if i in visited
      continue
    end

    if length(visited) < cutoff
      if i == target
        push!(visited, i)
        push!(paths, visited)
        pop!(visited)
        break
      end
    end
  end

  for i in nodes
    if i in visited || i == target
      continue
    end
    push!(visited, i)
    enumerate_paths!(graph, paths, visited, target, cutoff)
    pop!(visited)
  end
end

function all_simple_paths(
  graph::LightGraphs.AbstractGraph,
  source::Int64,
  target::Int64,
  cutoff::Int64)

  visited = [source]
  paths = Array{Any}[]

  enumerate_paths!(graph, paths, visited, target, cutoff)

  return paths
end

[jpfairbanks]

Great news! do you want to contribute this to the library? We could do something like:

mutable struct SimplePaths{N}
  paths::Vector{Array{Any,N} where N},
  visited::Vector{Int64},
  target::Int64,
  cutoff::Int64
end

function enumerate_paths!(
  graph::LightGraphs.AbstractGraph,
  pathcoll::SimplePaths)

  nodes = LightGraphs.outneighbors(graph, pathcoll.visited[end])

  for i in nodes
    if i in pathcoll.visited
      continue
    end

    if length(pathcoll.visited) < pathcoll.cutoff
      if i == pathcoll.target
        push!(pathcoll.visited, i)
        push!(pathcoll.paths, pathcoll.visited)
        pop!(pathcoll.visited)
        break
      end
    end
  end

  for i in nodes
    if i in pathcoll.visited || i == pathcoll.target
      continue
    end
    push!(pathcoll.visited, i)
    enumerate_paths!(graph, pathcoll.paths, pathcoll.visited, pathcoll.target, pathcoll.cutoff)
    pop!(pathcoll.visited)
  end
end

function all_simple_paths(
  graph::LightGraphs.AbstractGraph,
  source::Int64,
  target::Int64,
  cutoff::Int64)

  visited = [source]
  paths = Array{Any}[]
  pathcoll = SimplePaths(paths, visited, target, cutoff
  enumerate_paths!(graph, paths)

  return paths
end

[sbromberger]

We'd want to make a few changes here to improve the efficiency, but this looks awesome.

[jpfairbanks]

@elchiconuevo would you like to write some tests and file a PR?

[elchiconuevo]

Sorry about the delay. I have some pending tasks at the chair to complete and I wouldn't be able to work on the tests for the function.

[sbromberger]

I'd prefer to see this take an AbstractPathState.

[stale]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.