graph

Documentation

Index

• func NextId() int
• type BaseNode
  • func NewBaseNode[T comparable](id T) *BaseNode[T]
  • func NewBaseNodeAutoId() *BaseNode[int]
  • func (n *BaseNode[T]) AddNeighbor(neighbor Node[T], weight int)
  • func (n *BaseNode[T]) GetNeighbors() map[T]int
  • func (n *BaseNode[T]) HasNeighbor(id T) bool
  • func (n *BaseNode[T]) Id() T
  • func (n *BaseNode[T]) RemoveNeighbor(id T)
  • func (n *BaseNode[T]) String() string
• type Graph
  • func New[ID comparable]() *Graph[ID]
  • func (g *Graph[ID]) AddDirectedEdge(from, to ID, weight int)
  • func (g *Graph[ID]) AddEdge(a, b ID, weight int)
  • func (g *Graph[ID]) AddNode(node Node[ID])
  • func (g Graph[ID]) Dfs(start Node[ID], goal func(ID) bool) Path[ID]
  • func (g Graph[ID]) Dijkstra(start Node[ID], goal func(ID) bool) Path[ID]
  • func (g Graph[ID]) Distances(start Node[ID]) map[ID]int
  • func (g *Graph[ID]) GetNode(id ID) Node[ID]
  • func (g *Graph[ID]) GetNodes() map[ID]Node[ID]
  • func (g *Graph[ID]) HasNode(id ID) bool
  • func (g Graph[ID]) NodesOfBestPaths(start Node[ID], goal func(ID) bool) []ID
  • func (g *Graph[ID]) RemoveNode(id ID)
  • func (g *Graph[ID]) String() string
• type Node
• type Path
  • func NewPath[ID comparable](nodes []ID, cost int) Path[ID]
  • func NoPath[ID comparable]() Path[ID]
  • func (p *Path[ID]) AddFirstNode(node ID, cost int)
  • func (p *Path[ID]) AddNode(node ID, cost int)
  • func (p Path[ID]) Copy() Path[ID]
  • func (p Path[ID]) Cost() int
  • func (p Path[ID]) IsValid() bool
  • func (p Path[ID]) LastNode() ID
  • func (p Path[ID]) Nodes() []ID

Functions

func NextId

func NextId() int

Types

type BaseNode

type BaseNode[T comparable] struct {
	// contains filtered or unexported fields
}

func NewBaseNode

func NewBaseNode[T comparable](id T) *BaseNode[T]

func NewBaseNodeAutoId

func NewBaseNodeAutoId() *BaseNode[int]

func (*BaseNode[T]) AddNeighbor

func (n *BaseNode[T]) AddNeighbor(neighbor Node[T], weight int)

func (*BaseNode[T]) GetNeighbors

func (n *BaseNode[T]) GetNeighbors() map[T]int

func (*BaseNode[T]) HasNeighbor

func (n *BaseNode[T]) HasNeighbor(id T) bool

func (*BaseNode[T]) Id

func (n *BaseNode[T]) Id() T

func (*BaseNode[T]) RemoveNeighbor

func (n *BaseNode[T]) RemoveNeighbor(id T)

func (*BaseNode[T]) String

func (n *BaseNode[T]) String() string

String returns a string representation of the node

type Graph

type Graph[ID comparable] struct {
	// contains filtered or unexported fields
}

func New

func New[ID comparable]() *Graph[ID]

func (*Graph[ID]) AddDirectedEdge

func (g *Graph[ID]) AddDirectedEdge(from, to ID, weight int)

func (*Graph[ID]) AddEdge

func (g *Graph[ID]) AddEdge(a, b ID, weight int)

func (*Graph[ID]) AddNode

func (g *Graph[ID]) AddNode(node Node[ID])

func (Graph[ID]) Dfs

func (g Graph[ID]) Dfs(start Node[ID], goal func(ID) bool) Path[ID]

Dfs finds the shortest path from the start node to the end node using depth-first search

func (Graph[ID]) Dijkstra

func (g Graph[ID]) Dijkstra(start Node[ID], goal func(ID) bool) Path[ID]

Dijkstra finds the shortest path from the start node to the end node

func (Graph[ID]) Distances

func (g Graph[ID]) Distances(start Node[ID]) map[ID]int

Distances finds the shortest path from the start node to all other nodes

func (*Graph[ID]) GetNode

func (g *Graph[ID]) GetNode(id ID) Node[ID]

func (*Graph[ID]) GetNodes

func (g *Graph[ID]) GetNodes() map[ID]Node[ID]

func (*Graph[ID]) HasNode

func (g *Graph[ID]) HasNode(id ID) bool

func (Graph[ID]) NodesOfBestPaths

func (g Graph[ID]) NodesOfBestPaths(start Node[ID], goal func(ID) bool) []ID

NodesOfBestPaths finds all the shortest paths from the start node to the end node

func (*Graph[ID]) RemoveNode

func (g *Graph[ID]) RemoveNode(id ID)

func (*Graph[ID]) String

func (g *Graph[ID]) String() string

String returns a string representation of the graph

type Node

type Node[T comparable] interface {
	AddNeighbor(neighbor Node[T], weight int)
	GetNeighbors() map[T]int
	HasNeighbor(id T) bool
	Id() T
	RemoveNeighbor(id T)
	fmt.Stringer
}

type Path

type Path[ID comparable] struct {
	// contains filtered or unexported fields
}

func NewPath

func NewPath[ID comparable](nodes []ID, cost int) Path[ID]

func NoPath

func NoPath[ID comparable]() Path[ID]

func (*Path[ID]) AddFirstNode

func (p *Path[ID]) AddFirstNode(node ID, cost int)

func (*Path[ID]) AddNode

func (p *Path[ID]) AddNode(node ID, cost int)

func (Path[ID]) Copy

func (p Path[ID]) Copy() Path[ID]

func (Path[ID]) Cost

func (p Path[ID]) Cost() int

func (Path[ID]) IsValid

func (p Path[ID]) IsValid() bool

func (Path[ID]) LastNode

func (p Path[ID]) LastNode() ID

func (Path[ID]) Nodes

func (p Path[ID]) Nodes() []ID