Open s111 opened 10 months ago
Thanks for your PR! I'm currently having a busy time at work but I'm take a look as soon as I can.
You don't need an extra loop. An extra map depth map[K]int
to keep track of the actual depth of the node should be enough.
diff --git a/traversal.go b/traversal.go
index d7e232c..196dfe2 100644
--- a/traversal.go
+++ b/traversal.go
@@ -126,25 +127,26 @@ func BFSWithDepth[K comparable, T any](g Graph[K, T], start K, visit func(K, int
queue := make([]K, 0)
visited := make(map[K]bool)
+ depths := make(map[K]int)
visited[start] = true
queue = append(queue, start)
- depth := 0
+ depths[start] = 0
for len(queue) > 0 {
currentHash := queue[0]
queue = queue[1:]
- depth++
// Stop traversing the graph if the visit function returns true.
- if stop := visit(currentHash, depth); stop {
+ if stop := visit(currentHash, depths[currentHash]); stop {
break
}
for adjacency := range adjacencyMap[currentHash] {
if _, ok := visited[adjacency]; !ok {
visited[adjacency] = true
+ depths[adjacency] = depths[currentHash] + 1
queue = append(queue, adjacency)
}
}
Hi,
Thanks for making this library, awesome work!
I tried to use BFSWithDepth today and it would seem that the depth is not correctly being supplied to the callback. I see that an issue is already reported here #153.
This pull request is my attempt at resolving this bug, I hope that it looks good. I've added an inner for-loop which ensures that all vertices at the current depth is visited before incrementing the depth again at the start of the outer loop.
It looks like the test that was added with #120 doesn't actually verify the depth, so I've extracted a new test function for BFSWithDepth.
(I also took the liberty to remove what looks like some forgotten debug print statements, I hope that's OK.)