stanfordnlp/CoreNLP · error · CyclicGraphException

This graph has cycles. Topological sort not possible

Error message

This graph has cycles. Topological sort not possible

What it means

topologicalSort performs a DFS with temporary/permanent marks; when it re-enters a vertex still on the temporary (in-progress) mark, the graph contains a directed cycle and no topological order exists, so a CyclicGraphException is thrown. The message says the sort is not possible for this graph.

Solutions

1. Remove the cycle: find and delete the back edges creating it before sorting
2. Detect cycles beforehand (e.g. with a DFS or by checking getCycles if available)
3. If cycles are legitimate, use SCC condensation or a different ordering algorithm
4. Fix data upstream so dependencies are acyclic

Example fix

// before
List<V> order = graph.topologicalSort();
// after
if (!graph.isDAG()) { // or run cycle detection first
  throw new IllegalStateException("Fix circular dependencies before sorting");
}
List<V> order = graph.topologicalSort();

static <V,E> boolean hasCycle(DirectedMultiGraph<V,E> g) {
  Set<V> temp = new HashSet<>(), perm = new HashSet<>();
  try { g.topologicalSort(); return false; } catch (CyclicGraphException e) { return true; }
}

try { order = graph.topologicalSort(); }
catch (CyclicGraphException e) { order = null; reportCircularDependencies(e); }

When it happens

Trigger: Calling graph.topologicalSort() (or the constructor/helper path) on a graph whose vertex neighborMaps form a directed cycle, e.g. A->B, B->A.

Common situations: Building dependency graphs where circular dependencies were introduced by bad data or recent edge additions; topologically sorting scheduling/prerequisite graphs that legitimately contain cycles.

Understand the failure class

Background: "Invalid state transition" errors: "status must be X, actually Y", "already rejected/charging/uninstalled", "cannot ... while running" — what they mean when a library rejects your call — this error's family across 31 libraries.

Related errors

• Subtree cannot contain cycle leading back to root node!
• Creating nondeterminism while inserting arc
• Unexpected node class
• Path given with missing edge connection
• Graph edge iterator exhausted.

AI-assisted analysis of stanfordnlp/CoreNLP@1b7edd19c4 (2026-09-10). Data as JSON: /api/errors/6574d91f6be23be0. Report an issue: GitHub.

Appendix: source

Thrown at src/edu/stanford/nlp/graph/DirectedMultiGraph.java:642

    for (V vertex : getAllVertices()) {
      if (!temporary.contains(vertex)) {
        topologicalSortHelper(vertex, temporary, permanent, result);
      }
    }
    Collections.reverse(result);
    return result;
  }

  private void topologicalSortHelper(V vertex, Set<V> temporary, Set<V> permanent, List<V> result) {
    temporary.add(vertex);
    Map<V, List<E>> neighborMap = outgoingEdges.get(vertex);
    if (neighborMap != null) {
      for (V neighbor : neighborMap.keySet()) {
        if (permanent.contains(neighbor)) {
          continue;
        }
        if (temporary.contains(neighbor)) {
          throw new CyclicGraphException("This graph has cycles. Topological sort not possible", this);
        }
        topologicalSortHelper(neighbor, temporary, permanent, result);
      }
    }
    result.add(vertex);
    permanent.add(vertex);
  }

  /**
   * Cast this multi-graph as a map from vertices, to the outgoing data along edges out of those vertices.
   *
   * @return A map representation of the graph.
   */
  public Map<V, List<E>> toMap() {
    Map<V, List<E>> map = innerMapFactory.newMap();
    for (V vertex : getAllVertices()) {
      map.put(vertex, getOutgoingEdges(vertex));
    }

View on GitHub (pinned to 1b7edd19c4)