internal

Documentation

Index

• type Key
• type Path
  • func (p Path) Extend(cost int, vertex Key) Path
• type PathHeap
  • func NewPathHeap(paths ...Path) *PathHeap
  • func (p *PathHeap) Len() int
  • func (p *PathHeap) Pop() Path
  • func (p *PathHeap) Push(path Path)
• type Paths
  • func (p Paths) Len() int
  • func (p Paths) Less(i int, j int) bool
  • func (p *Paths) Pop() interface{}
  • func (p *Paths) Push(path interface{})
  • func (p Paths) Swap(i int, j int)

Types

type Key

type Key uint64

Key represents a graph vertex.

type Path

type Path struct {
	Cost     int
	Vertices []Key // TODO(mway): list
}

Path represents an ordered series of contiguously incident vertices.

func (Path) Extend

func (p Path) Extend(cost int, vertex Key) Path

Extend extends p to contain vertex as the latest incident vertex and increases p's total cost by cost.

type PathHeap

type PathHeap struct {
	// contains filtered or unexported fields
}

PathHeap is a convenience wrapper around Paths and heap.Interface.

func NewPathHeap

func NewPathHeap(paths ...Path) *PathHeap

NewPathHeap creates a new PathHeap, initialized to contain paths.

func (*PathHeap) Len

func (p *PathHeap) Len() int

Len returns the heap's length.

func (*PathHeap) Pop

func (p *PathHeap) Pop() Path

Pop removes and returns the latest path in p.

func (*PathHeap) Push

func (p *PathHeap) Push(path Path)

Push pushes path onto the heap.

type Paths

type Paths []Path

Paths is a sortable collection of paths.

func (Paths) Len

func (p Paths) Len() int

Len returns the number of paths in p.

func (Paths) Less

func (p Paths) Less(i int, j int) bool

Less returns true if the cost of the ith Path in p is less than the cost of the jth path.

func (*Paths) Pop

func (p *Paths) Pop() interface{}

Pop removes and returns the latest path from p.

func (*Paths) Push

func (p *Paths) Push(path interface{})

Push pushes path onto p. It should not be called directly and is used to satisfy heap.Interface.

func (Paths) Swap

func (p Paths) Swap(i int, j int)

Swap swaps the ith and jth paths in p.