graph/multi: test graph implementations with testgraph package
Fix bugs found by testgraph.
MODIFY
graph/multi/directed_test.go
graph/multi/directed_test.go
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
-package multi
+package multi_test
import (
+ "math"
"testing"
"gonum.org/v1/gonum/graph"
+ "gonum.org/v1/gonum/graph/internal/set"
+ "gonum.org/v1/gonum/graph/multi"
+ "gonum.org/v1/gonum/graph/testgraph"
)
+func directedBuilder(nodes []graph.Node, edges []graph.WeightedLine, _, _ float64) (g graph.Graph, n []graph.Node, e []graph.Edge, s, a float64, ok bool) {
+ seen := make(set.Nodes)
+ dg := multi.NewDirectedGraph()
+ for _, n := range nodes {
+ seen.Add(n)
+ dg.AddNode(n)
+ }
+ for _, edge := range edges {
+ f := dg.Node(edge.From().ID())
+ if f == nil {
+ f = edge.From()
+ }
+ t := dg.Node(edge.To().ID())
+ if t == nil {
+ t = edge.To()
+ }
+ cl := multi.Line{F: f, T: t, UID: edge.ID()}
+ seen.Add(cl.F)
+ seen.Add(cl.T)
+ e = append(e, cl)
+ dg.SetLine(cl)
+ }
+ if len(seen) != 0 {
+ n = make([]graph.Node, 0, len(seen))
+ }
+ for _, sn := range seen {
+ n = append(n, sn)
+ }
+ return dg, n, e, math.NaN(), math.NaN(), true
+}
+
+func TestDirected(t *testing.T) {
+ t.Run("EdgeExistence", func(t *testing.T) {
+ testgraph.EdgeExistence(t, directedBuilder)
+ })
+ t.Run("NodeExistence", func(t *testing.T) {
+ testgraph.NodeExistence(t, directedBuilder)
+ })
+ t.Run("ReturnAdjacentNodes", func(t *testing.T) {
+ testgraph.ReturnAdjacentNodes(t, directedBuilder)
+ })
+ t.Run("ReturnAllLines", func(t *testing.T) {
+ testgraph.ReturnAllLines(t, directedBuilder)
+ })
+ t.Run("ReturnAllNodes", func(t *testing.T) {
+ testgraph.ReturnAllNodes(t, directedBuilder)
+ })
+ t.Run("ReturnNodeSlice", func(t *testing.T) {
+ testgraph.ReturnNodeSlice(t, directedBuilder)
+ })
+}
+
// Tests Issue #27
func TestEdgeOvercounting(t *testing.T) {
g := generateDummyGraph()
@@ -19,7 +75,7 @@ func TestEdgeOvercounting(t *testing.T) {
}
}
-func generateDummyGraph() *DirectedGraph {
+func generateDummyGraph() *multi.DirectedGraph {
nodes := [4]struct{ srcID, targetID int }{
{2, 1},
{1, 0},
@@ -27,10 +83,10 @@ func generateDummyGraph() *DirectedGraph {
{0, 2},
}
- g := NewDirectedGraph()
+ g := multi.NewDirectedGraph()
for i, n := range nodes {
- g.SetLine(Line{F: Node(n.srcID), T: Node(n.targetID), UID: int64(i)})
+ g.SetLine(multi.Line{F: multi.Node(n.srcID), T: multi.Node(n.targetID), UID: int64(i)})
}
return g
@@ -43,7 +99,7 @@ func TestIssue123DirectedGraph(t *testing.T) {
t.Errorf("unexpected panic: %v", r)
}
}()
- g := NewDirectedGraph()
+ g := multi.NewDirectedGraph()
n0 := g.NewNode()
g.AddNode(n0)

MODIFY
graph/multi/multi.go
graph/multi/multi.go
@@ -75,10 +75,12 @@ func (e WeightedEdge) To() graph.Node { return e.T }
// expected to be positioned at the first line and is reset before
// Weight returns.
func (e WeightedEdge) Weight() float64 {
+ if e.WeightFunc != nil {
+ return e.WeightFunc(e.WeightedLines)
+ }
if e.WeightedLines == nil {
return 0
}
- if e.WeightFunc == nil {
var w float64
for e.Next() {
w += e.WeightedLine().Weight()
@@ -86,8 +88,6 @@ func (e WeightedEdge) Weight() float64 {
e.WeightedLines.Reset()
return w
}
- return e.WeightFunc(e.WeightedLines)
-}
// WeightedLine is a weighted multigraph edge.
type WeightedLine struct {

MODIFY
graph/multi/undirected_test.go
graph/multi/undirected_test.go
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
-package multi
+package multi_test
import (
+ "math"
"testing"
"gonum.org/v1/gonum/graph"
+ "gonum.org/v1/gonum/graph/internal/set"
+ "gonum.org/v1/gonum/graph/multi"
+ "gonum.org/v1/gonum/graph/testgraph"
)
+func undirectedBuilder(nodes []graph.Node, edges []graph.WeightedLine, _, _ float64) (g graph.Graph, n []graph.Node, e []graph.Edge, s, a float64, ok bool) {
+ seen := make(set.Nodes)
+ ug := multi.NewUndirectedGraph()
+ for _, n := range nodes {
+ seen.Add(n)
+ ug.AddNode(n)
+ }
+ for _, edge := range edges {
+ f := ug.Node(edge.From().ID())
+ if f == nil {
+ f = edge.From()
+ }
+ t := ug.Node(edge.To().ID())
+ if t == nil {
+ t = edge.To()
+ }
+ ce := multi.Line{F: f, T: t, UID: edge.ID()}
+ seen.Add(ce.F)
+ seen.Add(ce.T)
+ e = append(e, ce)
+ ug.SetLine(ce)
+ }
+ if len(seen) != 0 {
+ n = make([]graph.Node, 0, len(seen))
+ }
+ for _, sn := range seen {
+ n = append(n, sn)
+ }
+ return ug, n, e, math.NaN(), math.NaN(), true
+}
+
+func TestUndirected(t *testing.T) {
+ t.Run("EdgeExistence", func(t *testing.T) {
+ testgraph.EdgeExistence(t, undirectedBuilder)
+ })
+ t.Run("NodeExistence", func(t *testing.T) {
+ testgraph.NodeExistence(t, undirectedBuilder)
+ })
+ t.Run("ReturnAdjacentNodes", func(t *testing.T) {
+ testgraph.ReturnAdjacentNodes(t, undirectedBuilder)
+ })
+ t.Run("ReturnAllLines", func(t *testing.T) {
+ testgraph.ReturnAllLines(t, undirectedBuilder)
+ })
+ t.Run("ReturnAllNodes", func(t *testing.T) {
+ testgraph.ReturnAllNodes(t, undirectedBuilder)
+ })
+ t.Run("ReturnNodeSlice", func(t *testing.T) {
+ testgraph.ReturnNodeSlice(t, undirectedBuilder)
+ })
+}
+
func TestMaxID(t *testing.T) {
- g := NewUndirectedGraph()
+ g := multi.NewUndirectedGraph()
nodes := make(map[graph.Node]struct{})
- for i := Node(0); i < 3; i++ {
+ for i := multi.Node(0); i < 3; i++ {
g.AddNode(i)
nodes[i] = struct{}{}
}
g.RemoveNode(int64(0))
- delete(nodes, Node(0))
+ delete(nodes, multi.Node(0))
g.RemoveNode(int64(2))
- delete(nodes, Node(2))
+ delete(nodes, multi.Node(2))
n := g.NewNode()
g.AddNode(n)
if g.Node(n.ID()) == nil {
@@ -38,7 +94,7 @@ func TestIssue123UndirectedGraph(t *testing.T) {
t.Errorf("unexpected panic: %v", r)
}
}()
- g := NewUndirectedGraph()
+ g := multi.NewUndirectedGraph()
n0 := g.NewNode()
g.AddNode(n0)

MODIFY
graph/multi/weighted_directed_test.go
graph/multi/weighted_directed_test.go
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
-package multi
+package multi_test
import (
"testing"
"gonum.org/v1/gonum/graph"
+ "gonum.org/v1/gonum/graph/internal/set"
+ "gonum.org/v1/gonum/graph/multi"
+ "gonum.org/v1/gonum/graph/testgraph"
)
+func weightedDirectedBuilder(nodes []graph.Node, edges []graph.WeightedLine, self, absent float64) (g graph.Graph, n []graph.Node, e []graph.Edge, s, a float64, ok bool) {
+ seen := make(set.Nodes)
+ dg := multi.NewWeightedDirectedGraph()
+ dg.EdgeWeightFunc = func(l graph.WeightedLines) float64 {
+ // TODO(kortschak): Remove nil guard if nil iterators
+ // are forbidden, https://github.com/gonum/gonum/issues/614.
+ if l == nil || l.Len() == 0 {
+ return absent
+ }
+ var w float64
+ for l.Next() {
+ w += l.WeightedLine().Weight()
+ }
+ l.Reset()
+ return w
+ }
+ for _, n := range nodes {
+ seen.Add(n)
+ dg.AddNode(n)
+ }
+ for _, edge := range edges {
+ f := dg.Node(edge.From().ID())
+ if f == nil {
+ f = edge.From()
+ }
+ t := dg.Node(edge.To().ID())
+ if t == nil {
+ t = edge.To()
+ }
+ cl := multi.WeightedLine{F: f, T: t, UID: edge.ID(), W: edge.Weight()}
+ seen.Add(cl.F)
+ seen.Add(cl.T)
+ e = append(e, cl)
+ dg.SetWeightedLine(cl)
+ }
+ if len(seen) != 0 {
+ n = make([]graph.Node, 0, len(seen))
+ }
+ for _, sn := range seen {
+ n = append(n, sn)
+ }
+ return dg, n, e, self, absent, true
+}
+
+func TestWeightedDirected(t *testing.T) {
+ t.Run("EdgeExistence", func(t *testing.T) {
+ testgraph.EdgeExistence(t, weightedDirectedBuilder)
+ })
+ t.Run("NodeExistence", func(t *testing.T) {
+ testgraph.NodeExistence(t, weightedDirectedBuilder)
+ })
+ t.Run("ReturnAdjacentNodes", func(t *testing.T) {
+ testgraph.ReturnAdjacentNodes(t, weightedDirectedBuilder)
+ })
+ t.Run("ReturnAllLines", func(t *testing.T) {
+ testgraph.ReturnAllLines(t, weightedDirectedBuilder)
+ })
+ t.Run("ReturnAllNodes", func(t *testing.T) {
+ testgraph.ReturnAllNodes(t, weightedDirectedBuilder)
+ })
+ t.Run("ReturnAllWeightedLines", func(t *testing.T) {
+ testgraph.ReturnAllWeightedLines(t, weightedDirectedBuilder)
+ })
+ t.Run("ReturnNodeSlice", func(t *testing.T) {
+ testgraph.ReturnNodeSlice(t, weightedDirectedBuilder)
+ })
+ t.Run("Weight", func(t *testing.T) {
+ testgraph.Weight(t, weightedDirectedBuilder)
+ })
+}
+
// Tests Issue #27
func TestWeightedEdgeOvercounting(t *testing.T) {
g := generateDummyWeightedGraph()
@@ -19,7 +93,7 @@ func TestWeightedEdgeOvercounting(t *testing.T) {
}
}
-func generateDummyWeightedGraph() *WeightedDirectedGraph {
+func generateDummyWeightedGraph() *multi.WeightedDirectedGraph {
nodes := [4]struct{ srcID, targetID int }{
{2, 1},
{1, 0},
@@ -27,10 +101,10 @@ func generateDummyWeightedGraph() *WeightedDirectedGraph {
{0, 2},
}
- g := NewWeightedDirectedGraph()
+ g := multi.NewWeightedDirectedGraph()
for i, n := range nodes {
- g.SetWeightedLine(WeightedLine{F: Node(n.srcID), T: Node(n.targetID), W: 1, UID: int64(i)})
+ g.SetWeightedLine(multi.WeightedLine{F: multi.Node(n.srcID), T: multi.Node(n.targetID), W: 1, UID: int64(i)})
}
return g
@@ -43,7 +117,7 @@ func TestIssue123WeightedDirectedGraph(t *testing.T) {
t.Errorf("unexpected panic: %v", r)
}
}()
- g := NewWeightedDirectedGraph()
+ g := multi.NewWeightedDirectedGraph()
n0 := g.NewNode()
g.AddNode(n0)

MODIFY
graph/multi/weighted_undirected_test.go
graph/multi/weighted_undirected_test.go
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
-package multi
+package multi_test
import (
"testing"
"gonum.org/v1/gonum/graph"
+ "gonum.org/v1/gonum/graph/internal/set"
+ "gonum.org/v1/gonum/graph/multi"
+ "gonum.org/v1/gonum/graph/testgraph"
)
+func weightedUndirectedBuilder(nodes []graph.Node, edges []graph.WeightedLine, self, absent float64) (g graph.Graph, n []graph.Node, e []graph.Edge, s, a float64, ok bool) {
+ seen := make(set.Nodes)
+ ug := multi.NewWeightedUndirectedGraph()
+ ug.EdgeWeightFunc = func(l graph.WeightedLines) float64 {
+ // TODO(kortschak): Remove nil guard if nil iterators
+ // are forbidden, https://github.com/gonum/gonum/issues/614.
+ if l == nil || l.Len() == 0 {
+ return absent
+ }
+ var w float64
+ for l.Next() {
+ w += l.WeightedLine().Weight()
+ }
+ l.Reset()
+ return w
+ }
+ for _, n := range nodes {
+ seen.Add(n)
+ ug.AddNode(n)
+ }
+ for _, edge := range edges {
+ f := ug.Node(edge.From().ID())
+ if f == nil {
+ f = edge.From()
+ }
+ t := ug.Node(edge.To().ID())
+ if t == nil {
+ t = edge.To()
+ }
+ cl := multi.WeightedLine{F: f, T: t, UID: edge.ID(), W: edge.Weight()}
+ seen.Add(cl.F)
+ seen.Add(cl.T)
+ e = append(e, cl)
+ ug.SetWeightedLine(cl)
+ }
+ if len(seen) != 0 {
+ n = make([]graph.Node, 0, len(seen))
+ }
+ for _, sn := range seen {
+ n = append(n, sn)
+ }
+ return ug, n, e, self, absent, true
+}
+
+func TestWeightedUndirected(t *testing.T) {
+ t.Run("EdgeExistence", func(t *testing.T) {
+ testgraph.EdgeExistence(t, weightedUndirectedBuilder)
+ })
+ t.Run("NodeExistence", func(t *testing.T) {
+ testgraph.NodeExistence(t, weightedUndirectedBuilder)
+ })
+ t.Run("ReturnAdjacentNodes", func(t *testing.T) {
+ testgraph.ReturnAdjacentNodes(t, weightedUndirectedBuilder)
+ })
+ t.Run("ReturnAllLines", func(t *testing.T) {
+ testgraph.ReturnAllLines(t, weightedUndirectedBuilder)
+ })
+ t.Run("ReturnAllNodes", func(t *testing.T) {
+ testgraph.ReturnAllNodes(t, weightedUndirectedBuilder)
+ })
+ t.Run("ReturnAllWeightedLines", func(t *testing.T) {
+ testgraph.ReturnAllWeightedLines(t, weightedUndirectedBuilder)
+ })
+ t.Run("ReturnNodeSlice", func(t *testing.T) {
+ testgraph.ReturnNodeSlice(t, weightedUndirectedBuilder)
+ })
+ t.Run("Weight", func(t *testing.T) {
+ testgraph.Weight(t, weightedUndirectedBuilder)
+ })
+}
+
func TestWeightedMaxID(t *testing.T) {
- g := NewWeightedUndirectedGraph()
+ g := multi.NewWeightedUndirectedGraph()
nodes := make(map[graph.Node]struct{})
- for i := Node(0); i < 3; i++ {
+ for i := multi.Node(0); i < 3; i++ {
g.AddNode(i)
nodes[i] = struct{}{}
}
g.RemoveNode(int64(0))
- delete(nodes, Node(0))
+ delete(nodes, multi.Node(0))
g.RemoveNode(int64(2))
- delete(nodes, Node(2))
+ delete(nodes, multi.Node(2))
n := g.NewNode()
g.AddNode(n)
if g.Node(n.ID()) == nil {
@@ -38,7 +112,7 @@ func TestIssue123WeightedUndirectedGraph(t *testing.T) {
t.Errorf("unexpected panic: %v", r)
}
}()
- g := NewWeightedUndirectedGraph()
+ g := multi.NewWeightedUndirectedGraph()
n0 := g.NewNode()
g.AddNode(n0)

graph/multi: test graph implementations with testgraph package

Fix bugs found by testgraph.