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. 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 a08.js to react to these buttons. Your visualization should allow for transitions between any of the four possible layouts.

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 a08.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 -10 each bug at grader's discretion to fix


Point Breakdown of Features

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

Correctly computing tree node depth for Part 110
Correctly computing rects within setRectangle() for Part 120
Correctly setting the rectangle attributes (x,y,width,height) in setAttr() for Part 110
Correctly shrinking the rectangles with margins for Part 215
Correctly setting the fill color based on depth for Part 210
Correctly implementing the best direction cutting approach for Part 315

 80
Total 100/100


Cumulative Relationship to Final Grade

Worth 6% 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.

Squarified Treemaps (worth up to 40% extra credit)

In addition to augmenting the visualization to include more information about the contents of the tree, there are many other ways to perform layouts for treemaps. You may want to consider experimenting with these for extra credit.

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. 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.