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
• func MinimumCut[N, E comparable, W Weight](g UndirectedWeighted[N, E, W], a, b N) (cut W, edges iter.Seq[E], reachable iter.Seq[N])
• func WalkDepthFirst[N comparable, E any](g Graph[N, E], start N) iter.Seq[N]
• type Dense
  • func NewDense[W constraints.Integer | constraints.Float](n int) *Dense[W]
  • func (g *Dense[W]) Edges(i int) iter.Seq[[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
  • func NeighborFunc[N any](neighbors func(N) iter.Seq[N]) Graph[N, [2]N]
• type Sparse
  • func NewSparse[W constraints.Integer | constraints.Float](n int) *Sparse[W]
  • func (g *Sparse[W]) Edges(i int) iter.Seq[[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
  • func (g *Sparse[W]) WeightedEdges(i int) iter.Seq2[[2]int, W]
• type Undirected
• type UndirectedWeighted
  • func MaximumFlow[N, E comparable, W Weight](g UndirectedWeighted[N, E, W], source, sink N) (W, iter.Seq2[E, W], UndirectedWeighted[N, E, 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.

func MinimumCut

func MinimumCut[N, E comparable, W Weight](g UndirectedWeighted[N, E, W], a, b N) (cut W, edges iter.Seq[E], reachable iter.Seq[N])

MinimumCut returns a minimal cut separating a and b, an iterator over the edges to cut and the nodes of the sub graphs containing a.

func WalkDepthFirst

func WalkDepthFirst[N comparable, E any](g Graph[N, E], start N) iter.Seq[N]

WalkDepthFirst returns an iterator over a depth-first walk of g from start. Every reachable node is yielded exactly once.

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) iter.Seq[[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) iter.Seq[Edge]
	From(Edge) Node
	To(Edge) Node
}

func NeighborFunc

func NeighborFunc[N any](neighbors func(N) iter.Seq[N]) Graph[N, [2]N]

NeighborFunc returns a Graph that only has simple edges.

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) iter.Seq[[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.

func (*Sparse[W]) WeightedEdges

func (g *Sparse[W]) WeightedEdges(i int) iter.Seq2[[2]int, W]

WeightedEdges returns an iterator over the edges adjacent to i and their weights.

type Undirected

type Undirected[N, E any] interface {
	Graph[N, E]
	Reverse(E) E
}

Undirected graph. Every edge must be reversible.

type UndirectedWeighted

type UndirectedWeighted[N, E, W any] interface {
	Undirected[N, E]
	Weight(E) W
}

Undirected weighted graph. It must be Weight(Revers(e)) == Weight(e) for all edges.

func MaximumFlow

func MaximumFlow[N, E comparable, W Weight](g UndirectedWeighted[N, E, W], source, sink N) (W, iter.Seq2[E, W], UndirectedWeighted[N, E, W])

MaximumFlow returns the maximum flow from source to sink, an iterator over one maximizing flow and the residual graph of that flow.

type Weight

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

type Weighted

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