Codebase list golang-github-yourbasic-graph / HEAD top_test.go
HEAD

Tree @HEAD (Download .tar.gz)

top_test.go @HEAD — raw · history · blame 

  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
106
107
108
109
110
111
112
113
114
115
package graph

import (
	"math/rand"
	"testing"
)

func TestTopSort(t *testing.T) {
	g := New(0)
	order, ok := TopSort(g)
	if mess, diff := diff(order, []int{}); diff {
		t.Errorf("TopSort %s", mess)
	}
	if mess, diff := diff(ok, true); diff {
		t.Errorf("TopSort %s", mess)
	}

	g = New(4)
	g.Add(3, 2)
	g.Add(2, 1)
	g.Add(1, 0)
	expOrder := []int{3, 2, 1, 0}
	order, ok = TopSort(g)
	if mess, diff := diff(order, expOrder); diff {
		t.Errorf("TopSort %s", mess)
	}
	if mess, diff := diff(ok, true); diff {
		t.Errorf("TopSort %s", mess)
	}

	g = New(5)
	g.Add(0, 1)
	g.Add(1, 2)
	g.Add(1, 3)
	g.Add(2, 4)
	g.Add(3, 4)
	order, ok = TopSort(g)
	expOrder1 := []int{0, 1, 2, 3, 4}
	expOrder2 := []int{0, 1, 3, 2, 4}
	mess, diff1 := diff(order, expOrder1)
	_, diff2 := diff(order, expOrder2)
	if diff1 && diff2 {
		t.Errorf("TopSort %s", mess)
	}
	if mess, diff := diff(ok, true); diff {
		t.Errorf("TopSort %s", mess)
	}
}

func TestAcyclic(t *testing.T) {
	g := New(0)
	if mess, diff := diff(Acyclic(g), true); diff {
		t.Errorf("Acyclic %s", mess)
	}

	g = New(1)
	if mess, diff := diff(Acyclic(g), true); diff {
		t.Errorf("Acyclic %s", mess)
	}
	g.Add(0, 0)
	if mess, diff := diff(Acyclic(g), false); diff {
		t.Errorf("Acyclic %s", mess)
	}

	g = New(4)
	g.Add(0, 1)
	g.Add(2, 1)
	if mess, diff := diff(Acyclic(g), true); diff {
		t.Errorf("Acyclic %s", mess)
	}
	g.Add(0, 2)
	if mess, diff := diff(Acyclic(g), true); diff {
		t.Errorf("Acyclic %s", mess)
	}
	g.Add(3, 0)
	if mess, diff := diff(Acyclic(g), true); diff {
		t.Errorf("Acyclic %s", mess)
	}
	g.Add(1, 3)
	if mess, diff := diff(Acyclic(g), false); diff {
		t.Errorf("Acyclic %s", mess)
	}
}

func BenchmarkAcyclic(b *testing.B) {
	n := 1000
	b.StopTimer()
	g := New(n)
	for i := 0; i < 2*n; i++ {
		v, w := rand.Intn(n), rand.Intn(n)
		if v < w {
			g.AddBoth(v, w)
		}
	}
	b.StartTimer()
	for i := 0; i < b.N; i++ {
		_ = Acyclic(g)
	}
}

func BenchmarkTopSort(b *testing.B) {
	n := 1000
	b.StopTimer()
	g := New(n)
	for i := 0; i < 2*n; i++ {
		v, w := rand.Intn(n), rand.Intn(n)
		if v < w {
			g.AddBoth(v, w)
		}
	}
	b.StartTimer()
	for i := 0; i < b.N; i++ {
		_, _ = TopSort(g)
	}
}