dag

Documentation

Overview

Package dag is used to verify and map out directed acyclic graph implementations. This helps us verify that user's task dependencies actually work as a DAG and avoid entering in any cycles.

https://bertptrs.nl/2022/06/23/deadlock-free-mutexes-and-directed-acyclic-graphs.html

Index

• Variables
• type DAG
  • func New() DAG
  • func (dag DAG) AddEdge(from, to string) error
  • func (dag DAG) AddNode(id string) error
  • func (dag DAG) Edges(id string) ([]Node, error)
  • func (dag DAG) Exists(id string) bool
  • func (dag DAG) String() string
• type Node

Variables

var (
	// ErrEntityNotFound is returned when a certain entity could not be located.
	ErrEntityNotFound = errors.New("dag: entity not found")

	// ErrEntityExists is returned when a certain entity was located but not meant to be.
	ErrEntityExists = errors.New("dag: entity already exists")

	// ErrPreconditionFailure is returned when there was a validation error with the parameters passed.
	ErrPreconditionFailure = errors.New("dag: parameters did not pass validation")

	// ErrEdgeCreatesCycle is returned when the introduction of an edge would create a cycle.
	ErrEdgeCreatesCycle = errors.New("dag: edge would create a cycle")
)

Types

type DAG

type DAG map[string]Node

func New

func New() DAG

func (DAG) AddEdge

func (dag DAG) AddEdge(from, to string) error

func (DAG) AddNode

func (dag DAG) AddNode(id string) error

func (DAG) Edges

func (dag DAG) Edges(id string) ([]Node, error)

func (DAG) Exists

func (dag DAG) Exists(id string) bool

func (DAG) String

func (dag DAG) String() string

type Node

type Node struct {
	ID    string
	Edges []Node
}