In this assignment, you will write code to build a visualization of hierarchical data using a technique known as treemaps. Your main focus will be on designing a variety of different layouts to visually encode data that can be represented as a tree.

Please click here to create your repository

Objectives

This assignment is designed to teach you the basics of using space-partitioning to representing hierarchical data. Specific objectives include:

  • Implementing a treemap view suitable for visualizing data hierarchies using containment
  • Practicing implementing tree traversals in Javascript to compute geometric representations.
  • Experimenting with visual encoding for treemaps
  • Understanding the relationships and limitations of using size and area to encode hierarchies.
  • Further practice in d3, particularly on computing and setting properties for rectangles.

Description

Note that d3 offers native support for this kind of visualization, the goal of this assignment is for you to actually write the main part of this algorithm. Because of this, for this assignment, you are not allowed to use d3.layout.treemap, nor should you try to use existing d3 code to compute the layout. The skeleton code we’ve provided structures this computation in a slightly different way.

Please also see this paper for the original reference from Ben Shneiderman for additional details.

In this assignment, you will create a treemap visualization suitable for looking at hierarchies. We’ve provided a dataset known as the Flare dataset, which contains a hierarchy representing the directory hierarchy and files for a software library of the same name (courtesy of Jeff Heer). This dataset is stored in the flare.js file. You can see this particular dataset visualized in Mike Bostock’s Treemap Block.

Additionally, in the test-cases.js file, you’ll find two simpler trees that will be useful for testing your implementation. I’ve included a directory of screenshots (at a resolution of 1600x800) for both the test cases as well as the Flare dataset visualized using a variety of different layouts.

Part 1: Implementing the Basic Treemapping Algorithm

The basic treemapping heuristic draws a tree by progressively splitting a rectangle along vertical and horizontal lines such that the areas of the rectangles correspond to the weights of the subtrees. You will first implement the heuristic in its basic form, where the splits at any level are chosen along alternating directions. This is called the “slice-and-dice layout” as you alternative between slicing and dicing. Since our computer screens are usually wider than tall, start by splitting the first rectangle along the \(x\)-direction. The second level splits should be along the \(y\)-direction, and so on.

To implement this variant, in the skeleton code you’ll need to implement three components. First, you’ll have to implement the function setTreeDepth() which should add the variable depth to each node of tree as well as return the maximum depth. This function should be similar to setTreeSize() and setTreeCount(), both of which store additional information in the tree. You will use the depth of a given node to decide whether or not it is a horizontal or vertical split.

Second, you’ll finish the implementation of setRectangles(). This function should set the variable rect for each node in the tree. This code is currently set to store the minimum and maximum \(x\)-value (x1, x2) and the minimum and maximum \(y\)-value (y1, y2) for each rectangle, but you are allowed to change this if it is more convenient to store different information necessary to draw the rectangles. Note that setRectangles() is coded generically to compute the area of the rectangles using either count or size through the accessor attrFun().

Finally, you’ll implement the function setAttrs() which is used to set the visual attributes of each rect. This should use all of the information that you’ve inserted in the tree through the four “set” functions.

Part 2: Improving the Visual Representation

After getting the basic treemap up you should try to improve your visualization as much as possible to display information about the tree. Specifically, you are required to implement, at a minimum, the following two features:

  1. First, you should add margins to each rectangle to better depict the nested hierarchy. To do this, you should shrink the rectangles a small amount at each level of the tree. Note that there is a variable border in setRectangles() that you might want to use for this.

  2. Second, you should use a fill color to depict where a node occurs in the hierarchy. To do this, you can set the color based on the depth using an appropriate color scale.

Besides the above two features, you may want to consider additional visual features that could encode information about the tree. Any extra features should be documented in the README and are eligible for extra credit.

Part 3: Implementing the “Best Direction” Cutting Approach

The basic treemapping algorithm chooses a fixed direction for every tree node based on depth. This causes relatively uneven shapes, and makes it hard to read areas. A simple improvement is to have the layout algorithm choose, at every level, the direction of the cut along the longest dimension of the rectangle. If the rectangle is tall, we cut it horizontally. If the rectangle is wide, we cut it vertically.

You should implement this approach, and add 2 buttons to index.html with ids, respectively, best-size and best-count that will transition the rectangles to a layout using this approach. You will add new callbacks at the end a04.js to react to these buttons. Your visualization should allow for transitions between any of the four possible layouts.

Part 4: Squarified Treemaps

There are many other ways to perform layouts for treemaps. Many of these layouts cause relatively uneven shapes and make it hard to read areas. The squarified treemap tries to solve this deficiency by making nodes that are as close as possible to being square. To do so, it breaks the pattern of choosing a single direction to split each node.

See this paper by Bruls, Huizing, and van Wijk for a description of the algorithm squarified treemaps. For this version, add 2 more buttons with ids, respectively, square-size and square-count to switch the layouts to the squarified size layout and squarified count layout. You can then either modify how setRectangles() is called, or create a second function to implement the squarified approach that is called by these new buttons.

Written Questions (worth 25/90 points)

  1. Explain the differences between a sequential color map and a diverging color map. For the data visualized in this assignment, which (if either) would you prefer and why?

  2. One version of zooming on a treemap might be to click on a node and resize the layout to only show the associated subtree rooted at that node (see an example of treemap zooming on Observable). Would this sort of interaction help address some of the limitations in your visualization? Does it come with any deficiencies?

  3. Give one scenario where treemaps are a better choice for visualizing hierarchies compares to node-link diagrams. Give one scenario where node-link diagrams are the better choice. Explain why for both.

Submission

You should use git to submit all source code files. The expectation is that your code will be graded by cloning your repo and then executing it within a modern browser (Chrome, Firefox, etc.)

Please provide a README.md file that provides a text description of how to run your program and any parameters that you used. Also document any idiosyncrasies, behaviors, or bugs of note that you want us to be aware of.

To summarize, my expectation is that your repo will contain:

  1. A README.md file
  2. A index.html file
  3. An a04.js file
  4. All other Javascript files necessary to run the code (including flare.js and d3.js plus any others you require)
  5. Any .css files containing style information

Grading

Deductions

Reason Value
Bugs or syntax errors Up to -10 each bug at grader's discretion to fix


Point Breakdown of Features

Requirement Value
External documentation (README.md) following the template provided in the base repository 5
Consistent modular coding style, indentation, etc. 5
Header documentation and internal documentation (Block for functions and Inline descriptive comments). Wherever applicable / for all files 5
Expected output / behavior based on the assignment specification, including

Correctly computing tree node depth for Part 15
Correctly computing rects within setRectangle() for Part 110
Correctly setting the rectangle attributes (x,y,width,height) in setAttr() for Part 15
Correctly shrinking the rectangles with margins for Part 25
Correctly setting the fill color based on depth for Part 25
Correctly implementing the best direction cutting approach for Part 310
Implementing squarified treemaps for Part 410

 50
Written Questions

Written Question 15
Written Question 210
Written Question 310

 25
Total 80


Cumulative Relationship to Final Grade

Worth 9% of your final grade

Extra Credit

Implementing features above and beyond the specification may result in additional extra credit, please document these in your README.md.

The basic skeleton you implement for this visualization leaves much to be desired with respect to being informative. You may want to augment your visualization to include more information about the contents of the tree for extra credit.

Many variants of treemap layout algorithms exist and you might want to consider looking into these. In addition, many implementations include more sophisticated interactions (such as zooming discussed in the written questions). These alternatives can help the user see the hierarchical structure in more detail rather than just providing a single view of an entire tree.