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]) NumEdges() int
  • func (g *Graph[Key]) NumNodes() int
  • func (g *Graph[Key]) TopoSort(start Key) ([]Key, error)
  • func (g *Graph[Key]) WalkEdges(f func(Key, Key) error) error
  • func (g *Graph[Key]) WalkNodes(f func(Key, []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]) NumEdges

func (g *Graph[Key]) NumEdges() int

NumNodes returns the number of edges in the graph.

func (*Graph[Key]) NumNodes

func (g *Graph[Key]) NumNodes() int

NumNodes returns the number of nodes in the graph.

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]) WalkEdges

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

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

f is called for each directed edge. The first argument is the source node, the second is the destination node.

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

func (*Graph[Key]) WalkNodes

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

WalkNodes visited each node in the Graph based on insertion order.

f is called for each node. The first argument is the key for the node, the second argument is all inbound edges, the third argument is all outbound edges.