dag

Documentation

Index

• Variables
• type DAG
  • func New[K comparable, V any](hash func(V) K) DAG[K, V]
  • func (d DAG[K, V]) Add(val V, parentVals ...V) bool
  • func (d DAG[K, V]) Children(val V) []V
  • func (d DAG[K, V]) Descendents(val V) []V
  • func (d DAG[K, V]) Parents(val V, present bool) []V
  • func (d DAG[K, V]) Remove(val V)
  • func (d DAG[K, V]) Roots() []V
  • func (d DAG[K, V]) Visit(val V, fn VisitFunc[K, V]) error
• type VisitFunc

Variables

var ErrSkip = errors.New("dag: skip")

ErrSkip should be returned by a VisitFunc to skip the children of the visited node.

var ErrStop = errors.New("dag: stop")

ErrStop can be returned by a VisitFunc to signal a stopped visit. It does not carry special meaning in this package since any error other than ErrSkip stops a visit.

Types

type DAG

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

DAG implements a directed acyclic graph. Its implementation tracks unresolved references and resolves them if possible when new vertices are added. The implementation is not thread safe and panics if used incorrectly. It's based on the implementation in runtime/pkg/dag and should replace it when that package is no longer used.

func New

func New[K comparable, V any](hash func(V) K) DAG[K, V]

New initializes a DAG.

func (DAG[K, V]) Add

func (d DAG[K, V]) Add(val V, parentVals ...V) bool

Add adds a vertex to the DAG. It returns false if adding the vertex would create a cycle. It panics if the vertex is already present.

func (DAG[K, V]) Children

func (d DAG[K, V]) Children(val V) []V

Children returns the children of the given value.

func (DAG[K, V]) Descendents

func (d DAG[K, V]) Descendents(val V) []V

Descendents returns the recursive children of the given value.

func (DAG[K, V]) Parents

func (d DAG[K, V]) Parents(val V, present bool) []V

Parents returns the parents of the given value. If present is true, only parents that are present are returned.

func (DAG[K, V]) Remove

func (d DAG[K, V]) Remove(val V)

Remove removes a vertex from the DAG. It panics if the vertex is not present.

func (DAG[K, V]) Roots

func (d DAG[K, V]) Roots() []V

Roots return the vertices that have no parents. Vertices with non-present references are not returned.

func (DAG[K, V]) Visit

func (d DAG[K, V]) Visit(val V, fn VisitFunc[K, V]) error

Visit recursively visits the children of the given value. If the visitor function returns true, the visit is stopped.

type VisitFunc

type VisitFunc[K comparable, V any] func(K, V) error

VisitFunc is invoked for each node when visiting the DAG. If it returns ErrSkip, the children of the node are not visited. If it returns another error, the visitor is stopped.