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
|
package graph
import (
"math/rand"
"testing"
)
func TestStrongComponents(t *testing.T) {
g := New(0)
if mess, diff := diff(StrongComponents(g), [][]int{}); diff {
t.Errorf("StronglyConnected %s", mess)
}
g = New(10)
g.Add(0, 1)
g.Add(1, 2)
g.Add(2, 0)
g.Add(3, 1)
g.Add(3, 2)
g.Add(3, 5)
g.Add(4, 2)
g.Add(4, 6)
g.Add(5, 3)
g.Add(5, 4)
g.Add(6, 4)
g.Add(7, 5)
g.Add(7, 6)
g.Add(7, 7)
g.Add(8, 8)
exp := [][]int{{2, 1, 0}, {6, 4}, {5, 3}, {7}, {8}, {9}}
if mess, diff := diff(StrongComponents(g), exp); diff {
t.Errorf("StronglyConnected %s", mess)
}
}
func BenchmarkStrongComponents(b *testing.B) {
n := 1000
b.StopTimer()
g := New(n)
for i := 0; i < n; i++ {
g.Add(rand.Intn(n), rand.Intn(n))
}
b.StartTimer()
for i := 0; i < b.N; i++ {
_ = StrongComponents(g)
}
}
|
