dag

Documentation

Index

• Variables
• func EdgesToMap[T any](e map[int64][]Edge[T]) map[int64][]int64
• func EnsureGraphEdges[T any](t *testing.T, expected map[int64][]int64, graphEdges map[int64][]Edge[T])
• func EnsureGraphNodes[T any](t *testing.T, expected []int64, nodes []Node[T])
• func NodeIDs[T any](nodes []Node[T]) []int64
• type Edge
• type Graph
  • func New[T any]() *Graph[T]
  • func (g *Graph[T]) AddEdge(from, to int64) error
  • func (g *Graph[T]) AddNode(id int64, v T) error
  • func (g *Graph[T]) Adj(id int64) []*Node[T]
  • func (g *Graph[T]) BreadthFirstSearch(id int64, visitFunc VisitFunc[T]) error
  • func (g *Graph[T]) DepthFirstSearch(start int64, visitFunc VisitFunc[T]) error
  • func (g *Graph[T]) Node(id int64) (*Node[T], error)
  • func (g *Graph[T]) NodeList(id ...int64) ([]*Node[T], error)
• type Node
• type VisitFunc

Variables

var (
	ErrorDuplicateID = errors.New("node with ID already exists")
	ErrorNotFound    = errors.New("node with ID not found")
	ErrorNoVisitFunc = errors.New("no visitfunc provided")

	ErrorBreak = errors.New("break will stop the depth first search without an error")
)

Functions

func EdgesToMap

func EdgesToMap[T any](e map[int64][]Edge[T]) map[int64][]int64

func EnsureGraphEdges

func EnsureGraphEdges[T any](t *testing.T, expected map[int64][]int64, graphEdges map[int64][]Edge[T])

EnsureGraphEdges is a test helper function that is used inside the dag tests and outside in other implementations to easily ensure that we are using the dag properly.

func EnsureGraphNodes

func EnsureGraphNodes[T any](t *testing.T, expected []int64, nodes []Node[T])

EnsureGraphNodes is a test helper function that is used inside the dag tests and outside in other implementations to easily ensure that we are using the dag properly.

func NodeIDs

func NodeIDs[T any](nodes []Node[T]) []int64

Types

type Edge

type Edge[T any] struct {
	From *Node[T]
	To   *Node[T]
}

Edge is a connection from one node to another. Because this is a Directed graph, the edge has a direction. A connection from 'node A' to 'node B' is not the same as a connection from 'node B' to 'node A'.

type Graph

type Graph[T any] struct {
	Nodes []Node[T]
	Edges map[int64][]Edge[T]
	// contains filtered or unexported fields
}

Graph is a data structure that stores a list of Nodes (data) and Edges that connect nodes. Because it is a Directed graph, the edges connect from a node to another node, and the connection is not equal if reversed. Because it is an Acyclic graph, the nodes can not be connected in a loop or a cycle. If the nodes/edges look like (0 -> 1 -> 2 -> 0), then that is a cycle and is not allowed.

func New

func New[T any]() *Graph[T]

New creates a new Graph with nodes that contain data with type T.

func (*Graph[T]) AddEdge

func (g *Graph[T]) AddEdge(from, to int64) error

AddEdge adds a new node from node with the ID 'from' to the node with the ID 'to'.

func (*Graph[T]) AddNode

func (g *Graph[T]) AddNode(id int64, v T) error

AddNode adds a new node to the graph with the given ID and data (v).

func (*Graph[T]) Adj

func (g *Graph[T]) Adj(id int64) []*Node[T]

Adj returns nodes with edges that start at the provided node (n) (Where 'From' is this node). This function does not return nodes with edges that end at the provided node (where 'To' is this node).

func (*Graph[T]) BreadthFirstSearch

func (g *Graph[T]) BreadthFirstSearch(id int64, visitFunc VisitFunc[T]) error

func (*Graph[T]) DepthFirstSearch

func (g *Graph[T]) DepthFirstSearch(start int64, visitFunc VisitFunc[T]) error

DepthFirstSearch performs a depth-first search and calls the provided visitFunc callback for every node. 'visitFunc' is not called more than once per node. If 'visitFunc' returns an error, then so will this function. If 'visitFunc' returns ErrorBreak, then this function will return nil and will stop visiting nodes.

func (*Graph[T]) Node

func (g *Graph[T]) Node(id int64) (*Node[T], error)

Node returns the node with the given ID. If no node is found, ErrorNotFound is returned.

func (*Graph[T]) NodeList

func (g *Graph[T]) NodeList(id ...int64) ([]*Node[T], error)

Nodes returns the nodes with the given IDs. If one of the nodes is not found, ErrorNotFound is returned.

type Node

type Node[T any] struct {
	ID    int64
	Value T
}

Node is a graph node that has an ID and data. Nodes are connected by Edges.

type VisitFunc

type VisitFunc[T any] func(n *Node[T]) error