[Port] A proposal of an all_simple_paths function implementation

[etiennedeg]

this is a port of #1540

[codecov[bot]]

Codecov Report

Merging #20 (acf0d5a) into master (6ab2160) will increase coverage by 0.00%. The diff coverage is 100.00%.

@@           Coverage Diff           @@
##           master      #20   +/-   ##
=======================================
  Coverage   99.45%   99.46%           
=======================================
  Files         106      107    +1     
  Lines        5554     5609   +55     
=======================================
+ Hits         5524     5579   +55     
  Misses         30       30           

[jpfairbanks]

What about making the default cutoff smaller? typemax(T) is just completely impractical right? Even in 32 bit int that is ~10^10. What about min(typemax(T), nv(g)^3) or something?

Also, I think we should throw an exception if you hit the cutoff. That way people know that they should either increase the cutoff and try again or give up on enumerating all the paths in the graph. Silently giving an incomplete enumeration isn't the right answer.

[jpfairbanks]

@etienneINSA, @matbesancon, Any thoughts on raising an exception if we don't yield all the simple paths? I've never needed all the simple paths, so I don't really know the application context, but I would expect that if I got a partial result, it would come with some return code I could check, or exception that I needed to catch.

[matbesancon]

Any thoughts on raising an exception if we don't yield all the simple paths?

When does this happen? I didn't see this path in the code?

[etiennedeg]

Any thoughts on raising an exception if we don't yield all the simple paths?

When does this happen? I didn't see this path in the code?

This is not implemented yet, just a thought on if we need to implement it.

Silently giving an incomplete enumeration isn't the right answer.

Agreed. I don't have a strong opinion on how to do that, but it is also possible to just return a flag. Maybe we can implement this as an iterator on simple paths ? (So no cutoff needed)

[gdalle]

Related to #106

[simonschoelly]

What is the current status of this PR? I.e. who's turn is is to review/write code?

[gdalle]

What is the current status of this PR? I.e. who's turn is is to review/write code?

I was not aware we had defined turns, I thought it was more of a "whoever has time does their bit". As far as I'm concerned, I need to hand in my thesis manuscript in a month so i'm out of the equation for now

[simonschoelly]

What is the current status of this PR? I.e. who's turn is is to review/write code?

I was not aware we had defined turns, I thought it was more of a "whoever has time does their bit". As far as I'm concerned, I need to hand in my thesis manuscript in a month so i'm out of the equation for now

No of course there is no formal process, I was just trying to understand where we are :)

Good look with your manuscript,, I will try to avoid pinging you any further then for now.

[gdalle]

Good look with your manuscript,, I will try to avoid pinging you any further then for now.

On the contrary, do ping me when you need a quick opinion, it's the only way you'll get my attention ^^ But I won't be able to contribute lengthy reviews or code until the summer has elapsed

[mschauer]

@samurai-kant We need this

[mschauer]

By using outneighbors, does this work for directed and undirected graphs?

[i-aki-y]

Hi, I am the author of the original implementation. Thank you for being so interested in my PR. I recently found this project!

I will answer some questions.

@mschauer

By using outneighbors, does this work for directed and undirected graphs?

Yes. This support both. See the example below.

println("undir:", collect(all_simple_paths(cycle_graph(4), 1, [3])))
println("dir:", collect(all_simple_paths(cycle_digraph(4), 1, [3])))
> undir[[1, 2, 3], [1, 4, 3]]
> dir[[1, 2, 3]]

@jpfairbanks

What about making the default cutoff smaller? typemax(T) is just completely impractical right? Even in 32 bit int that is ~10^10. What about min(typemax(T), nv(g)^3) or something?

The resulting paths do not have any loop. So the cutoff upper bound is: nv(g), the paths that visit all nodes. Here, I intended to set no limit for the path length by using typemax. Note that the cutoff does not mean the number of outputs but the maximum length of each individual path, in other words, the max depth of the search path.

Also, I think we should throw an exception if you hit the cutoff. That way people know that they should either increase the cutoff and try again or give up on enumerating all the paths in the graph. Silently giving an incomplete enumeration isn't the right answer.

Would you clarify the meaning of "incomplete enumeration" in your comment? If a user set cutoff=c, the user expects the paths whose lengths are less than or equal to c, and the function returns all paths that satisfy the condition. In that sense, the enumeration is complete, I think. If the user wants to limit the iteration count and restart it afterward, the user can use Iterators.Stateful and Iterators.take. See:

g = complete_graph(5)
path_iter = Iterators.Stateful(all_simple_paths(g, 1, 2))
println("first 3:", collect(Iterators.take(path_iter, 3)))
println("rests:", collect(path_iter))
> first 3:Any[[1, 2], [1, 3, 2], [1, 3, 4, 2]]
> rests:Any[[1, 3, 4, 5, 2], [1, 3, 5, 2], [1, 3, 5, 4, 2], [1, 4, 2], [1, 4, 3, 2], [1, 4, 3, 5, 2], [1, 4, 5, 2], [1, 4, 5, 3, 2], [1, 5, 2], [1, 5, 3, 2], [1, 5, 3, 4, 2], [1, 5, 4, 2], [1, 5, 4, 3, 2]]

If you want to increase the depth gradually, we need to implement a breadth-first path search. It is possible, but I think the bfs requires much more memory footprint.

Please let me know if there is anything I can do to help you move forward with your review.

[mschauer]

Thank you, and sorry that this got stalled, @i-aki-y . I think this is fine, setting the cutoff to typemax(Int) just means there is no cut-off which is a reasonable default even if unsuitable for large graphs.

[mschauer]

I have no push access, can't proceed here (e.g. resolving the conflicts).

[gdalle]

It's weird, cause as a member of JuliaGraphs you should be able to work on this PR. Maybe @etiennedeg can give you access to his branch?

[gdalle]

Superseded by #353