edsger

README

edsger: a simple Go graph library

edsger is a simple Go graph library defining a graph datastructure and the following algorithms:

• Shortest path finding based on Dijkstra's shortest path algorithm
• Simple path finding based on depth first search (DFS) graph traversal
• Topological ordering for directed acyclic graphs (DAGs)

Installation

$ go get github.com/fabgeyer/edsger@latest

Documentation

Index

• func MaxInt[T Integer]() T
• func MaxValue[N Number]() N
• func Signed[T Number]() bool
• func SignedInt[T Integer]() bool
• type DijkstraDisjointShortestPathIterator
  • func (it *DijkstraDisjointShortestPathIterator[T, N]) Get() ([]T, N)
  • func (it *DijkstraDisjointShortestPathIterator[T, N]) Next() bool
  • func (it *DijkstraDisjointShortestPathIterator[T, N]) Shuffle() *DijkstraDisjointShortestPathIterator[T, N]
• type Graph
  • func NewDirectedGraph[T comparable, N Number]() *Graph[T, N]
  • func NewUndirectedGraph[T comparable, N Number]() *Graph[T, N]
  • func (g *Graph[T, N]) AddEdge(source, dest T, weight N)
  • func (g *Graph[T, N]) AddNode(n T)
  • func (g *Graph[T, N]) AllDijkstraDisjointShortestPaths(source, dest T) *DijkstraDisjointShortestPathIterator[T, N]
  • func (g *Graph[T, N]) AllDijkstraShortestPathsMap(source, dest T) (map[T][]T, N)
  • func (g *Graph[T, N]) AllPredecessors() map[T]map[T]bool
  • func (g *Graph[T, N]) AllShortestPathsNodes(source, dest T) ([]T, N)
  • func (g *Graph[T, N]) AllSimplePaths(source, dest T) *SimplePathIterator[T, N]
  • func (g *Graph[T, N]) AllSimplePathsWithHeuristic(source, dest T, heuristic func(i, j *NodeWeight[T, N]) int) *SimplePathIterator[T, N]
  • func (g *Graph[T, N]) AllSuccessors() map[T]map[T]bool
  • func (g *Graph[T, N]) Clone() *Graph[T, N]
  • func (g *Graph[T, N]) Degree() iter.Seq2[T, int]
  • func (g *Graph[T, N]) DijkstraShortestPath(source, dest T) ([]T, N)
  • func (g *Graph[T, N]) DijkstraShortestPathWithExclusionMap(source, dest T, excludedNodes map[T]bool) ([]T, N)
  • func (g *Graph[T, N]) DijkstraShortestPathWithoutNodes(source, dest T) ([]T, N)
  • func (g *Graph[T, N]) Edges() iter.Seq[*WeightedEdge[T, N]]
  • func (g *Graph[T, N]) GetEdge(source, dest T) (N, bool)
  • func (g *Graph[T, N]) HasEdge(source, dest T) bool
  • func (g *Graph[T, N]) HasNode(n T) bool
  • func (g *Graph[T, N]) HasSimplePath(source, dest T) bool
  • func (g *Graph[T, N]) IsDAG() bool
  • func (g *Graph[T, N]) IsDirected() bool
  • func (g *Graph[T, N]) Neighbors(n T) []*NodeWeight[T, N]
  • func (g *Graph[T, N]) Nodes() iter.Seq[T]
  • func (g *Graph[T, N]) NodesList() []T
  • func (g *Graph[T, N]) NumberOfEdges() int
  • func (g *Graph[T, N]) NumberOfNodes() int
  • func (g *Graph[T, N]) Predecessors(node T) iter.Seq[T]
  • func (g *Graph[T, N]) RemoveEdge(source, dest T)
  • func (g *Graph[T, N]) RemoveNode(node T)
  • func (g *Graph[T, N]) ShortestPathWithMinCost(source, dest T, minCost N) ([]T, N)
  • func (g *Graph[T, N]) ShortestPathWithMinNodes(source, dest T, minNodes int) ([]T, int)
  • func (g *Graph[T, N]) SimplePath(source, dest T) ([]T, N)
  • func (g *Graph[T, N]) Successors(node T) iter.Seq[T]
  • func (g *Graph[T, N]) TopologicalOrdering() ([]T, error)
  • func (g *Graph[T, N]) UpdateEdge(source, dest T, newWeight N)
• type Integer
• type NodeWeight
• type Number
• type SPIStackElem
• type SimplePathIterator
  • func (it *SimplePathIterator[T, N]) Get() ([]T, N)
  • func (it *SimplePathIterator[T, N]) Next() bool
• type WeightedEdge

Functions

func MaxInt

func MaxInt[T Integer]() T

func MaxValue

func MaxValue[N Number]() N

func Signed

func Signed[T Number]() bool

func SignedInt

func SignedInt[T Integer]() bool

Returns true if the type is signed

Types

type DijkstraDisjointShortestPathIterator

type DijkstraDisjointShortestPathIterator[T comparable, N Number] struct {
	// contains filtered or unexported fields
}

func (*DijkstraDisjointShortestPathIterator[T, N]) Get

func (it *DijkstraDisjointShortestPathIterator[T, N]) Get() ([]T, N)

func (*DijkstraDisjointShortestPathIterator[T, N]) Next

func (it *DijkstraDisjointShortestPathIterator[T, N]) Next() bool

func (*DijkstraDisjointShortestPathIterator[T, N]) Shuffle

func (it *DijkstraDisjointShortestPathIterator[T, N]) Shuffle() *DijkstraDisjointShortestPathIterator[T, N]

type Graph

type Graph[T comparable, N Number] struct {
	// contains filtered or unexported fields
}

func NewDirectedGraph

func NewDirectedGraph[T comparable, N Number]() *Graph[T, N]

Returns a new directed graph

func NewUndirectedGraph

func NewUndirectedGraph[T comparable, N Number]() *Graph[T, N]

Returns a new undirected graph

func (*Graph[T, N]) AddEdge

func (g *Graph[T, N]) AddEdge(source, dest T, weight N)

func (*Graph[T, N]) AddNode

func (g *Graph[T, N]) AddNode(n T)

func (*Graph[T, N]) AllDijkstraDisjointShortestPaths

func (g *Graph[T, N]) AllDijkstraDisjointShortestPaths(source, dest T) *DijkstraDisjointShortestPathIterator[T, N]

func (*Graph[T, N]) AllDijkstraShortestPathsMap

func (g *Graph[T, N]) AllDijkstraShortestPathsMap(source, dest T) (map[T][]T, N)

func (*Graph[T, N]) AllPredecessors

func (g *Graph[T, N]) AllPredecessors() map[T]map[T]bool

func (*Graph[T, N]) AllShortestPathsNodes

func (g *Graph[T, N]) AllShortestPathsNodes(source, dest T) ([]T, N)

func (*Graph[T, N]) AllSimplePaths

func (g *Graph[T, N]) AllSimplePaths(source, dest T) *SimplePathIterator[T, N]

func (*Graph[T, N]) AllSimplePathsWithHeuristic

func (g *Graph[T, N]) AllSimplePathsWithHeuristic(source, dest T, heuristic func(i, j *NodeWeight[T, N]) int) *SimplePathIterator[T, N]

func (*Graph[T, N]) AllSuccessors

func (g *Graph[T, N]) AllSuccessors() map[T]map[T]bool

func (*Graph[T, N]) Clone

func (g *Graph[T, N]) Clone() *Graph[T, N]

func (*Graph[T, N]) Degree

func (g *Graph[T, N]) Degree() iter.Seq2[T, int]

func (*Graph[T, N]) DijkstraShortestPath

func (g *Graph[T, N]) DijkstraShortestPath(source, dest T) ([]T, N)

func (*Graph[T, N]) DijkstraShortestPathWithExclusionMap

func (g *Graph[T, N]) DijkstraShortestPathWithExclusionMap(source, dest T, excludedNodes map[T]bool) ([]T, N)

func (*Graph[T, N]) DijkstraShortestPathWithoutNodes

func (g *Graph[T, N]) DijkstraShortestPathWithoutNodes(source, dest T) ([]T, N)

func (*Graph[T, N]) Edges

func (g *Graph[T, N]) Edges() iter.Seq[*WeightedEdge[T, N]]

func (*Graph[T, N]) GetEdge

func (g *Graph[T, N]) GetEdge(source, dest T) (N, bool)

func (*Graph[T, N]) HasEdge

func (g *Graph[T, N]) HasEdge(source, dest T) bool

func (*Graph[T, N]) HasNode

func (g *Graph[T, N]) HasNode(n T) bool

func (*Graph[T, N]) HasSimplePath

func (g *Graph[T, N]) HasSimplePath(source, dest T) bool

func (*Graph[T, N]) IsDAG

func (g *Graph[T, N]) IsDAG() bool

func (*Graph[T, N]) IsDirected

func (g *Graph[T, N]) IsDirected() bool

func (*Graph[T, N]) Neighbors

func (g *Graph[T, N]) Neighbors(n T) []*NodeWeight[T, N]

For undirected graphs: returns a slices of all neighbors of node n For directed graphs: returns a slice of all successor nodes of n

func (*Graph[T, N]) Nodes

func (g *Graph[T, N]) Nodes() iter.Seq[T]

func (*Graph[T, N]) NodesList

func (g *Graph[T, N]) NodesList() []T

func (*Graph[T, N]) NumberOfEdges

func (g *Graph[T, N]) NumberOfEdges() int

func (*Graph[T, N]) NumberOfNodes

func (g *Graph[T, N]) NumberOfNodes() int

func (*Graph[T, N]) Predecessors

func (g *Graph[T, N]) Predecessors(node T) iter.Seq[T]

Returns an iterator over predecessor nodes of n.

func (*Graph[T, N]) RemoveEdge

func (g *Graph[T, N]) RemoveEdge(source, dest T)

func (*Graph[T, N]) RemoveNode

func (g *Graph[T, N]) RemoveNode(node T)

func (*Graph[T, N]) ShortestPathWithMinCost

func (g *Graph[T, N]) ShortestPathWithMinCost(source, dest T, minCost N) ([]T, N)

func (*Graph[T, N]) ShortestPathWithMinNodes

func (g *Graph[T, N]) ShortestPathWithMinNodes(source, dest T, minNodes int) ([]T, int)

func (*Graph[T, N]) SimplePath

func (g *Graph[T, N]) SimplePath(source, dest T) ([]T, N)

func (*Graph[T, N]) Successors

func (g *Graph[T, N]) Successors(node T) iter.Seq[T]

Returns an iterator over successor nodes of n.

func (*Graph[T, N]) TopologicalOrdering

func (g *Graph[T, N]) TopologicalOrdering() ([]T, error)

Implementation using Kahn's algorithm

func (*Graph[T, N]) UpdateEdge

func (g *Graph[T, N]) UpdateEdge(source, dest T, newWeight N)

type Integer

type Integer interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64 | ~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64
}

type NodeWeight

type NodeWeight[T comparable, N Number] struct {
	Node   T
	Weight N
}

type Number

type Number interface {
	~float32 | ~float64 | Integer
}

type SPIStackElem

type SPIStackElem[T comparable, N Number] struct {
	// contains filtered or unexported fields
}

type SimplePathIterator

type SimplePathIterator[T comparable, N Number] struct {
	CutoffWeight N
	CutoffHops   int
	// contains filtered or unexported fields
}

func (*SimplePathIterator[T, N]) Get

func (it *SimplePathIterator[T, N]) Get() ([]T, N)

func (*SimplePathIterator[T, N]) Next

func (it *SimplePathIterator[T, N]) Next() bool

type WeightedEdge

type WeightedEdge[T comparable, N Number] struct {
	From   T
	To     T
	Weight N
}