algo-topological-sort

Answer

The implementation provides:

1. Generic Graph[T comparable] — a directed graph using Go 1.18+ generics, with AddNode, AddEdge, and Nodes.

2. TopologicalSort[T] — Kahn's BFS algorithm:

in-degree = map of all nodes to 0
for each edge src -> dst:
    increment in-degree[dst]
queue = all nodes with in-degree 0
while queue not empty:
    cur = pop queue
    append cur to sorted
    for each neighbor dst of cur:
        decrement in-degree[dst]
        if in-degree[dst] == 0:
            push dst to queue
if len(sorted) != total_nodes:
    cycle detected → return nil, false

3. PkgResolver — wraps the generic graph, mapping package dependencies as dep → pkg edges (dependency must be built before the dependent). A findCycle() helper uses DFS back-edge detection to produce a human-readable cycle path like "A → B → C → A".

Key code (topo.go):

package topo

import (
    "fmt"
    "strings"
)

// Graph supports any comparable node type.
type Graph[T comparable] struct {
    edges map[T][]T
}

// AddEdge creates a directed edge from src to dst.
func (g *Graph[T]) AddEdge(src, dst T) {
    g.edges[src] = append(g.edges[src], dst)
    if _, ok := g.edges[dst]; !ok {
        g.edges[dst] = nil
    }
}

// TopologicalSort returns a valid linear ordering, or false if a cycle exists.
func TopologicalSort[T comparable](g *Graph[T]) ([]T, bool) {
    inDegree := make(map[T]int, len(g.edges))
    for _, neighbors := range g.edges {
        for _, dst := range neighbors {
            inDegree[dst]++
        }
    }
    for n := range g.edges {
        if _, ok := inDegree[n]; !ok {
            inDegree[n] = 0
        }
    }
    queue := make([]T, 0)
    for n, deg := range inDegree {
        if deg == 0 {
            queue = append(queue, n)
        }
    }
    sorted := make([]T, 0, len(g.edges))
    for len(queue) > 0 {
        cur := queue[0]
        queue = queue[1:]
        sorted = append(sorted, cur)
        for _, dst := range g.edges[cur] {
            inDegree[dst]--
            if inDegree[dst] == 0 {
                queue = append(queue, dst)
            }
        }
    }
    if len(sorted) != len(g.edges) {
        return nil, false
    }
    return sorted, true
}

// PkgResolver uses topological sort for build dependency resolution.
type PkgResolver struct {
    graph *Graph[string]
}

func NewPkgResolver() *PkgResolver {
    return &PkgResolver{graph: NewGraph[string]()}
}

// Declare(pkg, deps...) records that pkg depends on each dep.
func (r *PkgResolver) Declare(pkg string, dependsOn ...string) {
    r.graph.AddNode(pkg)
    for _, dep := range dependsOn {
        r.graph.AddEdge(dep, pkg)
    }
}

// Resolve returns build order, or an error describing any detected cycle.
func (r *PkgResolver) Resolve() ([]string, error) {
    order, ok := TopologicalSort(r.graph)
    if !ok {
        cycle := r.findCycle()
        return nil, fmt.Errorf("dependency cycle detected: %s", strings.Join(cycle, " -> "))
    }
    return order, nil
}