grafo/fuzz_test.go at main · rschio/grafo · 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
102
103
104
105
package grafo

import (
	"bytes"
	"iter"
	"math/rand/v2"
	"strconv"
	"testing"

	"github.com/google/go-cmp/cmp"
	"github.com/rschio/grafo/internal/encoding/dot"
	"github.com/rschio/graph"
)

func itoa64(i int64) string { return strconv.FormatInt(i, 10) }

func FuzzStrongComponents(f *testing.F) {
	f.Add(uint(10), uint(20), uint64(0), uint64(1))
	f.Fuzz(func(t *testing.T, VV, EE uint, seed1, seed2 uint64) {
		V := int(VV%100_000 + 1)
		E := int(EE % uint(V*V))
		rnd := rand.New(rand.NewPCG(seed1, seed2))
		g := generateRandomWithRand(V, E, func() int64 { return 1 }, rnd)

		comps1 := StrongComponents(g)
		comps2 := graph.StrongComponents(g)
		sortComponents(comps1)
		sortComponents(comps2)

		if !cmp.Equal(comps1, comps2) {
			var buf bytes.Buffer
			enc := dot.NewEncoder(&buf, itoa64)
			if err := enc.Encode(g); err != nil {
				t.Errorf("failed to DOT: %v", err)
			}
			t.Errorf("V=%d E=%d\nGraph=[%s]\ncomps1=%v\ncomps2=%v", V, E, buf.String(), comps1, comps2)
		}
	})
}

func FuzzShortestPaths(f *testing.F) {
	f.Add(uint(10), uint(20), InfFor[int64](), uint64(0), uint64(1))
	f.Fuzz(func(t *testing.T, VV, EE uint, maxValue int64, seed1, seed2 uint64) {
		V := int(VV%500 + 1) // Use a small V to test.
		E := int(EE % uint(V*V))
		if maxValue <= 0 {
			maxValue = -maxValue
			if maxValue == 0 {
				maxValue = 1
			}
		}
		rnd := rand.New(rand.NewPCG(seed1, seed2))
		weightFn := func() int64 {
			return rnd.Int64N(maxValue)
		}
		g := generateRandomWithRand(V, E, weightFn, rnd)
		v := rand.IntN(V)

		_, dist1 := ShortestPaths(g, v)
		_, dist2, _ := BellmanFord(g, v)

		if diff := cmp.Diff(dist1, dist2); diff != "" {
			var buf bytes.Buffer
			enc := dot.NewEncoder(&buf, itoa64)
			if err := enc.Encode(g); err != nil {
				t.Errorf("failed to DOT: %v", err)
			}
			t.Errorf("V=%d E=%d maxValue=%d v=%d\nGraph=[%s]\ndiff=%v", V, E, maxValue, v, buf.String(), diff)
		}
	})
}

func FuzzDFS(f *testing.F) {
	f.Fuzz(func(t *testing.T, VV, EE uint, seed1, seed2 uint64) {
		V := int(VV%1000) + 1
		E := int(EE % uint((V * V)))
		rnd := rand.New(rand.NewPCG(seed1, seed2))
		g := generateRandomWithRand(V, E, func() int64 { return 1 }, rnd)

		next1, stop1 := iter.Pull(DFS(g, 0))
		defer stop1()

		next2, stop2 := iter.Pull(dfsRec(g, 0))
		defer stop2()

		path := make([]Edge[int64], 0)
		for {
			e1, ok1 := next1()
			e2, ok2 := next2()

			path = append(path, e1)
			if diff := cmp.Diff(e1, e2); diff != "" || ok1 != ok2 {
				var buf bytes.Buffer
				enc := dot.NewEncoder(&buf, itoa64)
				if err := enc.Encode(g); err != nil {
					t.Errorf("failed to DOT: %v", err)
				}
				t.Fatalf("ok1 %v ok2 %v diff: %s\npath[%v]\n%s", ok1, ok2, diff, path, buf.String())
			}
			if ok1 == false {
				break
			}
		}
	})
}