dag

README

dag

A generic DAG (Directed Acyclic Graph) algorithms package. Provides generic functions that work with any data structure.

Installation

import "github.com/linyows/probe/dag"

Algorithms

All algorithms have O(V + E) time complexity where V is the number of vertices and E is the number of edges.

Cycle Detection

Detects cycles in a graph using Depth-First Search (DFS) with a recursion stack.

Function	Description	Complexity
DetectCycleFn	Detect cycle and return the cycle path	O(V + E)
HasCycleFn	Check if cycle exists (faster when path not needed)	O(V + E)
DetectCycle	Interface-based cycle detection	O(V + E)
HasCycle	Interface-based cycle check	O(V + E)

Root & Leaf Discovery

Finds entry points (roots) and exit points (leaves) in a graph.

Function	Description	Complexity
FindRootsFn	Find root nodes (in-degree = 0)	O(V + E)
FindLeavesFn	Find leaf nodes (out-degree = 0)	O(V + E)
FindRoots	Interface-based root discovery	O(V + E)
FindLeaves	Interface-based leaf discovery	O(V + E)

Topological Sort

Sorts nodes so that dependencies come before dependents using Kahn's algorithm (BFS-based).

Function	Description	Complexity
TopologicalSortFn	Sort nodes by dependency order	O(V + E)
TopologicalSort	Interface-based topological sort	O(V + E)

Ancestor & Descendant Discovery

Traverses the graph to find all related nodes using Breadth-First Search (BFS).

Function	Description	Complexity
ComputeDescendantsFn	Get all descendants of a node	O(V + E)
ComputeAncestorsFn	Get all ancestors of a node	O(V + E)

Usage

There are two ways to use this package: function-based and interface-based.

Function-based (Fn suffix)

Pass a list of IDs and a dependency getter function. Works with any data structure.

// Dependencies: A → B → C
getDeps := func(id string) []string {
    switch id {
    case "A":
        return []string{"B"}
    case "B":
        return []string{"C"}
    default:
        return nil
    }
}
allIDs := []string{"A", "B", "C"}

// Cycle detection
if dag.HasCycleFn(allIDs, getDeps) {
    cycle := dag.DetectCycleFn(allIDs, getDeps)
    fmt.Println("Cycle found:", cycle)
}

// Topological sort
sorted, err := dag.TopologicalSortFn(allIDs, getDeps)
if err != nil {
    log.Fatal(err)
}
fmt.Println("Sorted:", sorted) // [C, B, A]

// Root & leaf discovery
roots := dag.FindRootsFn(allIDs, getDeps)  // [A]
leaves := dag.FindLeavesFn(allIDs, getDeps) // [C]

Interface-based

Implement the CycleDetectable interface for cleaner integration with your types.

type CycleDetectable[ID comparable] interface {
    ID() ID
    Dependencies() []ID
}

type Task struct {
    name string
    deps []string
}

func (t Task) ID() string             { return t.name }
func (t Task) Dependencies() []string { return t.deps }

tasks := []Task{
    {"build", []string{"compile"}},
    {"compile", []string{"parse"}},
    {"parse", nil},
}

sorted, err := dag.TopologicalSort(tasks)
// sorted: ["parse", "compile", "build"]

Use Cases

This package is useful for any system that needs to manage dependencies.

• Build Systems: Resolve task dependencies and determine execution order
• Package Managers: Determine installation order of dependencies
• Schedulers: Determine job execution order
• Static Analysis: Detect circular references
• Impact Analysis: Identify affected scope of changes

Documentation

Overview

Package dag provides generic DAG algorithms that work with any data structure.

Index

• Variables
• func ComputeAncestorsFn[ID comparable](allIDs []ID, startID ID, getDeps func(ID) []ID) []ID
• func ComputeDescendantsFn[ID comparable](allIDs []ID, startID ID, getDeps func(ID) []ID) []ID
• func DetectCycle[ID comparable, T CycleDetectable[ID]](items []T) []ID
• func DetectCycleFn[ID comparable](allIDs []ID, getDeps func(ID) []ID) []ID
• func FindLeaves[ID comparable, T CycleDetectable[ID]](items []T) []ID
• func FindLeavesFn[ID comparable](allIDs []ID, getDeps func(ID) []ID) []ID
• func FindRoots[ID comparable, T CycleDetectable[ID]](items []T) []ID
• func FindRootsFn[ID comparable](allIDs []ID, getDeps func(ID) []ID) []ID
• func HasCycle[ID comparable, T CycleDetectable[ID]](items []T) bool
• func HasCycleFn[ID comparable](allIDs []ID, getDeps func(ID) []ID) bool
• func TopologicalSort[ID comparable, T CycleDetectable[ID]](items []T) ([]ID, error)
• func TopologicalSortFn[ID comparable](allIDs []ID, getDeps func(ID) []ID) ([]ID, error)
• type CycleDetectable

Variables

var ErrCycleDetected = errors.New("cycle detected in graph")

ErrCycleDetected is returned when a cycle is detected during topological sort.

Functions

func ComputeAncestorsFn

func ComputeAncestorsFn[ID comparable](allIDs []ID, startID ID, getDeps func(ID) []ID) []ID

ComputeAncestorsFn computes all ancestors of a node.

func ComputeDescendantsFn

func ComputeDescendantsFn[ID comparable](allIDs []ID, startID ID, getDeps func(ID) []ID) []ID

ComputeDescendantsFn computes all descendants of a node. Useful for impact analysis.

func DetectCycle

func DetectCycle[ID comparable, T CycleDetectable[ID]](items []T) []ID

DetectCycle detects a cycle in a collection of CycleDetectable items.

func DetectCycleFn

func DetectCycleFn[ID comparable](allIDs []ID, getDeps func(ID) []ID) []ID

DetectCycleFn detects a cycle in a graph using a higher-order function. Returns the cycle path if found, nil otherwise.

Parameters:

• allIDs: All node identifiers in the graph
• getDeps: Function that returns dependencies (children) for a given node

Example:

getDeps := func(id string) []string {
    switch id {
    case "A": return []string{"B", "C"}
    case "B": return []string{"C"}
    default: return nil
    }
}
cycle := DetectCycleFn([]string{"A", "B", "C"}, getDeps)

func FindLeaves

func FindLeaves[ID comparable, T CycleDetectable[ID]](items []T) []ID

FindLeaves finds all leaf nodes from a collection of items.

func FindLeavesFn

func FindLeavesFn[ID comparable](allIDs []ID, getDeps func(ID) []ID) []ID

FindLeavesFn finds all leaf nodes (nodes with no outgoing edges).

Parameters:

• allIDs: All node identifiers in the graph
• getDeps: Function that returns dependencies (children) for a given node

Returns: Slice of leaf node IDs

func FindRoots

func FindRoots[ID comparable, T CycleDetectable[ID]](items []T) []ID

FindRoots finds all root nodes from a collection of items.

func FindRootsFn

func FindRootsFn[ID comparable](allIDs []ID, getDeps func(ID) []ID) []ID

FindRootsFn finds all root nodes (nodes with no incoming edges).

Parameters:

• allIDs: All node identifiers in the graph
• getDeps: Function that returns dependencies (children) for a given node

Returns: Slice of root node IDs

func HasCycle

func HasCycle[ID comparable, T CycleDetectable[ID]](items []T) bool

HasCycle checks if a cycle exists in a collection of CycleDetectable items.

func HasCycleFn

func HasCycleFn[ID comparable](allIDs []ID, getDeps func(ID) []ID) bool

HasCycleFn checks if a cycle exists in the graph. This is faster than DetectCycleFn when you don't need the cycle path.

func TopologicalSort

func TopologicalSort[ID comparable, T CycleDetectable[ID]](items []T) ([]ID, error)

TopologicalSort performs a topological sort on a collection of CycleDetectable items.

func TopologicalSortFn

func TopologicalSortFn[ID comparable](allIDs []ID, getDeps func(ID) []ID) ([]ID, error)

TopologicalSortFn performs a topological sort on a graph. Returns the nodes in topological order (dependencies before dependents).

Parameters:

• allIDs: All node identifiers in the graph
• getDeps: Function that returns dependencies (children) for a given node

Returns: Sorted slice of node IDs, or error if cycle detected

Types

type CycleDetectable

type CycleDetectable[ID comparable] interface {
	ID() ID
	Dependencies() []ID
}

CycleDetectable is an interface for types that can be checked for cycles.