You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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.
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)?
Activity
dominikbraun commentedon Apr 13, 2023
I'll add it to the list of algorithms to implement.
feat(dominikbraun#82): List all path between vertices
feat(dominikbraun#82): List all path between vertices
feat(dominikbraun#82): List all path between vertices
feat(dominikbraun#82): List all path between vertices
feat(dominikbraun#82): List all path between vertices
feat(dominikbraun#82): List all path between vertices
List all paths between vertices (dominikbraun#82)
List all paths between vertices (dominikbraun#82)
deitch commentedon Jun 26, 2023
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 commentedon Jun 27, 2023
@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 commentedon Jun 27, 2023
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 isShortestPath(a, b), maybe this should just bePaths(a, b)?dominikbraun commentedon Jun 29, 2023
@deitch That's right, maybe
Paths,AllPathsorAllPathsBetweenwould do the job, but we'll see.