dag

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.

Root & Leaf Discovery

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

Topological Sort

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

Ancestor & Descendant Discovery

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

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