List all path between vertices

[vumajc]

I have a need to list all the path available to traverse between any 2 given vertices. Does this exist? Thoughts on how to implement it?

[dominikbraun]

I'll add it to the list of algorithms to implement.

[deitch]

I was just looking for something like this. I can lay out my issue, maybe there is an alternate route.

I have a directed acyclical graph. Let's say it has nodes A,B,C,D,E,F and part of the current edge list is A->B->C->D

I want to add D->A, which causes a cycle. The graph catches, it, which is good.

The only reason C->D is because some algorithm I used determined that D satisfies some C dependency. But, it turns out that F also does. So I could remove C->D, add in C->F, and now D->A will not cause a cycle.

That part is somewhat easy, and ShortestPath() reveals it. But there may be more depencenies, e.g. maybe B->E->F->D also, so it is not the shortest path, but only will reveal itself after I remove C->D.

Essentially, I am looking for: give me all of the paths that A depends on D, so I can recalculate them and then be able to add D->A.

If there is a better way to do this, I am very much up for it.

[dominikbraun]

@deitch You may take a look at #137 and see if that approach would work for you – I haven't had the time for a review yet.

[deitch]

Yeah, I think that would do it. I haven't looked at the implementation, but the concept works. Although AllPathsBetweenTwoVertices() is quite the mouthful. If the shortest path is ShortestPath(a, b), maybe this should just be Paths(a, b)?

[dominikbraun]

@deitch That's right, maybe Paths, AllPaths or AllPathsBetween would do the job, but we'll see.