Background Knowledge

JavaScript (TypeScript)

This project is built in TypeScript which is pretty much JavaScript with (optional) type annotations. In fact, if you just write JavaScript there is a high chance that it will be valid TypeScript too (as long as you don't mind all the type warnings). TypeScript is developed by Microsoft. You can check out the official tutorial here.

0. Install a Local Copy

Make sure you can get a local copy of the site working on your computer. Follow the steps detailed in the main README page.

1. Pick Something

Pick an algorithm that you want to make a visualization for. One of the graph or tree algorithms covered in 2011 or 3101 are a good place to start. Th

2. Plan the Visualization

Make sure you understand what you want it to look like. Draw some pictures, look around on the internet, Wikipedia is often a good place to start.

3. Your TS Visualization File

This section will break down a typical TS (TypeScript) visualization file into multiple components to help you understand how to implement one for yourself. In this file, all of your visualization code will be written. Create it in src/algs and name it something like myVizTitle.ts.

Note: Your file will not compile unless it is included in visualizations.config.ts. Follow the example template at the top of the config file to include your visualization.

All components mentioned below should be included together in your file. For this tutorial we will be using the Tree Traversal visualization. See the full file in treeTraverals.ts.

Import Statements

Where classes and methods are imported from other files.

import {EdgeViz, NodeViz} from "../lib/components";
import {MultiTreeViz} from "../lib/structures";
import * as d3 from "d3";
import {Controller} from "../lib/gui";
import Queue from "../base/data-structures/queue";
import * as _ from "lodash";

A good IDE like IntelliJ IDEA will take care of this part automatically. So you can generally just forget about it.

General Setup

Instantiate your instance of StructureViz and a Controller.

let dimensions: number[] = Controller.getFullDimensions();      // full SVG dimensions
let treeViz: MultiTreeViz = new MultiTreeViz(dimensions[0], dimensions[1]);
treeViz.nodeRadius = 12;       // some specifications about the size of the tree

// Now that the structure has been created a `Controller` class can be instantiated
// The `Controller` class allows triggering animations, adding input features.
let ctrl: Controller = new Controller(treeViz);

Write the Algorithm

Now comes the hard part. Write the actual algorithm code (without worrying about the visualization, we will add that later).

Some tips before you start

Don't do it all yourself

Don't be afraid to look for help! Look around for existing implementations in JavaScript or TypeScript. We got permission from Loiane Groner to use her implementations of a bunch of algorithms and datastructures. They are located in the src/base/ directory. Even if you can't find the complete algorithm you are looking for, some of the more simple datastructures should be handy to build more complicated ones.

Don't over optimize

Your code doesn't need to be able to handle millions of entries. This means that you don't have to worry about the runtime happening behind the scenes. Don't be afraid to use arrays instead of trees or heaps if it is going to make your life easier.

// A simple node interface, doesn't store any values, up and down pointers only.
// Up pointers are only needed for the viz features
interface Node {
parent: Node,
children: Node[]
}

let time: number = 0;

function depthFirst(n: Node) {
time++;

// recursive call on the children
_.forEach(n.children, depthFirst)
}

That was easy! (If you are wondering what the _ is, it is a vey handy JavaScript library called Lodash which contains a lot of handy utility functions).

Uh oh! We don't have any trees to run our algorithm on! We better make a function for that too.

//
// Builds a random tree of size `nNodes`. Returns the root `Node` of the tree.
// @param nNodes the number of nodes to put in the tree
//
function buildTree(nNodes: number): Node {

let root: Node = {
parent: null,
children: []
};

for (let j = 0; j < nNodes-1; j++) {
let nodes = allNodes(root);

// pick a random node
let n = nodes[_.random(nodes.length - 1)];
addChild(n);        // and add a child
}
return root;
}

// Does a breadth-first traversal (oh! the irony) to extract all the nodes from the tree.
// @param root
function allNodes(root: Node): Node[] {
let q = new Queue();
let nodes = [];
q.enqueue(root);
while (q.size() > 0) {
let n = q.dequeue();
nodes.push(n);
_.forEach(n.children, c => q.enqueue(c));
}
return nodes;
}

// Adds a child to node `parent` 
// @param parent
function addChild(parent: Node) {
let child: Node = {
parent: parent,
children: []
};

parent.children.push(child);
}

Great! Now we can make trees and run our algorithm on them.

let treeRoot = buildTree(10);
depthFirst(treeRoot);

Now would be a good time to add console.log() statements to make sure that you made the algorithm correctly.

Add the Visuals

CSS Classes (Optional)

If you want things to really look nice (like multiple colours) you will need to define your own CSS classes (or use some from a previous visualization). This can be done in your TS file. Each component is made up a few SVG elements so make sure to specify which element you want to affect.

d3.select("#main").append("style").text(`
.new circle { fill: white; stroke: black;}

.active circle { fill: gray;}

.done circle { fill: black;}
.done text {fill: white;}
`);

Pseudocode

Adding pseudocode is super easy. First write it.

• Use backticks (`) to make the string sensitive to whitespace
• Use %% to denote a section ending which is used for dynamic pseudocode as explained below

  let depthFirstCode: string =
  `def depthFirstSearch(n): %%
  label n GREY
  for c in n.children: 
  depthFirstSearch(n) %%
  label n BLACK`;
  

  Then add it. treeViz.pseudo.newCode(depthFirstCode);.

Now we simply need to augment our existing calls with calls to our visualization structure. The main trick is to store the NodeViz instance in the actual Node.

Lines that start with a > have been modified.

interface Node {
parent: Node,
>   viz: NodeViz,       // IMPORTANT
children: Node[]
}

function buildTree(nNodes: number): Node {
// wipe out the tree in case it has anything already
>   treeViz.wipeOut();
>   treeViz.timeline = [];

let root: Node = {
parent: null,
>       viz: treeViz.addRoot(),
children: []
};

>   root.viz.toggleClasses(["new"]);

for (let j = 0; j < nNodes-1; j++) {
let nodes = allNodes(root);

// pick a random node
let n = nodes[_.random(nodes.length - 1)];
addChild(n);        // and add a child
}
// save the initial state of the tree and display it
>   treeViz.pushAndTransition();
>   ctrl.updateSlider();

return root;
}

function addChild(parent: Node): void {
let child: Node = {
parent: parent,
>       viz: treeViz.addChild(parent.viz),
children: []
};
>   child.viz.toggleClasses(["new"]);

parent.children.push(child);
}

Now we should be able to see the tree when the page loads.

Implementation, visualizations, transitions and states

The following is a brief description about how things work

Implementation and Visualization

There are 2 separate things working in a visualization, your implementation of the structure/algorithm and the Viz object. In order to separate concerns these 2 pieces are not inherently linked. This means that when you remove a node from your implementation it will not be removed from the visualization until you tell it to do so.

The most effective way of keeping things in sync is to store the NodeViz object within their corresponding nodes of your structure and when you change a node you also change the NodeViz.

States and Transitions

Any StructureViz object (a MultiTreeViz for example) always contains it full information about its structure and the information about the individual nodes. However, what is displayed does not always correspond to what that structure is. In order to support the viewing of the whole history of what happened, all the information needed to display the structure is stored in a state and all states are stored chronologically in a timeline. The animation is based soley off the state, this allows for displaying any state along the timeline without needing to change the internal structure of the StructureViz object. It also means that when something changes internally to StructureViz object this change is not displayed until instructed to do so.

To save the current state to the timeline call struct.pushState() at the end of the algorithm call ctrl.play(ms) and the states will play chronologically every ms milliseconds.

Dynamic Pseudocode (Optional)

To make it more understandable it helps to highlight the current lines being executed. To highlight a section before saving the state call treeViz.pseudo.setCurrentLine(line_number);. Numbers a lined according to the %% in the pseudocode. %% denotes the end of a section. Counting starts from 0.

With this knowledge, we can now edit our algorithm code.

function depthFirst(n: Node) {
// visual stuff
>   n.viz.toggleClasses(["new", "active"]);     // take off new, add active
>   treeViz.pseudo.setCurrentLine(1);
>   n.viz.label(time.toString());               // label with the time

// highlight edge connecting to parent
>   if (n != treeRoot) {
>       treeViz.getEdgeByNodes(n.parent.viz, n.viz).highlight();
>   }

time++;

// save state
>   treeViz.pushState();

// recursive call on children
_.forEach(n.children, depthFirst);

// leaving the node
>   n.viz.toggleClasses(["active", "done"]);
>   treeViz.pseudo.setCurrentLine(2);
>   treeViz.pushState();
}

Finishing Touches

Buttons

Use the method in the Controller class to add a button. The method accepts a function which is executed when the button is clicked.

ctrl.addButton("Depth First", () => {
treeViz.pseudo.newCode(depthFirstCode);
resetTree();

depthFirst(treeRoot);
ctrl.updateSlider();
ctrl.play(500);
});

Add Description

Add a brief description of the algorithm. The string is formatted using markdown format.

let markdown =
`## Tree Traversals
This page shows 2 basic traversals that can be applied to any tree.
The first is **Depth-First** which traverses down the tree first and the other is **Breadth-First**
which descends level by level.

Both algorithms take \`O(n)\` time to visit all the nodes.

Nodes change colour as they are visited and are labeled with the time they are visited.

Use the buttons on the top to select which traversal to use.`;
Controller.addVisualizationInfo(markdown);