(dolphinscheduler) branch dev updated: [Fix-18409][Common] Fix DAG.addEdge accepting an edge that creates a cycle when paths converge (#18410)

[zihaoxiang]

This is an automated email from the ASF dual-hosted git repository.

SbloodyS pushed a commit to branch dev
in repository https://gitbox.apache.org/repos/asf/dolphinscheduler.git


The following commit(s) were added to refs/heads/dev by this push:
     new 65bfc935c9 [Fix-18409][Common] Fix DAG.addEdge accepting an edge that 
creates a cycle when paths converge (#18410)
65bfc935c9 is described below

commit 65bfc935c9dd37db92206575cf0c991a4f12496b
Author: Nikita Kuprins <61872798+nkupr...@users.noreply.github.com>
AuthorDate: Wed Jul 15 11:10:07 2026 +0300

    [Fix-18409][Common] Fix DAG.addEdge accepting an edge that creates a cycle 
when paths converge (#18410)
---
 .../apache/dolphinscheduler/common/graph/DAG.java  |  9 ++++---
 .../dolphinscheduler/common/graph/DAGTest.java     | 30 ++++++++++++++++++++++
 2 files changed, 36 insertions(+), 3 deletions(-)

diff --git 
a/dolphinscheduler-common/src/main/java/org/apache/dolphinscheduler/common/graph/DAG.java
 
b/dolphinscheduler-common/src/main/java/org/apache/dolphinscheduler/common/graph/DAG.java
index 62d58efd1a..325cd182b2 100644
--- 
a/dolphinscheduler-common/src/main/java/org/apache/dolphinscheduler/common/graph/DAG.java
+++ 
b/dolphinscheduler-common/src/main/java/org/apache/dolphinscheduler/common/graph/DAG.java
@@ -24,6 +24,7 @@ import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.HashMap;
+import java.util.HashSet;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;
@@ -391,14 +392,14 @@ public class DAG<Node, NodeInfo, EdgeInfo> {
         }
 
         // Whether an edge can be successfully added(fromNode -> toNode),need 
to determine whether the DAG has cycle!
-        int verticesCount = getNodesCount();
+        Set<Node> visited = new HashSet<>();
 
         Queue<Node> queue = new LinkedList<>();
 
         queue.add(toNode);
 
         // if DAG doesn't find fromNode, it's not has cycle!
-        while (!queue.isEmpty() && (--verticesCount > 0)) {
+        while (!queue.isEmpty()) {
             Node key = queue.poll();
 
             for (Node subsequentNode : getSubsequentNodes(key)) {
@@ -406,7 +407,9 @@ public class DAG<Node, NodeInfo, EdgeInfo> {
                     return false;
                 }
 
-                queue.add(subsequentNode);
+                if (visited.add(subsequentNode)) {
+                    queue.add(subsequentNode);
+                }
             }
         }
 
diff --git 
a/dolphinscheduler-common/src/test/java/org/apache/dolphinscheduler/common/graph/DAGTest.java
 
b/dolphinscheduler-common/src/test/java/org/apache/dolphinscheduler/common/graph/DAGTest.java
index c0483cc187..c9d9db5c08 100644
--- 
a/dolphinscheduler-common/src/test/java/org/apache/dolphinscheduler/common/graph/DAGTest.java
+++ 
b/dolphinscheduler-common/src/test/java/org/apache/dolphinscheduler/common/graph/DAGTest.java
@@ -239,6 +239,36 @@ public class DAGTest {
         }
     }
 
+    /**
+     * test cycle detection with converging paths
+     */
+    @Test
+    public void testCycleWithConvergingPaths() {
+        clear();
+
+        // 1->2, 1->3, 1->4
+        // 2->5, 3->5, 4->5
+        // 5->6
+        // 6->7
+
+        for (int i = 1; i <= 7; ++i) {
+            graph.addNode(i, "v(" + i + ")");
+        }
+
+        Assertions.assertTrue(graph.addEdge(1, 2));
+        Assertions.assertTrue(graph.addEdge(1, 3));
+        Assertions.assertTrue(graph.addEdge(1, 4));
+        Assertions.assertTrue(graph.addEdge(2, 5));
+        Assertions.assertTrue(graph.addEdge(3, 5));
+        Assertions.assertTrue(graph.addEdge(4, 5));
+        Assertions.assertTrue(graph.addEdge(5, 6));
+        Assertions.assertTrue(graph.addEdge(6, 7));
+
+        // 7->1 would create a cycle, so it must be rejected
+        Assertions.assertFalse(graph.addEdge(7, 1));
+        Assertions.assertFalse(graph.hasCycle());
+    }
+
     @Test
     public void testTopologicalSort() {
         makeGraph();