dag

package

v0.0.13 Latest Latest Go to latest Published: Jun 11, 2025 License: MIT Imports: 4 Imported by: 0

Details

Package dag implements a generic directed acyclic graph with cycle detection, topological sorting, and ancestor chain computation.

This section is empty.

View Source

var ErrDag = errors.New("dag error")

ErrDag is returned when a DAG operation fails.

func Condense[K comparable](chain []K) []K

Condense returns a copy of `chain` with only *adjacent* duplicates removed.

["base","base","custom"]        → ["base","custom"]
["base","custom","base"]        → (unchanged)
["a","a","b","b","b","c","c"]   → ["a","b","c"]

The input slice is never modified.

type CycleError[K comparable] struct {
	// The node where the cycle was detected
	Node K
	// The path that forms the cycle
	Path []K
}

CycleError represents a cycle in the graph with the path that forms the cycle.

func (e *CycleError[K]) Error() string

Error implements the error interface for CycleError.

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

DAG is an immutable, validated representation of a dependency graph. The type parameter K must be comparable so it can act as a map key.

func Build[K comparable](
	nodes []K,
	parentsFn func(K) []K,
) (*DAG[K], error)

Build constructs the graph and performs **two** validations:

Every parent returned by parentsFn(node) must itself be present in the `nodes` slice.
The graph must be acyclic.

On success a *DAG is returned; otherwise an error explains the problem.

func (g *DAG[K]) Chain(node K) ([]K, error)

Chain returns the linearised chain `[grandParent … parent, node]`.

The slice is newly allocated on each call; modifying it will not affect the DAG or future calls.

func (g *DAG[K]) Topo() []K

Topo returns every node exactly once in "parents first" order.