graph/testgraph/testcases.go

// Copyright ©2018 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 testgraph

import (
	"math"

	"gonum.org/v1/gonum/graph"
)

// node is a graph.Node implementation that is not exported
// so that other packages will not be aware of its implementation.
type node int64

func (n node) ID() int64 { return int64(n) }

// line is an extended graph.Edge implementation that is not exported
// so that other packages will not be aware of its implementation. It
// covers all the edge types exported by graph.
type line struct {
	F, T graph.Node
	UID  int64
	W    float64
}

func (e line) From() graph.Node { return e.F }
func (e line) To() graph.Node   { return e.T }
func (e line) ID() int64        { return e.UID }
func (e line) Weight() float64  { return e.W }

var testCases = []struct {
	// name is the name of the test.
	name string

	// nodes is the set of nodes that should be used
	// to construct the graph.
	nodes []graph.Node

	// edges is the set of edges that should be used
	// to construct the graph.
	edges []graph.WeightedLine

	// nonexist is a set of nodes that should not be
	// found within the graph.
	nonexist []graph.Node

	// self is the weight value associated with
	// a self edge for simple graphs that do not
	// store individual self edges.
	self float64

	// absent is the weight value associated
	// with absent edges.
	absent float64
}{
	{
		name:     "empty",
		nonexist: []graph.Node{node(-1), node(0), node(1)},
		self:     0,
		absent:   math.Inf(1),
	},
	{
		name:     "one - negative",
		nodes:    []graph.Node{node(-1)},
		nonexist: []graph.Node{node(0), node(1)},
		self:     0,
		absent:   math.Inf(1),
	},
	{
		name:     "one - zero",
		nodes:    []graph.Node{node(0)},
		nonexist: []graph.Node{node(-1), node(1)},
		self:     0,
		absent:   math.Inf(1),
	},
	{
		name:     "one - positive",
		nodes:    []graph.Node{node(1)},
		nonexist: []graph.Node{node(-1), node(0)},
		self:     0,
		absent:   math.Inf(1),
	},

	{
		name:     "one - self loop",
		nodes:    []graph.Node{node(0)},
		edges:    []graph.WeightedLine{line{F: node(0), T: node(0), UID: 0, W: 0.5}},
		nonexist: []graph.Node{node(-1), node(1)},
		self:     0,
		absent:   math.Inf(1),
	},

	{
		name:     "two - positive",
		nodes:    []graph.Node{node(1), node(2)},
		edges:    []graph.WeightedLine{line{F: node(1), T: node(2), UID: 0, W: 0.5}},
		nonexist: []graph.Node{node(-1), node(0)},
		self:     0,
		absent:   math.Inf(1),
	},
	{
		name:     "two - negative",
		nodes:    []graph.Node{node(-1), node(-2)},
		edges:    []graph.WeightedLine{line{F: node(-1), T: node(-2), UID: 0, W: 0.5}},
		nonexist: []graph.Node{node(0), node(-3)},
		self:     0,
		absent:   math.Inf(1),
	},
	{
		name:     "two - zero spanning",
		nodes:    []graph.Node{node(-1), node(1)},
		edges:    []graph.WeightedLine{line{F: node(-1), T: node(1), UID: 0, W: 0.5}},
		nonexist: []graph.Node{node(0), node(2)},
		self:     0,
		absent:   math.Inf(1),
	},
	{
		name:     "two - zero contiguous",
		nodes:    []graph.Node{node(0), node(1)},
		edges:    []graph.WeightedLine{line{F: node(0), T: node(1), UID: 0, W: 0.5}},
		nonexist: []graph.Node{node(-1), node(2)},
		self:     0,
		absent:   math.Inf(1),
	},

	{
		name:     "three - positive",
		nodes:    []graph.Node{node(1), node(2), node(3)},
		edges:    []graph.WeightedLine{line{F: node(1), T: node(2), UID: 0, W: 0.5}},
		nonexist: []graph.Node{node(-1), node(0)},
		self:     0,
		absent:   math.Inf(1),
	},
	{
		name:     "three - negative",
		nodes:    []graph.Node{node(-1), node(-2), node(-3)},
		edges:    []graph.WeightedLine{line{F: node(-1), T: node(-2), UID: 0, W: 0.5}},
		nonexist: []graph.Node{node(0), node(1)},
		self:     0,
		absent:   math.Inf(1),
	},
	{
		name:     "three - zero spanning",
		nodes:    []graph.Node{node(-1), node(0), node(1)},
		edges:    []graph.WeightedLine{line{F: node(-1), T: node(1), UID: 0, W: 0.5}},
		nonexist: []graph.Node{node(-2), node(2)},
		self:     0,
		absent:   math.Inf(1),
	},
	{
		name:     "three - zero contiguous",
		nodes:    []graph.Node{node(0), node(1), node(2)},
		edges:    []graph.WeightedLine{line{F: node(0), T: node(1), UID: 0, W: 0.5}},
		nonexist: []graph.Node{node(-1), node(3)},
		self:     0,
		absent:   math.Inf(1),
	},

	{
		name: "4-clique - single(non-prepared)",
		edges: func() []graph.WeightedLine {
			const n = 4
			var uid int64
			var edges []graph.WeightedLine
			for i := 0; i < n; i++ {
				for j := i + 1; j < 4; j++ {
					edges = append(edges, line{F: node(i), T: node(j), UID: uid, W: 0.5})
					uid++
				}
			}
			return edges
		}(),
		nonexist: []graph.Node{node(-1), node(4)},
		self:     0,
		absent:   math.Inf(1),
	},
	{
		name: "4-clique+ - single(non-prepared)",
		edges: func() []graph.WeightedLine {
			const n = 4
			var uid int64
			var edges []graph.WeightedLine
			for i := 0; i < n; i++ {
				for j := i; j < 4; j++ {
					edges = append(edges, line{F: node(i), T: node(j), UID: uid, W: 0.5})
					uid++
				}
			}
			return edges
		}(),
		nonexist: []graph.Node{node(-1), node(4)},
		self:     0,
		absent:   math.Inf(1),
	},
	{
		name: "4-clique - single(prepared)",
		nodes: func() []graph.Node {
			const n = 4
			nodes := make([]graph.Node, n)
			for i := range nodes {
				nodes[i] = node(i)
			}
			return nodes
		}(),
		edges: func() []graph.WeightedLine {
			const n = 4
			var uid int64
			var edges []graph.WeightedLine
			for i := 0; i < n; i++ {
				for j := i + 1; j < n; j++ {
					edges = append(edges, line{F: node(i), T: node(j), UID: uid, W: 0.5})
					uid++
				}
			}
			return edges
		}(),
		nonexist: []graph.Node{node(-1), node(4)},
		self:     0,
		absent:   math.Inf(1),
	},
	{
		name: "4-clique+ - single(prepared)",
		nodes: func() []graph.Node {
			const n = 4
			nodes := make([]graph.Node, n)
			for i := range nodes {
				nodes[i] = node(i)
			}
			return nodes
		}(),
		edges: func() []graph.WeightedLine {
			const n = 4
			var uid int64
			var edges []graph.WeightedLine
			for i := 0; i < n; i++ {
				for j := i; j < n; j++ {
					edges = append(edges, line{F: node(i), T: node(j), UID: uid, W: 0.5})
					uid++
				}
			}
			return edges
		}(),
		nonexist: []graph.Node{node(-1), node(4)},
		self:     0,
		absent:   math.Inf(1),
	},

	{
		name: "4-clique - double(non-prepared)",
		edges: func() []graph.WeightedLine {
			const n = 4
			var uid int64
			var edges []graph.WeightedLine
			for i := 0; i < n; i++ {
				for j := i + 1; j < n; j++ {
					edges = append(edges, line{F: node(i), T: node(j), UID: uid, W: 0.5})
					uid++
					edges = append(edges, line{F: node(j), T: node(i), UID: uid, W: 0.5})
					uid++
				}
			}
			return edges
		}(),
		nonexist: []graph.Node{node(-1), node(4)},
		self:     0,
		absent:   math.Inf(1),
	},
	{
		name: "4-clique+ - double(non-prepared)",
		edges: func() []graph.WeightedLine {
			const n = 4
			var uid int64
			var edges []graph.WeightedLine
			for i := 0; i < n; i++ {
				for j := i; j < n; j++ {
					edges = append(edges, line{F: node(i), T: node(j), UID: uid, W: 0.5})
					uid++
					edges = append(edges, line{F: node(j), T: node(i), UID: uid, W: 0.5})
					uid++
				}
			}
			return edges
		}(),
		nonexist: []graph.Node{node(-1), node(4)},
		self:     0,
		absent:   math.Inf(1),
	},
	{
		name: "4-clique - double(prepared)",
		nodes: func() []graph.Node {
			const n = 4
			nodes := make([]graph.Node, n)
			for i := range nodes {
				nodes[i] = node(i)
			}
			return nodes
		}(),
		edges: func() []graph.WeightedLine {
			const n = 4
			var uid int64
			var edges []graph.WeightedLine
			for i := 0; i < n; i++ {
				for j := i + 1; j < n; j++ {
					edges = append(edges, line{F: node(i), T: node(j), UID: uid, W: 0.5})
					uid++
					edges = append(edges, line{F: node(j), T: node(i), UID: uid, W: 0.5})
					uid++
				}
			}
			return edges
		}(),
		nonexist: []graph.Node{node(-1), node(4)},
		self:     0,
		absent:   math.Inf(1),
	},
	{
		name: "4-clique+ - double(prepared)",
		nodes: func() []graph.Node {
			const n = 4
			nodes := make([]graph.Node, n)
			for i := range nodes {
				nodes[i] = node(i)
			}
			return nodes
		}(),
		edges: func() []graph.WeightedLine {
			const n = 4
			var uid int64
			var edges []graph.WeightedLine
			for i := 0; i < n; i++ {
				for j := i; j < n; j++ {
					edges = append(edges, line{F: node(i), T: node(j), UID: uid, W: 0.5})
					uid++
					edges = append(edges, line{F: node(j), T: node(i), UID: uid, W: 0.5})
					uid++
				}
			}
			return edges
		}(),
		nonexist: []graph.Node{node(-1), node(4)},
		self:     0,
		absent:   math.Inf(1),
	},
}