{"record":{"id":"e96cd9ab6f2eb5a7","repo":"stanfordnlp/CoreNLP","slug":"subtree-cannot-contain-cycle-leading-back-to-root","errorCode":null,"errorMessage":"Subtree cannot contain cycle leading back to root node!","messagePattern":"Subtree cannot contain cycle leading back to root node!","errorType":"exception","errorClass":"IllegalArgumentException","httpStatus":null,"severity":"error","filePath":"src/edu/stanford/nlp/semgraph/semgrex/ssurgeon/CollapseSubtree.java","lineNumber":58,"sourceCode":"  @Override\n  public boolean evaluate(SemanticGraph sg, SemgrexMatcher sm) {\n    IndexedWord rootNode = this.getNamedNode(rootName, sm);\n    Set<IndexedWord> subgraphNodeSet = sg.getSubgraphVertices(rootNode);\n    if (subgraphNodeSet.size() == 1) {\n      // our work here is done\n      return false;\n    }\n\n    // TODO: this doesn't do a full search for cycles.  Is that relevant?\n    // Why does this even matter?  Perhaps the only thing we care about\n    // is that the root of the whole graph isn't collapsed\n    // unless it stays the root\n    if ( ! sg.isDag(rootNode)) {\n      /* Check if there is a cycle going back to the root. */\n      for (IndexedWord child : sg.getChildren(rootNode)) {\n        Set<IndexedWord> reachableSet = sg.getSubgraphVertices(child);\n        if (reachableSet.contains(rootNode)) {\n          throw new IllegalArgumentException(\"Subtree cannot contain cycle leading back to root node!\");\n        }\n      }\n    }\n\n    List<IndexedWord> sortedSubgraphNodes = Generics.newArrayList(subgraphNodeSet);\n    Collections.sort(sortedSubgraphNodes);\n\n    IndexedWord newNode = new IndexedWord(rootNode.docID(), rootNode.sentIndex(), rootNode.index());\n    /* Copy all attributes from rootNode. */\n    for (Class key : newNode.backingLabel().keySet()) {\n      newNode.set(key, rootNode.get(key));\n    }\n\n    newNode.setValue(StringUtils.join(sortedSubgraphNodes.stream().map(IndexedWord::value), \" \"));\n    newNode.setWord(StringUtils.join(sortedSubgraphNodes.stream().map(IndexedWord::word), \" \"));\n    newNode.setLemma(StringUtils.join(sortedSubgraphNodes.stream().map(x -> x.lemma() == null ? x.word() : x.lemma()), \" \"));\n\n    if (sg.getRoots().contains(rootNode)) {","sourceCodeStart":40,"sourceCodeEnd":76,"githubUrl":"https://github.com/stanfordnlp/CoreNLP/blob/1b7edd19c4d0d7b1f13a2591425b9b60a0b1af7a/src/edu/stanford/nlp/semgraph/semgrex/ssurgeon/CollapseSubtree.java#L40-L76","documentation":"CollapseSubtree.evaluate refuses to collapse a subtree whose graph region is not a DAG with respect to the root: if some child of the root can reach the root again, the subgraph contains a cycle back to the root and collapsing it would produce an ill-formed result. It detects this with sg.isDag(rootNode) and a per-child reachability check via getSubgraphVertices, throwing IllegalArgumentException.","triggerScenarios":"Running CollapseSubtree on a SemanticGraph in which a descendant of the matched root node has an edge back to the root (e.g. a wrongly added second parent or enhanced-dependency edge), so getSubgraphVertices(child).contains(rootNode) is true.","commonSituations":"Working with enhanced+plus dependencies that add controlling-subject edges creating cycles; prior Ssurgeon edits (AddDep) introduced a back-edge; applying collapse rules to noisy machine-parsed graphs.","solutions":["Inspect the graph around the root node and delete the offending back-edge (e.g. with a DeleteDep or removeEdge step) before collapsing.","Run the collapse only on basic (non-enhanced) dependencies where such cycles cannot occur.","Pre-check with sg.isDag(rootNode) / getSubgraphVertices in your own code and skip or repair such matches."],"exampleFix":"// before\nCollapseSubtree op = new CollapseSubtree(\"root\", \"newnode\", attributes);\nop.evaluate sg // throws on cyclic graph\n\n// after\nSemanticGraph cleaned = sg;\nfor (IndexedWord child : cleaned.getChildren(root)) {\n  if (cleaned.getSubgraphVertices(child).contains(root)) {\n    cleaned.removeEdge(cleaned.getEdge(child, root));\n  }\n}\nnew CollapseSubtree(\"root\", \"newnode\", attributes).evaluate(cleaned, match, ...);","handlingStrategy":"validation","validationCode":"// Java\nif (!sg.isDag(rootNode)) {\n  for (IndexedWord child : sg.getChildren(rootNode)) {\n    if (sg.getSubgraphVertices(child).contains(rootNode)) {\n      throw new IllegalStateException(\"Cannot collapse: cycle back to root via child \" + child);\n    }\n  }\n}","typeGuard":null,"tryCatchPattern":"// Java\ntry {\n  collapseSubtree.evaluate(sg, match, ...);\n} catch (IllegalArgumentException e) {\n  log.warning(\"Skipping match: \" + e.getMessage()); // repair or skip the cyclic subgraph\n}","preventionTips":["Delete spurious back-edges (common in enhanced dependencies) before running CollapseSubtree.","Prefer basic dependencies for collapse operations.","Run isDag checks on candidate match roots before applying collapse rules."],"tags":["java","ssurgeon","graph","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"}