All simple paths (refresh #20)

[thchr]

This refreshes #20 by @etiennedeg. (I couldn't figure out how to do it there directly and also didn't want to bother with fixing merge conflicts either)

The original implementation is by @i-aki-y in https://github.com/sbromberger/LightGraphs.jl/pull/1540.

This "refresh" also simplifies the original implementation a bit (to the extent that I understand it), implements the comments/suggestions that were made in #20 (e.g., cutoff is now set to nv(g)), and improves the documentation (and removes superfluous documentation of internal methods), and removes redundant methods (e.g., the length and collect implementations; the latter comes from Base, and the former is a performance trap).

Cc. @gdalle cf. Slack conversation about this (and him pointing out the existence of #20).

I suspect there will be some issue from Formatter.jl: but there's no clue as to what's wrong when I run it locally, just that something is wrong.

[codecov[bot]]

Codecov Report

Attention: Patch coverage is 95.16129% with 3 lines in your changes are missing coverage. Please review.

Project coverage is 97.28%. Comparing base (e773bce) to head (1c9a813). Report is 5 commits behind head on master.

Files	Patch %	Lines
src/traversals/all_simple_paths.jl	95.16%	3 Missing :warning:

Additional details and impacted files

```diff @@ Coverage Diff @@ ## master #353 +/- ## ========================================== - Coverage 97.29% 97.28% -0.02% ========================================== Files 117 118 +1 Lines 6814 6876 +62 ========================================== + Hits 6630 6689 +59 - Misses 184 187 +3 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

[gdalle]

documentation seems to be failing

[thchr]

documentation seems to be failing

Should be fixed now, thanks.

[thchr]

There is one API question we should settle: what should the set of all paths from u to v = u be? I.e., what happens when the start and end point are identical? To my mind, it should return [[u]] which is a path of zero length. Currently, however, it returns no paths, i.e., [Int[]].

I propose we change it to return [[u]] in this case.

EDIT: to be more explicit, the choices are between the following behaviors.

Current behavior:

g = path_graph(4)
@test Set(all_simple_paths(g, 1, 1)) == Set(Int[])
@test Set(all_simple_paths(g, 1, [1, 4])) == Set([[1, 2, 3, 4]])

Suggested behavior:

g = path_graph(4)
@test Set(all_simple_paths(g, 1, 1)) == Set([[1]])
@test Set(all_simple_paths(g, 1, [1, 4])) == Set([[1], [1, 2, 3, 4]])

Although, honestly, the suggested behavior is not so natural to implement in the current iterator scheme, so I'd be happy to keep as-is also.

[thchr]

I've gone ahead an implemented the proposed u = v special-casing, adding corresponding tests also.

[gdalle]

I agree with your suggestion that paths from u to u should be [u] and not []. This is also more coherent with the way lengths are measured in the algorithm: a path [u] has length 0

[thchr]

Thanks for the second review. I've updated everything accordingly, with the exception of any action on your _stepback! question: I simply don't know (and admit that I do not have time or motivation to find out at the moment; I just want something that works and doesn't stall again).

[mschauer]

Sorry I only see this now that the work is done. Anyway thank you!

[mschauer]

Cc @mwien Graphs.jl has now path enumeration