blob: 5304e8343f92b8886c2941552ffb33c8058ae750 [file] [log] [blame]
// Copyright ©2015 The Gonum Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package graph_test
import (
"math"
"testing"
"gonum.org/v1/gonum/graph"
"gonum.org/v1/gonum/graph/simple"
"gonum.org/v1/gonum/mat"
)
type weightedDirectedBuilder interface {
graph.WeightedBuilder
graph.WeightedDirected
}
var weightedDirectedGraphs = []struct {
skipUnweighted bool
g func() weightedDirectedBuilder
edges []simple.WeightedEdge
absent float64
merge func(x, y float64, xe, ye graph.Edge) float64
want mat.Matrix
}{
{
g: func() weightedDirectedBuilder { return simple.NewWeightedDirectedGraph(0, 0) },
edges: []simple.WeightedEdge{
{F: simple.Node(0), T: simple.Node(1), W: 2},
{F: simple.Node(1), T: simple.Node(0), W: 1},
{F: simple.Node(1), T: simple.Node(2), W: 1},
},
want: mat.NewSymDense(3, []float64{
0, (1. + 2.) / 2., 0,
(1. + 2.) / 2., 0, 1. / 2.,
0, 1. / 2., 0,
}),
},
{
g: func() weightedDirectedBuilder { return simple.NewWeightedDirectedGraph(0, 0) },
edges: []simple.WeightedEdge{
{F: simple.Node(0), T: simple.Node(1), W: 2},
{F: simple.Node(1), T: simple.Node(0), W: 1},
{F: simple.Node(1), T: simple.Node(2), W: 1},
},
absent: 1,
merge: func(x, y float64, _, _ graph.Edge) float64 { return math.Sqrt(x * y) },
want: mat.NewSymDense(3, []float64{
0, math.Sqrt(1 * 2), 0,
math.Sqrt(1 * 2), 0, math.Sqrt(1 * 1),
0, math.Sqrt(1 * 1), 0,
}),
},
{
skipUnweighted: true, // The min merge function cannot be used in the unweighted case.
g: func() weightedDirectedBuilder { return simple.NewWeightedDirectedGraph(0, 0) },
edges: []simple.WeightedEdge{
{F: simple.Node(0), T: simple.Node(1), W: 2},
{F: simple.Node(1), T: simple.Node(0), W: 1},
{F: simple.Node(1), T: simple.Node(2), W: 1},
},
merge: func(x, y float64, _, _ graph.Edge) float64 { return math.Min(x, y) },
want: mat.NewSymDense(3, []float64{
0, math.Min(1, 2), 0,
math.Min(1, 2), 0, math.Min(1, 0),
0, math.Min(1, 0), 0,
}),
},
{
g: func() weightedDirectedBuilder { return simple.NewWeightedDirectedGraph(0, 0) },
edges: []simple.WeightedEdge{
{F: simple.Node(0), T: simple.Node(1), W: 2},
{F: simple.Node(1), T: simple.Node(0), W: 1},
{F: simple.Node(1), T: simple.Node(2), W: 1},
},
merge: func(x, y float64, xe, ye graph.Edge) float64 {
if xe == nil {
return y
}
if ye == nil {
return x
}
return math.Min(x, y)
},
want: mat.NewSymDense(3, []float64{
0, math.Min(1, 2), 0,
math.Min(1, 2), 0, 1,
0, 1, 0,
}),
},
{
g: func() weightedDirectedBuilder { return simple.NewWeightedDirectedGraph(0, 0) },
edges: []simple.WeightedEdge{
{F: simple.Node(0), T: simple.Node(1), W: 2},
{F: simple.Node(1), T: simple.Node(0), W: 1},
{F: simple.Node(1), T: simple.Node(2), W: 1},
},
merge: func(x, y float64, _, _ graph.Edge) float64 { return math.Max(x, y) },
want: mat.NewSymDense(3, []float64{
0, math.Max(1, 2), 0,
math.Max(1, 2), 0, math.Max(1, 0),
0, math.Max(1, 0), 0,
}),
},
}
func TestUndirect(t *testing.T) {
for i, test := range weightedDirectedGraphs {
if test.skipUnweighted {
continue
}
g := test.g()
for _, e := range test.edges {
g.SetWeightedEdge(e)
}
src := graph.Undirect{G: g}
dst := simple.NewUndirectedMatrixFrom(src.Nodes(), 0, 0, 0)
for _, u := range src.Nodes() {
for _, v := range src.From(u.ID()) {
dst.SetEdge(src.Edge(u.ID(), v.ID()))
}
}
want := unit{test.want}
if !mat.Equal(dst.Matrix(), want) {
t.Errorf("unexpected result for case %d:\ngot:\n%.4v\nwant:\n%.4v", i,
mat.Formatted(dst.Matrix()),
mat.Formatted(want),
)
}
}
}
func TestUndirectWeighted(t *testing.T) {
for i, test := range weightedDirectedGraphs {
g := test.g()
for _, e := range test.edges {
g.SetWeightedEdge(e)
}
src := graph.UndirectWeighted{G: g, Absent: test.absent, Merge: test.merge}
dst := simple.NewUndirectedMatrixFrom(src.Nodes(), 0, 0, 0)
for _, u := range src.Nodes() {
for _, v := range src.From(u.ID()) {
dst.SetWeightedEdge(src.WeightedEdge(u.ID(), v.ID()))
}
}
if !mat.Equal(dst.Matrix(), test.want) {
t.Errorf("unexpected result for case %d:\ngot:\n%.4v\nwant:\n%.4v", i,
mat.Formatted(dst.Matrix()),
mat.Formatted(test.want),
)
}
}
}
type unit struct {
mat.Matrix
}
func (m unit) At(i, j int) float64 {
v := m.Matrix.At(i, j)
if v == 0 {
return 0
}
return 1
}