{"record":{"id":"6574d91f6be23be0","repo":"stanfordnlp/CoreNLP","slug":"this-graph-has-cycles-topological-sort-not-possib","errorCode":null,"errorMessage":"This graph has cycles. Topological sort not possible","messagePattern":"This graph has cycles\\. Topological sort not possible","errorType":"exception","errorClass":"CyclicGraphException","httpStatus":null,"severity":"error","filePath":"src/edu/stanford/nlp/graph/DirectedMultiGraph.java","lineNumber":642,"sourceCode":"    for (V vertex : getAllVertices()) {\n      if (!temporary.contains(vertex)) {\n        topologicalSortHelper(vertex, temporary, permanent, result);\n      }\n    }\n    Collections.reverse(result);\n    return result;\n  }\n\n  private void topologicalSortHelper(V vertex, Set<V> temporary, Set<V> permanent, List<V> result) {\n    temporary.add(vertex);\n    Map<V, List<E>> neighborMap = outgoingEdges.get(vertex);\n    if (neighborMap != null) {\n      for (V neighbor : neighborMap.keySet()) {\n        if (permanent.contains(neighbor)) {\n          continue;\n        }\n        if (temporary.contains(neighbor)) {\n          throw new CyclicGraphException(\"This graph has cycles. Topological sort not possible\", this);\n        }\n        topologicalSortHelper(neighbor, temporary, permanent, result);\n      }\n    }\n    result.add(vertex);\n    permanent.add(vertex);\n  }\n\n  /**\n   * Cast this multi-graph as a map from vertices, to the outgoing data along edges out of those vertices.\n   *\n   * @return A map representation of the graph.\n   */\n  public Map<V, List<E>> toMap() {\n    Map<V, List<E>> map = innerMapFactory.newMap();\n    for (V vertex : getAllVertices()) {\n      map.put(vertex, getOutgoingEdges(vertex));\n    }","sourceCodeStart":624,"sourceCodeEnd":660,"githubUrl":"https://github.com/stanfordnlp/CoreNLP/blob/1b7edd19c4d0d7b1f13a2591425b9b60a0b1af7a/src/edu/stanford/nlp/graph/DirectedMultiGraph.java#L624-L660","documentation":"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.","triggerScenarios":"Calling graph.topologicalSort() (or the constructor/helper path) on a graph whose vertex neighborMaps form a directed cycle, e.g. A->B, B->A.","commonSituations":"Building dependency graphs where circular dependencies were introduced by bad data or recent edge additions; topologically sorting scheduling/prerequisite graphs that legitimately contain cycles.","solutions":["Remove the cycle: find and delete the back edges creating it before sorting","Detect cycles beforehand (e.g. with a DFS or by checking getCycles if available)","If cycles are legitimate, use SCC condensation or a different ordering algorithm","Fix data upstream so dependencies are acyclic"],"exampleFix":"// before\nList<V> order = graph.topologicalSort();\n// after\nif (!graph.isDAG()) { // or run cycle detection first\n  throw new IllegalStateException(\"Fix circular dependencies before sorting\");\n}\nList<V> order = graph.topologicalSort();","handlingStrategy":"validation","validationCode":"static <V,E> boolean hasCycle(DirectedMultiGraph<V,E> g) {\n  Set<V> temp = new HashSet<>(), perm = new HashSet<>();\n  try { g.topologicalSort(); return false; } catch (CyclicGraphException e) { return true; }\n}","typeGuard":null,"tryCatchPattern":"try { order = graph.topologicalSort(); }\ncatch (CyclicGraphException e) { order = null; reportCircularDependencies(e); }","preventionTips":["Validate dependency data for cycles at ingestion time","Keep cycle detection in a unit test on representative graphs","Break known cycles explicitly before sorting"],"tags":["graph","topological-sort","cycle"],"backgroundTag":"invalid-state-transition","analyzedSha":"1b7edd19c4d0d7b1f13a2591425b9b60a0b1af7a","analyzedAt":"2026-09-10T02:24:07.274Z","contentChangedAt":"2026-09-10T02:24:07.274Z","schemaVersion":2},"datasetVersion":"2026-09-15T23:17:13.987Z"}