Now Reading
Excessive-performance tidy timber visualization | Zxch3n

Excessive-performance tidy timber visualization | Zxch3n

2023-05-18 18:47:06

June 14, 2022 · 17 min learn

This text introduces the algorithm to attract non-layered timber in linear time and re-layout partially when some nodes change in O(d) time, the place d is the utmost depth of the modified node.

The supply code is out there at zxch3n/tidy. It solely takes a number of milliseconds to complete the structure of a tree with tens of 1000’s of nodes throughout the net browser.

Bushes are ubiquitous knowledge buildings. Numerous visualizations of timber have been proposed to assist folks perceive completely different facets of timber. This text focuses on the classical node-link diagrams.

tree drawing must be aesthetically pleasing whereas utilizing as little area as attainable. In 1979, Wetherell and Shannon [1] formalized aesthetic guidelines for tidy timber and offered the primary O(n) algorithm to unravel it. In 1981, Reingold and Tilford [2] prolonged the aesthetic guidelines to make the drawings extra aesthetically pleasing and compact. Nonetheless, each of them would violate the aesthetic rules when extended to m-ary trees. In 1990, Walker [3] solved this downside with O(n^2) time complexity. Buchheim [4] improved Walker’s work to run in O(n) in 2002. In 2014, Ploeg [5] offered the primary O(n) algorithm to provide tidy non-layered drawings of timber.

This text introduces the structure algorithm of non-layered tidy timber [5] and presents a quick relayout algorithm. Engineers can use it to construct quick tree editor instruments like mindmaps.

Layered and non-layered

In tree visualization, every node could have variant width and peak. For instance, nodes could include textual content content material of various lengths. On this case, the tree will be drawn as layered, the place nodes with the identical depth are horizontally aligned, or non-layered, the place there’s a mounted vertical distance between guardian and youngsters.

Layered drawings make depth comparability simpler, whereas non-layered ones typically use much less area.

The algorithm of non-layered drawing is more durable than the layered one because the former will be simply prolonged to the latter. Ploeg [5] designed the primary algorithm to complete the structure of non-layered tidy timber in linear time. The element of the algorithm shall be lined in the remainder of this text. If you’re excited by how layered drawing works, you may learn the article by Invoice Mill [6].

Aesthetic guidelines

A tidy drawing of a tree ought to obey the aesthetic guidelines whereas utilizing as little area as attainable. The aesthetic guidelines embody:

  1. No overlapped node
  2. No crossed line
  3. A node’s kids ought to keep on the identical line
  4. Dad and mom must be centered over their kids
  5. A subtree must be drawn the identical means no matter the place it happens within the tree
  6. Nodes are ordered. Drawings of nodes ought to have the identical order.
  7. A tree and its mirror picture ought to produce drawings which can be reflections of each other, which means
    • Small, inside subtrees must be spaced out evenly amongst bigger subtrees, the place the bigger subtrees are adjoining at a number of ranges.
    • Small subtrees on the far left or far proper must be adjoining to bigger subtrees.

Most thoughts map functions use a naive model of the tidy structure, i.e., it obeys the aesthetic guidelines however doesn’t care about compactness.

The naive tidy visualization algorithm treats every node and its offsprings as a bounding field, avoiding collision between the bounding containers.

perform naiveTidyLayout(root) {
  root.y = 0
  root.preOrderTraverse(node => {
    node.y = node.guardian.y + node.guardian.peak + margin
  })
  root.postOrderTraverse(node => {
    if (node.kids.size == 0) {
      node.bbox.width = node.width
      return
    }

    const childrenWidth = node.kids.cut back(
      (acc, cur) => acc + cur.width + margin,
      -margin
    )
    node.bbox.width = max(node.width, childrenWidth)
    let relativeX = node.width / 2 - childrenWidth / 2
    for (const baby of node.kids) {
      baby.relativeX = relativeX + baby.bbox.width / 2 - baby.width / 2
      relativeX += baby.bbox.width + margin
    }
  })
  root.preOrderTraverse(node => {
    node.x = node.guardian.x + node.relativeX
  })
}

It’s straightforward to implement and has good efficiency. However its structure just isn’t compact, as proven in the interactive example.

How one can obtain compactness

Notice that the aesthetic guidelines require {that a} subtree must be drawn the identical means regardless of the place it seems within the tree. It implies that if the structure of the subtree is completed, inside it, all nodes’ relative positions to their guardian are finalized. So we are able to use a post-order traversal to find out the relative positions. A high-level abstraction of the tree visualization algorithm is

perform structure(root) {
  root.postOrderTraverse(node => {
    
    layoutSubtree(node, node.kids)
  })

  root.preOrderTraverse(node => {
    finalizeAbsolutePosition(node)
  })
}

To rearrange kids compactly, throughout layoutSubtree, we want baby subtrees to be as near their siblings as attainable. Subsequently, we are able to summary a tidy structure algorithm as under.

perform layoutSubtree(node, kids) {
  if (kids.size == 0) {
    return
  }

  const prev = [children[0]]
  for (let i = 1; i < kids.size; i++) {
    const cur = kids[i]
    cur.relativeX = getMoveDistance(prev, cur)
    prev.push(cur)
  }

  positionRoot(node)
}

Suppose we’re visualizing an entire k-ary tree, then we’ve got , the place is the time complexity of the getMoveDistance perform. Primarily based on master theorem,

  • If , then .
  • If , then .
  • If , then .
  • ϵ > 0 is a continuing.

We solely want a distance perform with complexity of to make the algorithm run in linear time. – Ploeg [5] proposed a algorithm with , in order that . Ploeg [5] prooved its linear complexity for the circumstances apart from full k-ary tree.

Repair aesthetic rule 7

The above algorithm satisfies aesthetic guidelines 1-6, however not aesthetic rule 7: a tree and its mirror picture ought to produce drawings which can be reflections of each other, as proven within the picture under.

It occurs when giant neighbors encompass small subtrees. The algorithm will pile the small ones to the left.

A easy repair is to take the typical positions of the unique structure and the mirror of the mirrored structure. Nevertheless it tends to cluster the small subtrees on the heart.

Walker [3] designed the primary algorithm to deal with this problem, giving a extra visually pleasing output. Its thought is that when shifting a subtree to the suitable, the transfer distance must also be distributed to the smaller inside subtrees.



How to fix aesthetic rule 7

To make the general algorithm run inside linear time, we want an O(1) technique to

  1. Discover the intermediate siblings
  2. Distribute the gap evenly to the intermedia siblings

Now the code adjustments to

perform layoutSubtree(node, kids) {
  if (kids.size == 0) {
    return
  }

  const prev = [children[0]]
  for (let i = 1; i < kids.size; i++) {
    const cur = kids[i]
    const collideIndex = getCollisionIndex(prev, cur)
    const distance = getMoveDistance(prev, cur)
    cur.relativeX = distance
    distributeDistanceToInteriorSubtrees(kids, distance, collideIndex, i)
    prev.push(cur)
  }

  positionRoot(node)
}

The O(n) structure algorithm [5]

To make the general algorithm run in O(n), we want the next strategies completed in

1.  getMoveDistance(leftSiblings, subtree)
2.  getCollisionIndex(leftSiblings, subtree)
3.  distributeDistanceToInteriorSubtrees(kids, distance, collideIndex, currentIndex)

Decide transfer distance

getMoveDistance calculates how far a subtree wants to maneuver to keep away from colliding with the siblings on its left. For this function, it solely must calculate the gap between the siblings’ proper and the subtree’s left contour.

Notice that aesthetic rule 5 requires: a subtree must be drawn the identical means no matter the place it happens within the tree. So a subtree’s left and proper contour will not be affected by different subtrees or their ancestors.

We introduce 4 new variables for this function.

  • threadLeft: factors to the following left contour node
  • modifierThreadLeft: the following left contour node x place relative to this
  • threadRight: factors to the following proper contour node
  • modifierThreadRight: the following proper contour node x place relative to this

The thread of the suitable contour is:

  • The primary node of the thread is the rightmost subtree’s root.
  • If the present thread node has kids, then the following node within the thread is its last-child
  • If the present thread node c has no baby, the following node within the thread is c.threadRight.
  • c.modifierThreadRight is c.threadRight’s x place relative to c

The left contour thread follows the suitable contour’s mirrored guidelines.

When calculating the contour’s distance, solely nodes with intersections on the y-axis must be in contrast. And in each layered and non-layered circumstances, every node’s y positions will be precomputed.

We will categorical the prolonged behaviors in pseudocode.

perform layoutSubtree(node, kids) {
  if (kids.size == 0) {
    return;
  }

  const prev = [children[0]];
  for (let i = 1; i < kids.size; i++) {
    const cur = kids[i];
    const collideIndex = getCollisionIndex(prev, cur);
    const distance = getMoveDistance(prev, cur);
    cur.relativeX = distance;
    distributeDistanceToInteriorSubtrees(kids, distance, collideIndex, i);
+   mergeContour(prev, cur);
    prev.push(cur);
  }

  positionRoot(node);
}

+perform getMoveDistance(prev, cur) {
+  const curLeftContour = cur;
+  const prevRightContour = prev[prev.length - 1];
+  let maxDistance = 0;
+  whereas (curLeftContour && prevRightContour) {
+    const xL = getRelativeX(curLeftContour)
+    const xR = getRelativeX(prevRightContour) + prevRightContour.width + margin;
+    maxDistance = max(maxDistance, xR - xL);
+    const yL = curLeftContour.y + curLeftContour.peak;
+    const yR = prevRightContour.y + prevRightContour.peak;
+    if (yL <= yR) {
+      curLeftContour = nextLeftContour(curLeftContour);
+    }
+    if (yL >= yR) {
+      prevRightContour = nextRightContour(prevRightContour);
+    }
+  }
+
+  return maxDistance;
+}
+
+perform mergeContour(prev, cur) {
+  if (backside(prev) > backside(cur)) {
+    const extremeRight = getRightThreadLastNode(cur)
+    extremeRight.threadRight = getRightThreadNodeAtY(prev[prev.length - 1], extremeRight.y);
+    extremeRight.modifierThreadRight = ...;
+  } else if (backside(prev) < backside(cur)) {
+    const extremeLeft = getLeftThreadLastNode(prev[0])
+    extremeLeft.threadLeft = getLeftThreadNodeAtY(cur, extremeLeft.y);
+    extremeLeft.modifierThreadLeft = ...;
+  }
+}

Get collided subtree

In the course of the post-order traversal, inside every iteration, we do layouts on subtrees that share the identical guardian.
getCollisionIndex get which subtree the suitable contour node, which produces the maxDistance, belongs to.

The best option to implement is to comply with the guardian pointer of the node to search out the subtree’s root. However within the worst case, it takes O(n^2).

Discover that every subtree can solely take a steady y-span in the suitable contour thread of a forest. And the y-span at all times begins with one other subtree’s backside or 0 and ends with the underside of the subtree.

So we are able to inform which subtree the suitable contour node belongs to by the y place.

Ploeg [5] used a linked checklist to assemble this knowledge construction:

+class IYL {
+  constructor(
+    public backside: quantity,
+    public index: quantity,
+    public subsequent: IYL | null
+  ) {}
+
+  replace(minY: quantity, index: quantity) {
+    let cur = this;
+    whereas (cur != null && minY >= cur.backside) cur = cur.subsequent;
+    return new IYL(minY, index, cur);
+  }
+}

perform layoutSubtree(node, kids) {
  if (kids.size == 0) {
    return;
  }

  const prev = [children[0]];
+ let iyl = new IYL(getBottom(kids[0]), 0, null);
  for (let i = 1; i < kids.size; i++) {
    const cur = kids[i];
+   const [distance, collideIndex] = getMoveDistance(prev, cur, iyl);
    cur.relativeX = distance;
    distributeDistanceToInteriorSubtrees(kids, distance, collideIndex, i);
    mergeContour(prev, cur);
    prev.push(cur);
+   iyl = iyl.replace(getBottom(cur), i);
  }

  positionRoot(node);
}

perform getMoveDistance(prev, cur, iyl) {
  const curLeftContour = cur;
  const prevRightContour = prev[prev.length - 1];
  let maxDistance = 0;
  let collideIndex = 0;
  whereas (curLeftContour && prevRightContour) {
+   if (xR.y + xR.peak > iyl.backside) {
+     iyl = iyl.subsequent;
+   }

    const xL = getRelativeX(curLeftContour)
    const xR = getRelativeX(prevRightContour) + prevRightContour.width + margin;
+   if (xR - xL > maxDistance) {
+     maxDistance = xR - xL;
+     collideIndex = iyl.index;
+   }

    const yL = curLeftContour.y + curLeftContour.peak;
    const yR = prevRightContour.y + prevRightContour.peak;
    if (yL <= yR) {
      curLeftContour = nextLeftContour(curLeftContour);
    }
    if (yL >= yR) {
      prevRightContour = nextRightContour(prevRightContour);
    }
  }

  return [maxDistance, collideIndex];
}

Distribute spacing

We will implement it in a bruit-force means as under. However within the worst case, it causes the general complexity to be .

See Also

perform distributeDistanceToInteriorSubtrees(kids, distance, from, to) {
  for (let i = from + 1; i < to; i++) {
    kids[i].relativeX += (distance * (i - from)) / (to - from)
  }
}
[4] launched a easy trick to make it O(1). On condition that the gap distributed is at all times an arithmetic development, we are able to cache the distinction at first node and clear the impact on the finish node. We want two variables: shiftAcceleration and shiftChange. They’re cached place adjustments that may apply to kids[from+1..to] in finalizeAbsolutePosition.

perform structure(root) {
  root.postOrderTraverse(node => {
    
    layoutSubtree(node, node.kids);
  })

  root.preOrderTraverse(node => {
    finalizeAbsolutePosition(node);
  })
}

perform finalizeAbsolutePosition(node) {
  addChildSpacing(node);
  ...
}

perform addChildSpacing(node) {
  let velocity = 0.;
  let delta = 0.;
  for (const baby of node.kids) {
    velocity += baby.shiftAcceleration;
    delta += velocity + baby.shiftChange;
    baby.relativeX += delta;
  }
}

perform distributeDistanceToInteriorSubtrees(kids, distance, from, to) {
  if (to == from + 1){
    return;
  }

  kids[from + 1].shiftAcceleration += distance/(to-from);
  kids[to].shiftAcceleration -= distance/(to-from);
  kids[to].shiftChange -= distance - distance/(to-from);
}

Remaining Code

Yow will discover the ultimate code of this text here. Nonetheless, there are nonetheless a number of trivial particulars lacking on this abstraction. For particulars, please check with the source code.

Interactive instance

On this instance, you may strive non-layered tidy structure, layered tidy structure, and naive structure.

Node modifying is a typical situation in functions like thoughts maps. If the relayout time is bigger than 16ms, there shall be apparent freezes, which is unacceptable. Subsequently, a partial relayout is required for a easy consumer expertise on giant editable tree visualization.

On this part, we exclude the finalizeAbsolutePosition and solely speak about how you can re-calculate every node’s relative place to their guardian. As a result of altering one node’s measurement could trigger all the tree’s absolute positions to alter, relative positions are far more secure as aesthetic rule 5 required. And within the real-world utility, we solely want absolutely the positions of the nodes contained in the display screen. By detecting the collision between timber’ bounding containers and the display screen, we are able to filter out the offscreen content material swiftly. Strictly talking, the time complexity of partial relayout is O(d + m), the place m is the in-screen nodes quantity, and d is the max depth of modified nodes.

Including the partially relayout assist to the naive model is comparatively straightforward. As a result of the affected states are simple to motive about, i.e., solely the bounding containers of the edited nodes and their ancestors are modified.

For partial relayout, we have to decide which thread pointer caches are outdated. We are saying a subtree is modified if it or its offspring’s sizes change or an insertion or deletion occurs inside this subtree. Notice that

  1. If all nodes inside a subtree will not be modified, the thread pointers of its nodes that time to the node inside this subtree gained’t change. It is because the structure of a tree is agnostic about nodes outdoors. And the thread pointers that time inside are solely affected by the construction of the subtree itself.
  2. In a subtree, solely the deepest nodes, which have the best worth of node.y + node.peak, have thread pointers that time outdoors of the tree. This rule is clear within the mergeContour implementation.
  3. Primarily based on 1 and a pair of, we are able to infer that we solely have to replace the thread pointers of its deepest nodes for an unchanged subtree.
  4. From 3, we are able to infer that if a node and its guardian are roots of unchanged subtrees, we solely have to replace the guardian subtree’s deepest nodes’ threads.
  5. Generalizing 4, for all unchanged subtrees, solely those that are siblings of the modified subtrees have to replace their deepest nodes’ thread pointers.

Primarily based on the above observations, we solely have to relayout the modified subtree and replace its siblings’ thread pointers. Under is the code about partial relayout when there’s a single modified node. We will simply lengthen it to a number of modified nodes.

perform relayout(root, changedNode) {
  let node = changedNode
  whereas (node.guardian) {
    for (const sibling of node.guardian.kids) {
      const r = getRightBottomNode(sibling)
      r.threadRight = null
      r.modifierThreadRight = 0
      const l = getLeftBottomtNode(sibling)
      l.threadRight = null
      l.modifierThreadRight = 0
    }

    layoutSubtree(node.guardian, node.guardian.kids)
    node = node.guardian
  }
}

The code is out there at GitHub. The structure algorithms are written in Rust and compiled to WASM. The renderer is written in TypeScript.



benchmark

Benchmarks have been completed on MacBook Professional (13-inch, M1, 2020). It solely measures the structure algorithm with out the allocation and deallocation time. Mysteriously, the WASM construct is quicker than the native construct on giant knowledge. It is vitally fascinating, however I’ve not came upon why.

Remaining aesthetic problem

The present structure algorithm remains to be not ideally suited in some circumstances.

Because the above instance exhibits, the foundation’s kids will not be symmetric within the present structure although it obeys the aesthetic guidelines. It doesn’t violate aesthetic rule 7, because the drawing of mirrored construction would give a mirrored structure.

To repair this problem, we want a brand new aesthetic rule to formalize the issue.

The Tidy Library

Although tidy tree visualization is helpful in lots of fields, we haven’t seen many adoptions of this algorithm within the trade
as a result of it’s error-prone and slower. I hope Tidy Lib could make the adoption easy and dependable.

The plan is so as to add full assist for partial relayout, compress wasm measurement, and efficiency enchancment.
This lib primarily focuses on the structure algorithm. Constructing a full-fledged tree visualization software or editor just isn’t a precedence of this lib.

This lib is revealed beneath MIT License. Don’t hesitate to contact me if you wish to take part or have any ideas.

  • [1]C. Wetherell and A. Shannon, “Tidy Drawings of Bushes,” IEEE Transactions on Software program 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 Bushes,” IEEE Transactions on Software program 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 common timber,” Software program: Follow and Expertise, vol. 20, no. 7, pp. 685–705, 1990, doi: 10.1002/spe.4380200705.
  • [4] C. Buchheim, M. Jünger, and S. Leipert, “Enhancing 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 timber in linear time,” Software program: Follow and Expertise, vol. 44, no. 12, pp. 1467–1484, 2014, doi: 10.1002/spe.2213.
  • [6] Invoice Mill, “Drawing Presentable Bushes.” https://llimllib.github.io/pymag-trees/ 2008

Profile picture

Source Link

What's Your Reaction?
Excited
0
Happy
0
In Love
0
Not Sure
0
Silly
0
View Comments (0)

Leave a Reply

Your email address will not be published.

2022 Blinking Robots.
WordPress by Doejo

Scroll To Top