dag

Documentation

Overview

Package dag provides the Directed-Acyclic-Graph (DAG) primitives required by Terramate. The nodes can be added by providing both the descendants and ancestors of each node but only the descendant -> ancestors relationship is kept.

Index

• Constants
• type DAG
  • func New[V any]() *DAG[V]
  • func Transform[D, S any](from *DAG[S], f func(id ID, v S) (D, error)) (*DAG[D], error)
  • func (d *DAG[V]) AddNode(id ID, value V, descendants, ancestors []ID) error
  • func (d *DAG[V]) AncestorsOf(id ID) []ID
  • func (d *DAG[V]) HasCycle(id ID) bool
  • func (d *DAG[V]) IDs() []ID
  • func (d *DAG[V]) Node(id ID) (V, error)
  • func (d *DAG[V]) Order() []ID
  • func (d *DAG[V]) Reduce(predicate func(id ID) bool)
  • func (d *DAG[V]) Validate() (reason string, err error)
• type ID
• type Visited

Constants

const (
	ErrDuplicateNode errors.Kind = "duplicate node"
	ErrNodeNotFound  errors.Kind = "node not found"
	ErrCycleDetected errors.Kind = "cycle detected"
)

Errors returned by operations on the DAG.

Types

type DAG

type DAG[V any] struct {
	// contains filtered or unexported fields
}

DAG is a Directed-Acyclic Graph

func New

func New[V any]() *DAG[V]

New creates a new empty Directed-Acyclic-Graph.

func Transform

func Transform[D, S any](from *DAG[S], f func(id ID, v S) (D, error)) (*DAG[D], error)

Transform transforms a DAG of D's to a DAG of S's by applying the given function to each node. Afterwards, source DAG must be discarded.

func (*DAG[V]) AddNode

func (d *DAG[V]) AddNode(id ID, value V, descendants, ancestors []ID) error

AddNode adds a new node to the dag. The lists of descendants and ancestors defines its edge. The value is anything related to the node that needs to be retrieved later when processing the DAG.

func (*DAG[V]) AncestorsOf

func (d *DAG[V]) AncestorsOf(id ID) []ID

AncestorsOf returns the list of ancestor node ids of the given id.

func (*DAG[V]) HasCycle

func (d *DAG[V]) HasCycle(id ID) bool

HasCycle returns true if the DAG has a cycle.

func (*DAG[V]) IDs

func (d *DAG[V]) IDs() []ID

IDs returns the sorted list of node ids.

func (*DAG[V]) Node

func (d *DAG[V]) Node(id ID) (V, error)

Node returns the node with the given id.

func (*DAG[V]) Order

func (d *DAG[V]) Order() []ID

Order returns the topological order of the DAG. The node ids are lexicographic sorted whenever possible to give a consistent output.

func (*DAG[V]) Reduce

func (d *DAG[V]) Reduce(predicate func(id ID) bool)

Reduce removes nodes that match the given predicate. When a node is removed, all edges to it are replaced by edges to its children, so the order within the graph is preserved.

func (*DAG[V]) Validate

func (d *DAG[V]) Validate() (reason string, err error)

Validate the DAG looking for cycles.

type ID

type ID string

ID of nodes

type Visited

type Visited map[ID]struct{}

Visited in a map of visited dag nodes by id. Note: it's not concurrent-safe.