NationalSecurityAgency/ghidra · error · SorterException

Graph is cyclic: {}

Error message

Graph is cyclic: {}

What it means

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.

Source

Thrown at Ghidra/Debug/ProposedUtils/src/main/java/ghidra/graph/algo/TopologicalSorter.java:128

	 * Visit a vertex
	 * 
	 * @param n the vertex
	 * @throws SorterException if a cycle is detected
	 */
	protected void visit(V n) throws SorterException {
		visit(n, new LinkedList<>());
	}

	/**
	 * Visit a vertex, checking for a cycle
	 * 
	 * @param n the vertex
	 * @param temp a list of previously-visited vertices on this path
	 * @throws SorterException if a cycle is detected
	 */
	protected void visit(V n, Deque<V> temp) throws SorterException {
		if (temp.contains(n)) {
			throw new SorterException("Graph is cyclic", temp);
		}
		if (unmarked.contains(n)) {
			temp.push(n);
			try {
				for (V m : graph.getSuccessors(n)) {
					visit(m, temp);
				}
				unmarked.remove(n);
			}
			finally {
				temp.pop();
			}
			list.push(n);
		}
	}
}

View on GitHub (pinned to d5f144c24d)

Solutions

1. Detect cycles up front (e.g. Tarjan SCC or Kahn's algorithm) and report the cycle to the user before attempting to sort.
2. Break the cycle by removing or reversing the offending back-edge(s) identified in the exception's temp path.
3. If cyclic ordering is expected, use a cycle-tolerant ordering algorithm (e.g. order within strongly connected components) instead of TopologicalSorter.
4. Audit edge insertion code for accidental bidirectional/symmetric edges.

Example fix

// before
List<V> sorted = new TopologicalSorter<V,E>(graph).sort(); // throws on cycle

// after: pre-check for cycles and handle them
if (new JohnsonCircuitsAlgorithm<>(graph).findCycles().hasNext()) {
    throw new IllegalStateException("graph has a cycle; cannot topo-sort");
}
List<V> sorted = new TopologicalSorter<V,E>(graph).sort();

// Pre-check for cycles before topological sort
boolean hasCycle = !new CycleDetector<V,E>(graph).findCycles().isEmpty();
if (hasCycle) {
    // do not call sort(); break the cycle first
}

try {
    List<V> order = new TopologicalSorter<V,E>(graph).sort();
} catch (SorterException e) { // checked; message includes the cyclic path
    // e.getMessage() lists the vertices in the cycle
}

When it happens

Trigger: 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.

Common situations: 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.

Related errors

• Not a total order: {} ?? {}
• Failed to read {len} bytes at {addr}
• Trace does not contain referenced instruction: ({getStartSna
• Instruction has incompatible prototype at: ({getStartSnap},{
• Code units cannot overlap

AI-assisted analysis of NationalSecurityAgency/ghidra@d5f144c24d (2026-08-14). Data as JSON: /api/errors/729ac1999c57a1ee. Report an issue: GitHub.