dag

package
v0.47.6 Latest Latest
Warning

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

Go to latest
Published: Aug 6, 2024 License: Apache-2.0 Imports: 2 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

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

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

View Source
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.

Functions

This section is empty.

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 added in v0.36.0

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 added in v0.36.0

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

Children returns the children of the given value.

func (DAG[K, V]) Descendents added in v0.36.0

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

Descendents returns the recursive children of the given value.

func (DAG[K, V]) Parents added in v0.36.0

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 added in v0.36.0

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 added in v0.36.0

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 added in v0.36.0

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 added in v0.36.0

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.

Jump to

Keyboard shortcuts

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