This is a WIP - does it do the right thing, does the API have the right shape, and so on.

Consider directed trail nomenclature? https://en.wikipedia.org/wiki/Path_(graph_theory)

This is very neat! I'm definitely in favor of calling this all_trails_from; perhaps another function all_trails_from_to (I'm not familiar with petgraph naming conventions) makes sense too if we're limiting the trails in an SCC to those starting in a node with incident edges from outside the SCC and ending in a node with outgoing edges to outside the SCC? I believe it would be useful for uv, but perhaps it's too far out of scope for petgraph to host that.

One question I had about this algorithm - not related to uv - if we start at 0, aren't both A, D and A, D, E, F, G valid trails from 0 to 3? The current implementation only produces the first trail. The second is disallowed because it starts with the same sequence as the first.

(I think this implementation is useful, but not sure what's correct w.r.t finding all trails.)

I would say not allowed: 3 is a duplicate node if you allow that trail.

I got confused about paths vs. trails. I think you should actually allow the second trail too, since it's purely about the edges being traversed.

@bluss I noticed this PR the other day and thought it might be worth mentioning that a very similar thing was done in a recent student project here.

Your approach is less rough to be sure, but I'm putting this out there on account of the fact that using:

pub fn all_non_repeating_paths_from<
    G: IntoEdges + GraphProp<EdgeType = Directed> + GraphProp<NodeId = N> + GraphProp<EdgeId = E>,
    N: Eq + Copy + Clone,
    E: Eq + Copy + Clone,
>(
    graph: G,
    starting_node: G::NodeId,
) -> Vec<(G::NodeId, Vec<Path<G::EdgeId>>)> { ... }

gets to avoid using HashMap, if you're into that sort of thing of course! I have no idea how much of a no-std mentality one may be going for, and in fact what got me thinking about this + noticing this PR at all is that I have been thinking how to do the same thing lazily. I'm nowhere with that thinking just yet though.

@DeliciousHair I think that suggestion changes the algorithmic complexity of the implementation (not that I've analyzed fully), there needs to be some replacement of the O(1) hashmap lookup (could use compact space of integer indexes, but that's another constraint on the graph interface required - doesn't work well with the induced subgraph usecase of NodeFiltered?)

Also a tip, you don't need to have type parameters for N and E, they are available as G::NodeId and G::EdgeId (as seen in the PR).

@Peiffap I saw your edit now. I think we say the same thing now, the current algorithm finds only one path from 0 to 1 in this graph:

• The algorithm finds only the path A
• All trails would find both A and A, B as trails from 0 to 1?

I think the current algorithm because of this is an "all simple paths" algorithm, and that's fine for me. (Is there something we're missing?)

How does this differ from the existing all_simple_paths() function? Is it just about directed vs undirected graphs?

Note that for the uv use-case this originally spawned from, I don't think trails that aren't paths are particularly interesting - they just add additional markers, if I understand correctly.

The existing all_simple_paths should also use directed graphs I think, not very familiar with it. It produces all paths between two particular vertices and the new function, now named all_simple_paths_from produces all paths from one particular vertex to all reachable from there.

User ms on the ndarray zulip endorsed the function as "it's very useful and solid" 🙂, so it's gotten one review

May I suggest that the documentation contain a note/warning added about the size of the result being potentially quite large in the case where the graph contains parallel edges?

Hi all! Is there anything else that separates the adoption of this new algorithm in the next release?

Happy to put my hand up to fix the conflicts if that will get this merged?

@DeliciousHair I think that would be helpful

Happy to put my hand up to fix the conflicts if that will get this merged?

Thanks for the offer, that'd be wonderful 🌞 Note however, that currently a new major release is in the making which will break a lot of the existing functionality, which is why this change might need some time to be adopted until the scaffolding for 0.9 is done. As the algorithm will probably mostly use the current graph traits however, it should not be affected by the first "wave" of changes, which will keep the existing graph traits intact :)

TLDR: It might take more time than usual until this PR is merged :) Please also note the algorithm doc template we are using 👍

EDIT: Forgot to link the issue laying out the changes ^^
#891

Thanks for the heads up! With that in mind, if there are no objections I'll simply make a new pr to account for these details rather than trying to massage this one into a passing state. Sound OK?