feat(#82): List all path between vertices#137
feat(#82): List all path between vertices#137dominikbraun merged 3 commits intodominikbraun:mainfrom
Conversation
5b149e4 to
da075bf
Compare
179dfae to
5d136fa
Compare
5d136fa to
b760320
Compare
dominikbraun
left a comment
There was a problem hiding this comment.
Thank you for implementing this!
This is a very interesting algorithm. Do you have any sources? Where do you have it from?
@deitch and I remarked that the function name is a bit verbose and might be changed to something like AllPathsBetween before the release, but for now, this looks good to me. 👍
| for e := range adjacencyMap[element] { | ||
| var contains bool | ||
| mainStack.forEach(func(k K) { | ||
| if e == k { | ||
| contains = true | ||
| } | ||
| }) | ||
| if contains { | ||
| continue | ||
| } | ||
| newElements.push(e) | ||
| } | ||
| viceStack.push(newElements) | ||
| } |
There was a problem hiding this comment.
This could be simplified using a loop label:
adjacencies:
for e := range adjacencyMap[element] {
mainStack.forEach(func(k K) {
if e == k {
continue adjacencies
}
})
newElements.push(e)
}
viceStack.push(newElements)
}It isn't that important though, because I'm about to add a stack.contains method later.
There was a problem hiding this comment.
I got the idea from this blog (but I have not found the English-described version and the pictures in the blog has some mistakes).
I have renamed the function to AllPathsBetween.
I considered adding the method stack.contains. However, I'm not sure whether it's good or not to define the generic type of stack as comparable rather than any. Thus, I trickly used the method forEach. If a contains method is added to stack, this block of code will be nicer ~
There was a problem hiding this comment.
@tzq0301 Thanks for the link to the blog post!
I considered adding the method
stack.contains. However, I'm not sure whether it's good or not to define the generic type ofstackascomparablerather thanany.
I see. Since stack is only being used internally and only deals with hash values of type K comparable anyway, I think it is fine to constrain it to comparable.
|
This change has been released in graph v0.23.0. |
The algorithm uses 2 stack and a loop to find out all paths between 2 vertices. It could be applied to both directed-graph and undirected-graph.