dag

Documentation

Index

• type CycleError
  • func (c *CycleError[Key]) Error() string
• type Graph
  • func NewGraph[Key comparable]() *Graph[Key]
  • func (g *Graph[Key]) AddEdge(from Key, to Key)
  • func (g *Graph[Key]) AddNode(key Key)
  • func (g *Graph[Key]) ContainsNode(key Key) bool
  • func (g *Graph[Key]) DOTString(keyToString func(Key) string) (string, error)
  • func (g *Graph[Key]) TopoSort(start Key) ([]Key, error)
  • func (g *Graph[Key]) Walk(f func(Key, Key) error) error

Types

type CycleError

type CycleError[Key comparable] struct {
	Keys []Key
}

CycleError is an error if the Graph had a cycle.

func (*CycleError[Key]) Error

func (c *CycleError[Key]) Error() string

Error implements error.

type Graph

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

Graph is a directed acyclic graph structure with comparable keys.

func NewGraph

func NewGraph[Key comparable]() *Graph[Key]

NewGraph returns a new Graph.

Graphs can also safely be instantiated with &Graph{}.

func (*Graph[Key]) AddEdge

func (g *Graph[Key]) AddEdge(from Key, to Key)

AddEdge adds an edge.

func (*Graph[Key]) AddNode

func (g *Graph[Key]) AddNode(key Key)

AddNode adds a node.

func (*Graph[Key]) ContainsNode

func (g *Graph[Key]) ContainsNode(key Key) bool

ContainsNode returns true if the graph contains the given node.

func (*Graph[Key]) DOTString

func (g *Graph[Key]) DOTString(keyToString func(Key) string) (string, error)

DOTString returns a DOT representation of the graph.

keyToString is used to print out the label for each node. https://graphviz.org/doc/info/lang.html

func (*Graph[Key]) TopoSort

func (g *Graph[Key]) TopoSort(start Key) ([]Key, error)

TopoSort topologically sorts the nodes in the Graph starting at the given key.

Returns a *CycleError if there is a cycle in the graph.

func (*Graph[Key]) Walk

func (g *Graph[Key]) Walk(f func(Key, Key) error) error

Walk visits each edge in the Graph starting at the source keys.

Returns a *CycleError if there is a cycle in the graph.