testgraphs

package

v0.9.1 Latest Latest Go to latest Published: Mar 29, 2021 License: BSD-3-Clause Imports: 6 Imported by: 0

Details

Valid go.mod file

The Go module system was introduced in Go 1.11 and is the official dependency management solution for Go.
Redistributable license

Redistributable licenses place minimal restrictions on how software can be used, modified, and redistributed.
Tagged version

Modules with tagged versions give importers more predictable builds.
Stable version

When a project reaches major version v1 it is considered stable.
Learn more about best practices

Repository

github.com/gonum/gonum

Links

Open Source Insights

Documentation ¶

Overview ¶

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

Index ¶

Constants
Variables
type Grid
- func NewGrid(r, c int, open bool) *Grid
- func NewGridFrom(rows ...string) *Grid
type LimitedVisionGrid

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

?	: This menu
/	: Search site
f or F	: Jump to
y or Y	: Canonical URL