[Bug] [common] DAG.addEdge may accept an edge that creates a cycle when paths converge

[nkuprins]

Search before asking

• I had searched in the issues 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:

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?

• Yes I am willing to submit a PR!

Code of Conduct

• I agree to follow this project's Code of Conduct