Figure 1. Sample with specific colors rendered with VML in Internet Explorer.
Figure 2. Sample with specific colors rendered with canvas in Firefox.
Figure 3. Sample showing collapsed and selected nodes rendered with VML in Internet Explorer.
Contents
This article presents a JavaScript component which renders a tree on the screen using VML (Vector Markup Language) in Internet Explorer 6+ or the <canvas> element in Firefox 1.5+.
There are plenty of JavaScript trees out there, and most of them have a better cross-browser compatibility than this, are faster and better optimized. The goal of this code is to present a client-side implementation of the Walker's layout algorithm (see References), leaving off code optimizations. In short, the component has born after the algorithm, as I think that a living sample would be better than an abstract source-code level implementation.
One of the classic treeview JavaScript components I use sometimes is Geir Landrö's DTree: outstanding and simple. Some time ago, an article appeared here at CodeProject that presents a horizontal JavaScript tree, based upon DTree, which uses HTML tables to render the tree in a horizontal manner. I want to mention those here as they inspired me to publish this article. Moreover, much of the functionalities of this version mimic that on those scripts.
I hope this component will fill the gap in projects when a tree layout is needed, but without server-side code. Of course, any comments, corrections, suggestions, etc... are very welcome.
The best way to get an idea of what could be accomplished by using this component is to download the sources and play with the sample included. The API reference below could give you a more precise idea of what could be done. But, as a briefing, features include:
- Nodes could be of any size, color. (With some code tweaking, it's easy to adapt them as desired).
- Nodes could have a title and a hidden associated metadata.
- Selection modes are: Multiple selection, Single selection and No selection.
- Node links could be straight lines (Manhattan) or Bézier curves.
- The tree layout could be oriented top to bottom, right to left or reversed. (Thanks to Walker's algorithm, not to me...!)
- Nodes could have an associated hyperlink.
- Subtrees could be collapsed and expanded as desired.
- Node searches could be done based on both title and metadata.
I would like to say that this is a work in progress. In particular, the code is structured to allow different rendering technologies and I must definitively work harder on this topic.
The Walker's algorithm expands on the previous works of Reingold, Tilford, Shannon et al. providing a solution where a tree drawing occupies as little space as possible while satisfying the following aesthetic rules:
- Nodes of the same level are aligned, and the axis of all levels are parallel.
- A parent should be centered over its children.
- A tree and the same tree defined in reverse order, should produce layouts that are reflections of one another. The same subtree must be rendered the same way no matter where it appears in the tree.
The Walker's algorithm goal over its predecessors was to provide a solution to fully satisfy the third rule, by means of spacing out evenly smaller subtrees in the interior of adjacent larger subtrees.
Figure 4. Samples showing the difference of the apportion routine in Walker's algorithm..
The main concepts of the algorithm are:
- Treating each subtree as a rigid unit, moving a node implies moving all of its descendants.
- Doing so by using a preliminary coordinate and a modifier for each node. Moving a node implies to increase/decrease its preliminary coordinate and its modifier, but only the modifier will affect the final position of the node's descendants. So moving a subtree means alter the subtree's root modifier. The node's final position is computed summing up the node preliminary coordinate plus all its ancestor's modifiers.
The algorithm works in two passes. The first pass (firstWalk) is a postorder traversal. The different subtrees are processed recursively from bottom to top and left to right positioning the rigid units that form each subtree until no one touch each other. As the traversal goes, smaller subtrees are combined forming larger subtrees until we reach the root. During the process, the apportion routine space out evenly the inner smaller subtrees that could float between two adjacent larger subtrees (to satisfy the symmetry of the 3rd rule). The second pass (secondWalk) is a preorder traversal which calculates the final node position by adding all the ancestors modifiers to the preliminary coordinate of each node.
Gao Chaowei (see References) proposed an optimization to the firstWalk routine which consists in an incremental version of the Walker's algorithm. This version avoids to recalculate the node preliminary coordinate and modifier when changes made to the tree structure don't imply modifications to their values. This optimization is not yet implemented in this component.
The algorithm also adjust the calculations if the layout is to be made in a different direction (i.e. bottom to top). Different uses may require different views. In occident, traditionally a top disposition means power, like in organizational hierarchies; a bottom layout means evolution or growth, like in biology; whereas left and right layouts could mean time evolution. (But this is a particular consideration).
Just a word to mention that, an uniform layout algorithm like this one is adequate for relative small trees. Trees with a large number of nodes may require other layout and visualization techniques, like the ability to zoom, pan and focus, collapse some but not all the children of a node, adding interactive searching. There are a number of other solutions to achieve the same objectives including, but not limited to, hyperbolic trees, treemaps, Degree of interest calculations, ... The curious reader could find a lot of information on the net.
Let's build an example, (all samples are included in the download) to understand how to draw a simple tree. After that, with the API reference and looking at the advanced samples code you could fully understand how to use this component.
First of all, you must include the component script and link the style-sheet in the <head> section of your HTML page (remember to set the paths upon your installation):
<head>
<!--
<script type="text/javascript" src="ECOTree.js"></script>
<link type="text/css" rel="style-sheet" href="ECOTree.css" />
<!--
</head>
Besides, if you plan to user Internet Explorer you must add the next lines to the <head> section of your HTML page for VML to render correctly:
<head>
<!--
<xml:namespace ns="urn:schemas-microsoft-com:vml" prefix="v"/>
<style>v\:*{ behavior:url(#default#VML);}</style>
<!--
</head>
In your HTML page you must place a block container for the tree, like a <div> with an ID that you must supply to the tree constructor. Then you must include a <script> block to create the tree itself, add some nodes -probably from a database in real projects- and then draw the tree. Let's look at an example:
<div id="myTreeContainer"></div>
var myTree = new ECOTree("myTree","myTreeContainer");
myTree.add(0,-1,"Apex Node");
myTree.add(1,0,"Left Child");
myTree.add(2,0,"Right Child");
myTree.UpdateTree();
The result will be:
Figure 5. Quick example 1.
You must ensure that the script block gets executed once the page is loaded, or at least when the container is loaded. So you could choose to insert the script after the container or to create the tree inside a function that gets called when the OnLoad event occurs for the document or body, as usual.
Note that the component has default values for almost everything, causing that those five lines of code could create a tree that you can collapse or expand at will, and you can select/unselect multiple nodes by simply clicking them. Also, every node has a hyperlink Javascript:void(0); by default. Almost every time, you will want to change the look and feel and the behavior of the tree to better fit your needs. This can be done with the config instance member of the tree. Let's modify the previous example by adding some lines:
var myTree = new ECOTree("myTree","myTreeContainer");
myTree.config.linkType = 'B';
myTree.config.iRootOrientation = ECOTree.RO_BOTTOM;
myTree.config.topYAdjustment = -160;
myTree.config.linkColor = "black";
myTree.config.nodeColor = "#FFAAAA";
myTree.config.nodeBorderColor = "black";
myTree.config.useTarget = false;
myTree.config.selectMode = ECOTree.SL_SINGLE;
myTree.add(0,-1,"Apex Node");
myTree.add(1,0,"Left Child");
myTree.add(2,0,"Right Child");
myTree.UpdateTree();
With these minor changes, the tree now will look like this:
Figure 6. Quick example 2.
This time, the nodes don't have a hyperlink (useTarget = false) and you can select only one node at a time (selectMode = ECOTree.SL_SINGLE).
OK, now that the basics had been covered, let's go on to discover all the possibilities.
ECOTree configuration
Here are the config parameters with their default values:
this.config = {
iMaxDepth : 100,
iLevelSeparation : 40,
iSiblingSeparation : 40,
iSubtreeSeparation : 80,
iRootOrientation : ECOTree.RO_TOP,
iNodeJustification : ECOTree.NJ_TOP,
topXAdjustment : 0,
topYAdjustment : 0,
render : "AUTO",
linkType : "M",
linkColor : "blue",
nodeColor : "#CCCCFF",
nodeFill : ECOTree.NF_GRADIENT,
nodeBorderColor : "blue",
nodeSelColor : "#FFFFCC",
levelColors : ["#5555FF","#8888FF","#AAAAFF","#CCCCFF"],
levelBorderColors : ["#5555FF","#8888FF","#AAAAFF","#CCCCFF"],
colorStyle : ECOTree.CS_NODE,
useTarget : true,
searchMode : ECOTree.SM_DSC,
selectMode : ECOTree.SL_MULTIPLE,
defaultNodeWidth : 80,
defaultNodeHeight : 40,
defaultTarget : 'Javascript:void(0);',
expandedImage : './img/less.gif',
collapsedImage : './img/plus.gif',
transImage : './img/trans.gif'
}
iMaxDepth: The maximum number of levels allowed for tree. Set it to a value larger than the maximum level expected.
iLevelSeparation: The space distance between levels in pixels. Note that a level size will be given by the maximum node size at that level.
iSiblingSeparation: The minimum space distance between sibling nodes in pixels.
iSubtreeSeparation: The minimum space distance between neighbor nodes (don't have the same parent) in pixels.
iRootOrientation: The direction of the layout. Possible values are:
ECOTree.RO_TOP: Layout from top to bottom.
ECOTree.RO_BOTTOM: Layout from bottom to top.
ECOTree.RO_RIGHT: Layout from right to left.
ECOTree.RO_LEFT: Layout from left to right.
iNodeJustification: The alignment of the nodes that belong to the same level. Possible values are:
ECOTree.NJ_TOP: Nodes are top aligned.
ECOTree.NJ_CENTER: Nodes are center aligned.
ECOTree.NJ_BOTTOM: Nodes are bottom aligned.
topXAdjustment: The horizontal offset in pixels that the root node will be given. Use it to center/pan the tree on the screen.
topYAdjustment: The vertical offset in pixels that the root node will be given. Use it to center/pan the tree on the screen.
render: The render type. Possible values are:
"AUTO": Automatic. This is the default value. Code will autodetect if the client is Internet Explorer 6+ or Firefox and the render type will be set to "VML" or "CANVAS" respectively.
"VML": Vector Markup Language. For Internet Explorer only. If you use it, remember to add the XML namespace and the <style> in the head section as indicated in the article.
"CANVAS": Render will be based in the <canvas> HTML element. Only for Firefox 1.5+. (Firefox 2.0 is faster, though).
linkType: The style of the node links. Possible values are:
"M": Manhattan. Links are crossed straight lines. Classic.
"B": Bézier. Links are Bézier curves. More suitable in some cases.
linkColor: The color used for the link lines. Any color expressed in HTML is valid.
nodeColor: The color used for the nodes. See comments in the article on how to hack the mode how nodes are rendered. Any color expressed in HTML is valid.
nodeFill: The fill style of the nodes. Possible values are:
ECOTree.NF_GRADIENT: The nodes will be filled with a gradient between the node color and "whitesmoke".
ECOTree.NF_FLAT: The nodes will have a solid fill.
nodeBorderColor: The color used for the node borders. Any color expressed in HTML is valid.
nodeSelColor: The color used for the selected nodes. Any color expressed in HTML is valid.
levelColors: A Javascript array with the colors for consecutive levels. Applies when the colorStyle option is set to use level colors. The nodes at the first level of the tree will have the first color in this array, the second level nodes the second color of the array, and so on. If there are more levels than elements in this array the subsequent levels will repeat the colors anew. Any color expressed in HTML is valid.
levelBorderColors: Same as above, but for the border colors.
colorStyle: Indicates how the nodes colors are calculated. Possible values are:
ECOTree.CS_NODE: Each node will use it's own colors to render.
ECOTree.CS_LEVEL: The nodes will use different colors depending on the level of the node in the tree, ignoring it's own colors.
useTarget: Whether the nodes will show the hyperlinks or not. Possible values are true or false
searchMode: Express how the searches (see API searchNodes) will be done. Possible values are:
ECOTree.SM_DSC: Searches will be done within the node titles.
ECOTree.SM_META: Searches will be done within the node metadata.
ECOTree.SM_BOTH: Searches will be done within both values.
selectMode: Indicates the selection behavior of the tree. Possible values are:
ECOTree.SL_MULTIPLE: The user can interactively select and unselect multiple nodes by clicking them.
ECOTree.SL_SINGLE: The user can interactively select and unselect a single node by clicking it. A new node selection will unselect the previous selection.
ECOTree.SL_NONE: The user can't select nodes by clicking them. Anyway, the API methods that cause node selections will always work, like searches on the tree.
defaultNodeWidth: The node width in pixels, if no explicit width is given when adding a node to the tree.
defaultNodeHeight: The node height in pixels, if no explicit height is given when adding a node to the tree.
defaultTarget: The node hyperlink (when clicked on the title), if no explicit target is given when adding a node to the tree. Usually set when all or most nodes have the same link.
expandedImage: The minus icon which allows to collapse a subtree. Change it if you don't like it, or to point to your own images folder.
collapsedImage: The plus icon which allows to expand a collapsed subtree. Change it if you don't like it, or to point to your own images folder.
transImage: A transparent icon used to separate the collapse/expand icon and the title. Change it if you don't like it, or to point to your own images folder.
ECOTree public methods
UpdateTree(): Causes the tree to refresh.
add(id, pid, dsc, w, h, c, bc, target, meta): Adds a new node to the tree. The three first parameters are mandatory. Parameters are:
id: The node ID. Any number or string will be valid.
pid: The parent ID of this node. If this is a root node, the parent ID must be -1.
dsc: The node title. This will be the visible description. It will be the link to the node target as well.
w: (Optional) The node width in pixels.
c: (Optional) The node color.
bc: (Optional) The node border color.
h: (Optional) The node height in pixels.
target: (Optional) The node hyperlink target. If you don't supply this value, the node will have the dafault value. But, if you supply an empty string as target, you will end with a node without target.
meta: (Optional) The node's metadata. The metadata will not be visible. You can search nodes based on its contents, or you can use it simply as a container for your own node data. If you use a Javascript object as metadata, provide a toString() method in that object's prototype to get the searches working properly.
After the node has been added to the tree, you can use other API's to modify them, for example, to mark it as selected or collapsed if it has children, before the first call to UpdateTree(). It's not mandatory to add the nodes in any particular order.
searchNodes(str): Searches the tree for nodes containing the str string. The found nodes will be selected and, if it's the case, their ancestors expanded to get the found node into view. The searches could be done in the node's title, metadata or both. The search is case insensitive. If the selectMode is SL_MULTIPLE or SL_NONE all the found nodes will be selected. If the selectMode is SL_SINGLE only the first node (in database order) will be selected, but subsequent searches will start from the next node in order, so you can call this API to simulate the search next functionality. After all the nodes will be visited, searches will restart from the beginning. UpdateTree() is called internally, so you don't need to refresh the tree.
selectAll(): Causes all the nodes in the tree to appear as selected. If the selectMode is set to SL_NONE this API will return without selections. UpdateTree() is called internally, so you don't need to refresh the tree.
unselectAll(): Clears all the selections. Could be used no matter the selectMode was. Should be used to clear selections between searches. UpdateTree() is called internally, so you don't need to refresh the tree.
collapseAll(): Causes all the parent nodes to become collapsed. UpdateTree() is called internally, so you don't need to refresh the tree.
expandAll(): Causes all the parent nodes to become expanded. UpdateTree() is called internally, so you don't need to refresh the tree.
collapseNode(nodeid, upd): Collapses the node with ID = nodeid. UpdateTree() is called internally only if you supply the second parameter as true. So if you plan to collapse several nodes, you should refresh only once after all the work will be done.
selectNode(nodeid, upd): Marks as selected the node with ID = nodeid. UpdateTree() is called internally only if you supply the second parameter as true.
setNodeTitle(nodeid, title, upd): Sets the title title of the node with ID = nodeid. UpdateTree() is called internally only if you supply the third parameter as true.
setNodeMetadata(nodeid, meta, upd): Sets the metadata meta of the node with ID = nodeid. UpdateTree() is called internally only if you supply the third parameter as true.
setNodeTarget(nodeid, target, upd): Sets the hyperlink target of the node with ID = nodeid. UpdateTree() is called internally only if you supply the third parameter as true.
setNodeColors(nodeid, color, border, upd): Sets the background color and border color of the node with ID = nodeid. UpdateTree() is called internally only if you supply the fourth parameter as true.
getSelectedNodes(): Returns a JavaScript Array of objects, each having the instance members "id", "dsc", "meta" with the values of node ID, title and metadata of each of the selected nodes respectively. See the samples to get an example on how to use it. It could be useful if you're doing some editing with the tree client-side and you use the XMLHttp object to send the results of the user selections or searches to the server. (XMLHttp and AJAX are not in the scope of this article, but good to hear that IE7 finally implements XMLHttp as a native intrinsic object...).
In the download you can find several simple examples you can play with. All the images in this article are made with the code on the examples. There is an advanced example which will let you play with almost all the options in the component. The data in the samples has been obtained in the Wikipedia.
- Add in-place (client) editing capabilities to the component, like adding, deleting, shuffling nodes and changing its properties, (i.e. context menu)
- Implement the Gao Chaowei proposed optimization to the layout algorithm (see References).
- 11/23/2006 - 1.1. Changes are:
- Added Firefox compatibility. Now if you set the render type to
"AUTO", the component will auto-detect the browser and will choose a render type accordingly. I strongly recommend to use Firefox 2.0 to get a much faster <canvas> experience, but Firefox 1.5 will work as well.
- 10/26/2006 - 1.0. First release.
