testgraphs

package
v0.9.2 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: May 11, 2021 License: BSD-3-Clause Imports: 6 Imported by: 0

Documentation

Overview

Package testsgraphs provides a number of graphs used for testing routines in the path and path/dynamic packages.

Index

Constants

View Source 
const (
	Closed  = '*' // Closed is the closed grid node representation.
	Open    = '.' // Open is the open grid node repesentation.
	Unknown = '?' // Unknown is the unknown grid node repesentation.
)

Variables

View Source 
var ShortestPathTests = []struct {
	Name                   string
	Graph                  func() graph.WeightedEdgeAdder
	Edges                  []simple.WeightedEdge
	HasNegativeWeight      bool
	HasNegativeCycle       bool
	HasNegativeCycleInPath bool

	Query         simple.Edge
	Weight        float64
	WantPaths     [][]int64
	HasUniquePath bool

	NoPathFor simple.Edge
}{

	{
		Name:  "empty directed",
		Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) },

		Query:  simple.Edge{F: simple.Node(0), T: simple.Node(1)},
		Weight: math.Inf(1),

		NoPathFor: simple.Edge{F: simple.Node(0), T: simple.Node(1)},
	},
	{
		Name:  "empty undirected",
		Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedUndirectedGraph(0, math.Inf(1)) },

		Query:  simple.Edge{F: simple.Node(0), T: simple.Node(1)},
		Weight: math.Inf(1),

		NoPathFor: simple.Edge{F: simple.Node(0), T: simple.Node(1)},
	},
	{
		Name:  "one edge directed",
		Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) },
		Edges: []simple.WeightedEdge{
			{F: simple.Node(0), T: simple.Node(1), W: 1},
		},

		Query:  simple.Edge{F: simple.Node(0), T: simple.Node(1)},
		Weight: 1,
		WantPaths: [][]int64{
			{0, 1},
		},
		HasUniquePath: true,

		NoPathFor: simple.Edge{F: simple.Node(2), T: simple.Node(3)},
	},
	{
		Name:  "one edge self directed",
		Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) },
		Edges: []simple.WeightedEdge{
			{F: simple.Node(0), T: simple.Node(1), W: 1},
		},

		Query:  simple.Edge{F: simple.Node(0), T: simple.Node(0)},
		Weight: 0,
		WantPaths: [][]int64{
			{0},
		},
		HasUniquePath: true,

		NoPathFor: simple.Edge{F: simple.Node(2), T: simple.Node(3)},
	},
	{
		Name:  "one edge undirected",
		Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedUndirectedGraph(0, math.Inf(1)) },
		Edges: []simple.WeightedEdge{
			{F: simple.Node(0), T: simple.Node(1), W: 1},
		},

		Query:  simple.Edge{F: simple.Node(0), T: simple.Node(1)},
		Weight: 1,
		WantPaths: [][]int64{
			{0, 1},
		},
		HasUniquePath: true,

		NoPathFor: simple.Edge{F: simple.Node(2), T: simple.Node(3)},
	},
	{
		Name:  "two paths directed",
		Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) },
		Edges: []simple.WeightedEdge{
			{F: simple.Node(0), T: simple.Node(2), W: 2},
			{F: simple.Node(0), T: simple.Node(1), W: 1},
			{F: simple.Node(1), T: simple.Node(2), W: 1},
		},

		Query:  simple.Edge{F: simple.Node(0), T: simple.Node(2)},
		Weight: 2,
		WantPaths: [][]int64{
			{0, 1, 2},
			{0, 2},
		},
		HasUniquePath: false,

		NoPathFor: simple.Edge{F: simple.Node(2), T: simple.Node(1)},
	},
	{
		Name:  "two paths undirected",
		Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedUndirectedGraph(0, math.Inf(1)) },
		Edges: []simple.WeightedEdge{
			{F: simple.Node(0), T: simple.Node(2), W: 2},
			{F: simple.Node(0), T: simple.Node(1), W: 1},
			{F: simple.Node(1), T: simple.Node(2), W: 1},
		},

		Query:  simple.Edge{F: simple.Node(0), T: simple.Node(2)},
		Weight: 2,
		WantPaths: [][]int64{
			{0, 1, 2},
			{0, 2},
		},
		HasUniquePath: false,

		NoPathFor: simple.Edge{F: simple.Node(2), T: simple.Node(4)},
	},
	{
		Name:  "confounding paths directed",
		Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) },
		Edges: []simple.WeightedEdge{

			{F: simple.Node(0), T: simple.Node(1), W: 1},
			{F: simple.Node(1), T: simple.Node(2), W: 1},
			{F: simple.Node(2), T: simple.Node(3), W: 1},
			{F: simple.Node(3), T: simple.Node(5), W: 1},

			{F: simple.Node(0), T: simple.Node(5), W: 4},

			{F: simple.Node(0), T: simple.Node(2), W: 2},

			{F: simple.Node(0), T: simple.Node(3), W: 4},

			{F: simple.Node(0), T: simple.Node(4), W: 0.25},
		},

		Query:  simple.Edge{F: simple.Node(0), T: simple.Node(5)},
		Weight: 4,
		WantPaths: [][]int64{
			{0, 1, 2, 3, 5},
			{0, 2, 3, 5},
			{0, 5},
		},
		HasUniquePath: false,

		NoPathFor: simple.Edge{F: simple.Node(4), T: simple.Node(5)},
	},
	{
		Name:  "confounding paths undirected",
		Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedUndirectedGraph(0, math.Inf(1)) },
		Edges: []simple.WeightedEdge{

			{F: simple.Node(0), T: simple.Node(1), W: 1},
			{F: simple.Node(1), T: simple.Node(2), W: 1},
			{F: simple.Node(2), T: simple.Node(3), W: 1},
			{F: simple.Node(3), T: simple.Node(5), W: 1},

			{F: simple.Node(0), T: simple.Node(5), W: 4},

			{F: simple.Node(0), T: simple.Node(2), W: 2},

			{F: simple.Node(0), T: simple.Node(3), W: 4},

			{F: simple.Node(0), T: simple.Node(4), W: 0.25},
		},

		Query:  simple.Edge{F: simple.Node(0), T: simple.Node(5)},
		Weight: 4,
		WantPaths: [][]int64{
			{0, 1, 2, 3, 5},
			{0, 2, 3, 5},
			{0, 5},
		},
		HasUniquePath: false,

		NoPathFor: simple.Edge{F: simple.Node(5), T: simple.Node(6)},
	},
	{
		Name:  "confounding paths directed 2-step",
		Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) },
		Edges: []simple.WeightedEdge{

			{F: simple.Node(0), T: simple.Node(1), W: 1},
			{F: simple.Node(1), T: simple.Node(2), W: 1},
			{F: simple.Node(2), T: simple.Node(3), W: 1},
			{F: simple.Node(3), T: simple.Node(5), W: 1},

			{F: simple.Node(0), T: simple.Node(6), W: 2},
			{F: simple.Node(6), T: simple.Node(5), W: 2},

			{F: simple.Node(0), T: simple.Node(2), W: 2},

			{F: simple.Node(0), T: simple.Node(3), W: 4},

			{F: simple.Node(0), T: simple.Node(4), W: 0.25},
		},

		Query:  simple.Edge{F: simple.Node(0), T: simple.Node(5)},
		Weight: 4,
		WantPaths: [][]int64{
			{0, 1, 2, 3, 5},
			{0, 2, 3, 5},
			{0, 6, 5},
		},
		HasUniquePath: false,

		NoPathFor: simple.Edge{F: simple.Node(4), T: simple.Node(5)},
	},
	{
		Name:  "confounding paths undirected 2-step",
		Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedUndirectedGraph(0, math.Inf(1)) },
		Edges: []simple.WeightedEdge{

			{F: simple.Node(0), T: simple.Node(1), W: 1},
			{F: simple.Node(1), T: simple.Node(2), W: 1},
			{F: simple.Node(2), T: simple.Node(3), W: 1},
			{F: simple.Node(3), T: simple.Node(5), W: 1},

			{F: simple.Node(0), T: simple.Node(6), W: 2},
			{F: simple.Node(6), T: simple.Node(5), W: 2},

			{F: simple.Node(0), T: simple.Node(2), W: 2},

			{F: simple.Node(0), T: simple.Node(3), W: 4},

			{F: simple.Node(0), T: simple.Node(4), W: 0.25},
		},

		Query:  simple.Edge{F: simple.Node(0), T: simple.Node(5)},
		Weight: 4,
		WantPaths: [][]int64{
			{0, 1, 2, 3, 5},
			{0, 2, 3, 5},
			{0, 6, 5},
		},
		HasUniquePath: false,

		NoPathFor: simple.Edge{F: simple.Node(5), T: simple.Node(7)},
	},
	{
		Name:  "zero-weight cycle directed",
		Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) },
		Edges: []simple.WeightedEdge{

			{F: simple.Node(0), T: simple.Node(1), W: 1},
			{F: simple.Node(1), T: simple.Node(2), W: 1},
			{F: simple.Node(2), T: simple.Node(3), W: 1},
			{F: simple.Node(3), T: simple.Node(4), W: 1},

			{F: simple.Node(1), T: simple.Node(5), W: 0},
			{F: simple.Node(5), T: simple.Node(1), W: 0},
		},

		Query:  simple.Edge{F: simple.Node(0), T: simple.Node(4)},
		Weight: 4,
		WantPaths: [][]int64{
			{0, 1, 2, 3, 4},
		},
		HasUniquePath: false,

		NoPathFor: simple.Edge{F: simple.Node(4), T: simple.Node(5)},
	},
	{
		Name:  "zero-weight cycle^2 directed",
		Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) },
		Edges: []simple.WeightedEdge{

			{F: simple.Node(0), T: simple.Node(1), W: 1},
			{F: simple.Node(1), T: simple.Node(2), W: 1},
			{F: simple.Node(2), T: simple.Node(3), W: 1},
			{F: simple.Node(3), T: simple.Node(4), W: 1},

			{F: simple.Node(1), T: simple.Node(5), W: 0},
			{F: simple.Node(5), T: simple.Node(1), W: 0},

			{F: simple.Node(5), T: simple.Node(6), W: 0},
			{F: simple.Node(6), T: simple.Node(5), W: 0},
		},

		Query:  simple.Edge{F: simple.Node(0), T: simple.Node(4)},
		Weight: 4,
		WantPaths: [][]int64{
			{0, 1, 2, 3, 4},
		},
		HasUniquePath: false,

		NoPathFor: simple.Edge{F: simple.Node(4), T: simple.Node(5)},
	},
	{
		Name:  "zero-weight cycle^2 confounding directed",
		Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) },
		Edges: []simple.WeightedEdge{

			{F: simple.Node(0), T: simple.Node(1), W: 1},
			{F: simple.Node(1), T: simple.Node(2), W: 1},
			{F: simple.Node(2), T: simple.Node(3), W: 1},
			{F: simple.Node(3), T: simple.Node(4), W: 1},

			{F: simple.Node(1), T: simple.Node(5), W: 0},
			{F: simple.Node(5), T: simple.Node(1), W: 0},

			{F: simple.Node(5), T: simple.Node(6), W: 0},
			{F: simple.Node(6), T: simple.Node(5), W: 0},

			{F: simple.Node(5), T: simple.Node(4), W: 3},
		},

		Query:  simple.Edge{F: simple.Node(0), T: simple.Node(4)},
		Weight: 4,
		WantPaths: [][]int64{
			{0, 1, 2, 3, 4},
			{0, 1, 5, 4},
		},
		HasUniquePath: false,

		NoPathFor: simple.Edge{F: simple.Node(4), T: simple.Node(5)},
	},
	{
		Name:  "zero-weight cycle^3 directed",
		Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) },
		Edges: []simple.WeightedEdge{

			{F: simple.Node(0), T: simple.Node(1), W: 1},
			{F: simple.Node(1), T: simple.Node(2), W: 1},
			{F: simple.Node(2), T: simple.Node(3), W: 1},
			{F: simple.Node(3), T: simple.Node(4), W: 1},

			{F: simple.Node(1), T: simple.Node(5), W: 0},
			{F: simple.Node(5), T: simple.Node(1), W: 0},

			{F: simple.Node(5), T: simple.Node(6), W: 0},
			{F: simple.Node(6), T: simple.Node(5), W: 0},

			{F: simple.Node(6), T: simple.Node(7), W: 0},
			{F: simple.Node(7), T: simple.Node(6), W: 0},
		},

		Query:  simple.Edge{F: simple.Node(0), T: simple.Node(4)},
		Weight: 4,
		WantPaths: [][]int64{
			{0, 1, 2, 3, 4},
		},
		HasUniquePath: false,

		NoPathFor: simple.Edge{F: simple.Node(4), T: simple.Node(5)},
	},
	{
		Name:  "zero-weight 3·cycle^2 confounding directed",
		Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) },
		Edges: []simple.WeightedEdge{

			{F: simple.Node(0), T: simple.Node(1), W: 1},
			{F: simple.Node(1), T: simple.Node(2), W: 1},
			{F: simple.Node(2), T: simple.Node(3), W: 1},
			{F: simple.Node(3), T: simple.Node(4), W: 1},

			{F: simple.Node(1), T: simple.Node(5), W: 0},
			{F: simple.Node(5), T: simple.Node(1), W: 0},

			{F: simple.Node(5), T: simple.Node(6), W: 0},
			{F: simple.Node(6), T: simple.Node(5), W: 0},
			{F: simple.Node(5), T: simple.Node(7), W: 0},
			{F: simple.Node(7), T: simple.Node(5), W: 0},

			{F: simple.Node(5), T: simple.Node(4), W: 3},
			{F: simple.Node(6), T: simple.Node(4), W: 3},
			{F: simple.Node(7), T: simple.Node(4), W: 3},
		},

		Query:  simple.Edge{F: simple.Node(0), T: simple.Node(4)},
		Weight: 4,
		WantPaths: [][]int64{
			{0, 1, 2, 3, 4},
			{0, 1, 5, 4},
			{0, 1, 5, 6, 4},
			{0, 1, 5, 7, 4},
		},
		HasUniquePath: false,

		NoPathFor: simple.Edge{F: simple.Node(4), T: simple.Node(5)},
	},
	{
		Name:  "zero-weight reversed 3·cycle^2 confounding directed",
		Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) },
		Edges: []simple.WeightedEdge{

			{F: simple.Node(0), T: simple.Node(1), W: 1},
			{F: simple.Node(1), T: simple.Node(2), W: 1},
			{F: simple.Node(2), T: simple.Node(3), W: 1},
			{F: simple.Node(3), T: simple.Node(4), W: 1},

			{F: simple.Node(3), T: simple.Node(5), W: 0},
			{F: simple.Node(5), T: simple.Node(3), W: 0},

			{F: simple.Node(5), T: simple.Node(6), W: 0},
			{F: simple.Node(6), T: simple.Node(5), W: 0},
			{F: simple.Node(5), T: simple.Node(7), W: 0},
			{F: simple.Node(7), T: simple.Node(5), W: 0},

			{F: simple.Node(0), T: simple.Node(5), W: 3},
			{F: simple.Node(0), T: simple.Node(6), W: 3},
			{F: simple.Node(0), T: simple.Node(7), W: 3},
		},

		Query:  simple.Edge{F: simple.Node(0), T: simple.Node(4)},
		Weight: 4,
		WantPaths: [][]int64{
			{0, 1, 2, 3, 4},
			{0, 5, 3, 4},
			{0, 6, 5, 3, 4},
			{0, 7, 5, 3, 4},
		},
		HasUniquePath: false,

		NoPathFor: simple.Edge{F: simple.Node(4), T: simple.Node(5)},
	},
	{
		Name:  "zero-weight |V|·cycle^(n/|V|) directed",
		Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) },
		Edges: func() []simple.WeightedEdge {
			e := []simple.WeightedEdge{

				{F: simple.Node(0), T: simple.Node(1), W: 1},
				{F: simple.Node(1), T: simple.Node(2), W: 1},
				{F: simple.Node(2), T: simple.Node(3), W: 1},
				{F: simple.Node(3), T: simple.Node(4), W: 1},
			}
			next := len(e) + 1

			// Add n zero-weight cycles.
			const n = 100
			for i := 0; i < n; i++ {
				e = append(e,
					simple.WeightedEdge{F: simple.Node(next + i), T: simple.Node(i), W: 0},
					simple.WeightedEdge{F: simple.Node(i), T: simple.Node(next + i), W: 0},
				)
			}
			return e
		}(),

		Query:  simple.Edge{F: simple.Node(0), T: simple.Node(4)},
		Weight: 4,
		WantPaths: [][]int64{
			{0, 1, 2, 3, 4},
		},
		HasUniquePath: false,

		NoPathFor: simple.Edge{F: simple.Node(4), T: simple.Node(5)},
	},
	{
		Name:  "zero-weight n·cycle directed",
		Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) },
		Edges: func() []simple.WeightedEdge {
			e := []simple.WeightedEdge{

				{F: simple.Node(0), T: simple.Node(1), W: 1},
				{F: simple.Node(1), T: simple.Node(2), W: 1},
				{F: simple.Node(2), T: simple.Node(3), W: 1},
				{F: simple.Node(3), T: simple.Node(4), W: 1},
			}
			next := len(e) + 1

			// Add n zero-weight cycles.
			const n = 100
			for i := 0; i < n; i++ {
				e = append(e,
					simple.WeightedEdge{F: simple.Node(next + i), T: simple.Node(1), W: 0},
					simple.WeightedEdge{F: simple.Node(1), T: simple.Node(next + i), W: 0},
				)
			}
			return e
		}(),

		Query:  simple.Edge{F: simple.Node(0), T: simple.Node(4)},
		Weight: 4,
		WantPaths: [][]int64{
			{0, 1, 2, 3, 4},
		},
		HasUniquePath: false,

		NoPathFor: simple.Edge{F: simple.Node(4), T: simple.Node(5)},
	},
	{
		Name:  "zero-weight bi-directional tree with single exit directed",
		Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) },
		Edges: func() []simple.WeightedEdge {
			e := []simple.WeightedEdge{

				{F: simple.Node(0), T: simple.Node(1), W: 1},
				{F: simple.Node(1), T: simple.Node(2), W: 1},
				{F: simple.Node(2), T: simple.Node(3), W: 1},
				{F: simple.Node(3), T: simple.Node(4), W: 1},
			}

			// Make a bi-directional tree rooted at node 2 with
			// a single exit to node 4 and co-equal cost from
			// 2 to 4.
			const (
				depth     = 4
				branching = 4
			)

			next := len(e) + 1
			src := 2
			var i, last int
			for l := 0; l < depth; l++ {
				for i = 0; i < branching; i++ {
					last = next + i
					e = append(e, simple.WeightedEdge{F: simple.Node(src), T: simple.Node(last), W: 0})
					e = append(e, simple.WeightedEdge{F: simple.Node(last), T: simple.Node(src), W: 0})
				}
				src = next + 1
				next += branching
			}
			e = append(e, simple.WeightedEdge{F: simple.Node(last), T: simple.Node(4), W: 2})
			return e
		}(),

		Query:  simple.Edge{F: simple.Node(0), T: simple.Node(4)},
		Weight: 4,
		WantPaths: [][]int64{
			{0, 1, 2, 3, 4},
			{0, 1, 2, 6, 10, 14, 20, 4},
		},
		HasUniquePath: false,

		NoPathFor: simple.Edge{F: simple.Node(4), T: simple.Node(5)},
	},

	{
		Name:  "one edge directed negative",
		Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) },
		Edges: []simple.WeightedEdge{
			{F: simple.Node(0), T: simple.Node(1), W: -1},
		},
		HasNegativeWeight: true,

		Query:  simple.Edge{F: simple.Node(0), T: simple.Node(1)},
		Weight: -1,
		WantPaths: [][]int64{
			{0, 1},
		},
		HasUniquePath: true,

		NoPathFor: simple.Edge{F: simple.Node(2), T: simple.Node(3)},
	},
	{
		Name:  "one edge undirected negative",
		Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedUndirectedGraph(0, math.Inf(1)) },
		Edges: []simple.WeightedEdge{
			{F: simple.Node(0), T: simple.Node(1), W: -1},
		},
		HasNegativeWeight: true,
		HasNegativeCycle:  true,

		Query:                  simple.Edge{F: simple.Node(0), T: simple.Node(1)},
		HasNegativeCycleInPath: true,
		Weight:                 math.Inf(-1),
		WantPaths: [][]int64{
			{0, 1},
		},

		NoPathFor: simple.Edge{F: simple.Node(2), T: simple.Node(3)},
	},
	{
		Name:  "two path directed negative cycle",
		Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) },
		Edges: []simple.WeightedEdge{
			{F: simple.Node(0), T: simple.Node(1), W: 1},
			{F: simple.Node(1), T: simple.Node(2), W: -1},
			{F: simple.Node(2), T: simple.Node(1), W: -1},
			{F: simple.Node(1), T: simple.Node(3), W: 1},
			{F: simple.Node(0), T: simple.Node(4), W: 1},
		},
		HasNegativeWeight: true,
		HasNegativeCycle:  true,

		Query:                  simple.Edge{F: simple.Node(0), T: simple.Node(3)},
		HasNegativeCycleInPath: true,
		Weight:                 math.Inf(-1),
		WantPaths: [][]int64{
			{1, 2, 1, 3},
		},

		NoPathFor: simple.Edge{F: simple.Node(5), T: simple.Node(6)},
	},
	{
		Name:  "two path directed off-path negative cycle",
		Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) },
		Edges: []simple.WeightedEdge{
			{F: simple.Node(0), T: simple.Node(1), W: 1},
			{F: simple.Node(1), T: simple.Node(2), W: -1},
			{F: simple.Node(2), T: simple.Node(1), W: -1},
			{F: simple.Node(1), T: simple.Node(3), W: 1},
			{F: simple.Node(0), T: simple.Node(4), W: 10},
		},
		HasNegativeWeight: true,
		HasNegativeCycle:  true,

		Query:                  simple.Edge{F: simple.Node(0), T: simple.Node(4)},
		HasNegativeCycleInPath: false,
		Weight:                 10,
		WantPaths: [][]int64{
			{0, 4},
		},
		HasUniquePath: true,

		NoPathFor: simple.Edge{F: simple.Node(5), T: simple.Node(6)},
	},
	{
		Name:  "two path directed diamond negative cycle",
		Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) },
		Edges: []simple.WeightedEdge{
			{F: simple.Node(0), T: simple.Node(1), W: 1},
			{F: simple.Node(1), T: simple.Node(2), W: -1},
			{F: simple.Node(2), T: simple.Node(1), W: -1},
			{F: simple.Node(1), T: simple.Node(3), W: 1},
			{F: simple.Node(0), T: simple.Node(3), W: 10},
		},
		HasNegativeWeight: true,
		HasNegativeCycle:  true,

		Query:                  simple.Edge{F: simple.Node(0), T: simple.Node(3)},
		HasNegativeCycleInPath: true,
		Weight:                 math.Inf(-1),
		WantPaths: [][]int64{
			{1, 2, 1, 3},
		},

		NoPathFor: simple.Edge{F: simple.Node(5), T: simple.Node(6)},
	},
	{
		Name:  "wp graph negative",
		Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) },
		Edges: []simple.WeightedEdge{
			{F: simple.Node('w'), T: simple.Node('z'), W: 2},
			{F: simple.Node('x'), T: simple.Node('w'), W: 6},
			{F: simple.Node('x'), T: simple.Node('y'), W: 3},
			{F: simple.Node('y'), T: simple.Node('w'), W: 4},
			{F: simple.Node('y'), T: simple.Node('z'), W: 5},
			{F: simple.Node('z'), T: simple.Node('x'), W: -7},
			{F: simple.Node('z'), T: simple.Node('y'), W: -3},
		},
		HasNegativeWeight: true,

		Query:  simple.Edge{F: simple.Node('z'), T: simple.Node('y')},
		Weight: -4,
		WantPaths: [][]int64{
			{'z', 'x', 'y'},
		},
		HasUniquePath: true,

		NoPathFor: simple.Edge{F: simple.Node(2), T: simple.Node(3)},
	},
	{
		Name:  "roughgarden negative",
		Graph: func() graph.WeightedEdgeAdder { return simple.NewWeightedDirectedGraph(0, math.Inf(1)) },
		Edges: []simple.WeightedEdge{
			{F: simple.Node('a'), T: simple.Node('b'), W: -2},
			{F: simple.Node('b'), T: simple.Node('c'), W: -1},
			{F: simple.Node('c'), T: simple.Node('a'), W: 4},
			{F: simple.Node('c'), T: simple.Node('x'), W: 2},
			{F: simple.Node('c'), T: simple.Node('y'), W: -3},
			{F: simple.Node('z'), T: simple.Node('x'), W: 1},
			{F: simple.Node('z'), T: simple.Node('y'), W: -4},
		},
		HasNegativeWeight: true,

		Query:  simple.Edge{F: simple.Node('a'), T: simple.Node('y')},
		Weight: -6,
		WantPaths: [][]int64{
			{'a', 'b', 'c', 'y'},
		},
		HasUniquePath: true,

		NoPathFor: simple.Edge{F: simple.Node(2), T: simple.Node(3)},
	},
}

ShortestPathTests are graphs used to test the static shortest path routines in path: BellmanFord, DijkstraAllPaths, DijkstraFrom, FloydWarshall and Johnson, and the static degenerate case for the dynamic shortest path routine in path/dynamic: DStarLite.

Functions

This section is empty.

Types

type Grid 

type Grid struct {
	// AllowDiagonal specifies whether
	// diagonally adjacent nodes can
	// be connected by an edge.
	AllowDiagonal bool
	// UnitEdgeWeight specifies whether
	// finite edge weights are returned as
	// the unit length. Otherwise edge
	// weights are the Euclidean distance
	// between connected nodes.
	UnitEdgeWeight bool

	// AllVisible specifies whether
	// non-open nodes are visible
	// in calls to Nodes and HasNode.
	AllVisible bool
	// contains filtered or unexported fields
}

Grid is a 2D grid planar undirected graph.

func NewGrid 

func NewGrid(r, c int, open bool) *Grid

NewGrid returns an r by c grid with all positions set to the specified open state.

func NewGridFrom 

func NewGridFrom(rows ...string) *Grid

NewGridFrom returns a grid specified by the rows strings. All rows must be the same length and must only contain the Open or Closed characters, NewGridFrom will panic otherwise.

func (*Grid) Dims 

func (g *Grid) Dims() (r, c int)

Dims returns the dimensions of the grid.

func (*Grid) Edge 

func (g *Grid) Edge(uid, vid int64) graph.Edge

Edge returns the edge between u and v.

func (*Grid) EdgeBetween 

func (g *Grid) EdgeBetween(uid, vid int64) graph.Edge

EdgeBetween returns the edge between u and v.

func (*Grid) From 

func (g *Grid) From(uid int64) graph.Nodes

From returns all the nodes reachable from u. Reachabilty requires that both ends of an edge must be open.

func (*Grid) HasEdgeBetween 

func (g *Grid) HasEdgeBetween(uid, vid int64) bool

HasEdgeBetween returns whether there is an edge between u and v.

func (*Grid) HasOpen 

func (g *Grid) HasOpen(id int64) bool

HasOpen returns whether n is an open node in the grid.

func (*Grid) Node 

func (g *Grid) Node(id int64) graph.Node

Node returns the node with the given ID if it exists in the graph, and nil otherwise.

func (*Grid) NodeAt 

func (g *Grid) NodeAt(r, c int) graph.Node

NodeAt returns the node at (r, c). The returned node may be open or closed.

func (*Grid) Nodes 

func (g *Grid) Nodes() graph.Nodes

Nodes returns all the open nodes in the grid if AllVisible is false, otherwise all nodes are returned.

func (*Grid) Render 

func (g *Grid) Render(path []graph.Node) ([]byte, error)

Render returns a text representation of the graph with the given path included. If the path is not a path in the grid Render returns a non-nil error and the path up to that point.

func (*Grid) RowCol 

func (g *Grid) RowCol(id int64) (r, c int)

RowCol returns the row and column of the id. RowCol will panic if the node id is outside the range of the grid.

func (*Grid) Set 

func (g *Grid) Set(r, c int, open bool)

Set sets the node at position (r, c) to the specified open state.

func (*Grid) String 

func (g *Grid) String() string

String returns a string representation of the grid.

func (*Grid) Weight 

func (g *Grid) Weight(xid, yid int64) (w float64, ok bool)

Weight returns the weight of the given edge.

func (*Grid) WeightedEdge 

func (g *Grid) WeightedEdge(uid, vid int64) graph.WeightedEdge

WeightedEdge returns the weighted edge between u and v.

func (*Grid) WeightedEdgeBetween 

func (g *Grid) WeightedEdgeBetween(uid, vid int64) graph.WeightedEdge

WeightedEdgeBetween returns the weighted edge between u and v.

func (*Grid) XY 

func (g *Grid) XY(id int64) (x, y float64)

XY returns the cartesian coordinates of n. If n is not a node in the grid, (NaN, NaN) is returned.

type LimitedVisionGrid 

type LimitedVisionGrid struct {
	Grid *Grid

	// Location is the current
	// location on the grid.
	Location graph.Node

	// VisionRadius specifies how far
	// away edges can be detected.
	VisionRadius float64

	// Known holds a store of known
	// nodes, if not nil.
	Known map[int64]bool
}

LimitedVisionGrid is a 2D grid planar undirected graph where the capacity to determine the presence of edges is dependent on the current and past positions on the grid. In the absence of information, the grid is optimistic.

func (*LimitedVisionGrid) Edge 

func (l *LimitedVisionGrid) Edge(uid, vid int64) graph.Edge

Edge optimistically returns the edge from u to v.

func (*LimitedVisionGrid) EdgeBetween 

func (l *LimitedVisionGrid) EdgeBetween(uid, vid int64) graph.Edge

WeightedEdgeBetween optimistically returns the edge between u and v.

func (*LimitedVisionGrid) From 

func (l *LimitedVisionGrid) From(uid int64) graph.Nodes

From returns nodes that are optimistically reachable from u.

func (*LimitedVisionGrid) HasEdgeBetween 

func (l *LimitedVisionGrid) HasEdgeBetween(uid, vid int64) bool

HasEdgeBetween optimistically returns whether an edge is exists between u and v.

func (*LimitedVisionGrid) MoveTo 

func (l *LimitedVisionGrid) MoveTo(n graph.Node) (new, old []graph.Edge)

MoveTo moves to the node n on the grid and returns a slice of newly seen and already known edges. MoveTo panics if n is nil.

func (*LimitedVisionGrid) Node 

func (l *LimitedVisionGrid) Node(id int64) graph.Node

Node returns the node with the given ID if it exists in the graph, and nil otherwise.

func (*LimitedVisionGrid) NodeAt 

func (l *LimitedVisionGrid) NodeAt(r, c int) graph.Node

NodeAt returns the node at (r, c). The returned node may be open or closed.

func (*LimitedVisionGrid) Nodes 

func (l *LimitedVisionGrid) Nodes() graph.Nodes

Nodes returns all the nodes in the grid.

func (*LimitedVisionGrid) Render 

func (l *LimitedVisionGrid) Render(path []graph.Node) ([]byte, error)

Render returns a text representation of the graph with the given path included. If the path is not a path in the grid Render returns a non-nil error and the path up to that point.

func (*LimitedVisionGrid) RowCol 

func (l *LimitedVisionGrid) RowCol(id int64) (r, c int)

RowCol returns the row and column of the id. RowCol will panic if the node id is outside the range of the grid.

func (*LimitedVisionGrid) String 

func (l *LimitedVisionGrid) String() string

String returns a string representation of the grid.

func (*LimitedVisionGrid) Weight 

func (l *LimitedVisionGrid) Weight(xid, yid int64) (w float64, ok bool)

Weight returns the weight of the given edge.

func (*LimitedVisionGrid) WeightedEdge 

func (l *LimitedVisionGrid) WeightedEdge(uid, vid int64) graph.WeightedEdge

Edge optimistically returns the weighted edge from u to v.

func (*LimitedVisionGrid) WeightedEdgeBetween 

func (l *LimitedVisionGrid) WeightedEdgeBetween(uid, vid int64) graph.WeightedEdge

WeightedEdgeBetween optimistically returns the weighted edge between u and v.

func (*LimitedVisionGrid) XY 

func (l *LimitedVisionGrid) XY(id int64) (x, y float64)

XY returns the cartesian coordinates of n. If n is not a node in the grid, (NaN, NaN) is returned.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.