1// Copyright ©2015 The Gonum Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package graph_test
6
7import (
8	"math"
9	"testing"
10
11	"gonum.org/v1/gonum/graph"
12	"gonum.org/v1/gonum/graph/iterator"
13	"gonum.org/v1/gonum/graph/simple"
14	"gonum.org/v1/gonum/mat"
15)
16
17type weightedDirectedBuilder interface {
18	graph.WeightedBuilder
19	graph.WeightedDirected
20}
21
22var weightedDirectedGraphs = []struct {
23	skipUnweighted bool
24
25	g      func() weightedDirectedBuilder
26	edges  []simple.WeightedEdge
27	absent float64
28	merge  func(x, y float64, xe, ye graph.Edge) float64
29
30	want mat.Matrix
31}{
32	{
33		g: func() weightedDirectedBuilder { return simple.NewWeightedDirectedGraph(0, 0) },
34		edges: []simple.WeightedEdge{
35			{F: simple.Node(0), T: simple.Node(1), W: 2},
36			{F: simple.Node(1), T: simple.Node(0), W: 1},
37			{F: simple.Node(1), T: simple.Node(2), W: 1},
38		},
39		want: mat.NewSymDense(3, []float64{
40			0, (1. + 2.) / 2., 0,
41			(1. + 2.) / 2., 0, 1. / 2.,
42			0, 1. / 2., 0,
43		}),
44	},
45	{
46		g: func() weightedDirectedBuilder { return simple.NewWeightedDirectedGraph(0, 0) },
47		edges: []simple.WeightedEdge{
48			{F: simple.Node(0), T: simple.Node(1), W: 2},
49			{F: simple.Node(1), T: simple.Node(0), W: 1},
50			{F: simple.Node(1), T: simple.Node(2), W: 1},
51		},
52		absent: 1,
53		merge:  func(x, y float64, _, _ graph.Edge) float64 { return math.Sqrt(x * y) },
54		want: mat.NewSymDense(3, []float64{
55			0, math.Sqrt(1 * 2), 0,
56			math.Sqrt(1 * 2), 0, math.Sqrt(1 * 1),
57			0, math.Sqrt(1 * 1), 0,
58		}),
59	},
60	{
61		skipUnweighted: true, // The min merge function cannot be used in the unweighted case.
62
63		g: func() weightedDirectedBuilder { return simple.NewWeightedDirectedGraph(0, 0) },
64		edges: []simple.WeightedEdge{
65			{F: simple.Node(0), T: simple.Node(1), W: 2},
66			{F: simple.Node(1), T: simple.Node(0), W: 1},
67			{F: simple.Node(1), T: simple.Node(2), W: 1},
68		},
69		merge: func(x, y float64, _, _ graph.Edge) float64 { return math.Min(x, y) },
70		want: mat.NewSymDense(3, []float64{
71			0, math.Min(1, 2), 0,
72			math.Min(1, 2), 0, math.Min(1, 0),
73			0, math.Min(1, 0), 0,
74		}),
75	},
76	{
77		g: func() weightedDirectedBuilder { return simple.NewWeightedDirectedGraph(0, 0) },
78		edges: []simple.WeightedEdge{
79			{F: simple.Node(0), T: simple.Node(1), W: 2},
80			{F: simple.Node(1), T: simple.Node(0), W: 1},
81			{F: simple.Node(1), T: simple.Node(2), W: 1},
82		},
83		merge: func(x, y float64, xe, ye graph.Edge) float64 {
84			if xe == nil {
85				return y
86			}
87			if ye == nil {
88				return x
89			}
90			return math.Min(x, y)
91		},
92		want: mat.NewSymDense(3, []float64{
93			0, math.Min(1, 2), 0,
94			math.Min(1, 2), 0, 1,
95			0, 1, 0,
96		}),
97	},
98	{
99		g: func() weightedDirectedBuilder { return simple.NewWeightedDirectedGraph(0, 0) },
100		edges: []simple.WeightedEdge{
101			{F: simple.Node(0), T: simple.Node(1), W: 2},
102			{F: simple.Node(1), T: simple.Node(0), W: 1},
103			{F: simple.Node(1), T: simple.Node(2), W: 1},
104		},
105		merge: func(x, y float64, _, _ graph.Edge) float64 { return math.Max(x, y) },
106		want: mat.NewSymDense(3, []float64{
107			0, math.Max(1, 2), 0,
108			math.Max(1, 2), 0, math.Max(1, 0),
109			0, math.Max(1, 0), 0,
110		}),
111	},
112}
113
114func TestUndirect(t *testing.T) {
115	for i, test := range weightedDirectedGraphs {
116		if test.skipUnweighted {
117			continue
118		}
119		g := test.g()
120		for _, e := range test.edges {
121			g.SetWeightedEdge(e)
122		}
123
124		src := graph.Undirect{G: g}
125		nodes := graph.NodesOf(src.Nodes())
126		dst := simple.NewUndirectedMatrixFrom(nodes, 0, 0, 0)
127		for _, u := range nodes {
128			for _, v := range graph.NodesOf(src.From(u.ID())) {
129				dst.SetEdge(src.Edge(u.ID(), v.ID()))
130			}
131		}
132
133		want := unit{test.want}
134		if !mat.Equal(dst.Matrix(), want) {
135			t.Errorf("unexpected result for case %d:\ngot:\n%.4v\nwant:\n%.4v", i,
136				mat.Formatted(dst.Matrix()),
137				mat.Formatted(want),
138			)
139		}
140	}
141}
142
143func TestUndirectWeighted(t *testing.T) {
144	for i, test := range weightedDirectedGraphs {
145		g := test.g()
146		for _, e := range test.edges {
147			g.SetWeightedEdge(e)
148		}
149
150		src := graph.UndirectWeighted{G: g, Absent: test.absent, Merge: test.merge}
151		nodes := graph.NodesOf(src.Nodes())
152		dst := simple.NewUndirectedMatrixFrom(nodes, 0, 0, 0)
153		for _, u := range nodes {
154			for _, v := range graph.NodesOf(src.From(u.ID())) {
155				dst.SetWeightedEdge(src.WeightedEdge(u.ID(), v.ID()))
156			}
157		}
158
159		if !mat.Equal(dst.Matrix(), test.want) {
160			t.Errorf("unexpected result for case %d:\ngot:\n%.4v\nwant:\n%.4v", i,
161				mat.Formatted(dst.Matrix()),
162				mat.Formatted(test.want),
163			)
164		}
165	}
166}
167
168type unit struct {
169	mat.Matrix
170}
171
172func (m unit) At(i, j int) float64 {
173	v := m.Matrix.At(i, j)
174	if v == 0 {
175		return 0
176	}
177	return 1
178}
179
180var nodeIteratorPairTests = []struct {
181	a, b graph.Nodes
182	len  int
183}{
184	{a: graph.Empty, b: graph.Empty, len: 0},
185	{a: iterator.NewOrderedNodes(nil), b: iterator.NewOrderedNodes(nil), len: 0},
186	{a: iterator.NewOrderedNodes([]graph.Node{simple.Node(0)}), b: graph.Empty, len: 1},
187	{a: graph.Empty, b: iterator.NewOrderedNodes([]graph.Node{simple.Node(0)}), len: 1},
188	{a: iterator.NewOrderedNodes([]graph.Node{simple.Node(0)}), b: iterator.NewOrderedNodes([]graph.Node{simple.Node(0)}), len: 1},
189	{a: iterator.NewOrderedNodes([]graph.Node{simple.Node(0)}), b: iterator.NewOrderedNodes([]graph.Node{simple.Node(1)}), len: 2},
190	{a: iterator.NewOrderedNodes([]graph.Node{simple.Node(0), simple.Node(1)}), b: iterator.NewOrderedNodes([]graph.Node{simple.Node(1)}), len: 2},
191	{a: iterator.NewOrderedNodes([]graph.Node{simple.Node(1)}), b: iterator.NewOrderedNodes([]graph.Node{simple.Node(0), simple.Node(1)}), len: 2},
192}
193
194func TestNodeIteratorPair(t *testing.T) {
195	for _, test := range nodeIteratorPairTests {
196		it := graph.NewNodeIteratorPair(test.a, test.b)
197		for i := 0; i < 2; i++ {
198			n := it.Len()
199			if n != test.len {
200				t.Errorf("unexpected length of iterator construction/reset: got:%d want:%d", n, test.len)
201			}
202			for it.Next() {
203				n--
204			}
205			if n != 0 {
206				t.Errorf("unexpected remaining nodes after iterator completion: got:%d want:0", n)
207			}
208			it.Reset()
209		}
210	}
211}
212