{"record":{"id":"c2326774d5b7a9eb","repo":"TheAlgorithms/C-Sharp","slug":"graph-contains-a-cycle-involving-vertex-vertex-topological","errorCode":null,"errorMessage":"Graph contains a cycle involving vertex: {vertex}. Topological sort is only possible for Directed Acyclic Graphs (DAGs).","messagePattern":"Graph contains a cycle involving vertex: (.+?)\\. Topological sort is only possible for Directed Acyclic Graphs \\(DAGs\\)\\.","errorType":"exception","errorClass":"InvalidOperationException","httpStatus":null,"severity":"error","filePath":"Algorithms/Graph/TopologicalSort.cs","lineNumber":330,"sourceCode":"    /// <param name=\"visited\">Set of all visited vertices.</param>\n    /// <param name=\"recursionStack\">Set of vertices in the current DFS path.</param>\n    /// <param name=\"stack\">Stack to store vertices in reverse topological order.</param>\n    /// <exception cref=\"InvalidOperationException\">\n    ///     Thrown when a cycle is detected.\n    /// </exception>\n    private void DfsTopologicalSort(\n        IDirectedWeightedGraph<T> graph,\n        Vertex<T> vertex,\n        HashSet<Vertex<T>> visited,\n        HashSet<Vertex<T>> recursionStack,\n        Stack<Vertex<T>> stack)\n    {\n        // CYCLE DETECTION:\n        // If the vertex is in the recursion stack, we've encountered it again\n        // in the current DFS path, which means there's a cycle.\n        if (recursionStack.Contains(vertex))\n        {\n            throw new InvalidOperationException(\n                $\"Graph contains a cycle involving vertex: {vertex}. \" +\n                \"Topological sort is only possible for Directed Acyclic Graphs (DAGs).\");\n        }\n\n        // If already visited, no need to process again.\n        if (visited.Contains(vertex))\n        {\n            return;\n        }\n\n        // Mark vertex as visited and add to recursion stack.\n        visited.Add(vertex);\n        recursionStack.Add(vertex);\n\n        // Recursively visit all neighbors (descendants).\n        // This ensures all dependencies are processed first.\n        foreach (var neighbor in graph.GetNeighbors(vertex))\n        {","sourceCodeStart":312,"sourceCodeEnd":348,"githubUrl":"https://github.com/TheAlgorithms/C-Sharp/blob/96e2905cab7bc6b33ac0a34ee5bb82ddccbcbb6c/Algorithms/Graph/TopologicalSort.cs#L312-L348","documentation":"The DFS-based topological sort maintains a recursion stack of the current path. If a vertex is encountered that is already in the recursion stack, the path revisits itself — a cycle — and the sort cannot proceed, so DfsTopologicalSort throws an InvalidOperationException naming the vertex.","triggerScenarios":"Calling Sort (DFS variant) on a directed graph with a cycle; the recursionStack.Contains(vertex) check fires for the first vertex found back on the current DFS path (self-loop or mutual edge included).","commonSituations":"Circular dependencies in module build graphs; self-referencing nodes (v -> v) from bad data; graphs loaded from external sources without prior cycle validation.","solutions":["Validate the graph is a DAG before sorting (e.g., run Kahn's sort or an SCC check)","Find and remove the cycle involving the reported vertex (audit its outgoing/incoming edges)","Fix upstream data that introduced the circular dependency or self-loop","Catch InvalidOperationException and surface the named vertex to help users locate the cycle"],"exampleFix":"// before\ngraph.AddEdge(v, v); // self-loop\nvar order = sorter.Sort(graph); // throws\n// after\ngraph.RemoveEdge(v, v);\nvar order = sorter.Sort(graph);","handlingStrategy":"try-catch","validationCode":"bool hasSelfLoop = graph.Vertices.Any(v => graph.ContainsEdge(v, v));","typeGuard":null,"tryCatchPattern":"try { var order = sorter.Sort(graph); }\ncatch (InvalidOperationException ex) { log.Error($\"Cycle at {ex.Message}\"); }","preventionTips":["Reject self-loops and mutual edges in directed-acyclic contexts","Run an SCC/cycle check before DFS sorting","Surface the offending vertex (included in the message) in error reports"],"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"}