76 lines
1.3 KiB
Go
76 lines
1.3 KiB
Go
|
package aoc_test
|
||
|
|
|
||
|
|
import (
|
||
|
|
"iter"
|
||
|
|
"testing"
|
||
|
|
|
||
|
|
"github.com/matryer/is"
|
||
|
|
aoc "go.sour.is/advent-of-code"
|
||
|
|
)
|
||
|
|
|
||
|
|
func TestGraph(t *testing.T) {
|
||
|
|
is := is.New(t)
|
||
|
|
|
||
|
|
var adjacencyList = map[int][]int{
|
||
|
|
2: {3, 5, 1},
|
||
|
|
1: {2, 4},
|
||
|
|
3: {6, 2},
|
||
|
|
4: {1, 5, 7},
|
||
|
|
5: {2, 6, 8, 4},
|
||
|
|
6: {3, 0, 9, 5},
|
||
|
|
7: {4, 8},
|
||
|
|
8: {5, 9, 7},
|
||
|
|
9: {6, 0, 8},
|
||
|
|
}
|
||
|
|
|
||
|
|
g := aoc.Graph(aoc.WithAdjacencyList[int](adjacencyList))
|
||
|
|
is.Equal(g.Neighbors(1), []int{2, 4})
|
||
|
|
is.Equal(map[int][]int(g.AdjacencyList()), adjacencyList)
|
||
|
|
}
|
||
|
|
|
||
|
|
func TestGraphDFS(t *testing.T) {
|
||
|
|
is := is.New(t)
|
||
|
|
|
||
|
|
var adjacencyList = map[int][]int{
|
||
|
|
2: {3, 5, 1},
|
||
|
|
1: {2, 4},
|
||
|
|
3: {6, 2},
|
||
|
|
4: {1, 5, 7},
|
||
|
|
5: {2, 6, 8, 4},
|
||
|
|
6: {3, 0, 9, 5},
|
||
|
|
7: {4, 8},
|
||
|
|
8: {5, 9, 7},
|
||
|
|
9: {6, 0, 8},
|
||
|
|
}
|
||
|
|
|
||
|
|
g := aoc.Graph(aoc.WithAdjacencyList[int](adjacencyList))
|
||
|
|
is.Equal(toList(g.DFS(6)), []int{6, 3, 2, 5, 8, 9, 0, 7, 4, 1})
|
||
|
|
}
|
||
|
|
|
||
|
|
func TestGraphBFS(t *testing.T) {
|
||
|
|
is := is.New(t)
|
||
|
|
|
||
|
|
var adjacencyList = map[int][]int{
|
||
|
|
2: {3, 5, 1},
|
||
|
|
1: {2, 4},
|
||
|
|
3: {6, 2},
|
||
|
|
4: {1, 5, 7},
|
||
|
|
5: {2, 6, 8, 4},
|
||
|
|
6: {3, 0, 9, 5},
|
||
|
|
7: {4, 8},
|
||
|
|
8: {5, 9, 7},
|
||
|
|
9: {6, 0, 8},
|
||
|
|
}
|
||
|
|
|
||
|
|
g := aoc.Graph(aoc.WithAdjacencyList[int](adjacencyList))
|
||
|
|
is.Equal(toList(g.BFS(6)), []int{6, 3, 0, 9, 5, 2, 8, 4, 1, 7})
|
||
|
|
}
|
||
|
|
|
||
|
|
func toList[T any](seq iter.Seq[T]) []T {
|
||
|
|
var list []T
|
||
|
|
for v := range seq {
|
||
|
|
list = append(list, v)
|
||
|
|
}
|
||
|
|
return list
|
||
|
|
}
|