graph

Documentation

Index

• func AStar[N comparable, E any, W Weight](g Weighted[N, E, W], start N, goal func(N) bool, h func(N) W) []E
• func BreadthFirstSearch[N comparable, E any](g Graph[N, E], start N, goal func(N) bool) []E
• func Dijkstra[N comparable, E any, W Weight](g Weighted[N, E, W], start N, goal func(N) bool) []E
• type Dense
  • func NewDense[W constraints.Integer | constraints.Float](n int) *Dense[W]
  • func (g *Dense[W]) Edges(i int) [][2]int
  • func (g *Dense[W]) From(e [2]int) int
  • func (g *Dense[W]) SetWeight(i, j int, w W)
  • func (g *Dense[W]) To(e [2]int) int
  • func (g *Dense[W]) Weight(e [2]int) W
• type Edge
• type Graph
• type Sparse
  • func NewSparse[W constraints.Integer | constraints.Float](n int) *Sparse[W]
  • func (g *Sparse[W]) Edges(i int) [][2]int
  • func (g *Sparse[W]) From(e [2]int) int
  • func (g *Sparse[W]) SetWeight(i, j int, w W)
  • func (g *Sparse[W]) To(e [2]int) int
  • func (g *Sparse[W]) Weight(e [2]int) W
• type Weight
• type Weighted

Functions

func AStar

func AStar[N comparable, E any, W Weight](g Weighted[N, E, W], start N, goal func(N) bool, h func(N) W) []E

AStar calculates the shortest path from start to a node satisfying goal using the A* algorithm.

func BreadthFirstSearch

func BreadthFirstSearch[N comparable, E any](g Graph[N, E], start N, goal func(N) bool) []E

BreadthFirstSearch calculates the shortest path from start to a node satisfying goal.

func Dijkstra

func Dijkstra[N comparable, E any, W Weight](g Weighted[N, E, W], start N, goal func(N) bool) []E

Dijkstra calculates the shortest path from start to a node satisfying goal using Dijkstra's algorithm.

Types

type Dense

type Dense[W constraints.Integer | constraints.Float] struct {
	N int // Number of nodes
	W []W // Weight of edge i->j at i•N+j
}

Dense is a weighted graph represented by an adjacency matrix. It implements Weighted[int, [2]int, W].

func NewDense

func NewDense[W constraints.Integer | constraints.Float](n int) *Dense[W]

NewDense creates a Dense graph with n nodes.

func (*Dense[W]) Edges

func (g *Dense[W]) Edges(i int) [][2]int

Edges returns the non-zero edges adjacent to i.

func (*Dense[W]) From

func (g *Dense[W]) From(e [2]int) int

From returns e[0].

func (*Dense[W]) SetWeight

func (g *Dense[W]) SetWeight(i, j int, w W)

SetWeight sets the weight of i->j to w.

func (*Dense[W]) To

func (g *Dense[W]) To(e [2]int) int

From returns e[1].

func (*Dense[W]) Weight

func (g *Dense[W]) Weight(e [2]int) W

Weight returns the weight of e.

type Edge

type Edge[Node any] struct {
	From Node
	To   Node
}

type Graph

type Graph[Node, Edge any] interface {
	Edges(Node) []Edge
	From(Edge) Node
	To(Edge) Node
}

type Sparse

type Sparse[W constraints.Integer | constraints.Float] struct {
	N int
	// contains filtered or unexported fields
}

Sparse is a weighted graph represented by an adjacency list. It implements Weighted[int, [2]int, W].

func NewSparse

func NewSparse[W constraints.Integer | constraints.Float](n int) *Sparse[W]

func (*Sparse[W]) Edges

func (g *Sparse[W]) Edges(i int) [][2]int

Edges returns the edges adjacent to i. The returned slice must not be modified.

func (*Sparse[W]) From

func (g *Sparse[W]) From(e [2]int) int

From returns e[0].

func (*Sparse[W]) SetWeight

func (g *Sparse[W]) SetWeight(i, j int, w W)

SetWeight sets the weight of i->j to w.

func (*Sparse[W]) To

func (g *Sparse[W]) To(e [2]int) int

To returns e[1].

func (*Sparse[W]) Weight

func (g *Sparse[W]) Weight(e [2]int) W

Weight returns the weight of e.

type Weight

type Weight interface {
	constraints.Integer | constraints.Float
}

type Weighted

type Weighted[Node, Edge, Weight any] interface {
	Graph[Node, Edge]
	Weight(Edge) Weight
}