Community
Participate
Working Groups
In certain cases, edges with virtual nodes are not properly handled during the layout process. They are never uninverted and thus *point* in the wrong direction. I realize that the plan is to eventually eliminate the use of VirtualNodes during graph layout (Bug 72201), but the following modification could be made to fix the bug until that virtual node change is made. Explanation of what is causing the bug and my fix: org.eclipse.draw2d.graph.DirectedGraphLayout calls visit() for each of 11 different layout classes, and then calls revisit() for each of those same 11 layout classes, but in the reverse order. In order to break cycles, the first visit method inverts edges so that they all 'point' in the same direction (so that there isn't an A->B edge and an B->A edge) and sets edge.isFeedback on all the inverted edges. After ranks are assigned (during InitialRankSolver, TightSpanningTreeSolver, and RankAssignmentSolver), PopulateRanks.visit() adds VirtualNodes for all edges that span multiple ranks. However, when PopulateRanks.visit() calls VirtualNodeCreation(), the isFeedback setting is not preserved, so inverted edges with virtual nodes are never uninverted. That was the *bug*. Fixing it is more involved than simply preserving the isFeedback setting, because Draw2D does not provide a means to correctly invert edges with virtual nodes. Thus, for InvertEdges.visit(), it is necessary to NOT invert edges whose source or target is a VirtualNode, and TO unset isFeedback for those that can be inverted. Then, at the very end of the list of classes when they are re-visited, during BreakCycles (which formerly didn't have a revisit() method), we invert all the edges which still have isFeedback set. These are all the edges that had been inverted and had VirtualNodes inserted (and thus were not un-inverted during InvertEdges.visit()). We've seen this bug occur with as few as 3 nodes and 4 edges. E.g., nodes A, B, C, and edges A->B, B->A, B->C, C->A. I've tested this fix with some rather complex graphs, and in every case thus far it has fixed the problem without introducing any new ones. The modified draw2d code is used by many others as well. The files needing modification are BreakCycles and InvertEdges in org.eclipse.draw2d.internal.graph. In BreakCycles I've added an override for method revisit. I'll be attaching modified versions of these 2 files.
Created attachment 35274 [details] BreakCycles.java The modified version of BreakCycles includes the revisit() method, as described above.
Created attachment 35275 [details] InvertEdges.java This version of InvertEdges modifies the if statement in the visit() method.
Isn't is possible for the consumer of the virtual edges to look at the isFeedback flag, and reverse a copy of the list?
Thanks for the patch and description of the changes. Could you also describe only the symptom of the bug, and let us know whether this behavior is different than the 3.1 release? Thanks.
Is this behavior different from the 3.1 release? The behavior is the same. We started using 3.1 in August, found the bug in September, and upgraded to 3.1.1 in October. The symptoms? I'm not sure that our particular symptoms will be very meaningful to you. A null pointer exception occurs when we try to update our view based upon the graph. Tracing things back, I eventually found that the problem occurred during the layout when visit(graph) is called. People may not typically notice this problem because the edge is there, it just points in the wrong direction (if arrows are shown). But because our particular implementation (a dataflow graph) depends on the direction of the graph edges, it causes a failure (as it should be!) and prevents the graph from being displayed.
By symptoms, I mean what is actually changed by your patch? Is it just the ordering of the vNodes?
I see that CompoundBreakCycles has a revisit method. I'm not sure why BreakCycles doesn't. Also missing, is reversing the new points field added to Edge. I've added code in Edge#invert() to reverse the points. This required swapping RouteEdges and BreakCycles order, since RouteEdges needs to run while the edge is downward orientation. I'm going to release the changes to invert() and the reordering of visitors, but this won't do anything to the results of the layout yet.
What this patch does: During InvertEdges.visit(), edges with virtual nodes are _not_ inverted, isFeedback is set to false for all edges which are inverted. Then when BreakCycles.revisit() is called, at that point the edges no longer have virtual nodes and can be properly inverted. Only the edges which formerly had virtual nodes still have isFeedback set, and these edges are now inverted. (The ordering of the vNodes is not changed.) Another possible solution, as we both have mentioned, is to implement inversion for virtual edges which would involve re-ordering the vNodes, etc. That might provide cleaner code with fewer special cases for virtual nodes, which would be preferable.
When InvertEdges runs, there are no edges with virtual nodes anywhere. All edges have been converted to "simple" edges at that point. I think the solution is to remove the InvertEdges visitor completely. We can now handle this in BreakCycles#revisit(). Revisiting was added after InvertEdges was created, I believe.
I only learned enough about that draw2d graph code to make a work-around. Whatever you do for the fix sounds good to me. Thanks!
