blob: 85def08132449189bfe61371ec99cf0553970c3a [file] [log] [blame]
 // 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), }, }