community,topo: add benchmarks excercising set use
MODIFY
graph/community/k_communities_test.go
graph/community/k_communities_test.go
package community
import (
+ "fmt"
"reflect"
"sort"
"testing"
@@ -43,11 +44,13 @@ var batageljZaversnikGraph = []intset{
}
var kCliqueCommunitiesTests = []struct {
+ name string
g []intset
k int
want [][]graph.Node
}{
{
+ name: "simple",
g: []intset{
0: linksTo(1, 2, 4, 6),
1: linksTo(2, 4, 6),
@@ -65,6 +68,7 @@ var kCliqueCommunitiesTests = []struct {
},
},
{
+ name: "Batagelj-Zaversnik Graph",
g: batageljZaversnikGraph,
k: 3,
want: [][]graph.Node{
@@ -84,6 +88,7 @@ var kCliqueCommunitiesTests = []struct {
},
},
{
+ name: "Batagelj-Zaversnik Graph",
g: batageljZaversnikGraph,
k: 4,
want: [][]graph.Node{
@@ -126,7 +131,32 @@ func TestKCliqueCommunities(t *testing.T) {
sort.Sort(ordered.BySliceIDs(got))
if !reflect.DeepEqual(got, test.want) {
- t.Errorf("unexpected k-connected components:\ngot: %v\nwant:%v", got, test.want)
+ t.Errorf("unexpected k-connected components for %q k=%d:\ngot: %v\nwant:%v", test.name, test.k, got, test.want)
}
}
}
+
+func BenchmarkKCliqueCommunities(b *testing.B) {
+ for _, test := range kCliqueCommunitiesTests {
+ g := simple.NewUndirectedGraph()
+ for u, e := range test.g {
+ // Add nodes that are not defined by an edge.
+ if g.Node(int64(u)) == nil {
+ g.AddNode(simple.Node(u))
+ }
+ for v := range e {
+ g.SetEdge(simple.Edge{F: simple.Node(u), T: simple.Node(v)})
+ }
+ }
+
+ b.Run(fmt.Sprintf("%s-k=%d", test.name, test.k), func(b *testing.B) {
+ var got [][]graph.Node
+ for i := 0; i < b.N; i++ {
+ got = KCliqueCommunities(test.k, g)
+ }
+ if len(got) != len(test.want) {
+ b.Errorf("unexpected k-connected components for %q k=%d:\ngot: %v\nwant:%v", test.name, test.k, got, test.want)
+ }
+ })
+ }
+}

MODIFY
graph/topo/bron_kerbosch_test.go
graph/topo/bron_kerbosch_test.go
@@ -9,6 +9,7 @@ import (
"sort"
"testing"
+ "gonum.org/v1/gonum/graph"
"gonum.org/v1/gonum/graph/internal/ordered"
"gonum.org/v1/gonum/graph/simple"
)
@@ -126,12 +127,14 @@ func TestKCore(t *testing.T) {
}
var bronKerboschTests = []struct {
+ name string
g []intset
want [][]int64
}{
{
// This is the example given in the Bron-Kerbosch article on wikipedia (renumbered).
// http://en.wikipedia.org/w/index.php?title=Bron%E2%80%93Kerbosch_algorithm&oldid=656805858
+ name: "wikipedia example",
g: []intset{
0: linksTo(1, 4),
1: linksTo(2, 4),
@@ -149,6 +152,7 @@ var bronKerboschTests = []struct {
},
},
{
+ name: "Batagelj-Zaversnik Graph",
g: batageljZaversnikGraph,
want: [][]int64{
{0},
@@ -171,7 +175,7 @@ var bronKerboschTests = []struct {
}
func TestBronKerbosch(t *testing.T) {
- for i, test := range bronKerboschTests {
+ for _, test := range bronKerboschTests {
g := simple.NewUndirectedGraph()
for u, e := range test.g {
// Add nodes that are not defined by an edge.
@@ -194,7 +198,32 @@ func TestBronKerbosch(t *testing.T) {
}
sort.Sort(ordered.BySliceValues(got))
if !reflect.DeepEqual(got, test.want) {
- t.Errorf("unexpected cliques for test %d:\ngot: %v\nwant:%v", i, got, test.want)
+ t.Errorf("unexpected cliques for test %q:\ngot: %v\nwant:%v", test.name, got, test.want)
}
}
}
+
+func BenchmarkBronKerbosch(b *testing.B) {
+ for _, test := range bronKerboschTests {
+ g := simple.NewUndirectedGraph()
+ for u, e := range test.g {
+ // Add nodes that are not defined by an edge.
+ if g.Node(int64(u)) == nil {
+ g.AddNode(simple.Node(u))
+ }
+ for v := range e {
+ g.SetEdge(simple.Edge{F: simple.Node(u), T: simple.Node(v)})
+ }
+ }
+
+ b.Run(test.name, func(b *testing.B) {
+ var got [][]graph.Node
+ for i := 0; i < b.N; i++ {
+ got = BronKerbosch(g)
+ }
+ if len(got) != len(test.want) {
+ b.Errorf("unexpected cliques for test %q:\ngot: %v\nwant:%v", test.name, got, test.want)
+ }
+ })
+ }
+}

MODIFY
graph/topo/clique_graph_test.go
graph/topo/clique_graph_test.go
@@ -14,10 +14,12 @@ import (
)
var cliqueGraphTests = []struct {
+ name string
g []intset
want string
}{
{
+ name: "simple",
g: []intset{
0: linksTo(1, 2, 4, 6),
1: linksTo(2, 4, 6),
@@ -45,6 +47,7 @@ var cliqueGraphTests = []struct {
}`,
},
{
+ name: "Batagelj-Zaversnik Graph",
g: batageljZaversnikGraph,
want: `strict graph {
// Node definitions.
@@ -106,7 +109,7 @@ func TestCliqueGraph(t *testing.T) {
got := string(b)
if got != test.want {
- t.Errorf("unexpected clique graph result: got:\n%s\nwant:\n%s", got, test.want)
+ t.Errorf("unexpected clique graph result for %q: got:\n%s\nwant:\n%s", test.name, got, test.want)
}
}
}
@@ -118,3 +121,28 @@ func (n Clique) Attributes() []encoding.Attribute {
func (e CliqueGraphEdge) Attributes() []encoding.Attribute {
return []encoding.Attribute{{Key: "nodes", Value: fmt.Sprintf(`"%v"`, e.Nodes())}}
}
+
+func BenchmarkCliqueGraph(b *testing.B) {
+ for _, test := range cliqueGraphTests {
+ g := simple.NewUndirectedGraph()
+ for u, e := range test.g {
+ // Add nodes that are not defined by an edge.
+ if g.Node(int64(u)) == nil {
+ g.AddNode(simple.Node(u))
+ }
+ for v := range e {
+ g.SetEdge(simple.Edge{F: simple.Node(u), T: simple.Node(v)})
+ }
+ }
+
+ b.Run(test.name, func(b *testing.B) {
+ var dst *simple.UndirectedGraph
+ for i := 0; i < b.N; i++ {
+ b.StopTimer()
+ dst = simple.NewUndirectedGraph()
+ b.StartTimer()
+ CliqueGraph(dst, g)
+ }
+ })
+ }
+}

community,topo: add benchmarks excercising set use