dag

package
v0.0.0-...-a078c60 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Aug 11, 2023 License: Apache-2.0 Imports: 5 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

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.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL