TheAlgorithms/C-Sharp · error · InvalidOperationException

Graph contains a cycle involving vertex

Error message

Graph contains a cycle involving vertex: {vertex}. Topological sort is only possible for Directed Acyclic Graphs (DAGs).

What it means

The DFS-based topological sort maintains a recursion stack of the current path. If a vertex is encountered that is already in the recursion stack, the path revisits itself — a cycle — and the sort cannot proceed, so DfsTopologicalSort throws an InvalidOperationException naming the vertex.

Solutions

1. Validate the graph is a DAG before sorting (e.g., run Kahn's sort or an SCC check)
2. Find and remove the cycle involving the reported vertex (audit its outgoing/incoming edges)
3. Fix upstream data that introduced the circular dependency or self-loop
4. Catch InvalidOperationException and surface the named vertex to help users locate the cycle

Example fix

// before
graph.AddEdge(v, v); // self-loop
var order = sorter.Sort(graph); // throws
// after
graph.RemoveEdge(v, v);
var order = sorter.Sort(graph);

bool hasSelfLoop = graph.Vertices.Any(v => graph.ContainsEdge(v, v));

try { var order = sorter.Sort(graph); }
catch (InvalidOperationException ex) { log.Error($"Cycle at {ex.Message}"); }

When it happens

Trigger: Calling Sort (DFS variant) on a directed graph with a cycle; the recursionStack.Contains(vertex) check fires for the first vertex found back on the current DFS path (self-loop or mutual edge included).

Common situations: Circular dependencies in module build graphs; self-referencing nodes (v -> v) from bad data; graphs loaded from external sources without prior cycle validation.

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. Topological sort is only possible…
• 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/c2326774d5b7a9eb. Report an issue: GitHub.

Appendix: source

Thrown at Algorithms/Graph/TopologicalSort.cs:330

    /// <param name="visited">Set of all visited vertices.</param>
    /// <param name="recursionStack">Set of vertices in the current DFS path.</param>
    /// <param name="stack">Stack to store vertices in reverse topological order.</param>
    /// <exception cref="InvalidOperationException">
    ///     Thrown when a cycle is detected.
    /// </exception>
    private void DfsTopologicalSort(
        IDirectedWeightedGraph<T> graph,
        Vertex<T> vertex,
        HashSet<Vertex<T>> visited,
        HashSet<Vertex<T>> recursionStack,
        Stack<Vertex<T>> stack)
    {
        // CYCLE DETECTION:
        // If the vertex is in the recursion stack, we've encountered it again
        // in the current DFS path, which means there's a cycle.
        if (recursionStack.Contains(vertex))
        {
            throw new InvalidOperationException(
                $"Graph contains a cycle involving vertex: {vertex}. " +
                "Topological sort is only possible for Directed Acyclic Graphs (DAGs).");
        }

        // If already visited, no need to process again.
        if (visited.Contains(vertex))
        {
            return;
        }

        // Mark vertex as visited and add to recursion stack.
        visited.Add(vertex);
        recursionStack.Add(vertex);

        // Recursively visit all neighbors (descendants).
        // This ensures all dependencies are processed first.
        foreach (var neighbor in graph.GetNeighbors(vertex))
        {

View on GitHub (pinned to 96e2905cab)