Weekend fun: Treemaps in Erlang

[Joel Reymont]

Here's an assignment for those who want to play along...

This shows what treemaps are:

http://blog.tupleshop.com/2006/7/27/treemap-on-rails

This gives the background:

http://www.win.tue.nl/~vanwijk/stm.pdf

And this is the Ruby implementation:

http://rubyforge.org/projects/rubytreemap/

There's not a lot of code but it's heavily object-oriented and
destructive.

How do we translate it to Erlang?

As a bonus, I'll do a Nitrogen demo showing a treemap of Flickr
photos, once we have a working implementation.

What do you think?

--
http://wagerlabs.com

[Denis Laprise]

Love that approach. In fact that's the only way to learn.
Just not sure where's the hierarchy in the flickr dataset? Photos by Tags?
D

[Joel Reymont]

No need for a hierarchy for now. Just arranging, say, flowers in an
irregular grid will do.

Sent from my iPhone

[Eli Liang]

Where should our solutions go?

[Joel Reymont]

On Dec 6, 2008, at 5:03 PM, Eli Liang wrote:

> Where should our solutions go?

Paste them here until we have a code review tool.

Alternatively, set up a GitHub repo and post the link.

--
http://twitter.com/wagerlabs

[Joel Reymont]

Who is actually going through this exercise this weekend?

[Eli Liang]

This Padawan started, but found that he is too weak in the Erlang for this exercise. Maybe you can have some baby-steps exercises sometimes for us beginners. (Sort of like those puzzles that go in the comics sections of the newspapers! :-) )

[Joel Reymont]

On Dec 7, 2008, at 3:25 PM, Eli Liang wrote:

> This Padawan started, but found that he is too weak in the Erlang
> for this
> exercise. Maybe you can have some baby-steps exercises sometimes for
> us
> beginners. (Sort of like those puzzles that go in the comics
> sections of the
> newspapers! :-) )

I would suggest modeling objects as processes initially. The process
would hold the object fields in its internal state and accept requests
to fetch and modify the field values. Create an object by creating a
process.

You can also implement the clone message by having your object
duplicate its current state (easy in Erlang) and launch a new process
with that state.

Does this help?

--
http://wagerlabs.com

[Eli Liang]

Alright then. Let me work on it some more.

 

So is the objective to entirely transliterate the Ruby code into Erlang code? Or to implement a minimal treemapping algorithm in Erlang ala Ben Schneiderman (who happened to be one of my professors at the University of Maryland a quarter of a century ago)? Looking through the Ruby code, it seems to do a bunch of additional stuff not central to the treemapping algorithm.

 

Could you give an example of the API or contract ( http://en.wikipedia.org/wiki/Design_by_contract ) you are seeking? That might help me to gel my thinking if I knew what the input/output is.

 

Sorry, if this seems really elementary, but I'm a bit slow these days with anything involving programming.

[Eli Liang]

BTW, is there a better cheat-sheet to Ruby than this http://refcardz.dzone.com/refcardz/essential-ruby for those who have never read/written any Ruby before?

[Joel Reymont]

On Dec 7, 2008, at 3:53 PM, Eli Liang wrote:

> So is the objective to entirely transliterate the Ruby code into
> Erlang
> code? Or to implement a minimal treemapping algorithm in Erlang ala
> Ben
> Schneiderman (who happened to be one of my professors at the
> University of
> Maryland a quarter of a century ago)?

Implement a squarified treemapping algorithm to display beautiful
Flickr photos in an irregular grid (treemap). I just found the Ruby
implementation to be the easiest to grasp.

The pseudocode is given in the paper but, I'll be honest, I don't know
how to implement the row layout :-).

--
http://wagerlabs.com

[Joel Reymont]

You can safely ignore Ruby and we can all improve on your
implementation according to the squarified treemap paper.

On Dec 7, 2008, at 4:03 PM, Eli Liang wrote:

> BTW, is there a better cheat-sheet to Ruby than this
> http://refcardz.dzone.com/refcardz/essential-ruby for those who have
> never
> read/written any Ruby before?

--
http://wagerlabs.com

[Eli Liang]

OK. I'm working on it then! But don't set your expectations too high; it's never good to rely on the Padawan. ;-)  (I hope there is someone on this list working on the "master's" implementation!)

[Eli Liang]

OK. I've read the paper. But I'm a weak on Flickr, since I never use it, although my wife has. I assume that Flickr holds photos of an arbitrary rectangular size, scaling as needed to fit each photo within it's own display constraints. If this is the case, having now fully understood the algorithm for squarifying treemaps, I don't see how it will solve the Flickr problem (tessellating photos).

Let me explain myself.

The Bruls-Huizing-Wijk (BHW) algorithm takes a numerical list of values and an arbitrary rectangle, and then squarifies that arbitrary rectangle by subdividing it into component rectangles with areas equal S(i) where S(i) = value of a given element i * area of the original arbitrary rectangle / sum of all element values, such that each component rectangle has a "somewhat" low aspect-ratio.

The problem is that the result of the BHW algorithm is a set of positioned component rectangles each with a certain aspect ratio which is derived by the BHW algorithm.

In the case of Flickr photos, there is not just one parameter per photo (i.e. area), but there are two parameters (i.e. both area and the ratio of height/width). In fact, area is not an important parameter at all, since area can be scaled for individually for each photo, only affecting its resolution. This makes the ratio of height/width the most important parameter input parameter. However, since aspect ratio of each component rectangle is not an input parameter but is an output of the algorithm, there is never any guarantee that any of the component rectangles that result from executing the algorithm will have the same aspect ratios of any of the input photos. Also, by the nature of the algorithm, the resulting component rectangles will have aspect ratios that range from 0.5 to 2.0.

This is because the BHW algorithm does not try to fit a predefined set rectangles into a larger rectangle.

So as an example, if we started with 3 Flickr photos, the first which is 10(H) x 30(W), the 2nd which is 25(H) x 6(W) and the 3rd which is 5(H) x 20(W) and asked this to be fit in a 165(H) x 220(W) frame, scaling as needed, then the following would result from running the BHW algorithm using the respective areas of each photo as the values of each element of the input list.

INPUTS to BHW algorithm:

Input list = (300, 150, 100)

List of height/widths = (0.333, 4.167, 0.250)

Original framing rectangle = 165(H) x 220(W)

OUTPUTS of BHW algorithm:

Component rectangle #1: 165(H) x 120(W), aspect ratio = 1.375

Component rectangle #2: 99(H) x 100(W), aspect ratio = 0.990

Component rectangle #3: 66(H) x 100(W), aspect ratio = 0.660

In this example, none of the resulting aspect ratios (1.375, 0.990, 0.660) are close to the ratios of height/width of the 3 starting photos (0.333, 4.167, 0.250), so none of them would fit well into any of the component rectangles, even if they were individually scaled.

If we are looking to tessellate arbitrary photos, then we need something other than the BHW  algorithm to do it.

[Joel Reymont]

Eli,

On Dec 7, 2008, at 9:33 PM, Eli Liang wrote:

> OK. I've read the paper. But I'm a weak on Flickr, since I never use
> it,
> although my wife has. I assume that Flickr holds photos of an
> arbitrary
> rectangular size, scaling as needed to fit each photo within it's own
> display constraints.

Thank you for your in-depth explanation. Perhaps my use of Flickr was
misguided but I still think the algorithm could be useful for other
things, e.g. visualizing disk space or code coverage.

If the exercise is not as fun as I thought (not many takers, huh?)
then let's move on to something else!

--
http://wagerlabs.com

[Eli Liang]

I think the BHW algorithm could be useful for graphically representing anything which can be represented by a unordered set of scalar values. e.g., comparing sizes of countries in the world, etc.

Since I've spent time reading the paper, I'm going to try to implement it (or at least the algorithm itself) in Erlang. (This is where my programming ineptness will show!)

[Joel Reymont]

On Dec 7, 2008, at 10:40 PM, Eli Liang wrote:

> Since I've spent time reading the paper, I'm going to try to
> implement it
> (or at least the algorithm itself) in Erlang. (This is where my
> programming
> ineptness will show!)

Don't worry, it's a rough draft that we'll improve on!

--
http://wagerlabs.com

[Eli Liang]

I haven't forgotten this. I'm still working on it in my spare time today. It's pretty simple, but I think there was a bug in the BHW paper that I'm trying to figure out right now. It might take another day or so for this poor padawan to get it together in a working Erlang form.

...but the important thing is that I'm having fun! :-)

BTW, this exactly ties into something I want to do in Erlang. Which is to implement an extensive library of traditional and modern data structures and algorithms (red-black trees, generalized tries, splay heaps, etc.)