Introduction
In this tutorial, you will learn the difference between trees and graphs and how they can be used together in Thinkmap.
This examples uses two trees that move in the opposite direction from a shared root. Typically, when using two trees, one tree is used for exploring the children and descendants of the root, while the other tree is for moving up the hierarchy. Although this movie data is by no means hierarchical, we can still demonstrate this behavior by only advancing movies and genres in the left tree, and movies and people in the right tree.
Getting Started
In this example, both trees can be expanded by simply clicking each node in the graph. When clicking entities in the right tree (movies & people) any entities from the left tree that are shared between the two are moved to the right tree. When expanding the left tree, any entities shared with the right tree are simply ignored and not added to the left tree.
This example also allows you to center on any movie by 'shift-clicking' the movie entity.
In addition to the above, you can isolate which tree to view with the drop down menu. Notice that upon expanding both trees and toggling the view, that certain edges remain while others are removed. We will cover why this happens through this tutorial.
If you view the source of this page,
you can see the code that makes up this example in its entirety. You will notice that we are linking to two important source files:
The first file is the thinkmap.js file for your project. The second file trees-graphs.js contains
the code for this example, which we will now discuss.
Graphs and Trees in Thinkmap
Graphs are the central underlying concept behind Thinkmap. Mostly everything is considered a graph, including displays and trees. A graph contains nodes (vertices) and edges (arcs) which connect two nodes. There are no restrictions placed within a graph. A node can have 0 or more edges, and any two nodes can be connected by several edges.
A tree is a special type of graph that maintains a strict hierarchical structure. Every tree has a root which is the top most node of the hierarchy. A great example is to think of a file system, with there being a single top level directory from which all folders are a descendant. Another example would be an organization chart, where the root would be the CEO, and all the directors, bosses, and employees descend down the tree.
Although graphs can have multiple edges between the same two nodes, a tree, by definition, cannot allow this. There can be only one edge connecting two nodes. Furthermore, in a tree, an edge can only connect a parent to its child. Edges between other ancestors, descendants, and siblings are not allowed as this breaks the definition of a tree. The moment an edge connects more than just a parent to its children, it is no longer a tree but rather a graph. This is a very important concept to understand. For instance, an organization chart, which is hierarchical in nature, is no longer a tree if an employee has two bosses.
To declare a Graph and Tree in Thinkmap, we do the following
var graph = new thinkmap.graph.Graph();
var tree = new thinkmap.graph.Tree();
The one important difference is that for trees, we usually want to set the root almost immediately as a tree really can't do much without a root.
var tree = new thinkmap.graph.Tree();
tree.root(entity);
If you are interested in getting the root from a tree, you can do this:
var currentRoot = tree.root();
It is important to note, however, that setting a new root will truncate the entire tree. Also, removing a node from a tree will cause all of its children to be removed from the tree as well.
Adding Entities to a Tree
In many applications, we have seen that adding to a Graph is pretty straight forward. We can pass selections,
traversal paths, nodes, edges, and arrays to the Graphs add() method and everything will behave as expected.
Adding to a tree is a little different. Trees are more concerned with the adding of edges as we are only building relations between a node and its child nodes. Therefore, the most basic way of adding to a tree is to pass an edge, where either the FROM or TO is already in the tree.
var edge = tree.createEdge(from,to);
tree.add(edge);
It is important to realize, that when adding an edge, one of the nodes must not yet exist in the tree. If two nodes are already in the tree, then that means the edge is not a strict child/parent relationship and the edge will be ignored. For instance:
var a = tree.createNode();
var b = tree.createNode();
var c = tree.createNode();
var ab = tree.createEdge(a,b);
var bc = tree.createEdge(b,c);
var ac = tree.createEdge(a, c);
// these nodes and edges will be added fine
tree.add(ab);
tree.add(bc);
// this edge will be completely ignored
tree.add(ac);
As you can see, edges need to be added carefully to a graph to accommodate this condition. Therefore, some objects in Thinkmap have a
addToTree method and the tree itself checks before trying to add entities to it self. If this method exists, the tree calls addToTree
method passing itself as the parameter
graph.query(['node','edge','node'])
.execute(entity)
// typically you would just say tree.add for the on result but
// this shows what happens behind the scenes
.onresult(function(path) {
path.addToTree(tree);
});
Trees, Graphs, Layouts, and Displays
One of the main limitations for hierarchical data and trees is that a tree enforces a strict one parent rule for any given node. But when it comes to visualizing data in Thinkmap, we can give the appearance of a node having multiple parents by using displays and trees together.
Although a tree in Thinkmap can be used for analysis purposes, most of the time people use a tree specifically
with a tree layout. A tree layout binds a display and a specific tree, and upon calling of the display.layout(), the
TreeLayout uses the tree to place entities in their correct place. Let's look at how we define the two trees
and two layouts for this example:
// define a root variable which will be the root of the two trees
var root = null;
// create a right tree which will store movies and people
var rightTree = new thinkmap.graph.Tree();
// create a left tree which will store movies and genres
var leftTree = new thinkmap.graph.Tree();
// create a left layout that is bound to the left tree
var leftLayout = thinkmap.layout.treeLayout(display)
.tree(leftTree)
.spacing(-200);
// create a right layout that is bound to the right tree
var rightLayout = thinkmap.layout.treeLayout(display)
.tree(rightTree)
.spacing(200);
We have two trees, a left tree which will store movies and genres, and a right tree that stores movies and people. Notice that the left layout has a negative spacing of -200 and the right layout has a spacing of 200. This means that the left tree will move across to the left of the screen and the right tree will move to the right of the screen.
So how can we overcome the limitations of a tree hierarchy? Well first, remember that a tree requires there be one parent for every node (with the exception of the root). However, a display is also a graph and can have many edges between nodes.
This means that we can add edges to both trees and the display at the same time. If the tree encounters an edge where both nodes are already in the tree, it just harmlessly ignores it. The Display, however, will add the edge to the Display so the user can actually see the edge. So when layout is called, both the tree and the display will contain the exact same nodes but the display will most likely have more edges. The TreeLayout just lays out the tree as expected and the display maintains all edges so the tree shape remains.
For instance, when using a tree and display, this is a very common pattern and is exactly what we described above
function center(entity) {
tree.root(null); // deletes the entire tree
tree.root(entity); // set a new root
graph.query(['node','edge','node'])
.execute(entity)
.onresult(display.add) // add all results to display
// Add all results to tree. Any edges in result that
// connect two nodes already in tree are silently ignored.
.onresult(tree.add)
.onresult(display.layout) //call layout on each result
.oncomplete(function(results) {
// remove all old entities in display that weren't
// in results
display.retainOnly(results);
});
}
Adding nodes to left and right Trees
Any time there are two trees, it is typically best to define two queries (a left query and right query) that append entities to their respective trees. Let's take a look at how these two queries are defined:
// The left query is for building up the movies and genres which
// are laid out to the left
function leftQuery(entity) {
// return the query (which is a future)
return graph.query({$choice:[
['movie','edge', 'genre'],
['genre','edge', 'movie']
]})
.execute(entity)
.onresult(display.add) // add all results to the display
.onresult(addToLeftTree) // call addToLeftTree for each result
.oncomplete(display.layout);
}
// The right query is for building up the movies and people which
// are laid out to the right
function rightQuery(entity) {
return graph.query({$choice:[
['movie','edge', 'person'],
['person','edge', 'movie']
]})
.execute(entity)
.onresult(display.add)
.onresult(addToRightTree) // call addToRightTree for each result
.oncomplete(display.layout);
}
So both queries add to the display but each one calls a different function for adding to the tree. Adding to the left tree and right tree has different behaviors. When adding movies and genres to the left tree, we don't want any movies that appear in the right tree to become part of the left tree. So we merely check to make sure this doesn't happen as if a node is added to both trees, its layout will not be correct.
// When adding to the left tree, we must first verify that no nodes
// in the traversal path are contained in the right tree. If so, then
// we don't add this path to the tree. However, there will still be
// an edge in the display that connects the two nodes even though they
// are in different trees.
function addToLeftTree(path) {
var current = path;
while (current.prev) {
if (rightTree.contains(current.entity)) {
return;
}
current = current.prev;
}
path.addToTree(leftTree);
}
Conversely, when we are adding entities to the right tree, we want to remove any movies from the left tree and put them in the right tree. This requires us to first remove the movie from the left tree before adding it to the right tree.
// Adding to the right tree is different then the left. If a node in
// the traversal path is contained in the left tree, we remove the node
// from the left tree first. We then add the path to the right tree and
// and then remove any nodes that may have been orphaned from the left tree
// when removing any nodes. From the users point of view, nodes from the
// left will sweep across the screen as the right tree steals nodes from
// the left tree on each expand.
function addToRightTree(path) {
var remove = false;
var current = path;
while (current.prev) {
if (leftTree.contains(current.entity) && current.entity !== root) {
remove = true;
leftTree.remove(current.entity);
}
current = current.prev;
}
path.addToTree(rightTree);
// if we removed any nodes, then we need to do some cleanup
// by removing any nodes that are in neither tree from the display
if (remove) {
validateDisplay();
}
}
Centering and Expanding with Trees
As seen in other examples, clicking a node expands it and shift-clicking makes the node the center. When using two trees, there are a couple of things to consider, especially when making a node the center.
First, this example makes sure that when calling makeCenter that the given entity is of type
movie and is also not currently the center. This is good practice.
function makeCenter(entity) {
// return if entity is undefined or equal to the current root or not
// a movie
if (!entity || root === entity || !entity.isType('movie')) return;
// set the root to the new entity
root = entity;
// Setting the NEW root on the two trees will remove all existing
// nodes and edges in those trees
leftTree.root(root);
rightTree.root(root);
// add the root to the display
display.add(root);
// Because the two queries are run asynchronously, we can't
// remove entities from the display until both queries complete.
// Since both queries return a future, we wrap them into a single
// future. When both queries complete, our wrapped future completes
// and we cleanup the display and then focus on the root entity
thinkmap.async.all(
// both queries return a future
leftQuery(entity), rightQuery(entity)
)
.then(validateDisplay) // removes any nodes not in any trees
.then(focusEntity);
}
Notice that we wrap the two queries into a future. This allows us to run both queries at the same time and then do some housekeeping when both complete.
An important method here is validateDisplay. This method makes sure that all nodes in the
display belong to a tree that has an enabled layout. It will also remove any nodes from the display
that were not a part of the result set. In essence, it is a more sophisticated way of doing a
display.retainOnly(results) but accounting for multiple trees and layouts.
// Validates that every node in the display is contained in at least one
// enabled tree. If a node is in the display but is not contained within
// an enabled tree, then we know it should be removed from the display.
// Removing the nodes will also remove any connecting edges as an edge can
// only be in a graph if both of its nodes are in the graph.
function validateDisplay() {
display.nodes().filter(function(n) {
return !((leftLayout.enabled() && leftTree.contains(n)) ||
(rightLayout.enabled() && rightTree.contains(n)));
}).remove(); // finally removing those nodes in the selection
display.layout();
}
Expanding entities on each display is actually very simple. We just check which tree the node belongs to and call the appropriate query.
// depending on what tree the expanded node is in, we call either the
// right or left query function
function expand(entity) {
if (entity !== root){
var query = rightTree.contains(entity) ? rightQuery : leftQuery;
return query(entity).then(function() { focusEntity(entity); });
}
}
Focusing on Entities in a Tree
In both the center and expand functions, we call a function focusEntity after the queries complete and the results
have been added to both trees. This function focuses either on the root or a given entity.
The problem with just scrolling to an entity in a tree is that it could be in the process of being
layed out by the TreeLayout. So the current position of the entity may not be accurate. We instead want to scroll to where the entity
will end up. The focusEntity function gets around this problem by a one time event listener to
the displays layout event and focusing on the targetPosition of the entity using the layout.
// Focus the given entity so that it is in the middle of the screen.
function focusEntity(entity) {
// If the entity is not passed in or not of type Node, then
// we use the root as the entity.
if (!(entity instanceof thinkmap.graph.Node)) {
entity = root;
}
// This is a special way of attaching a listener for just one call
// upon which it is then removed. In this case, we want the following
// function to happen just after the next layout call.
display.once('layout',function(){
var activeLayout = null;
// find a layout that will actually be used for laying out the
// entity
if (rightLayout.enabled() && rightTree.contains(entity)) {
activeLayout = rightLayout;
}else {
activeLayout = leftLayout;
}
// Because the entity may currently be
// moving on the screen, we can't just scroll to
// where it currently is. Rather, we need to scroll to where it
// will be headed. In this case, the target position of the layout
// will give us this value.
display.transition().scrollTo(activeLayout.targetPosition(entity));
});
display.layout();
}
Removing and Adding Trees from the Display
This example has a drop down menu that allows the user to select which tree they can view. First, we add an event listener to the select menu:
// add an event listener to the tree select menu
document.getElementById('treeSelect')
.addEventListener('change', changeTrees);
The changeTrees function actually handles the enableing and disabling of layouts while also adding and removing nodes from the display.
// changes the trees
function changeTrees() {
// get the value of the tree select menu
var tree = document.getElementById('treeSelect').value;
if (tree == 'both') { //enable both layouts
rightLayout.enabled(true);
leftLayout.enabled(true);
display.add(rightTree); // add both trees to the dispay
display.add(leftTree);
} else if (tree == 'left') { // enable only the left layout
leftLayout.enabled(true);
rightLayout.enabled(false);
display.add(leftTree); // add left tree to display
validateDisplay(); // validate display
} else { // enable only the right layout
rightLayout.enabled(true); // enable only the right layout
leftLayout.enabled(false);
display.add(rightTree); // add right tree to display
validateDisplay(); // validate display
}
focusEntity();
}
In the case of 'both', both trees are added to the display. However, if either the left or right is selected, the
appropriate tree is added to the display, and then validateDisplay is called, which will remove nodes from the
display that are in the other tree.
It is important to notice upon expanding both trees, that selecting different trees and returning to them will have edges missing. This is because the edges spanning across trees and multiple nodes were removed from the display. However, because these edges don't exist in trees, they are not readded to the display.
Summary
This summary explained how to use multiple trees and graphs together in Thinkmap. The code in this example will serve as a great foundation for any application that wishes to use two trees to present hierarchical data.