TheAlgorithms/Java · error · RuntimeException

This graph contains a cycle. No linear ordering is possible.

Error message

This graph contains a cycle. No linear ordering is possible. Back edge: {u.label} -> {label}

What it means

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.

Source

Thrown at src/main/java/com/thealgorithms/sorts/TopologicalSort.java:136

     *           v.π = u
     *           DFS-Visit(G, u)
     *   u.color = BLACK
     *   time = time + 1
     *   u.f = time
     * */
    private static String sort(Graph graph, Vertex u, LinkedList<String> list) {
        u.color = Color.GRAY;
        graph.adj.get(u.label).next.forEach(label -> {
            if (graph.adj.get(label).color == Color.WHITE) {
                list.addFirst(sort(graph, graph.adj.get(label), list));
            } else if (graph.adj.get(label).color == Color.GRAY) {
                /*
                 * A back edge exists if an edge (u, v) connects a vertex u to its ancestor vertex v
                 * in a depth first tree. If v.d ≤ u.d < u.f ≤ v.f
                 *
                 * In many cases, we will not know u.f, but v.color denotes the type of edge
                 * */
                throw new RuntimeException("This graph contains a cycle. No linear ordering is possible. Back edge: " + u.label + " -> " + label);
            }
        });
        u.color = Color.BLACK;
        return u.label;
    }
}

View on GitHub (pinned to fdfb9a395b)

Solutions

1. Inspect the reported back edge `u -> label` and remove or reverse one edge of that cycle.
2. Pre-validate acyclicity before sorting (e.g. Kahn's algorithm or a separate DFS cycle detector).
3. Catch the RuntimeException and report which task/dependency loop to the user instead of crashing.

Example fix

// before
List<String> order = TopologicalSort.sort(graph); // graph has A->B->A

// after
// break the cycle first, or guard:
try {
    order = TopologicalSort.sort(graph);
} catch (RuntimeException e) {
    // e.getMessage() names the back edge, e.g. "A -> B"
    throw new IllegalStateException("Dependency cycle: " + e.getMessage(), e);
}

// Optional pre-check using Kahn's algorithm (in-degree based):
static boolean isAcyclic(Graph g) {
    Map<Vertex,Integer> indeg = new HashMap<>();
    g.adj.keySet().forEach(v -> indeg.put(v, 0));
    g.adj.values().forEach(u -> u.next.forEach(label ->
        indeg.merge(g.adj.get(label), 1, Integer::sum)));
    Deque<Vertex> q = new ArrayDeque<>(
        indeg.entrySet().stream().filter(e -> e.getValue()==0)
            .map(Map.Entry::getKey).toList());
    int seen = 0;
    while (!q.isEmpty()) { Vertex u = q.poll(); seen++;
        for (String l : g.adj.get(u.label).next)
            if (indeg.merge(g.adj.get(l), -1, Integer::sum) == 0) q.add(g.adj.get(l));
    }
    return seen == indeg.size();
}

try {
    List<String> order = TopologicalSort.sort(graph);
} catch (RuntimeException e) {
    if (e.getMessage() != null && e.getMessage().contains("cycle")) {
        // e.getMessage() names the back edge, e.g. "... Back edge: A -> B"
        reportCycle(e.getMessage());
    } else {
        throw e;
    }
}

When it happens

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

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

Related errors

• Graph contains a cycle, topological sort not possible
• Number of vertices must be positive
• Edges list must not be null or empty
• Edge vertex out of range
• Source vertex is out of bounds.

AI-assisted analysis of TheAlgorithms/Java@fdfb9a395b (2026-08-13). Data as JSON: /api/errors/95159474bd0f7555. Report an issue: GitHub.