{"record":{"id":"95159474bd0f7555","repo":"TheAlgorithms/Java","slug":"this-graph-contains-a-cycle-no-linear-ordering-is","errorCode":null,"errorMessage":"This graph contains a cycle. No linear ordering is possible. Back edge: {u.label} -> {label}","messagePattern":"This graph contains a cycle\\. No linear ordering is possible\\. Back edge: (.+?) -> (.+?)","errorType":"exception","errorClass":"RuntimeException","httpStatus":null,"severity":"error","filePath":"src/main/java/com/thealgorithms/sorts/TopologicalSort.java","lineNumber":136,"sourceCode":"     *           v.π = u\n     *           DFS-Visit(G, u)\n     *   u.color = BLACK\n     *   time = time + 1\n     *   u.f = time\n     * */\n    private static String sort(Graph graph, Vertex u, LinkedList<String> list) {\n        u.color = Color.GRAY;\n        graph.adj.get(u.label).next.forEach(label -> {\n            if (graph.adj.get(label).color == Color.WHITE) {\n                list.addFirst(sort(graph, graph.adj.get(label), list));\n            } else if (graph.adj.get(label).color == Color.GRAY) {\n                /*\n                 * A back edge exists if an edge (u, v) connects a vertex u to its ancestor vertex v\n                 * in a depth first tree. If v.d ≤ u.d < u.f ≤ v.f\n                 *\n                 * In many cases, we will not know u.f, but v.color denotes the type of edge\n                 * */\n                throw new RuntimeException(\"This graph contains a cycle. No linear ordering is possible. Back edge: \" + u.label + \" -> \" + label);\n            }\n        });\n        u.color = Color.BLACK;\n        return u.label;\n    }\n}\n","sourceCodeStart":118,"sourceCodeEnd":143,"githubUrl":"https://github.com/TheAlgorithms/Java/blob/fdfb9a395b310167a66bd29e311e36e0e3e9b964/src/main/java/com/thealgorithms/sorts/TopologicalSort.java#L118-L143","documentation":"TopologicalSort performs a DFS and colors vertices WHITE (unvisited) -> GRAY (in progress) -> BLACK (finished). Encountering an edge to a still-GRAY vertex means a back edge exists, i.e. the graph has a cycle and therefore no valid topological (linear) ordering exists. The message names the offending edge `u.label -> label` to pinpoint the cycle. Note this throws a plain RuntimeException, not IllegalArgumentException.","triggerScenarios":"Calling `sort(...)` on a directed graph that contains any cycle, e.g. A->B->A or A->B->C->A. Any edge from a GRAY vertex back to another GRAY ancestor during the DFS triggers it.","commonSituations":"Dependency resolution graphs with circular dependencies; build/task schedulers where two tasks mutually depend on each other; importing graph data that accidentally contains a back-edge due to a data-entry or parsing bug; version changes where a previously-acyclic graph gains a new edge.","solutions":["Inspect the reported back edge `u -> label` and remove or reverse one edge of that cycle.","Pre-validate acyclicity before sorting (e.g. Kahn's algorithm or a separate DFS cycle detector).","Catch the RuntimeException and report which task/dependency loop to the user instead of crashing."],"exampleFix":"// before\nList<String> order = TopologicalSort.sort(graph); // graph has A->B->A\n\n// after\n// break the cycle first, or guard:\ntry {\n    order = TopologicalSort.sort(graph);\n} catch (RuntimeException e) {\n    // e.getMessage() names the back edge, e.g. \"A -> B\"\n    throw new IllegalStateException(\"Dependency cycle: \" + e.getMessage(), e);\n}","handlingStrategy":"try-catch","validationCode":"// Optional pre-check using Kahn's algorithm (in-degree based):\nstatic boolean isAcyclic(Graph g) {\n    Map<Vertex,Integer> indeg = new HashMap<>();\n    g.adj.keySet().forEach(v -> indeg.put(v, 0));\n    g.adj.values().forEach(u -> u.next.forEach(label ->\n        indeg.merge(g.adj.get(label), 1, Integer::sum)));\n    Deque<Vertex> q = new ArrayDeque<>(\n        indeg.entrySet().stream().filter(e -> e.getValue()==0)\n            .map(Map.Entry::getKey).toList());\n    int seen = 0;\n    while (!q.isEmpty()) { Vertex u = q.poll(); seen++;\n        for (String l : g.adj.get(u.label).next)\n            if (indeg.merge(g.adj.get(l), -1, Integer::sum) == 0) q.add(g.adj.get(l));\n    }\n    return seen == indeg.size();\n}","typeGuard":null,"tryCatchPattern":"try {\n    List<String> order = TopologicalSort.sort(graph);\n} catch (RuntimeException e) {\n    if (e.getMessage() != null && e.getMessage().contains(\"cycle\")) {\n        // e.getMessage() names the back edge, e.g. \"... Back edge: A -> B\"\n        reportCycle(e.getMessage());\n    } else {\n        throw e;\n    }\n}","preventionTips":["Validate graph inputs at the trust boundary before building edges.","Log/audit every added edge so cycles can be traced to their source.","Treat a topology error as a data problem, not a crash: surface the back edge to the user."],"tags":["topological-sort","graph","cycle-detection","dfs","runtime-exception"],"backgroundTag":null,"analyzedSha":"fdfb9a395b310167a66bd29e311e36e0e3e9b964","analyzedAt":"2026-08-13T23:36:13.315Z","schemaVersion":2},"datasetVersion":"2026-08-14T00:17:13.853Z"}