I'm currently trying to implement a treemap algorithm in Javascript. More specifically the algorithm described in Squarified Treemaps. The pseudo code given looks like the following:

procedure squarify(list of real children, list of real row, real w)
begin
    real c = head(children);
    if worst(row, w) <= worst(row++[c], w) then
        squarify(tail(children),row++[c], w)
    else
        layoutrow(row);
        squarify(children,[], width());
    fi
end

however my JavaScript looks like:

var c = children[0];
if (worst(row, w) >= worst(row.concat(c), w)) {
    this.squarify(children.splice(1), row.concat(c), w);
} else {
    layoutrow(row);
    this.squarify(children, [], width());
}

As far as I can tell my code works correctly, but the inequality is the wrong way around. I'm assuming I'm overlooking something in my implementation, or is the inequality the wrong way around in the pseudo code? Thanks

I'm currently trying to implement a treemap algorithm in Javascript. More specifically the algorithm described in Squarified Treemaps. The pseudo code given looks like the following:

procedure squarify(list of real children, list of real row, real w)
begin
    real c = head(children);
    if worst(row, w) <= worst(row++[c], w) then
        squarify(tail(children),row++[c], w)
    else
        layoutrow(row);
        squarify(children,[], width());
    fi
end

however my JavaScript looks like:

var c = children[0];
if (worst(row, w) >= worst(row.concat(c), w)) {
    this.squarify(children.splice(1), row.concat(c), w);
} else {
    layoutrow(row);
    this.squarify(children, [], width());
}

As far as I can tell my code works correctly, but the inequality is the wrong way around. I'm assuming I'm overlooking something in my implementation, or is the inequality the wrong way around in the pseudo code? Thanks

• javascript
• algorithm
• pseudocode
• treemap

• Perhaps the flaw is in your implementation of worst(). – gilly3 Commented Mar 26, 2012 at 22:56
• 3 Thanks for the feedback. I've looked fairly closely at my implementation of worst, and as far as I can tell it does return the worst ratio correctly. Interestingly a blog post appears to have the inequality the other way, so I'm starting to suspect the pseudocode is incorrectly. – Floating Octothorpe Commented Mar 26, 2012 at 23:05
• Sorry, should have read the blog post, not just the code. It does indeed look like the inequality is the wrong way around. – Floating Octothorpe Commented Mar 26, 2012 at 23:07

2 Answers 2

You want to add c to the current row when doing so will improve the aspect ratio i.e. when

worst(row++[c], w) < worst(row, w)

I've recently mitted a piece of code on github that implements the algorithm in TypeScript and includes ready-to-use JavaScript:

https://github./nicnguyen/treemap

If you're only interested in the layout algorithm, check out my squarify npm package. It returns the layout data only, leaving you free to render the result however you want.