Remote-Url: https://www.zxch3n.com/tidy/tidy/ Retrieved-at: 2023-05-19 07:48:00.164981+00:00 This article introduces the algorithm to draw non-layered trees in linear time and re-layout partially when some nodes change in O(d) time, where d is the maximum depth of the changed node.The source code is available atzxch3n/tidy. It only takes a few milliseconds to finish the layout of a tree with tens of thousands of nodes within the web browser.Trees are ubiquitous data structures. Various visualizations of trees were proposed to help people understand different aspects of trees. This article focuses on the classical node-link diagrams.A good tree drawing should be aesthetically pleasing while using as little space as possible. In 1979, Wetherell and Shannon [1] formalized aesthetic rules for tidy trees and presented the first O(n) algorithm to solve it. In 1981, Reingold and Tilford [2] extended the aesthetic rules to make the drawings more aesthetically pleasing and compact. However, both of them wouldviolate the aesthetic rules when extended to m-ary trees. In 1990, Walker [3] solved this problem with O(n^2) time complexity. Buchheim [4] improved Walker’s work to run in O(n) in 2002. In 2014, Ploeg [5] presented the first O(n) algorithm to produce tidy non-layered drawings of trees.This article introduces the layout algorithm of non-layered tidy trees [5] and presents a fast relayout algorithm. Engineers can use it to build fast tree editor tools like mindmaps.Layered and non-layeredIn tree visualization, each node may have variant width and height. For example, nodes may contain text content of different lengths. In this case, the tree can be drawn as layered, where nodes with the same depth are horizontally aligned, or non-layered, where there is a fixed vertical distance between parent and children.Layered drawings make depth comparison easier, whereas non-layered ones generally use less space.The algorithm of non-layered drawing is harder than the layered one since the former can be easily extended to the latter. Ploeg [5] designed the first algorithm to finish the layout of non-layered tidy trees in linear time. The detail of the algorithm will be covered in the rest of this article. If you are interested in how layered drawing works, you can read the article by Bill Mill [6].Aesthetic rulesA tidy drawing of a tree should obey the aesthetic rules while using as little space as possible. The aesthetic rules include:No overlapped nodeNo crossed lineA node’s children should stay on the same lineParents should be centered over their childrenA subtree should be drawn the same way regardless of where it occurs in the treeNodes are ordered. Drawings of nodes should have the same order.A tree and its mirror image should produce drawings that are reflections of one another, which impliesSmall, interior subtrees should be spaced out evenly among larger subtrees, where the larger subtrees are adjacent at one or more levels.Small subtrees at the far left or far right should be adjacent to larger subtrees.Most mind map applications use a naive version of the tidy layout, i.e., it obeys the aesthetic rules but does not care about compactness.The naive tidy visualization algorithm treats each node and its offsprings as a bounding box, avoiding collision between the bounding boxes.functionnaiveTidyLayout(root){root.y=0root.preOrderTraverse(node=>{node.y=node.parent.y+node.parent.height+margin})root.postOrderTraverse(node=>{if(node.children.length==0){node.bbox.width=node.widthreturn}constchildrenWidth=node.children.reduce((acc,cur)=>acc+cur.width+margin,-margin)node.bbox.width=max(node.width,childrenWidth)letrelativeX=node.width/2-childrenWidth/2for(constchildofnode.children){child.relativeX=relativeX+child.bbox.width/2-child.width/2relativeX+=child.bbox.width+margin}})root.preOrderTraverse(node=>{node.x=node.parent.x+node.relativeX})}It is easy to implement and has good performance. But its layout is not compact, as shown inthe interactive example.How to achieve compactnessNote that the aesthetic rules require that a subtree should be drawn the same way no matter where it appears in the tree. It means that if the layout of the subtree is done, inside it, all nodes’ relative positions to their parent are finalized. So we can use a post-order traversal to determine the relative positions. A high-level abstraction of the tree visualization algorithm isfunctionlayout(root){root.postOrderTraverse(node=>{layoutSubtree(node,node.children)})root.preOrderTraverse(node=>{finalizeAbsolutePosition(node)})}To arrange children compactly, duringlayoutSubtree, we need child subtrees to be as close to their siblings as possible. Therefore, we can abstract a tidy layout algorithm as below.functionlayoutSubtree(node,children){if(children.length==0){return}constprev=[children[0]]for(leti=1;i 0 is a constant.We only need a distance function with complexity ofto make the algorithm run in linear time. - Ploeg [5] proposed a algorithm with, so that. Ploeg [5] prooved its linear complexity for the cases other than complete k-ary tree.Fix aesthetic rule 7The above algorithm satisfies aesthetic rules 1-6, but not aesthetic rule 7: a tree and its mirror image should produce drawings that are reflections of one another, as shown in the image below.It happens when large neighbors surround small subtrees. The algorithm will pile the small ones to the left.A simple fix is to take the average positions of the original layout and the mirror of the mirrored layout. But it tends to cluster the small subtrees at the center.Walker [3] designed the first algorithm to address this issue, giving a more visually pleasing output. Its idea is that when moving a subtree to the right, the move distance should also be distributed to the smaller interior subtrees.To make the overall algorithm run within linear time, we need an O(1) method toFind the intermediate siblingsDistribute the distance evenly to the intermedia siblingsNow the code changes tofunctionlayoutSubtree(node,children){if(children.length==0){return}constprev=[children[0]]for(leti=1;i=yR){+prevRightContour=nextRightContour(prevRightContour);+}+}++returnmaxDistance;+}++functionmergeContour(prev,cur){+if(bottom(prev)>bottom(cur)){+constextremeRight=getRightThreadLastNode(cur)+extremeRight.threadRight=getRightThreadNodeAtY(prev[prev.length-1],extremeRight.y);+extremeRight.modifierThreadRight=...;+}elseif(bottom(prev)=cur.bottom)cur=cur.next;+returnnewIYL(minY,index,cur);+}+}functionlayoutSubtree(node,children){if(children.length==0){return;}constprev=[children[0]];+letiyl=newIYL(getBottom(children[0]),0,null);for(leti=1;iiyl.bottom){+iyl=iyl.next;+}constxL=getRelativeX(curLeftContour)constxR=getRelativeX(prevRightContour)+prevRightContour.width+margin;+if(xR-xL>maxDistance){+maxDistance=xR-xL;+collideIndex=iyl.index;+}constyL=curLeftContour.y+curLeftContour.height;constyR=prevRightContour.y+prevRightContour.height;if(yL<=yR){curLeftContour=nextLeftContour(curLeftContour);}if(yL>=yR){prevRightContour=nextRightContour(prevRightContour);}}return[maxDistance,collideIndex];}Distribute spacingWe can implement it in a bruit-force way as below. But in the worst case, it causes the overall complexity to be.functiondistributeDistanceToInteriorSubtrees(children,distance,from,to){for(leti=from+1;i{layoutSubtree(node,node.children);})root.preOrderTraverse(node=>{finalizeAbsolutePosition(node);})}functionfinalizeAbsolutePosition(node){addChildSpacing(node);...}functionaddChildSpacing(node){letspeed=0.;letdelta=0.;for(constchildofnode.children){speed+=child.shiftAcceleration;delta+=speed+child.shiftChange;child.relativeX+=delta;}}functiondistributeDistanceToInteriorSubtrees(children,distance,from,to){if(to==from+1){return;}children[from+1].shiftAcceleration+=distance/(to-from);children[to].shiftAcceleration-=distance/(to-from);children[to].shiftChange-=distance-distance/(to-from);}Final CodeYou can find the final code of this articlehere. However, there are still a few trivial details missing in this abstraction. For details, please refer to thesource code.Interactive exampleIn this example, you can try non-layered tidy layout, layered tidy layout, and naive layout.Node editing is a common scenario in applications like mind maps. If the relayout time is larger than 16ms, there will be obvious freezes, which is unacceptable. Therefore, a partial relayout is required for a smooth user experience on large editable tree visualization.In this section, we exclude thefinalizeAbsolutePositionand only talk about how to re-calculate each node’s relative position to their parent. Because changing one node’s size may cause the entire tree’s absolute positions to change, relative positions are much more stable asaesthetic rule 5required. And in the real-world application, we only need the absolute positions of the nodes inside the screen. By detecting the collision between trees’ bounding boxes and the screen, we can filter out the offscreen content swiftly. Strictly speaking, the time complexity of partial relayout is O(d + m), where m is the in-screen nodes number, and d is the max depth of changed nodes.Adding the partially relayout support to the naive version is relatively easy. Because the affected states are straightforward to reason about, i.e., only the bounding boxes of the edited nodes and their ancestors are changed.For partial relayout, we need to determine which thread pointer caches are outdated. We say a subtree is changed if it or its offspring’s sizes change or an insertion or deletion happens inside this subtree. Note thatIf all nodes inside a subtree are not changed, the thread pointers of its nodes that point to the node inside this subtree won’t change. This is because the layout of a tree is agnostic about nodes outside. And the thread pointers that point inside are only affected by the structure of the subtree itself.In a subtree, only the deepest nodes, which have the greatest value ofnode.y + node.height, have thread pointers that point outside of the tree. This rule is obvious in themergeContourimplementation.Based on 1 and 2, we can infer that we only need to update the thread pointers of its deepest nodes for an unchanged subtree.From 3, we can infer that if a node and its parent are roots of unchanged subtrees, we only need to update the parent subtree’s deepest nodes’ threads.Generalizing 4, for all unchanged subtrees, only those who are siblings of the changed subtrees need to update their deepest nodes’ thread pointers.Based on the above observations, we only need to relayout the changed subtree and update its siblings’ thread pointers. Below is the code about partial relayout when there is a single changed node. We can easily extend it to multiple changed nodes.functionrelayout(root,changedNode){letnode=changedNodewhile(node.parent){for(constsiblingofnode.parent.children){constr=getRightBottomNode(sibling)r.threadRight=nullr.modifierThreadRight=0constl=getLeftBottomtNode(sibling)l.threadRight=nulll.modifierThreadRight=0}layoutSubtree(node.parent,node.parent.children)node=node.parent}}The code is available atGitHub. The layout algorithms are written in Rust and compiled to WASM. The renderer is written in TypeScript.Run Benchmark On Your DeviceBenchmarks were done on MacBook Pro (13-inch, M1, 2020). It only measures the layout algorithm without the allocation and deallocation time. Mysteriously, the WASM build is faster than the native build on large data. It is very interesting, but I have not found out why.Remaining aesthetic issueThe current layout algorithm is still not ideal in some cases.As the above example shows, the root’s children are not symmetric in the current layout though it obeys the aesthetic rules. It does not violateaesthetic rule 7, since the drawing of mirrored structure would give a mirrored layout.To fix this issue, we need a new aesthetic rule to formalize the problem.The Tidy LibraryThough tidy tree visualization is useful in many fields, we haven’t seen many adoptions of this algorithm in the industry because it is error-prone and slower. I hopeTidy Libcan make the adoption simple and reliable.The plan is to add full support for partial relayout, compress wasm size, and performance improvement. This lib mainly focuses on the layout algorithm. Building a full-fledged tree visualization tool or editor is not a priority of this lib.This lib is published under MIT License. Don’t hesitate to contact me if you want to participate or have any suggestions.[1]C. Wetherell and A. Shannon, “Tidy Drawings of Trees,” IEEE Transactions on Software Engineering, vol. SE-5, no. 5, pp. 514–520, Sep. 1979, doi: 10.1109/TSE.1979.234212.[2] E. M. Reingold and J. S. Tilford, “Tidier Drawings of Trees,” IEEE Transactions on Software Engineering, vol. SE-7, no. 2, pp. 223–228, Mar. 1981, doi: 10.1109/TSE.1981.234519.[3] J. Q. Walker II, “A node-positioning algorithm for general trees,” Software: Practice and Experience, vol. 20, no. 7, pp. 685–705, 1990, doi: 10.1002/spe.4380200705.[4] C. Buchheim, M. Jünger, and S. Leipert, “Improving Walker’s Algorithm to Run in Linear Time,” in Graph Drawing, Berlin, Heidelberg, 2002, pp. 344–353. doi: 10.1007/3-540-36151-0_32.[5] A. van der Ploeg, “Drawing non-layered tidy trees in linear time,” Software: Practice and Experience, vol. 44, no. 12, pp. 1467–1484, 2014, doi: 10.1002/spe.2213.[6] Bill Mill, “Drawing Presentable Trees.” https://llimllib.github.io/pymag-trees/ 2008