graph

Documentation

Index

• Variables
• func TestBFS(t *testing.T)
• func TestDFS(t *testing.T)
• type BreadthFirst
  • func (b BreadthFirst[T]) Walk(ctx context.Context, g Directed, r Node) error
• type Builder
  • func (b *Builder) AddEdge(o Origination, d Destination) error
  • func (b *Builder) AddEdges(e OriginationMap) error
  • func (b *Builder) AddNode(n Node)
  • func (b *Builder) AddNodes(ns []Node)
• type DebugFunc
• type DebugSelector
  • func (d DebugSelector[T]) Select(g Directed, n Node) ([]T, error)
• type DebugVisitor
  • func (d DebugVisitor) Visit(ctx context.Context, node Node) error
• type DepthFirst
  • func (d DepthFirst[T]) Walk(ctx context.Context, g Directed, r Node) error
• type Destination
  • func (d Destination) String() string
• type Directed
  • func FromOriginationMap(src OriginationMap) Directed
  • func New() Directed
  • func WithCapacity(c int) Directed
  • func (g Directed) NodeCount() int
  • func (g Directed) Predecessors(n Node) ([]Origination, error)
  • func (g Directed) Successors(n Node) ([]Destination, error)
• type Direction
• type Edge
• type Node
  • func (n Node) String() string
• type Origination
  • func (o Origination) String() string
• type OriginationMap
• type Selector
• type SelectorFunc
  • func (s SelectorFunc[T]) Select(g Directed, n Node) ([]T, error)
• type Visitor
• type VisitorArray
  • func (v VisitorArray) Visit(ctx context.Context, node Node) error
• type VisitorFunc
  • func (v VisitorFunc) Visit(ctx context.Context, n Node) error
• type Walker

Variables

var ErrDestNotFound = errors.New("destination not found")

var ErrNodeNotFound = errors.New("node not found")

var ErrOriginNotFound = errors.New("origin not found")

Functions

func TestBFS

func TestBFS(t *testing.T)

func TestDFS

func TestDFS(t *testing.T)

Types

type BreadthFirst

type BreadthFirst[T Direction] struct {
	Visitor
	Selector[T]
}

func (BreadthFirst[T]) Walk

func (b BreadthFirst[T]) Walk(ctx context.Context, g Directed, r Node) error

type Builder

type Builder struct {
	G Directed
}

adds nodes and edges to a Directed

func (*Builder) AddEdge

func (b *Builder) AddEdge(o Origination, d Destination) error

connects o -> d, if either node doesn't exist they are created

duplicate edges are not added, order isn't guaranteed

func (*Builder) AddEdges

func (b *Builder) AddEdges(e OriginationMap) error

func (*Builder) AddNode

func (b *Builder) AddNode(n Node)

adds a node to the graph if it doesn't exist already

func (*Builder) AddNodes

func (b *Builder) AddNodes(ns []Node)

type DebugFunc

type DebugFunc func(string, ...any)

used to provide human readable diagnostic output

type DebugSelector

type DebugSelector[T Direction] struct {
	F DebugFunc
	S Selector[T]
}

calls F on current node, selected and err results from S

func (DebugSelector[T]) Select

func (d DebugSelector[T]) Select(g Directed, n Node) ([]T, error)

type DebugVisitor

type DebugVisitor struct {
	F DebugFunc
	V Visitor
}

calls F on current node, error from V

func (DebugVisitor) Visit

func (d DebugVisitor) Visit(ctx context.Context, node Node) error

type DepthFirst

type DepthFirst[T Direction] struct {
	Visitor
	Selector[T]
}

func (DepthFirst[T]) Walk

func (d DepthFirst[T]) Walk(ctx context.Context, g Directed, r Node) error

type Destination

type Destination Node

an entity in the graph that is the destination for an edge

func (Destination) String

func (d Destination) String() string

type Directed

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

adjanceny list, edges maintain insertion order, nodes do not do not construct directly, use a provided ctor direct usage of Directed is readonly

func FromOriginationMap

func FromOriginationMap(src OriginationMap) Directed

func New

func New() Directed

returns a Directed with a small predetermined capacity

func WithCapacity

func WithCapacity(c int) Directed

func (Directed) NodeCount

func (g Directed) NodeCount() int

func (Directed) Predecessors

func (g Directed) Predecessors(n Node) ([]Origination, error)

given Node n, find all other nodes that point at it

func (Directed) Successors

func (g Directed) Successors(n Node) ([]Destination, error)

given Node n, find all nodes that it points at

type Direction

type Direction interface {
	Origination | Destination
}

allows specifying direction when interacting with a Directed graph

type Edge

type Edge struct {
	O Origination
	D Destination
}

a connection between two entities in the graph

type Node

type Node int

an entity in the graph

const (
	A Node = 1 << iota
	B Node = 1 << iota
	C Node = 1 << iota
	D Node = 1 << iota
	E Node = 1 << iota
	F Node = 1 << iota
)

func (Node) String

func (n Node) String() string

type Origination

type Origination Node

an entity in the graph that is the origination for an edge

func (Origination) String

func (o Origination) String() string

type OriginationMap

type OriginationMap map[Origination][]Destination

describes a graph as the set of originating edges

type Selector

type Selector[T Direction] interface {
	Select(Directed, Node) ([]T, error)
}

responsible for determining which nodes to explore next and in which direction to explore

type SelectorFunc

type SelectorFunc[T Direction] func(Directed, Node) ([]T, error)

var (
	// given Node n, return all nodes it points at
	Successors SelectorFunc[Destination] = Directed.Successors
	// given Node n, return all nodes that point at it
	Predecessors SelectorFunc[Origination] = Directed.Predecessors
	// visitors should return this err to gracefully exit a walk
	ErrVisitTerminated = errors.New("visit terminated")
)

func (SelectorFunc[T]) Select

func (s SelectorFunc[T]) Select(g Directed, n Node) ([]T, error)

type Visitor

type Visitor interface {
	Visit(context.Context, Node) error
}

called with the current node and a context visitors may gracefully end a walk by returning ErrVisitTerminated all other errors terminate the walk and the error is returned to the user

type VisitorArray

type VisitorArray []Visitor

provides current node to every Visitor in slice

func (VisitorArray) Visit

func (v VisitorArray) Visit(ctx context.Context, node Node) error

type VisitorFunc

type VisitorFunc func(context.Context, Node) error

func (VisitorFunc) Visit

func (v VisitorFunc) Visit(ctx context.Context, n Node) error

type Walker

type Walker[T Direction] interface {
	Walk(context.Context, Directed, Node) error
}