Guidance on Implementing Radial Drawing with d3-dag's Sugiyama Algorithm

[benzproduction]

Hello there,

I am exploring the capabilities of the d3-dag library, and I am particularly interested in understanding whether it is possible to leverage the Sugiyama algorithm to create a radial drawing of a graph.

I came across a resource that illustrates what I have in mind; a visualization and explanation of a radial drawing approach can be seen in Fig. 1 of this document.

Could you provide guidance on whether this is possible using the d3-dag library? And if so, what layout tweaks would be necessary to achieve a radial drawing as described in the referenced document?

Thank you for your time and assistance!

[erikbrinkman]

Hey @benzproduction,

Skimming the paper, it seems like the whole paper fits within the sugiyama framework, so it should be possible to tweak every aspect to replicate the paper. The nice part about the way I implemented everything is you should be able to do this gradually.

I'll go through the sections of the paper and talk about what it would take to implement them, but the way I would start is just implement the first radial transform, which should, and see how it looks. Then depending on how it looks bad, consider the other techniques.

• V.D (easy/necessary): This is where you turn the normal layout into a radial layout, and should be a pretty trivial transformation. IF you were to implement this in the framework, it'd be a Tweak, but essentially you're just post-processing all of the assignments.
• III (easy): This section refers to better layering so that more nodes are positioned at the edge. They mention using longest path layering, which you can enable using d3dag.sugiyama().layering(d3dag.layeringLongestPath()).
• III (medium): The better way to handle layering is with a modified coffman-graham. This was removed from d3-dag for a number of reasons, and you'd need to do the modification anyway, but the solution is to implement a custom Layering operator. A version of the old coffman-graham code is here, which may help. Since you only need to modify some old code slightly, I imagine it'll be a little easier.
• IV (medium/hard): This section proposed three different heuristics for crossing reduction. The key problem this solves is that the current methods don't know that wrapping around the outside doesn't count as a crossing. If you're finding a lot of weird edges at the border, this is the problem. I haven't gone over them, so I can't really assess how hard they are to do. Since this covers decrossing, you'll need to implement a custom Decrossing operator.
• V: (medium/hard) The rest of this section (minus the part of above) concerns coordinate assignment, and should be handled by a custom Coord assignment operator. Without really reading it, it's hard to see how difficult that will be. Similar to above, you could end up with weird edges at the boarder, and this might be the solution, but a more likely scenario is that edges look a little a squiggly near the boundary, so this is probably the lowest priority.

Hope this helps, always down to answer more questions, or take PRs on the stuff that works

[erikbrinkman]

I read through the paper. I missed a few things, and have a little more information on difficulty:

• IV: It seems like doing radial crossing reduction properly involves storing φ, which technically you can't. However, this is javascript, so you should be able to hackily either add a property, or store a Map from links to number used across functions if you really need it.
• IV.B (easy): This is essentially just a version of twolayerAgg, but with the barycenter method. You may need to get access to the total number in the layer above, so you might not be able to use twolayerAgg directly, and instead will need to implement a similar Twolayer operator.
• IV.C (easy): This is the same as above, but with median instead of mean, same as using twolayerAgg with aggMedian vs aggMean.
• IV.D (hard): This is ultimately similar to what's implemented in twolayerGreedy, but for a number of reasons they lay out, is much more complicated. The author says they implemented it in java, so that might help, but this is probably not worth doing unless there are a lot of crossings over a cut that you need to get rid of.
• V:B (hard): I should probably implement the Brandes/Kopf coordinate assignment (although it's unlikely) and implementing yourself is probably quite the ordeal. I imagine the default Simplex assignment will work well enough, but will have problems with cut edges.
• V: (medium): The built-in simplex method should hopefully be an 80% solution. But you could probably make it better by implementing custom weights depending on the node level, because nodes with a high level will be much father apart for the same coordinate distance.
• V (hard): There's also no implementation of UNWIND-LEVEL, it's not clear how important this is, but might in volved some effort.
• V (easy): I neglected how you'll have to curve the edges themselves. The easiest way to do this is probably to use the same barycenter method. Essentially take every pair of adjacent control points, and add a new control point that's level (e.g. distance from the center) is half way, and it's angle is also bisected in half. This should create the same curves as in the paper (when using d3 splines), and will prevent some wonky behavior for some edges.

There was a time when I would rush into implementing this because I thought it was cool, but I generally don't have time anymore (which is why this is in semi-archive state). If you do get things working, I'd love to try and incorporate what you do, but I don't have time to implement and test from scratch. Also, if you run into roadblocks, or are unsure where to look for something, I'm happy to give pointers. I tried to give as much info in the documentation for implementing custom parts of the layout, but I never know how effective they are.

Good luck!

[benzproduction]

Hey @erikbrinkman,

First of all: Thank you very much for your very detailed and very fast response. I truly appreciate the depth and thoughtfulness that went into breaking down the potential routes to implement the radial layout as described in the paper.

At the moment, the project I am working on is a side project and hence, I haven't had the time yet to delve into implementing the techniques you mentioned. However, I am optimistic that I will find the time in the coming days/weeks to start working on it.

Interestingly, in the interim, I initiated a test with a radial force-directed tree (native d3), which is quite promising and somewhat mirrors the outcome I envisage. This has put me in a bit of a dilemma regarding the necessity of translating the algorithms to JavaScript, considering the encouraging results from the preliminary test. That being said, I am keen to at least give the radial layout tweak a shot to have a more rounded perspective before making a final decision. The decision will predominantly be influenced by aspects such as performance and the feasibility of integrating it with Next.js.

I certainly intend to keep you updated as I progress, and would be more than willing to share the tweak and any other pertinent points here, providing a starting point for others who might be interested in exploring this avenue. Your willingness to guide and offer pointers is genuinely encouraging and I look forward to potentially working closely, albeit asynchronously given the side project nature of this initiative, as I delve deeper into the implementation.

Best regards!