Explaining the squarified treemap algorithm from Glamorous Toolkit
As part of the visualization support, Glamorous Toolkit
offers an implementation of a squarified treemap. The algorithm is responsible for creating visualizations such as this one:
The implementation is captured in
and a few adjacent helper classes. But how does it work?
One way to answer the question is to read the code. However, this particular algorithm was already published previously inSquarified Treemaps, Bruls etal, 2000
, a paper that starts with the following abstract:
"An extension to the treemap method for the visualization of hierarchical information, such as directory structures and organization structures, is presented. The standard treemap method often gives thin, elongated rectangles. As a result, rectangles are difficult to compare and to select. A new method is presented to generate layouts in which the rectangles approximate squares."
The paper details the algorithm in several ways, but the core of the explanation is based on this depiction showing the steps that the algorithm takes for a specific input.
The example in the picture is about laying out nodes with the following weights #(6 6 4 3 2 2 1). The whole idea of the algorithm is to choose subdivisions that preserve the desired ratio. The diagram shows both the accepted and the rejected choices.
This picture is worth a thousand words. Of course, the primary intent of implementing an algorithm is to get to the final result. But our goal is not only to produce a functional system. We want an explainable system. The rule of thumb is that if a human deems a representation as meaningful, it should be the responsibility of the system to carry it forward.
So, naturally, we want our implementation to offer this kind of view, too.
In our case, when we inspect an instance of
, we see the picture showing the steps as in the paper! This picture is available as a custom view (see the Steps Figure view below):
Once the algorithm object knows how to present itself, we document the code through examples that give us interesting algorithm objects. For example, the object inspected above was produced in
GtGraphTreemapLayoutExamples >> #squarifyWithSevenNodes