Drawing a hierarchical tree: treemapping

Question

Hello,

I'm trying to develop a view of a hierarchical tree in which the weight of each node is the actual number of children it has. A leaf node has weight 1.

I want to arrange these items in a way they can be browsed going deeper into the tree by showing the root categories (with no parent) at the beginning. Clicking on a node makes the view repaint iself to show just children of that node.

The tricky part is that the size in pixel of a node should be proportional to its weight compared to adjacents nodes. According to wikipedia this is called treemapping and what I need is a tiling algorithm, I was trying to figure out by myself but it seems more complex that I expected..

To give you an example there is a program for Mac Os X called GrandPerspective that shows folder sizes of your HD:

I want to arrange nodes in a way like this! (of course size is proportional to folder size)

Any suggestions?

Thanks

Answer 1

The data structure used in the file system example you show is most likely a KD tree. I'm not exactly sure how well the problem you want to solve maps to the file system example but this is how I would go along solving the file system case myself:

You start with a rectangle representing the root of the hard disk. You take all files and directories in the directory and give them a size.

1. For files the size is the size of the file
2. For directories, the size is the the complete size of all files it contains (including all its subfolders, and their subfolders and so on).

Now you try to cut this list into two as equally sized lists as possible. Now you cut the input rectangle into two rectangles that has the same size proportions as the two lists you cut the input files into. You should make the cut along the axis that is shorter of the input rectangles size to make sure you always have as quadratic as possible rectangles. Now you run the algorithm recursively on the two lists with their corresponding rectangle.

The base cases would be:

1. There is only a single file in the list. You then fill the rectangle with the color of the file type.
2. There is a single directory in the list. For this case you run the algorithm recursively on the contents in the directory inside the rectangle.

Choosing how to split the lists into two as equally sized parts as possible may not be trivial (is it a knapsack?). A decent heuristic approach would probably be to sort the list in descending order and take the elements out of the list and put it in the currently smallest of the two resulting lists.

EDIT: The splitting problem is called partition and is a special case of knapsack. It's covered in this thread here on SO.

Answer 2

That's a squarified treemap. You can read the paper explaining this technique.