{"record":{"id":"729ac1999c57a1ee","repo":"NationalSecurityAgency/ghidra","slug":"graph-is-cyclic","errorCode":null,"errorMessage":"Graph is cyclic: {}","messagePattern":"Graph is cyclic: (.+?)","errorType":"exception","errorClass":"SorterException","httpStatus":null,"severity":"error","filePath":"Ghidra/Debug/ProposedUtils/src/main/java/ghidra/graph/algo/TopologicalSorter.java","lineNumber":128,"sourceCode":"\t * Visit a vertex\n\t * \n\t * @param n the vertex\n\t * @throws SorterException if a cycle is detected\n\t */\n\tprotected void visit(V n) throws SorterException {\n\t\tvisit(n, new LinkedList<>());\n\t}\n\n\t/**\n\t * Visit a vertex, checking for a cycle\n\t * \n\t * @param n the vertex\n\t * @param temp a list of previously-visited vertices on this path\n\t * @throws SorterException if a cycle is detected\n\t */\n\tprotected void visit(V n, Deque<V> temp) throws SorterException {\n\t\tif (temp.contains(n)) {\n\t\t\tthrow new SorterException(\"Graph is cyclic\", temp);\n\t\t}\n\t\tif (unmarked.contains(n)) {\n\t\t\ttemp.push(n);\n\t\t\ttry {\n\t\t\t\tfor (V m : graph.getSuccessors(n)) {\n\t\t\t\t\tvisit(m, temp);\n\t\t\t\t}\n\t\t\t\tunmarked.remove(n);\n\t\t\t}\n\t\t\tfinally {\n\t\t\t\ttemp.pop();\n\t\t\t}\n\t\t\tlist.push(n);\n\t\t}\n\t}\n}\n","sourceCodeStart":110,"sourceCodeEnd":145,"githubUrl":"https://github.com/NationalSecurityAgency/ghidra/blob/d5f144c24d6bc53c9cbf4448c6d11143e7696206/Ghidra/Debug/ProposedUtils/src/main/java/ghidra/graph/algo/TopologicalSorter.java#L110-L145","documentation":"Thrown by TopologicalSorter.visit() (a checked SorterException) during depth-first traversal when the current vertex n is already present in the active path Deque (temp). That means a back-edge was found, i.e. the directed graph contains a cycle, and a topological ordering therefore cannot exist. The exception message includes the cyclic path (the temp deque) for diagnosis.","triggerScenarios":"Sorting a directed graph that contains at least one directed cycle — visit() recurses into successors and, upon re-entering a vertex still on the current recursion stack (temp.contains(n)), aborts. Common with dependency graphs that have circular dependencies or accidentally bidirectional edges.","commonSituations":"Circular dependency between modules/blocks; a graph builder that inserted symmetric edges (a->b and b->a); user-edited ordering constraints that form a loop; feeding an SCC-containing graph to a DAG-only algorithm.","solutions":["Detect cycles up front (e.g. Tarjan SCC or Kahn's algorithm) and report the cycle to the user before attempting to sort.","Break the cycle by removing or reversing the offending back-edge(s) identified in the exception's temp path.","If cyclic ordering is expected, use a cycle-tolerant ordering algorithm (e.g. order within strongly connected components) instead of TopologicalSorter.","Audit edge insertion code for accidental bidirectional/symmetric edges."],"exampleFix":"// before\nList<V> sorted = new TopologicalSorter<V,E>(graph).sort(); // throws on cycle\n\n// after: pre-check for cycles and handle them\nif (new JohnsonCircuitsAlgorithm<>(graph).findCycles().hasNext()) {\n    throw new IllegalStateException(\"graph has a cycle; cannot topo-sort\");\n}\nList<V> sorted = new TopologicalSorter<V,E>(graph).sort();","handlingStrategy":"validation","validationCode":"// Pre-check for cycles before topological sort\nboolean hasCycle = !new CycleDetector<V,E>(graph).findCycles().isEmpty();\nif (hasCycle) {\n    // do not call sort(); break the cycle first\n}","typeGuard":null,"tryCatchPattern":"try {\n    List<V> order = new TopologicalSorter<V,E>(graph).sort();\n} catch (SorterException e) { // checked; message includes the cyclic path\n    // e.getMessage() lists the vertices in the cycle\n}","preventionTips":["Detect cycles (Tarjan/Kahn/CycleDetector) before sorting.","Audit edge-insertion code for accidental symmetric/back edges.","Use an SCC-aware ordering algorithm when cycles are expected."],"tags":["graph","topological-sort","cycle-detection","dfs","checked-exception"],"backgroundTag":null,"analyzedSha":"d5f144c24d6bc53c9cbf4448c6d11143e7696206","analyzedAt":"2026-08-14T01:00:57.564Z","schemaVersion":2},"datasetVersion":"2026-08-14T05:17:29.042Z"}