gonum: gonum.org/v1/gonum/graph/path/internal/testgraphs Index | Files

package testgraphs

import "gonum.org/v1/gonum/graph/path/internal/testgraphs"

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

Index

Package Files

doc.go grid.go limited.go shortest.go

Constants

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

var ShortestPathTests = []struct {
    Name              string
    Graph             func() graph.WeightedEdgeAdder
    Edges             []simple.WeightedEdge
    HasNegativeWeight bool
    HasNegativeCycle  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)},
    },
    {
        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.

type Grid Uses

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 Uses

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 Uses

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 Uses

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

Dims returns the dimensions of the grid.

func (*Grid) Edge Uses

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

Edge returns the edge between u and v.

func (*Grid) EdgeBetween Uses

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

EdgeBetween returns the edge between u and v.

func (*Grid) From Uses

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 Uses

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

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

func (*Grid) HasOpen Uses

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

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

func (*Grid) Node Uses

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 Uses

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 Uses

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 Uses

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 Uses

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 Uses

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 Uses

func (g *Grid) String() string

String returns a string representation of the grid.

func (*Grid) Weight Uses

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

Weight returns the weight of the given edge.

func (*Grid) WeightedEdge Uses

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

WeightedEdge returns the weighted edge between u and v.

func (*Grid) WeightedEdgeBetween Uses

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

WeightedEdgeBetween returns the weighted edge between u and v.

func (*Grid) XY Uses

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 Uses

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 Uses

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

Edge optimistically returns the edge from u to v.

func (*LimitedVisionGrid) EdgeBetween Uses

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

WeightedEdgeBetween optimistically returns the edge between u and v.

func (*LimitedVisionGrid) From Uses

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

From returns nodes that are optimistically reachable from u.

func (*LimitedVisionGrid) HasEdgeBetween Uses

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

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

func (*LimitedVisionGrid) MoveTo Uses

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 Uses

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 Uses

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 Uses

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

Nodes returns all the nodes in the grid.

func (*LimitedVisionGrid) Render Uses

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 Uses

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 Uses

func (l *LimitedVisionGrid) String() string

String returns a string representation of the grid.

func (*LimitedVisionGrid) Weight Uses

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

Weight returns the weight of the given edge.

func (*LimitedVisionGrid) WeightedEdge Uses

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

Edge optimistically returns the weighted edge from u to v.

func (*LimitedVisionGrid) WeightedEdgeBetween Uses

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

WeightedEdgeBetween optimistically returns the weighted edge between u and v.

func (*LimitedVisionGrid) XY Uses

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.

Package testgraphs imports 6 packages (graph). Updated 2019-01-30. Refresh now. Tools for package owners.