TheAlgorithms/C-Sharp · error · InvalidOperationException

Graph contains a cycle. Topological sort is only possible…

Error message

Graph contains a cycle. Topological sort is only possible for Directed Acyclic Graphs (DAGs).

What it means

After Kahn's algorithm finishes, ValidateNoCycles checks whether all vertices were dequeued. If result.Count != graph.Count, some vertices never had in-degree 0, proving the graph contains a cycle; a topological order then cannot exist, so an InvalidOperationException is thrown.

Solutions

1. Run cycle detection (or this same sort) on the graph before relying on a topological order
2. Locate and break the cycle: audit dependency edges for the strongly connected components with size > 1
3. Fix the input data so dependencies form a DAG (remove or reverse the offending edge)
4. Catch InvalidOperationException and fall back to reporting the dependency cycle to the user

Example fix

// before
graph.AddEdge(a, b);
graph.AddEdge(b, a); // cycle
var order = sorter.SortKahn(graph); // throws
// after
graph.AddEdge(a, b); // keep DAG
var order = sorter.SortKahn(graph);

// Kahn's algorithm itself is the validator; pre-check with an SCC pass:
bool isDag = TarjanSCC(graph).All(scc => scc.Count == 1);

try { var order = sorter.SortKahn(graph); }
catch (InvalidOperationException) { reportDependencyCycle(graph); }

When it happens

Trigger: Calling SortKahn on an IDirectedWeightedGraph<T> that contains at least one directed cycle (e.g., A -> B -> A). The exception is raised after the queue drains with unprocessed vertices remaining.

Common situations: Build-order/task-scheduling graphs where a job depends on itself transitively; course prerequisite data with circular prerequisites; graphs mutated with cycles after validation; misdirected edges loaded from config files.

Understand the failure class

Background: UnsupportedOperationException and "is not supported" errors: when a library deliberately refuses a call — this error's family across 30 libraries.

Related errors

• Graph contains a cycle involving vertex
• Graph contains a negative weight cycle.
• Matrix must be symmetric!
• Graph must be undirected!
• Adjacency matrix must be square!

AI-assisted analysis of TheAlgorithms/C-Sharp@96e2905cab (2026-09-13). Data as JSON: /api/errors/39a8f74afedd590f. Report an issue: GitHub.

Appendix: source

Thrown at Algorithms/Graph/TopologicalSort.cs:291

                    queue.Enqueue(neighbor);
                }
            }
        }
    }

    /// <summary>
    ///     Validates that all vertices were processed, ensuring no cycles exist.
    /// </summary>
    /// <param name="graph">The graph being sorted.</param>
    /// <param name="result">The list of processed vertices.</param>
    /// <exception cref="InvalidOperationException">
    ///     Thrown when not all vertices were processed (cycle detected).
    /// </exception>
    private void ValidateNoCycles(IDirectedWeightedGraph<T> graph, List<Vertex<T>> result)
    {
        if (result.Count != graph.Count)
        {
            throw new InvalidOperationException(
                "Graph contains a cycle. Topological sort is only possible for Directed Acyclic Graphs (DAGs).");
        }
    }

    /// <summary>
    ///     Helper method for DFS-based topological sort.
    ///     Recursively visits vertices and adds them to the stack in post-order.
    ///
    ///     POST-ORDER TRAVERSAL:
    ///     - Visit all descendants first.
    ///     - Then process the current vertex.
    ///     - This ensures dependencies are processed before dependents.
    ///
    ///     CYCLE DETECTION:
    ///     - We maintain a recursion stack to track the current DFS path.
    ///     - If we encounter a vertex that's already in the recursion stack,
    ///       we've found a back edge, indicating a cycle.
    /// </summary>

View on GitHub (pinned to 96e2905cab)