graph/simple: test graph implementations with testgraph package
Fix bugs found by testgraph.
MODIFY
graph/iterator/nodes.go
graph/iterator/nodes.go
@@ -113,3 +113,13 @@ func (n *ImplicitNodes) Node() graph.Node {
func (n *ImplicitNodes) Reset() {
n.curr = n.beg - 1
}
+
+// NodeSlice returns all the remaining nodes in the iterator and advances
+// the iterator.
+func (n *ImplicitNodes) NodeSlice() []graph.Node {
+ nodes := make([]graph.Node, 0, n.Len())
+ for n.curr++; n.curr < n.end; n.curr++ {
+ nodes = append(nodes, n.newNode(n.curr))
+ }
+ return nodes
+}

MODIFY
graph/simple/dense_directed_matrix.go
graph/simple/dense_directed_matrix.go
@@ -248,7 +248,7 @@ func (g *DirectedMatrix) Weight(xid, yid int64) (w float64, ok bool) {
if xid == yid {
return g.self, true
}
- if g.has(xid) && g.has(yid) {
+ if g.HasEdgeFromTo(xid, yid) {
// xid and yid are not greater than maximum int by this point.
return g.mat.At(int(xid), int(yid)), true
}
@@ -265,6 +265,23 @@ func (g *DirectedMatrix) WeightedEdge(uid, vid int64) graph.WeightedEdge {
return nil
}
+// WeightedEdges returns all the edges in the graph.
+func (g *DirectedMatrix) WeightedEdges() graph.WeightedEdges {
+ var edges []graph.WeightedEdge
+ r, _ := g.mat.Dims()
+ for i := 0; i < r; i++ {
+ for j := 0; j < r; j++ {
+ if i == j {
+ continue
+ }
+ if w := g.mat.At(i, j); !isSame(w, g.absent) {
+ edges = append(edges, WeightedEdge{F: g.Node(int64(i)), T: g.Node(int64(j)), W: w})
+ }
+ }
+ }
+ return iterator.NewOrderedWeightedEdges(edges)
+}
+
func (g *DirectedMatrix) has(id int64) bool {
r, _ := g.mat.Dims()
return 0 <= id && id < int64(r)

MODIFY
graph/simple/dense_undirected_matrix.go
graph/simple/dense_undirected_matrix.go
@@ -216,7 +216,7 @@ func (g *UndirectedMatrix) Weight(xid, yid int64) (w float64, ok bool) {
if xid == yid {
return g.self, true
}
- if g.has(xid) && g.has(yid) {
+ if g.HasEdgeBetween(xid, yid) {
// xid and yid are not greater than maximum int by this point.
return g.mat.At(int(xid), int(yid)), true
}
@@ -238,6 +238,20 @@ func (g *UndirectedMatrix) WeightedEdgeBetween(uid, vid int64) graph.WeightedEdg
return nil
}
+// WeightedEdges returns all the edges in the graph.
+func (g *UndirectedMatrix) WeightedEdges() graph.WeightedEdges {
+ var edges []graph.WeightedEdge
+ r, _ := g.mat.Dims()
+ for i := 0; i < r; i++ {
+ for j := i + 1; j < r; j++ {
+ if w := g.mat.At(i, j); !isSame(w, g.absent) {
+ edges = append(edges, WeightedEdge{F: g.Node(int64(i)), T: g.Node(int64(j)), W: w})
+ }
+ }
+ }
+ return iterator.NewOrderedWeightedEdges(edges)
+}
+
func (g *UndirectedMatrix) has(id int64) bool {
r := g.mat.Symmetric()
return 0 <= id && id < int64(r)

MODIFY
graph/simple/densegraph_test.go
graph/simple/densegraph_test.go
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
-package simple
+package simple_test
import (
"math"
@@ -11,10 +11,302 @@ import (
"gonum.org/v1/gonum/graph"
"gonum.org/v1/gonum/graph/internal/ordered"
+ "gonum.org/v1/gonum/graph/internal/set"
+ "gonum.org/v1/gonum/graph/simple"
+ "gonum.org/v1/gonum/graph/testgraph"
)
+func isZeroContiguousSet(nodes []graph.Node) bool {
+ t := make([]graph.Node, len(nodes))
+ copy(t, nodes)
+ nodes = t
+ sort.Sort(ordered.ByID(nodes))
+ for i, n := range nodes {
+ if int64(i) != n.ID() {
+ return false
+ }
+ }
+ return true
+}
+
+func directedMatrixBuilder(nodes []graph.Node, edges []graph.WeightedLine, self, absent float64) (g graph.Graph, n []graph.Node, e []graph.Edge, s, a float64, ok bool) {
+ if len(nodes) == 0 {
+ return
+ }
+ if !isZeroContiguousSet(nodes) {
+ return
+ }
+ seen := make(set.Nodes)
+ dg := simple.NewDirectedMatrix(len(nodes), absent, self, absent)
+ for i := range nodes {
+ seen.Add(simple.Node(i))
+ }
+ for _, edge := range edges {
+ if edge.From().ID() == edge.To().ID() {
+ continue
+ }
+ if !seen.Has(edge.From()) || !seen.Has(edge.To()) {
+ continue
+ }
+ ce := simple.WeightedEdge{F: dg.Node(edge.From().ID()), T: dg.Node(edge.To().ID()), W: edge.Weight()}
+ e = append(e, ce)
+ dg.SetWeightedEdge(ce)
+ }
+ if len(e) == 0 && len(edges) != 0 {
+ return nil, nil, nil, math.NaN(), math.NaN(), false
+ }
+ n = make([]graph.Node, 0, len(seen))
+ for _, sn := range seen {
+ n = append(n, sn)
+ }
+ return dg, n, e, self, absent, true
+}
+
+func TestDirectedMatrix(t *testing.T) {
+ t.Run("AdjacencyMatrix", func(t *testing.T) {
+ testgraph.AdjacencyMatrix(t, directedMatrixBuilder)
+ })
+ t.Run("EdgeExistence", func(t *testing.T) {
+ testgraph.EdgeExistence(t, directedMatrixBuilder)
+ })
+ t.Run("NodeExistence", func(t *testing.T) {
+ testgraph.NodeExistence(t, directedMatrixBuilder)
+ })
+ t.Run("ReturnAdjacentNodes", func(t *testing.T) {
+ testgraph.ReturnAdjacentNodes(t, directedMatrixBuilder)
+ })
+ t.Run("ReturnAllEdges", func(t *testing.T) {
+ testgraph.ReturnAllEdges(t, directedMatrixBuilder)
+ })
+ t.Run("ReturnAllNodes", func(t *testing.T) {
+ testgraph.ReturnAllNodes(t, directedMatrixBuilder)
+ })
+ t.Run("ReturnAllWeightedEdges", func(t *testing.T) {
+ testgraph.ReturnAllWeightedEdges(t, directedMatrixBuilder)
+ })
+ t.Run("ReturnEdgeSlice", func(t *testing.T) {
+ testgraph.ReturnEdgeSlice(t, directedMatrixBuilder)
+ })
+ t.Run("ReturnWeightedEdgeSlice", func(t *testing.T) {
+ testgraph.ReturnWeightedEdgeSlice(t, directedMatrixBuilder)
+ })
+ t.Run("ReturnNodeSlice", func(t *testing.T) {
+ testgraph.ReturnNodeSlice(t, directedMatrixBuilder)
+ })
+ t.Run("Weight", func(t *testing.T) {
+ testgraph.Weight(t, directedMatrixBuilder)
+ })
+}
+
+func directedMatrixFromBuilder(nodes []graph.Node, edges []graph.WeightedLine, self, absent float64) (g graph.Graph, n []graph.Node, e []graph.Edge, s, a float64, ok bool) {
+ if len(nodes) == 0 {
+ return
+ }
+ if !isZeroContiguousSet(nodes) {
+ return
+ }
+ seen := make(set.Nodes)
+ dg := simple.NewDirectedMatrixFrom(nodes, absent, self, absent)
+ for _, n := range nodes {
+ seen.Add(n)
+ }
+ for _, edge := range edges {
+ if edge.From().ID() == edge.To().ID() {
+ continue
+ }
+ if !seen.Has(edge.From()) || !seen.Has(edge.To()) {
+ continue
+ }
+ ce := simple.WeightedEdge{F: dg.Node(edge.From().ID()), T: dg.Node(edge.To().ID()), W: edge.Weight()}
+ e = append(e, ce)
+ dg.SetWeightedEdge(ce)
+ }
+ if len(e) == 0 && len(edges) != 0 {
+ return nil, nil, nil, math.NaN(), math.NaN(), false
+ }
+ n = make([]graph.Node, 0, len(seen))
+ for _, sn := range seen {
+ n = append(n, sn)
+ }
+ return dg, n, e, self, absent, true
+}
+
+func TestDirectedMatrixFrom(t *testing.T) {
+ t.Run("AdjacencyMatrix", func(t *testing.T) {
+ testgraph.AdjacencyMatrix(t, directedMatrixFromBuilder)
+ })
+ t.Run("EdgeExistence", func(t *testing.T) {
+ testgraph.EdgeExistence(t, directedMatrixFromBuilder)
+ })
+ t.Run("NodeExistence", func(t *testing.T) {
+ testgraph.NodeExistence(t, directedMatrixFromBuilder)
+ })
+ t.Run("ReturnAdjacentNodes", func(t *testing.T) {
+ testgraph.ReturnAdjacentNodes(t, directedMatrixFromBuilder)
+ })
+ t.Run("ReturnAllEdges", func(t *testing.T) {
+ testgraph.ReturnAllEdges(t, directedMatrixFromBuilder)
+ })
+ t.Run("ReturnAllNodes", func(t *testing.T) {
+ testgraph.ReturnAllNodes(t, directedMatrixFromBuilder)
+ })
+ t.Run("ReturnAllWeightedEdges", func(t *testing.T) {
+ testgraph.ReturnAllWeightedEdges(t, directedMatrixFromBuilder)
+ })
+ t.Run("ReturnEdgeSlice", func(t *testing.T) {
+ testgraph.ReturnEdgeSlice(t, directedMatrixFromBuilder)
+ })
+ t.Run("ReturnWeightedEdgeSlice", func(t *testing.T) {
+ testgraph.ReturnWeightedEdgeSlice(t, directedMatrixFromBuilder)
+ })
+ t.Run("ReturnNodeSlice", func(t *testing.T) {
+ testgraph.ReturnNodeSlice(t, directedMatrixFromBuilder)
+ })
+ t.Run("Weight", func(t *testing.T) {
+ testgraph.Weight(t, directedMatrixFromBuilder)
+ })
+}
+
+func undirectedMatrixBuilder(nodes []graph.Node, edges []graph.WeightedLine, self, absent float64) (g graph.Graph, n []graph.Node, e []graph.Edge, s, a float64, ok bool) {
+ if len(nodes) == 0 {
+ return
+ }
+ if !isZeroContiguousSet(nodes) {
+ return
+ }
+ seen := make(set.Nodes)
+ dg := simple.NewUndirectedMatrix(len(nodes), absent, self, absent)
+ for i := range nodes {
+ seen.Add(simple.Node(i))
+ }
+ for _, edge := range edges {
+ if edge.From().ID() == edge.To().ID() {
+ continue
+ }
+ if !seen.Has(edge.From()) || !seen.Has(edge.To()) {
+ continue
+ }
+ ce := simple.WeightedEdge{F: dg.Node(edge.From().ID()), T: dg.Node(edge.To().ID()), W: edge.Weight()}
+ e = append(e, ce)
+ dg.SetWeightedEdge(ce)
+ }
+ if len(e) == 0 && len(edges) != 0 {
+ return nil, nil, nil, math.NaN(), math.NaN(), false
+ }
+ n = make([]graph.Node, 0, len(seen))
+ for _, sn := range seen {
+ n = append(n, sn)
+ }
+ return dg, n, e, self, absent, true
+}
+
+func TestUnirectedMatrix(t *testing.T) {
+ t.Run("AdjacencyMatrix", func(t *testing.T) {
+ testgraph.AdjacencyMatrix(t, undirectedMatrixBuilder)
+ })
+ t.Run("EdgeExistence", func(t *testing.T) {
+ testgraph.EdgeExistence(t, undirectedMatrixBuilder)
+ })
+ t.Run("NodeExistence", func(t *testing.T) {
+ testgraph.NodeExistence(t, undirectedMatrixBuilder)
+ })
+ t.Run("ReturnAdjacentNodes", func(t *testing.T) {
+ testgraph.ReturnAdjacentNodes(t, undirectedMatrixBuilder)
+ })
+ t.Run("ReturnAllEdges", func(t *testing.T) {
+ testgraph.ReturnAllEdges(t, undirectedMatrixBuilder)
+ })
+ t.Run("ReturnAllNodes", func(t *testing.T) {
+ testgraph.ReturnAllNodes(t, undirectedMatrixBuilder)
+ })
+ t.Run("ReturnAllWeightedEdges", func(t *testing.T) {
+ testgraph.ReturnAllWeightedEdges(t, undirectedMatrixBuilder)
+ })
+ t.Run("ReturnEdgeSlice", func(t *testing.T) {
+ testgraph.ReturnEdgeSlice(t, undirectedMatrixBuilder)
+ })
+ t.Run("ReturnWeightedEdgeSlice", func(t *testing.T) {
+ testgraph.ReturnWeightedEdgeSlice(t, undirectedMatrixBuilder)
+ })
+ t.Run("ReturnNodeSlice", func(t *testing.T) {
+ testgraph.ReturnNodeSlice(t, undirectedMatrixBuilder)
+ })
+ t.Run("Weight", func(t *testing.T) {
+ testgraph.Weight(t, undirectedMatrixBuilder)
+ })
+}
+
+func undirectedMatrixFromBuilder(nodes []graph.Node, edges []graph.WeightedLine, self, absent float64) (g graph.Graph, n []graph.Node, e []graph.Edge, s, a float64, ok bool) {
+ if len(nodes) == 0 {
+ return
+ }
+ if !isZeroContiguousSet(nodes) {
+ return
+ }
+ seen := make(set.Nodes)
+ dg := simple.NewUndirectedMatrixFrom(nodes, absent, self, absent)
+ for _, n := range nodes {
+ seen.Add(n)
+ }
+ for _, edge := range edges {
+ if edge.From().ID() == edge.To().ID() {
+ continue
+ }
+ if !seen.Has(edge.From()) || !seen.Has(edge.To()) {
+ continue
+ }
+ ce := simple.WeightedEdge{F: dg.Node(edge.From().ID()), T: dg.Node(edge.To().ID()), W: edge.Weight()}
+ e = append(e, ce)
+ dg.SetWeightedEdge(ce)
+ }
+ if len(e) == 0 && len(edges) != 0 {
+ return nil, nil, nil, math.NaN(), math.NaN(), false
+ }
+ n = make([]graph.Node, 0, len(seen))
+ for _, sn := range seen {
+ n = append(n, sn)
+ }
+ return dg, n, e, self, absent, true
+}
+
+func TestUndirectedMatrixFrom(t *testing.T) {
+ t.Run("AdjacencyMatrix", func(t *testing.T) {
+ testgraph.AdjacencyMatrix(t, undirectedMatrixFromBuilder)
+ })
+ t.Run("EdgeExistence", func(t *testing.T) {
+ testgraph.EdgeExistence(t, undirectedMatrixFromBuilder)
+ })
+ t.Run("NodeExistence", func(t *testing.T) {
+ testgraph.NodeExistence(t, undirectedMatrixFromBuilder)
+ })
+ t.Run("ReturnAdjacentNodes", func(t *testing.T) {
+ testgraph.ReturnAdjacentNodes(t, undirectedMatrixFromBuilder)
+ })
+ t.Run("ReturnAllEdges", func(t *testing.T) {
+ testgraph.ReturnAllEdges(t, undirectedMatrixFromBuilder)
+ })
+ t.Run("ReturnAllNodes", func(t *testing.T) {
+ testgraph.ReturnAllNodes(t, undirectedMatrixFromBuilder)
+ })
+ t.Run("ReturnAllWeightedEdges", func(t *testing.T) {
+ testgraph.ReturnAllWeightedEdges(t, undirectedMatrixFromBuilder)
+ })
+ t.Run("ReturnEdgeSlice", func(t *testing.T) {
+ testgraph.ReturnEdgeSlice(t, undirectedMatrixFromBuilder)
+ })
+ t.Run("ReturnWeightedEdgeSlice", func(t *testing.T) {
+ testgraph.ReturnWeightedEdgeSlice(t, undirectedMatrixFromBuilder)
+ })
+ t.Run("ReturnNodeSlice", func(t *testing.T) {
+ testgraph.ReturnNodeSlice(t, undirectedMatrixFromBuilder)
+ })
+ t.Run("Weight", func(t *testing.T) {
+ testgraph.Weight(t, undirectedMatrixFromBuilder)
+ })
+}
+
func TestBasicDenseImpassable(t *testing.T) {
- dg := NewUndirectedMatrix(5, math.Inf(1), 0, math.Inf(1))
+ dg := simple.NewUndirectedMatrix(5, math.Inf(1), 0, math.Inf(1))
if dg == nil {
t.Fatal("Directed graph could not be made")
}
@@ -37,7 +329,7 @@ func TestBasicDenseImpassable(t *testing.T) {
}
func TestBasicDensePassable(t *testing.T) {
- dg := NewUndirectedMatrix(5, 1, 0, math.Inf(1))
+ dg := simple.NewUndirectedMatrix(5, 1, 0, math.Inf(1))
if dg == nil {
t.Fatal("Directed graph could not be made")
}
@@ -60,8 +352,8 @@ func TestBasicDensePassable(t *testing.T) {
}
func TestDirectedDenseAddRemove(t *testing.T) {
- dg := NewDirectedMatrix(10, math.Inf(1), 0, math.Inf(1))
- dg.SetWeightedEdge(WeightedEdge{F: Node(0), T: Node(2), W: 1})
+ dg := simple.NewDirectedMatrix(10, math.Inf(1), 0, math.Inf(1))
+ dg.SetWeightedEdge(simple.WeightedEdge{F: simple.Node(0), T: simple.Node(2), W: 1})
if neighbors := graph.NodesOf(dg.From(int64(0))); len(neighbors) != 1 || neighbors[0].ID() != 2 ||
dg.Edge(int64(0), int64(2)) == nil {
@@ -78,7 +370,7 @@ func TestDirectedDenseAddRemove(t *testing.T) {
t.Errorf("Removing directed edge wrongly kept predecessor")
}
- dg.SetWeightedEdge(WeightedEdge{F: Node(0), T: Node(2), W: 2})
+ dg.SetWeightedEdge(simple.WeightedEdge{F: simple.Node(0), T: simple.Node(2), W: 2})
// I figure we've torture tested From/To at this point
// so we'll just use the bool functions now
if dg.Edge(int64(0), int64(2)) == nil {
@@ -92,8 +384,8 @@ func TestDirectedDenseAddRemove(t *testing.T) {
}
func TestUndirectedDenseAddRemove(t *testing.T) {
- dg := NewUndirectedMatrix(10, math.Inf(1), 0, math.Inf(1))
- dg.SetEdge(Edge{F: Node(0), T: Node(2)})
+ dg := simple.NewUndirectedMatrix(10, math.Inf(1), 0, math.Inf(1))
+ dg.SetEdge(simple.Edge{F: simple.Node(0), T: simple.Node(2)})
if neighbors := graph.NodesOf(dg.From(int64(0))); len(neighbors) != 1 || neighbors[0].ID() != 2 ||
dg.EdgeBetween(int64(0), int64(2)) == nil {
@@ -107,7 +399,7 @@ func TestUndirectedDenseAddRemove(t *testing.T) {
}
func TestDenseLists(t *testing.T) {
- dg := NewDirectedMatrix(15, 1, 0, math.Inf(1))
+ dg := simple.NewDirectedMatrix(15, 1, 0, math.Inf(1))
nodes := graph.NodesOf(dg.Nodes())
if len(nodes) != 15 {

MODIFY
graph/simple/directed_test.go
graph/simple/directed_test.go
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
-package simple
+package simple_test
import (
+ "math"
"testing"
"gonum.org/v1/gonum/graph"
+ "gonum.org/v1/gonum/graph/internal/set"
+ "gonum.org/v1/gonum/graph/simple"
+ "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 := simple.NewDirectedGraph()
+ for _, n := range nodes {
+ seen.Add(n)
+ dg.AddNode(n)
+ }
+ for _, edge := range edges {
+ if edge.From().ID() == edge.To().ID() {
+ continue
+ }
+ f := dg.Node(edge.From().ID())
+ if f == nil {
+ f = edge.From()
+ }
+ t := dg.Node(edge.To().ID())
+ if t == nil {
+ t = edge.To()
+ }
+ ce := simple.Edge{F: f, T: t}
+ seen.Add(ce.F)
+ seen.Add(ce.T)
+ e = append(e, ce)
+ dg.SetEdge(ce)
+ }
+ if len(e) == 0 && len(edges) != 0 {
+ return nil, nil, nil, math.NaN(), math.NaN(), false
+ }
+ 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("ReturnAllEdges", func(t *testing.T) {
+ testgraph.ReturnAllEdges(t, directedBuilder)
+ })
+ t.Run("ReturnAllNodes", func(t *testing.T) {
+ testgraph.ReturnAllNodes(t, directedBuilder)
+ })
+ t.Run("ReturnEdgeSlice", func(t *testing.T) {
+ testgraph.ReturnEdgeSlice(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 +84,7 @@ func TestEdgeOvercounting(t *testing.T) {
}
}
-func generateDummyGraph() *DirectedGraph {
+func generateDummyGraph() *simple.DirectedGraph {
nodes := [4]struct{ srcID, targetID int }{
{2, 1},
{1, 0},
@@ -27,10 +92,10 @@ func generateDummyGraph() *DirectedGraph {
{0, 2},
}
- g := NewDirectedGraph()
+ g := simple.NewDirectedGraph()
for _, n := range nodes {
- g.SetEdge(Edge{F: Node(n.srcID), T: Node(n.targetID)})
+ g.SetEdge(simple.Edge{F: simple.Node(n.srcID), T: simple.Node(n.targetID)})
}
return g
@@ -43,7 +108,7 @@ func TestIssue123DirectedGraph(t *testing.T) {
t.Errorf("unexpected panic: %v", r)
}
}()
- g := NewDirectedGraph()
+ g := simple.NewDirectedGraph()
n0 := g.NewNode()
g.AddNode(n0)

MODIFY
graph/simple/undirected_test.go
graph/simple/undirected_test.go
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
-package simple
+package simple_test
import (
+ "math"
"testing"
"gonum.org/v1/gonum/graph"
+ "gonum.org/v1/gonum/graph/internal/set"
+ "gonum.org/v1/gonum/graph/simple"
+ "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 := simple.NewUndirectedGraph()
+ for _, n := range nodes {
+ seen.Add(n)
+ ug.AddNode(n)
+ }
+ for _, edge := range edges {
+ if edge.From().ID() == edge.To().ID() {
+ continue
+ }
+ 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 := simple.Edge{F: f, T: t}
+ seen.Add(ce.F)
+ seen.Add(ce.T)
+ e = append(e, ce)
+ ug.SetEdge(ce)
+ }
+ if len(e) == 0 && len(edges) != 0 {
+ return nil, nil, nil, math.NaN(), math.NaN(), false
+ }
+ 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("ReturnAllEdges", func(t *testing.T) {
+ testgraph.ReturnAllEdges(t, undirectedBuilder)
+ })
+ t.Run("ReturnAllNodes", func(t *testing.T) {
+ testgraph.ReturnAllNodes(t, undirectedBuilder)
+ })
+ t.Run("ReturnEdgeSlice", func(t *testing.T) {
+ testgraph.ReturnEdgeSlice(t, undirectedBuilder)
+ })
+ t.Run("ReturnNodeSlice", func(t *testing.T) {
+ testgraph.ReturnNodeSlice(t, undirectedBuilder)
+ })
+}
+
func TestAssertMutableNotDirected(t *testing.T) {
- var g graph.UndirectedBuilder = NewUndirectedGraph()
+ var g graph.UndirectedBuilder = simple.NewUndirectedGraph()
if _, ok := g.(graph.Directed); ok {
t.Fatal("Graph is directed, but a MutableGraph cannot safely be directed!")
}
}
func TestMaxID(t *testing.T) {
- g := NewUndirectedGraph()
+ g := simple.NewUndirectedGraph()
nodes := make(map[graph.Node]struct{})
- for i := Node(0); i < 3; i++ {
+ for i := simple.Node(0); i < 3; i++ {
g.AddNode(i)
nodes[i] = struct{}{}
}
g.RemoveNode(int64(0))
- delete(nodes, Node(0))
+ delete(nodes, simple.Node(0))
g.RemoveNode(int64(2))
- delete(nodes, Node(2))
+ delete(nodes, simple.Node(2))
n := g.NewNode()
g.AddNode(n)
if g.Node(n.ID()) == nil {
@@ -45,7 +110,7 @@ func TestIssue123UndirectedGraph(t *testing.T) {
t.Errorf("unexpected panic: %v", r)
}
}()
- g := NewUndirectedGraph()
+ g := simple.NewUndirectedGraph()
n0 := g.NewNode()
g.AddNode(n0)

MODIFY
graph/simple/weighted_directed.go
graph/simple/weighted_directed.go
@@ -256,12 +256,12 @@ func (g *WeightedDirectedGraph) WeightedEdge(uid, vid int64) graph.WeightedEdge
}
// WeightedEdges returns all the weighted edges in the graph.
-func (g *WeightedDirectedGraph) WeightedEdges() []graph.WeightedEdge {
+func (g *WeightedDirectedGraph) WeightedEdges() graph.WeightedEdges {
var edges []graph.WeightedEdge
for _, u := range g.nodes {
for _, e := range g.from[u.ID()] {
edges = append(edges, e)
}
}
- return edges
+ return iterator.NewOrderedWeightedEdges(edges)
}

MODIFY
graph/simple/weighted_directed_test.go
graph/simple/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 simple
+package simple_test
import (
"math"
"testing"
"gonum.org/v1/gonum/graph"
+ "gonum.org/v1/gonum/graph/internal/set"
+ "gonum.org/v1/gonum/graph/simple"
+ "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 := simple.NewWeightedDirectedGraph(self, absent)
+ for _, n := range nodes {
+ seen.Add(n)
+ dg.AddNode(n)
+ }
+ for _, edge := range edges {
+ if edge.From().ID() == edge.To().ID() {
+ continue
+ }
+ f := dg.Node(edge.From().ID())
+ if f == nil {
+ f = edge.From()
+ }
+ t := dg.Node(edge.To().ID())
+ if t == nil {
+ t = edge.To()
+ }
+ ce := simple.WeightedEdge{F: f, T: t, W: edge.Weight()}
+ seen.Add(ce.F)
+ seen.Add(ce.T)
+ e = append(e, ce)
+ dg.SetWeightedEdge(ce)
+ }
+ if len(e) == 0 && len(edges) != 0 {
+ return nil, nil, nil, math.NaN(), math.NaN(), false
+ }
+ 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("ReturnAllEdges", func(t *testing.T) {
+ testgraph.ReturnAllEdges(t, weightedDirectedBuilder)
+ })
+ t.Run("ReturnAllNodes", func(t *testing.T) {
+ testgraph.ReturnAllNodes(t, weightedDirectedBuilder)
+ })
+ t.Run("ReturnAllWeightedEdges", func(t *testing.T) {
+ testgraph.ReturnAllWeightedEdges(t, weightedDirectedBuilder)
+ })
+ t.Run("ReturnEdgeSlice", func(t *testing.T) {
+ testgraph.ReturnEdgeSlice(t, weightedDirectedBuilder)
+ })
+ t.Run("ReturnWeightedEdgeSlice", func(t *testing.T) {
+ testgraph.ReturnWeightedEdgeSlice(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 := generateDummyGraph()
@@ -20,7 +93,7 @@ func TestWeightedEdgeOvercounting(t *testing.T) {
}
}
-func generateDummyWeightedGraph() *WeightedDirectedGraph {
+func generateDummyWeightedGraph() *simple.WeightedDirectedGraph {
nodes := [4]struct{ srcID, targetID int }{
{2, 1},
{1, 0},
@@ -28,10 +101,10 @@ func generateDummyWeightedGraph() *WeightedDirectedGraph {
{0, 2},
}
- g := NewWeightedDirectedGraph(0, math.Inf(1))
+ g := simple.NewWeightedDirectedGraph(0, math.Inf(1))
for _, n := range nodes {
- g.SetWeightedEdge(WeightedEdge{F: Node(n.srcID), T: Node(n.targetID), W: 1})
+ g.SetWeightedEdge(simple.WeightedEdge{F: simple.Node(n.srcID), T: simple.Node(n.targetID), W: 1})
}
return g
@@ -44,7 +117,7 @@ func TestIssue123WeightedDirectedGraph(t *testing.T) {
t.Errorf("unexpected panic: %v", r)
}
}()
- g := NewWeightedDirectedGraph(0, math.Inf(1))
+ g := simple.NewWeightedDirectedGraph(0, math.Inf(1))
n0 := g.NewNode()
g.AddNode(n0)

MODIFY
graph/simple/weighted_undirected_test.go
graph/simple/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 simple
+package simple_test
import (
"math"
"testing"
"gonum.org/v1/gonum/graph"
+ "gonum.org/v1/gonum/graph/internal/set"
+ "gonum.org/v1/gonum/graph/simple"
+ "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 := simple.NewWeightedUndirectedGraph(self, absent)
+ for _, n := range nodes {
+ seen.Add(n)
+ ug.AddNode(n)
+ }
+ for _, edge := range edges {
+ if edge.From().ID() == edge.To().ID() {
+ continue
+ }
+ 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 := simple.WeightedEdge{F: f, T: t, W: edge.Weight()}
+ seen.Add(ce.F)
+ seen.Add(ce.T)
+ e = append(e, ce)
+ ug.SetWeightedEdge(ce)
+ }
+ if len(e) == 0 && len(edges) != 0 {
+ return nil, nil, nil, math.NaN(), math.NaN(), false
+ }
+ 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("ReturnAllEdges", func(t *testing.T) {
+ testgraph.ReturnAllEdges(t, weightedUndirectedBuilder)
+ })
+ t.Run("ReturnAllNodes", func(t *testing.T) {
+ testgraph.ReturnAllNodes(t, weightedUndirectedBuilder)
+ })
+ t.Run("ReturnAllWeightedEdges", func(t *testing.T) {
+ testgraph.ReturnAllWeightedEdges(t, weightedUndirectedBuilder)
+ })
+ t.Run("ReturnEdgeSlice", func(t *testing.T) {
+ testgraph.ReturnEdgeSlice(t, weightedUndirectedBuilder)
+ })
+ t.Run("ReturnWeightedEdgeSlice", func(t *testing.T) {
+ testgraph.ReturnWeightedEdgeSlice(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 TestAssertWeightedMutableNotDirected(t *testing.T) {
- var g graph.UndirectedWeightedBuilder = NewWeightedUndirectedGraph(0, math.Inf(1))
+ var g graph.UndirectedWeightedBuilder = simple.NewWeightedUndirectedGraph(0, math.Inf(1))
if _, ok := g.(graph.Directed); ok {
t.Fatal("Graph is directed, but a MutableGraph cannot safely be directed!")
}
}
func TestWeightedMaxID(t *testing.T) {
- g := NewWeightedUndirectedGraph(0, math.Inf(1))
+ g := simple.NewWeightedUndirectedGraph(0, math.Inf(1))
nodes := make(map[graph.Node]struct{})
- for i := Node(0); i < 3; i++ {
+ for i := simple.Node(0); i < 3; i++ {
g.AddNode(i)
nodes[i] = struct{}{}
}
g.RemoveNode(int64(0))
- delete(nodes, Node(0))
+ delete(nodes, simple.Node(0))
g.RemoveNode(int64(2))
- delete(nodes, Node(2))
+ delete(nodes, simple.Node(2))
n := g.NewNode()
g.AddNode(n)
if g.Node(n.ID()) == nil {
@@ -46,7 +119,7 @@ func TestIssue123WeightedUndirectedGraph(t *testing.T) {
t.Errorf("unexpected panic: %v", r)
}
}()
- g := NewWeightedUndirectedGraph(0, math.Inf(1))
+ g := simple.NewWeightedUndirectedGraph(0, math.Inf(1))
n0 := g.NewNode()
g.AddNode(n0)

graph/simple: test graph implementations with testgraph package

Fix bugs found by testgraph.