Polyglot Code Offline Layout

Polyglot Code Offline Layout

The Offline Layout tool is a script to calculate the layouts used by the explorer - it runs offline as the layout algorithms are too slow to run in a browser. It uses a mixture of weighted Voronoi Treemap layouts and Circle Packing.

The source code is available at https://github.com/kornysietsma/polyglot-code-offline-layout

I use Franck LeBeau's d3-voronoi-treemap library - or more specifically, it's underlying d3-voronoi-map library - to do the Voronoi calculations.

What is a weighted voronoi treemap?

See Voronoi Treemaps for more

Why is this run offline?

There are two big problems with the libraries I am using:

  1. They are slow for big diagrams - sometimes quite painfully slow
  2. They are not always successful - sometimes initial positions never get a good solution.


The slowness might be improved in some cases with a lot of code optimising. But it might be somewhat inherent in the kind of layouts I'm using. Some source code directories are huge - and the Voronoi algorithms are iterative, and sometimes they take a long time to get a good solution.

I'd love to build a carefully optimised implementation - possibly in rust using WebAssembly - but it would be a lot of work - and even then, it might not be fast enough, and you'd need a lot of JavaScript work to do the layouts incrementally without blocking the browser.

So as I don't have time or brain space to do all this work, I decided to cheat. I use Franck LeBeau's code, but instead of running it in a browser, I run it offline using node.js, and save the resulting layout for use later in the browser.

Failures and bugs

The other problem is that the layout doesn't always find a solution. As of version 2.1.0 the main bugs that plagued me previously have been fixed - but still on occasion the layout throws a strange exception on encountering an edge case, or it just doesn't find a good solution. (The way the algorithm works is it defines starting positions for the algorithm randomly, and then iterates to find a solution - and sometimes those starting positions just don't work well.)

So my layout application runs the Voronoi algorithm in a loop - every time I start the loop, it uses different random starting points, so I keep going until I get a good enough solution - or if I have looped too many times, I give up and just choose the best solution I've seen so far.

This of course is even slower! In big codebases, recursively finding layouts can take over an hour. So again, better to do this offline than to try to squeeze it into a browser.

What are the downsides?

The biggest issue is that the layout can't change in the UI. You can't exclude files and re-draw the layout, or go back in time and re-draw the layout - whatever you got from this tool, you are stuck with. So you can't (say) decide to exclude all XML files in the UI - if you decide you want to show source but not data, you need to re-run the initial scan with an ignore file and then re-calculate the layout from scratch.

Also sometimes the result still isn't quite accurate. The layout doesn't always converge to a perfect result. It's probably good enough for most purposes - but it's not always quite right. That's why I still have a visualisation that highlights file size, so you don't have to trust your eyes.

Have you considered other algorithms?

I tried rectangular treemaps first - I don't like them much.

I'd love to try a Gosper treemap just because I love fractals. If I find the time. It might also solve the speed problem - but it's not as easy on the eyes for a deeply nested tree as the Voronoi layout, I tend to think.

Edit this page on GitHub