{"record":{"id":"ebc456f259e4e5f6","repo":"TheAlgorithms/Java","slug":"graph-contains-a-cycle-topological-sort-not-possi","errorCode":null,"errorMessage":"Graph contains a cycle, topological sort not possible","messagePattern":"Graph contains a cycle, topological sort not possible","errorType":"exception","errorClass":"IllegalStateException","httpStatus":null,"severity":"error","filePath":"src/main/java/com/thealgorithms/datastructures/graphs/KahnsAlgorithm.java","lineNumber":135,"sourceCode":"\n        ArrayList<E> answer = new ArrayList<>();\n        int processedVertices = 0;\n\n        while (!q.isEmpty()) {\n            E current = q.poll();\n            answer.add(current);\n            processedVertices++;\n\n            for (E adjacent : graph.getAdjacents(current)) {\n                inDegree.put(adjacent, inDegree.get(adjacent) - 1);\n                if (inDegree.get(adjacent) == 0) {\n                    q.add(adjacent);\n                }\n            }\n        }\n\n        if (processedVertices != graph.getVertices().size()) {\n            throw new IllegalStateException(\"Graph contains a cycle, topological sort not possible\");\n        }\n\n        return answer;\n    }\n}\n\n/**\n * A driver class that sorts a given graph in topological order using Kahn's algorithm.\n */\npublic final class KahnsAlgorithm {\n    private KahnsAlgorithm() {\n    }\n\n    public static void main(String[] args) {\n        // Graph definition and initialization\n        AdjacencyList<String> graph = new AdjacencyList<>();\n        graph.addEdge(\"a\", \"b\");\n        graph.addEdge(\"c\", \"a\");","sourceCodeStart":117,"sourceCodeEnd":153,"githubUrl":"https://github.com/TheAlgorithms/Java/blob/fdfb9a395b310167a66bd29e311e36e0e3e9b964/src/main/java/com/thealgorithms/datastructures/graphs/KahnsAlgorithm.java#L117-L153","documentation":"Thrown by Kahn's algorithm when the number of processed vertices is less than the total vertex count. Kahn's algorithm repeatedly removes zero-in-degree vertices; if some vertices remain, they sit on a cycle, so a topological order is impossible. This is an `IllegalStateException` because the graph's structure, not the arguments, is the problem.","triggerScenarios":"Calling the topological sort on a directed graph that contains at least one cycle — the queue empties before all vertices are emitted, so `processedVertices != graph.getVertices().size()`.","commonSituations":"Dependency graphs with circular dependencies (build/compile order, task scheduling); accidentally bidirectional edges in what should be a DAG; data import that introduces a loop.","solutions":["Break the cycle in the input graph (remove or reverse the offending edge)","Detect and report the cycle (DFS/Tarjan cycle detection) before sorting","If cycles are expected in your domain, use a routine that handles them"],"exampleFix":"// before\nList<E> order = KahnsAlgorithm.topoSort(graph); // throws on cyclic graph\n// after\nif (hasCycle(graph)) {\n    reportCycle(graph);\n} else {\n    List<E> order = KahnsAlgorithm.topoSort(graph);\n}","handlingStrategy":"validation","validationCode":"// Verify the graph is acyclic (DFS or Tarjan) before invoking the\n// topological sort.","typeGuard":null,"tryCatchPattern":"try {\n    KahnsAlgorithm.topoSort(graph);\n} catch (IllegalStateException e) {\n    // graph has a cycle; report the offending edges\n}","preventionTips":["Validate acyclicity at the boundary if your domain requires a DAG","Catch IllegalStateException to surface cyclic-dependency errors cleanly"],"tags":["graph","topological-sort","cycle","algorithm-invariant"],"backgroundTag":null,"analyzedSha":"fdfb9a395b310167a66bd29e311e36e0e3e9b964","analyzedAt":"2026-08-13T23:36:13.315Z","schemaVersion":2},"datasetVersion":"2026-08-14T00:17:13.853Z"}