{"record":{"id":"39a8f74afedd590f","repo":"TheAlgorithms/C-Sharp","slug":"graph-contains-a-cycle-topological-sort-is-only-possible-for","errorCode":null,"errorMessage":"Graph contains a cycle. Topological sort is only possible for Directed Acyclic Graphs (DAGs).","messagePattern":"Graph contains a cycle\\. Topological sort is only possible for Directed Acyclic Graphs \\(DAGs\\)\\.","errorType":"exception","errorClass":"InvalidOperationException","httpStatus":null,"severity":"error","filePath":"Algorithms/Graph/TopologicalSort.cs","lineNumber":291,"sourceCode":"                    queue.Enqueue(neighbor);\n                }\n            }\n        }\n    }\n\n    /// <summary>\n    ///     Validates that all vertices were processed, ensuring no cycles exist.\n    /// </summary>\n    /// <param name=\"graph\">The graph being sorted.</param>\n    /// <param name=\"result\">The list of processed vertices.</param>\n    /// <exception cref=\"InvalidOperationException\">\n    ///     Thrown when not all vertices were processed (cycle detected).\n    /// </exception>\n    private void ValidateNoCycles(IDirectedWeightedGraph<T> graph, List<Vertex<T>> result)\n    {\n        if (result.Count != graph.Count)\n        {\n            throw new InvalidOperationException(\n                \"Graph contains a cycle. Topological sort is only possible for Directed Acyclic Graphs (DAGs).\");\n        }\n    }\n\n    /// <summary>\n    ///     Helper method for DFS-based topological sort.\n    ///     Recursively visits vertices and adds them to the stack in post-order.\n    ///\n    ///     POST-ORDER TRAVERSAL:\n    ///     - Visit all descendants first.\n    ///     - Then process the current vertex.\n    ///     - This ensures dependencies are processed before dependents.\n    ///\n    ///     CYCLE DETECTION:\n    ///     - We maintain a recursion stack to track the current DFS path.\n    ///     - If we encounter a vertex that's already in the recursion stack,\n    ///       we've found a back edge, indicating a cycle.\n    /// </summary>","sourceCodeStart":273,"sourceCodeEnd":309,"githubUrl":"https://github.com/TheAlgorithms/C-Sharp/blob/96e2905cab7bc6b33ac0a34ee5bb82ddccbcbb6c/Algorithms/Graph/TopologicalSort.cs#L273-L309","documentation":"After Kahn's algorithm finishes, ValidateNoCycles checks whether all vertices were dequeued. If result.Count != graph.Count, some vertices never had in-degree 0, proving the graph contains a cycle; a topological order then cannot exist, so an InvalidOperationException is thrown.","triggerScenarios":"Calling SortKahn on an IDirectedWeightedGraph<T> that contains at least one directed cycle (e.g., A -> B -> A). The exception is raised after the queue drains with unprocessed vertices remaining.","commonSituations":"Build-order/task-scheduling graphs where a job depends on itself transitively; course prerequisite data with circular prerequisites; graphs mutated with cycles after validation; misdirected edges loaded from config files.","solutions":["Run cycle detection (or this same sort) on the graph before relying on a topological order","Locate and break the cycle: audit dependency edges for the strongly connected components with size > 1","Fix the input data so dependencies form a DAG (remove or reverse the offending edge)","Catch InvalidOperationException and fall back to reporting the dependency cycle to the user"],"exampleFix":"// before\ngraph.AddEdge(a, b);\ngraph.AddEdge(b, a); // cycle\nvar order = sorter.SortKahn(graph); // throws\n// after\ngraph.AddEdge(a, b); // keep DAG\nvar order = sorter.SortKahn(graph);","handlingStrategy":"try-catch","validationCode":"// Kahn's algorithm itself is the validator; pre-check with an SCC pass:\nbool isDag = TarjanSCC(graph).All(scc => scc.Count == 1);","typeGuard":null,"tryCatchPattern":"try { var order = sorter.SortKahn(graph); }\ncatch (InvalidOperationException) { reportDependencyCycle(graph); }","preventionTips":["Validate dependency data for cycles at load time","Never add an edge that closes a cycle (check reachability before AddEdge)","Design config schemas to reject circular includes"],"tags":["csharp","graph","topological-sort","cycle"],"backgroundTag":"unsupported-operation","analyzedSha":"96e2905cab7bc6b33ac0a34ee5bb82ddccbcbb6c","analyzedAt":"2026-09-13T17:04:01.438Z","contentChangedAt":"2026-09-13T17:04:01.438Z","schemaVersion":2},"datasetVersion":"2026-09-16T04:17:20.429Z"}