grokking-algorithms/dijkstra_algorithm_test.go at master · avisnakovs/grokking-algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
package grokking_algorithms

import (
	"testing"

	"github.com/stretchr/testify/assert"
)

func TestDijkstra_Find(t *testing.T) {
	t.Run("empty graph", func(t *testing.T) {
		wg := WeightedGraph{Nodes: map[string]*WeightedNode{}}

		got, found := Dijkstra(wg).Find("start", "end")

		assert.False(t, found)
		assert.Equal(t, Weight(0), got)
	})

	t.Run("not connected", func(t *testing.T) {
		start := &WeightedNode{Value: "start"}
		a := &WeightedNode{Value: "a"}
		end := &WeightedNode{Value: "end"}

		start.Edges = map[*WeightedNode]Weight{a: 6}
		a.Edges = map[*WeightedNode]Weight{}

		wg := WeightedGraph{Nodes: map[string]*WeightedNode{"start": start, "a": a, "end": end}}

		got, found := Dijkstra(wg).Find("start", "end")
		assert.False(t, found)
		assert.Equal(t, Weight(0), got)
	})

	t.Run("self connected to self", func(t *testing.T) {
		start := &WeightedNode{Value: "start"}

		wg := WeightedGraph{Nodes: map[string]*WeightedNode{"start": start}}

		got, found := Dijkstra(wg).Find("start", "start")

		assert.True(t, found)
		assert.Equal(t, Weight(0), got)
	})

	t.Run("4-nodes graph", func(t *testing.T) {
		start := &WeightedNode{Value: "start"}
		a := &WeightedNode{Value: "a"}
		b := &WeightedNode{Value: "b"}
		end := &WeightedNode{Value: "end"}

		start.Edges = map[*WeightedNode]Weight{a: 6, b: 2}
		a.Edges = map[*WeightedNode]Weight{end: 1}
		b.Edges = map[*WeightedNode]Weight{a: 3, end: 5}

		wg := WeightedGraph{Nodes: map[string]*WeightedNode{"start": start, "a": a, "b": b, "end": end}}

		got, found := Dijkstra(wg).Find("start", "end")
		assert.True(t, found)
		assert.Equal(t, Weight(6), got)
	})

	t.Run("6-node graph", func(t *testing.T) {
		book := &WeightedNode{Value: "book"}
		record := &WeightedNode{Value: "record"}
		poster := &WeightedNode{Value: "poster"}
		guitar := &WeightedNode{Value: "guitar"}
		drum := &WeightedNode{Value: "drum"}
		piano := &WeightedNode{Value: "piano"}

		book.Edges = map[*WeightedNode]Weight{record: 5, poster: 0}
		record.Edges = map[*WeightedNode]Weight{drum: 20, guitar: 15}
		poster.Edges = map[*WeightedNode]Weight{guitar: 30, drum: 35}
		guitar.Edges = map[*WeightedNode]Weight{piano: 20}
		drum.Edges = map[*WeightedNode]Weight{piano: 10}

		wg := WeightedGraph{Nodes: map[string]*WeightedNode{
			"book": book, "record": record, "poster": poster, "drum": drum, "guitar": guitar, "piano": piano}}

		got, found := Dijkstra(wg).Find("book", "piano")
		assert.True(t, found)
		assert.Equal(t, Weight(35), got)
	})

	t.Run("circular connection", func(t *testing.T) {
		start := &WeightedNode{Value: "start"}
		a := &WeightedNode{Value: "a"}
		b := &WeightedNode{Value: "b"}
		end := &WeightedNode{Value: "end"}

		start.Edges = map[*WeightedNode]Weight{a: 6, b: 2}
		a.Edges = map[*WeightedNode]Weight{b: 1, end: 1}
		b.Edges = map[*WeightedNode]Weight{a: 3, end: 5}
		end.Edges = map[*WeightedNode]Weight{a: 3}

		wg := WeightedGraph{Nodes: map[string]*WeightedNode{"start": start, "a": a, "b": b, "end": end}}

		got, found := Dijkstra(wg).Find("start", "end")
		assert.True(t, found)
		assert.Equal(t, Weight(6), got)
	})
}