graph_walking.go

// https://go.dev/play/p/eDtSd13eu5r
// graph walking from start to end 🦔🐾🐾🐾
package main

import "fmt"

type Graph map[int][]int

func sliceContains[T comparable](vs []T, v T) bool {
	for _, q := range vs {
		if v == q {
			return true
		}
	}
	return false
}

func pathToDFS(g Graph, to int, path []int) (paths [][]int) {
	if len(path) == 0 {
		return nil
	}

	if to == path[len(path)-1] {
		return [][]int{path}
	}

	for _, next := range g[path[len(path)-1]] {
		if sliceContains(path, next) {
			continue
		}
		paths = append(paths, pathToDFS(g, to, append(path, next))...)
	}

	return paths
}

func GetAllPathsFromTo(g Graph, from, to int) [][]int { return pathToDFS(g, to, []int{0}) }

func main() {
	tests := []struct {
		g    Graph
		from int
		to   int
	}{
		{
			g:    Graph{0: []int{1, 2}, 1: []int{3}, 2: []int{3}, 3: nil},
			from: 0,
			to:   3,
		},
		{
			g:    Graph{0: []int{4, 3, 1}, 1: []int{3, 2, 4}, 2: []int{3}, 3: []int{4}, 4: nil},
			from: 0,
			to:   4,
		},
	}
	for i, tc := range tests {
		fmt.Printf("%d: %#v\n", i, GetAllPathsFromTo(tc.g, tc.from, tc.to))
	}
}