I'm trying to pass slices as arguments to a recursive function. Since slices are passed as reference, I believe that the recursive function that I'm passing it to should be able to perform the manipulations without any problem. I'm only using append() and therefore shouldn't have a problem with slices having inadequate capacity right?
package main
import "fmt"
func allPossiblePaths(arrGraph [8][8]bool, src int, dest int) [][]int {
var visited []bool //a slice that marks if visited
var path []int //a slice to store a possible path
var paths [][]int //a slice to store all paths
visited = make([]bool, 8) //set all nodes to unvisited
dfs(arrGraph, src, dest, visited, path, paths)
return paths
}
func dfs(myGraph [8][8]bool, src int, dest int, visited []bool, path []int, paths [][]int) {
//add current node to path
path = append(path, src)
//mark current node as visited
visited[src] = true
//if the current node is the destination
//print the path and return
if src == dest {
//make a copy of path slice
buffer := make([]int, len(path))
copy(buffer, path)
//append the copy of path slice into the slice of paths
paths = append(paths, buffer)
fmt.Println(path) //Just for debugging purpose
return
}
for i := 1; i <= 7; i++ { //loop through all nodes
//if ith node is a neighbour of the current node and it is not visited
if myGraph[src][i] && visited[i] == false {
// call dfs on the current node
dfs(myGraph, i, dest, visited, path, paths)
//mark the current node as unvisited
//so that we can other paths to the final destination
visited[i] = false
//re-slice the slice - get rid of the current node
path = path[:len(path)-1]
}
}
}
func main() {
var myGraph [8][8]bool //the graph
//creating the graph
myGraph[1] = [...]bool{false, false, true, true, false, false, true, false}
myGraph[2] = [...]bool{false, true, false, true, false, true, false, false}
myGraph[3] = [...]bool{false, true, true, false, true, false, true, false}
myGraph[4] = [...]bool{false, false, false, true, false, false, true, false}
myGraph[5] = [...]bool{false, false, true, false, false, false, true, false}
myGraph[6] = [...]bool{false, true, false, true, true, false, false, true}
myGraph[7] = [...]bool{false, false, false, false, false, false, true, false}
fmt.Println(allPossiblePaths(myGraph, 1, 7))
}
OUTPUT:
[1 2 3 4 6 7]
[1 2 7]
[1 7]
[3 2 5 7]
[4 6 7]
panic: runtime error: slice bounds out of range
goroutine 1 [running]:
panic(0x4dc300, 0xc82000a0b0)
/usr/local/opt/go/src/runtime/panic.go:481 +0x3e6
main.dfs(0x0, 0x1000001010000, 0x10001000100, 0x1000100010100, 0x1000001000000, 0x1000000010000, 0x100000101000100, 0x1000000000000, 0x3, 0x7, ...)
/home/nitrous/src/test2b/main.go:52 +0x480
main.dfs(0x0, 0x1000001010000, 0x10001000100, 0x1000100010100, 0x1000001000000, 0x1000000010000, 0x100000101000100, 0x1000000000000, 0x1, 0x7, ...)
/home/nitrous/src/test2b/main.go:45 +0x41f
main.allPossiblePaths(0x0, 0x1000001010000, 0x10001000100, 0x1000100010100, 0x1000001000000, 0x1000000010000, 0x100000101000100, 0x1000000000000, 0x1, 0x7, ...)
/home/nitrous/src/test2b/main.go:12 +0x150
main.main()
/home/nitrous/src/test2b/main.go:71 +0x423
Expected output: (achieved when using global variables instead of passing variables to a function)
[[1 2 3 4 6 7] [1 2 3 6 7] [1 2 5 6 7] [1 3 2 5 6 7] [1 3 4 6 7] [1 3 6 7] [1 6 7]]
Any idea what I'm doing wrong?
The error message is telling exactly what is the issue:
panic: runtime error: slice bounds out of range
Since you are calling the same function iteratively and re-slicing the slice you need to check each time if you reached the slice capacity range, in other terms if the slice pointer is pointing to a valid address (index), otherwise you get the out of range error message.
And since you are making a recursive iteration, by decreasing the path length each time, you have to check if the slice index is within a valid range.
//re-slice the slice - get rid of the current node
if len(path) > 0 {
path = path[:len(path)-1]
}
I solved it by using a pointer to my slice 'path' as an argument to the recursive function. It works now! Thanks anyway.
package main
import "fmt"
func allPossiblePaths(arrGraph [8][8]bool, src int, dest int) [][]int {
var visited []bool //a slice that marks if visited
var path []int //a slice to store a possible path
var paths [][]int //a slice to store all paths
visited = make([]bool, 8) //set all nodes to unvisited
dfs(arrGraph, src, dest, visited, &path, paths)
return paths
}
func dfs(myGraph [8][8]bool, src int, dest int, visited []bool, path *[]int, paths [][]int) {
//add current node to path
*path = append(*path, src)
//mark current node as visited
visited[src] = true
//if the current node is the destination
//print the path and return
if src == dest {
//make a copy of path slice
buffer := make([]int, len(*path))
copy(buffer, *path)
//append the copy of path slice into the slice of paths
paths = append(paths, buffer)
fmt.Println(*path) //Just for debugging purpose
return
}
for i := 1; i <= 7; i++ { //loop through all nodes
//if ith node is a neighbour of the current node and it is not visited
if myGraph[src][i] && visited[i] == false {
// call dfs on the current node
dfs(myGraph, i, dest, visited, path, paths)
//mark the current node as unvisited
//so that we can other paths to the final destination
visited[i] = false
//re-slice the slice - get rid of the current node
*path = (*path)[:len(*path)-1]
//fmt.Println(path)
}
}
}
func main() {
var myGraph [8][8]bool //the graph
//creating the graph
myGraph[1] = [...]bool{false, false, true, true, false, false, true, false}
myGraph[2] = [...]bool{false, true, false, true, false, true, false, false}
myGraph[3] = [...]bool{false, true, true, false, true, false, true, false}
myGraph[4] = [...]bool{false, false, false, true, false, false, true, false}
myGraph[5] = [...]bool{false, false, true, false, false, false, true, false}
myGraph[6] = [...]bool{false, true, false, true, true, false, false, true}
myGraph[7] = [...]bool{false, false, false, false, false, false, true, false}
fmt.Println(allPossiblePaths(myGraph, 1, 7))
}