nkuprins opened a new issue, #18409: URL: https://github.com/apache/dolphinscheduler/issues/18409
### Search before asking - [x] I had searched in the [issues](https://github.com/apache/dolphinscheduler/issues?q=is%3Aissue) and found no similar issues. ### What happened `org.apache.dolphinscheduler.common.graph.DAG#addEdge` is documented to return `false` when the new edge would create a cycle. However, on graphs where multiple paths converge into one node, it can return `true` for a cycle-creating edge and insert the cycle into the DAG. The root cause is in the private method `isLegalAddEdge`: it does a BFS from `toNode` looking for `fromNode`, but 1. it has **no visited set** - a node is re-enqueued once per incoming edge, and 2. the loop is bounded by a step budget `while (!queue.isEmpty() && (--verticesCount > 0))`. When paths converge, the duplicate visits consume the budget and the BFS gives up **before** reaching `fromNode`, so the edge is judged legal. After that, `hasCycle()` returns `true` and `topologicalSort()` throws `"serious error: graph has cycle"`. https://github.com/apache/dolphinscheduler/blob/dev/dolphinscheduler-common/src/main/java/org/apache/dolphinscheduler/common/graph/DAG.java#L394-L411 ### What you expected to happen `addEdge` should return `false` for any edge that would create a cycle, per its javadoc contract ("returns false if the DAG result is a ring result"), and the DAG should remain acyclic. Some callers rely on this contract without a second check - e.g. `DagHelper.buildDagGraph` ignores the return value and assumes the resulting graph is a DAG. (`WorkflowDefinitionServiceImpl.graphHasCycle` happens to be protected because it calls `hasCycle()` afterwards.) ### How to reproduce Minimal unit-level reproduction against current `dev`: ```java DAG<Integer, String, String> graph = new DAG<>(); for (int i = 1; i <= 7; i++) { graph.addNode(i, "v(" + i + ")"); } // three paths converge into node 5 graph.addEdge(1, 2); graph.addEdge(1, 3); graph.addEdge(1, 4); graph.addEdge(2, 5); graph.addEdge(3, 5); graph.addEdge(4, 5); graph.addEdge(5, 6); graph.addEdge(6, 7); boolean added = graph.addEdge(7, 1); // creates cycle 7 -> 1 -> ... -> 7 System.out.println(added); // prints true, expected false System.out.println(graph.hasCycle()); // prints true - the DAG now contains a cycle ``` Trace: the BFS starts at node 1 with a budget of 7 steps. Node 5 is enqueued three times (once per incoming edge 2→5, 3→5, 4→5). The duplicate visits of node 5 exhaust the budget before the walk reaches node 6/7, so `fromNode` is never found and the edge is accepted. ### Anything else - Occurs deterministically for any graph shape where duplicate enqueues exhaust the vertex-count budget before the BFS reaches `fromNode`. - The defect has been present since the earliest imported version of this class; existing `DAGTest` cycle tests only cover simple chains, which the budget happens to survive. - Fix is small: track visited nodes in the BFS (`Set<Node> visited`) so each node is enqueued at most once - this both fixes correctness and makes the budget unnecessary. I have the patch plus a regression test (`DAGTest#testCycleWithConvergingPaths`) ready; the test fails on current `dev` and passes with the fix. ### Version dev ### Are you willing to submit PR? - [x] Yes I am willing to submit a PR! ### Code of Conduct - [x] I agree to follow this project's [Code of Conduct](https://www.apache.org/foundation/policies/conduct) -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
