{"record":{"id":"145957924da827dd","repo":"argoproj/argo-workflows","slug":"graph-with-cycle","errorCode":null,"errorMessage":"graph with cycle","messagePattern":"graph with cycle","errorType":"exception","errorClass":null,"httpStatus":null,"severity":"error","filePath":"util/sorting/topological_sorting.go","lineNumber":44,"sourceCode":"\t\t\t\treturn nil, fmt.Errorf(\"invalid dependency %s\", dependency)\n\t\t\t}\n\t\t\tnextNodeMap[dependency] = append(nextNodeMap[dependency], node.NodeName)\n\t\t}\n\t}\n\n\tqueue := make([]*TopologicalSortingNode, len(graph))\n\thead, tail := 0, 0\n\tfor nodeName, priorNodeCount := range priorNodeCountMap {\n\t\tif priorNodeCount == 0 {\n\t\t\tqueue[tail] = nodeNameMap[nodeName]\n\t\t\ttail++\n\t\t}\n\t}\n\n\tfor head < len(queue) {\n\t\tcurr := queue[head]\n\t\tif curr == nil {\n\t\t\treturn nil, fmt.Errorf(\"graph with cycle\")\n\t\t}\n\t\tfor _, next := range nextNodeMap[curr.NodeName] {\n\t\t\tif priorNodeCountMap[next] > 0 {\n\t\t\t\tif priorNodeCountMap[next] == 1 {\n\t\t\t\t\tqueue[tail] = nodeNameMap[next]\n\t\t\t\t\ttail++\n\t\t\t\t}\n\t\t\t\tpriorNodeCountMap[next]--\n\t\t\t}\n\t\t}\n\t\thead++\n\t}\n\n\treturn queue, nil\n}\n","sourceCodeStart":26,"sourceCodeEnd":60,"githubUrl":"https://github.com/argoproj/argo-workflows/blob/35bff19146f5a6ada77468c431f2624bd577e373/util/sorting/topological_sorting.go#L26-L60","documentation":"TopologicalSorting detects cycles with a Kahn-style queue: after seeding, the queue is pre-allocated to len(graph), and any nil slot means fewer nodes than expected reached zero indegree — i.e. some nodes form a cycle and can never be scheduled. The function returns this fixed error to report an unsatisfiable dependency graph.","triggerScenarios":"Passing a graph whose Dependencies form a cycle, e.g. A depends on B and B depends on A (or a self-dependency A→A), so no node in the cycle ever reaches indegree 0 and the queue fills with nils.","commonSituations":"DAG templates with circular depends/after references between tasks; synchronization edges added in both directions by accident; self-referencing node built from a name that includes itself; test fixtures GraphWithCycle/GraphWithCycle2 exercising this path.","solutions":["Break the cycle: audit Dependencies and remove or invert one edge (e.g. A→B and B→A means dropping one direction).","Check for self-dependencies — a node listing its own NodeName in Dependencies.","Run a cycle-detection pass (DFS with a visiting set) on the graph before calling TopologicalSorting to produce a better message naming the offending nodes.","If edges are derived from template definitions, fix the workflow spec's depends clauses; the sort input mirrors them."],"exampleFix":"// before\nnodes := []*sorting.TopologicalSortingNode{\n    {NodeName: \"A\", Dependencies: []string{\"B\"}},\n    {NodeName: \"B\", Dependencies: []string{\"A\"}}, // cycle\n}\n// after\nnodes := []*sorting.TopologicalSortingNode{\n    {NodeName: \"A\"},\n    {NodeName: \"B\", Dependencies: []string{\"A\"}},\n}","handlingStrategy":"validation","validationCode":"func hasCycle(graph []*sorting.TopologicalSortingNode) bool {\n    state := map[string]int{} // 0 unvisited, 1 visiting, 2 done\n    var visit func(string) bool\n    visit = func(n string) bool {\n        switch state[n] {\n        case 1: return true\n        case 2: return false\n        }\n        state[n] = 1\n        for _, node := range graph {\n            if node.NodeName != n { continue }\n            for _, d := range node.Dependencies {\n                if visit(d) { return true }\n            }\n        }\n        state[n] = 2\n        return false\n    }\n    for _, n := range graph { if visit(n.NodeName) { return true } }\n    return false\n}","typeGuard":null,"tryCatchPattern":"sorted, err := sorting.TopologicalSorting(graph)\nif err != nil {\n    if err.Error() == \"graph with cycle\" {\n        cycle := findCycleNodes(graph) // report specifics to the user\n        return fmt.Errorf(\"workflow dependency cycle involving: %v\", cycle)\n    }\n    return err\n}","preventionTips":["Validate the workflow DAG spec (depends edges) for cycles before building the sort graph.","Never add a node's own name to its Dependencies; guard self-references where edges are generated.","Reuse the controller/validator's cycle detection on template specs so bad specs fail at submission time."],"tags":["go","dag","topological-sort","cycle-detection"],"backgroundTag":"dependency-cycle","analyzedSha":"35bff19146f5a6ada77468c431f2624bd577e373","analyzedAt":"2026-09-03T19:34:35.908Z","contentChangedAt":"2026-09-03T19:34:35.908Z","schemaVersion":2},"datasetVersion":"2026-09-08T10:18:20.063Z"}