Llimllib.github. IO /pymag-trees… The translation of the article, the original text uses python language, the translator uses JavaScript to achieve, and at the end of the article with a detailed analysis of the translator, mind map and other tree structure drawing needs of friends do not miss it.
When I needed to draw some trees for my project, I thought there would be a classic and simple algorithm, but in the end I discovered something interesting: tree layout is not just an NP-complete problem, there is a long and interesting history behind tree drawing algorithms. Next, I’ll go through the tree drawing algorithms that have emerged throughout history, try each of them, and finally achieve a tree drawing algorithm of full O(n) complexity.
What’s the problem?
Give us a tree T, and all we have to do is try to draw it so that other people can understand it at a glance. Each algorithm in this article gives the tree node an (x,y) coordinate, so it can be drawn on the screen or printed out after the algorithm runs.
To store the results of the tree drawing algorithm, we create a DrawTree data structure to mirror the tree we draw. The only thing we have to assume is that each tree node can iterate over its children. The basic implementation of a DrawTree is as follows:
/ / code 1
class DrawTree {
constructor(tree, depth = 0) {
this.x = -1
this.y = depth
this.tree = tree
this.children = tree.children.map((child) = > {
return new DrawTree(child, depth + 1)}}}Copy the codeAs our method gets more complex, the complexity of the DrawTree increases. For now, it simply assigns each node its x-coordinate to -1, its y-coordinate to its depth in the tree, and stores references to tree nodes. It then recursively creates a DrawTree for each node to build the list of child nodes of that node. In this way, we build a DrawTree to represent the tree to be drawn and add specific drawing information to each node.
As we implement better algorithms in this article, we will use principles from each person’s experience to help us build the next better algorithm, and while generating a “beautiful” tree is a matter of taste, these principles will help us optimize the program’s output.
The story begins in Knuth
What we’re going to draw is a special kind of root node at the top, with its children below it, and so on. This kind of graph, and this kind of problem solving, owes a lot to Donald Knuth, from whom we’ll derive the first two principles:
Principle 1: Tree edges should not cross
Rule 2: Nodes of the same depth should be drawn at the same level. This will make the structure of the tree clearer
Knuth’s algorithm is simple and fast, but it is only suitable for binary trees, and will generate some rather deformed graphics, it is a simple tree order traversal, set a global count variable, used as the X coordinate, the counter will increase with the node, the code is as follows:
/ / code 2
let i = 0
const knuth_layout = (tree, depth) = > {
if (tree.left_child) {
knuth_layout(tree.left_child, depth + 1)
}
tree.x = i
tree.y = depth
i += 1
if (tree.right_child) {
knuth_layout(tree.right_child, depth + 1)}}Copy the code
As shown in the figure above, this algorithm generates a tree that satisfies principle 1, but it is not very beautiful. You can see that Knuth’s graph expands quickly horizontally because it does not reuse the X coordinate, even though this makes the tree significantly narrower. To avoid wasting space like this, we can come up with a third principle:
Rule 3: Trees should be drawn as compact as possible
A quick review
Before we move on to more advanced algorithms, let’s pause for some terminology. First, when describing the relationships between our data nodes, we’ll use the analogy of a family tree. Nodes can have children below them, siblings to the left or right, and parents above them.
We’ve talked about middle-order traversal of trees, and we’ll look at pre-order traversal and post-order traversal, three terms you might have seen in a “data Structure” class a long time ago, but unless you’ve been working with trees lately, you’re probably already a little fuzzy about them.
Traverse way just decided we conducted on a given node processing time, in sequence traversal, namely above Knuth algorithm, only accept a binary tree, means that we will deal with the left child node, then the current node, and then the right child nodes, preorder traversal, means that we deal with the current node first, then process all of its child nodes, Post-order traversal is just the opposite.
Finally, you probably already know the concept of the capital O symbol, which is used to indicate the time complexity of an algorithm, and we will mention it from time to time throughout this article as a simple tool to determine whether an algorithm is acceptable in terms of runtime. If an algorithm frequently traverses all the children of a node in its main loop, we call its time complexity O(n^2), otherwise O(n). If you want more details, the paper cited at the end of this article contains a lot of information about the time complexity of these algorithms.
From the bottom up
Two men, Charles Wetherell and Alfred Shannon, came along in 1979, eight years after Knuth had proposed a tree layout algorithm. They introduced some innovative techniques. First, they showed how to generate as compact a tree as possible that met the first three principles. Only the position of the next node at the same depth needs to be maintained:
/ / code 3
const nexts = []
const minimum_ws = (tree, depth = 0) = > {
if (nexts[depth] === undefined) {
nexts[depth] = 0
}
tree.x = nexts[depth]
tree.y = depth
nexts[depth] += 1
tree.children.forEach((child) = > {
minimum_ws(child, depth + 1)})}Copy the code
Although this algorithm produces a tree that meets all of our principles, you’ll probably agree that it’s ugly to actually draw it. Even in a simple tree like the one above, it’s hard to quickly determine the relationship between the tree nodes, and the whole tree seems to be squeezed together. Now it’s time to introduce the next principle, which will help optimize Knuth and minimum width trees:
Rule 4: The parent node should be in the middle of the child node
So far, we can use a very simple algorithm to draw the tree is because we have no real consider each node itself, we rely on the global counter to prevent overlapping nodes, in order to meet the parent node principle, in the middle of a child node, we need to consider each node state of its own context, so need some new strategies.
Wetherell and Shannon introduced the first strategy is through the tree after the sequence traversal tree from the bottom to start building, rather like code 2 from top to bottom, or through the middle like a code 3, as long as you look at this tree in this way, then let the parent node center is a very simple operation, as long as the child nodes of the x coordinate it into two and a half.
But we must remember that on the right side of the tree construction, attention should be paid to the left side of the tree, as shown in the above, the right side of the tree is pushed to the right in order to accommodate the left, in order to achieve this separation, Wetherell and Shannon in code 2 through the array on the basis of maintaining the next available points, but only in the center the parent tree can lead to the right side of the tree and left overlap, Use the next available location.
ModsandRockers
Before we see more code, let’s take a closer look at the results of the build tree from bottom to top, if the node is a leaf node, we will give it to the next available x coordinates, if it is a branch, it is centered on its child nodes, however, if the branch center will cause it clashed with the other part of the tree, We need to move it correctly enough to avoid conflict.
When we move the branch correctly, we need to move all of its children, otherwise we will lose the central parent we have been trying to maintain. It is easy to write a function that moves the branch and its children correctly:
/ / code 4
const move_right = (branch, n) = > {
branch.x += n
branch.children.forEach((child) = > {
move_right(child, n)
})
}
Copy the codeThe above function works, but there is a problem. If we use this function to move a subtree to the right, we will recurse (move the tree) in the recursion (place tree nodes), which means that our algorithm is very inefficient with O(n²) time.
To solve this problem, we will add a mod attribute to each node, and when we reach a branch we need to move n Spaces correctly, we will add n to the x coordinate, assign the value to the mod attribute, and happily continue to execute the layout algorithm because we are moving from bottom to top, So don’t worry about the bottom of the tree colliding (we’ve already shown that they don’t), let’s wait until we get them moving correctly.
Once performed the first tree traversal, we start to the second traversal process, will need to correct mobile branch to move, because we traverse the each node only once, and only perform arithmetic operations, we can determine the time complexity and, for the first time is O (n), so the two together is O (n).
The following code shows how to center the parent node and use the mod attribute to make the code more efficient:
5 / / code
class DrawTree {
constructor(tree, depth = 0) {
this.x = -1;
this.y = depth;
this.tree = tree;
this.children = tree.children.map((child) = > {
return new DrawTree(child, depth + 1);
});
this.mod = 0; }}const setup = (tree, depth = 0, nexts = {}, offset = {}) = > {
tree.children.forEach((child) = > {
setup(child, depth + 1, nexts, offset);
});
tree.y = depth;
let place;
let childrenLength = tree.children.length
if (childrenLength <= 0) {
place = nexts[depth] || 0;
tree.x = place;
} else if (childrenLength === 1) {
place = tree.children[0].x - 1;
} else {
let s = tree.children[0].x + tree.children[1].x;
place = s / 2;
}
offset[depth] = Math.max(offset[depth] || 0, (nexts[depth] || 0) - place);
if (childrenLength > 0) {
tree.x = place + offset[depth];
}
if (nexts[depth] === undefined) {
nexts[depth] = 0;
}
nexts[depth] += 2;
tree.mod = offset[depth];
};
const addmods = (tree, modsum = 0) = > {
tree.x = tree.x + modsum;
modsum += tree.mod;
tree.children.forEach((child) = > {
addmods(child, modsum);
});
};
const layout = (tree) = > {
setup(tree);
addmods(tree);
return tree;
};
Copy the codeTree as Block Block
Although in many cases, it has a good effect, but the code may also produces some strange trees, like the picture above (sorry, figure was lost in the long river of time, Wetherell – Shannon algorithm of another understanding of the difficulty is that the same tree structure, when in the different position of the tree, may draw different structure. To solve this problem, we will borrow a principle from the paper of Edward Reingold and John Tilford:
Principle 5: The same subtree should draw the same result no matter where in the tree
Although this increases the width of our drawings, this principle helps them convey more information. It also helps simplify bottom-up traversal, for example, once we’ve figured out the X-coordinate of a subtree, we just need to move it left or right as a unit.
Here is the algorithm for code 6:
- Perform a backward traversal of the tree
- If a node is a leaf node, give it a value of
0thexcoordinates - Otherwise, place its right subtree as close as possible to its left subtree without conflict
- Use the same as before
modWay,O(n)Time to move the tree
- Use the same as before
- Place the node between its children
- One more time through the tree, will accumulate
modeValue added to thexCoordinate on
This algorithm is simple, but to implement it, we need to introduce some complexity.
outline
The outline of tree is a tree on the side of the maximum or minimum of the coordinates of the list, as shown above, there are two trees, they overlap, if we are along the left side of the tree on the left, take the smallest x coordinates of each layer, we can get [1, 1, 0], we called it the tree left outline, if we go along the right, the right the x coordinate of each layer, You get [1, 1, 2], which is the right-hand outline of the tree.
In order to find the left contour of the tree on the right, we also take the x coordinate of the leftmost node of each layer and get [1, 0, 1]. At this point, we can see that the contour has an interesting feature, that is, not all nodes are connected in parent-child relationship, and 0 of the second layer is not the parent node of 1 of the third layer.
If I want to connect the two trees according to code 6, we can find the right contour of the left tree, and the left contour of the right tree. Then we can easily find the minimum value we need to push the right tree to the right so that it does not overlap the left tree. The following code is a simple implementation:
/ / code 7
const lt = (a, b) = > {
return a < b
}
const gt = (a, b) = > {
return a > b
}
// [a, b, c],[d, e, f] => [[a, d], [b, e], [c, f]]
const zip = (a, b) = > {
let len = Math.min(a.length, b.length)
let arr = []
for(let i = 0; i < len; i++) {
arr.push([a[i], b[i]])
}
return arr
}
const push_right = (left, right) = > {
// The right outline of the left tree
let wl = contour(left, lt)
// The left outline of the right tree
let wr = contour(right, gt)
let res = zip(wl, wr)
let arr = res.map((item) = > {
return item[0] - item[1]})return Math.max(... arr) +1
}
// Get the outline of a tree
const contour = (tree, comp, level = 0, cont = null) = > {
// There is only one root node, so add it directly
if (cont === null) {
cont = [tree.x]
} else if (cont.length < level + 1) {// This level is not yet added
cont.push(tree.x)
} else if (comp(cont[level], tree.x)) {// This level already has a value, so compare
cont[level] = tree.x
}
tree.children.forEach((child) = > {
contour(child, comp, level + 1, cont)
})
return cont
}
Copy the codeIf we run push_right with the two trees above, we can get the right outline of the left tree [1, 1, 2] and the left outline of the right tree [1, 0, 1], then compare these lists to find the maximum space between them and add a space to fill them. For the two trees above, pushing the tree on the right by two Spaces will prevent it from overlapping with the tree on the left.
A new thread
Using code 7, we can find the correct how far is the need to push on the right side of the tree of values, but in order to do this, we need to scan the two subtrees of the outline of each node to get we need, because it needs the time complexity is likely to be O (n ^ 2), Reingold and Tilford, introduced the concept of a confused, is called a thread, They are completely different from threads used for parallel execution.
Threading is a way to reduce the time it takes to scan a subtree contour by creating links between nodes on the contour (if one node is no longer a child of another node), as shown in the figure above, where dashed lines represent a thread and solid lines represent parent-child relationships.
We can also take advantage of the fact that if one tree is deeper than the other, we just need to go down to the shorter tree. Any deeper content does not require the two trees to separate again, as there is no possibility of conflict between them.
Using threads and traversing into shorter trees, we can get an outline of the tree and set up threads in linear time complexity using the following code.
8 / / code
const nextright = (tree) = > {
if (tree.thread) {
return tree.thread
} else if (tree.children.length > 0) {
return tree.children[tree.children.length - 1]}else {
return null}}const nextleft = (tree) = > {
if (tree.thread) {
return tree.thread
} else if (tree.children.length > 0) {
return tree.children[0]}else {
return null}}const contour = (left, right, max_offset = 0, left_outer = null, right_outer = null) = > {
if (left_outer === null) {
left_outer = left
}
if (right_outer === null) {
right_outer = right
}
if (left.x - right.x > max_offset) {
max_offset = left.x - right.x
}
let lo = nextleft(left)
let li = nextright(left)
let ri = nextleft(right)
let ro = nextright(right)
if (li && ri) {
return contour(li, ri, max_offset, lo, ro)
}
return max_offset
}
Copy the codeObviously, this procedure accesses only two nodes at each level of the scanned subtree.
Let’s combine them
The procedure for calculating the contour in Code 8 is neat and quick, but it doesn’t work with the modding approach we discussed earlier, because the actual x-coordinate of a node is the x value of that node plus the sum of all the mod values along the path from it to the root node. To solve this problem, we need to add some complexity to the contour algorithm.
The first thing we need to do is to maintain two additional variables, the sum of the mod values of the left subtree and the sum of the mod values of the right subtree, which are necessary to calculate the actual position of each node on the contour, so that we can check if it conflicts with nodes on the other side:
/ / code 9
const contour = (left, right, max_offset = null, loffset = 0, roffset = 0, left_outer = null, right_outer = null) = > {
let delta = left.x + loffset - (right.x + roffset)
if (max_offset === null || delta > max_offset) {
max_offset = delta
}
if (left_outer === null) {
left_outer = left
}
if (right_outer === null) {
right_outer = right
}
let lo = nextleft(left_outer)
let li = nextright(left)
let ri = nextleft(right)
let ro = nextright(right_outer)
if (li && ri) {
loffset += left.mod
roffset += right.mod
return contour(li, ri, max_offset, loffset, roffset, lo, ro)
}
return [li, ri, max_offset, loffset, roffset, left_outer, right_outer]
}
Copy the codeThe other thing we need to do is return the current state of the function on exit so that we can set the appropriate offset on the thread node. Armed with this information, we can look at this function, which uses code 8 to make the two trees as close together as possible:
10 / / code
const fix_subtrees = (left, right) = > {
let [li, ri, diff, loffset, roffset, lo, ro] = contour(left, right)
diff += 1
diff += (right.x + diff + left.x) % 2
right.mod = diff
right.x += diff
if (right.children.length > 0) {
roffset += diff
}
if(ri && ! li) { lo.thread = ri lo.mod = roffset - loffset }else if(li && ! ri) { ro.thread = li ro.mod = loffset - roffset }return (left.x + right.x) / 2
}
Copy the codeOnce we’re done with the contour process, we add 1 to the maximum difference between the left and right trees, so they don’t clash, and if the midpoints are odd, we add another 1, which makes our testing easier – all nodes have integer x coordinates, without loss of accuracy.
We then move the tree on the right by the appropriate distance to the right. Remember, the reason we add diff to the x-coordinate and also save diff to the mod property is that mod values are only used for nodes below the current node. If the right subtree has more than one child, we add the difference to roffset because all the children of the right node have to move that far to the right.
If the left side of the tree is deeper than the right, or vice versa, we need to set up a thread. We simply check to see if the node pointer on one side advances further than the node pointer on the other, and if so, set the thread from the outside of the shallow tree to the inside of the deep tree.
To properly handle the mod values we mentioned earlier, we need to set a special mod value on the thread node, since we have updated our right offset value to reflect the amount of movement on the right side of the tree, all we need to do is set the thread node mod value to the difference between the offset of the deeper tree and itself.
Now that we have the appropriate code to find the contour of the tree and place the two trees as close together as possible, we can easily implement the algorithm described above. I’ll render the rest of the code uncommented:
/ / code 11
const layout = (tree) = > {
return addmods(setup(tree))
}
const addmods = (tree, mod = 0) = > {
tree.x += mod
tree.children.forEach((child) = > {
addmods(child, mod + tree.mod)
})
return tree
}
const setup = (tree, depth = 0) = > {
if (tree.children.length === 0) {
tree.x = 0
return tree
} else if (tree.children.length === 1) {
tree.x = setup(tree.children[0], depth + 1).x
return tree
}
left = setup(tree.children[0], depth + 1)
right = setup(tree.children[1], depth + 1)
tree.x = fix_subtrees(left, right)
return tree
}
Copy the codeExtend to the n-fork tree
Now that we finally have an algorithm for drawing binary trees that meets all of our principles, looks good in most cases, and is linear in time, it’s natural to think about how to scale it up to support any number of child nodes. If you keep looking at this, you might be wondering, do we just apply the nice algorithm we just defined to all the children of the node.
Extend the previous algorithm to work on multi-fork trees:
- Perform a backward traversal of the tree
- If the node is a leaf node, give it a value of
0thexcoordinates - Otherwise, it iterates through its children, placing them as close as possible to its sibling to the left
- Place the parent node between its leftmost and rightmost children
This algorithm works, and quickly, but there is a problem. It fills all the subtrees of the node to the left as far as possible. If the right-most node conflicts with the left-most node, the middle tree will be filled to the right. Let’s solve this problem by applying the last principle of drawing trees:
Rule 6: Children of the same parent node should be evenly spaced
In order to draw n-branch trees symmetrically and quickly, we need to use all the techniques we’ve learned so far, and add some new ones, and thanks to a recent paper by Christoph Buchheim et al., we have all the knowledge we need to do this and still be able to do it in linear time.
To modify the above algorithm so that it satisfies principle 6, we need a way to separate the trees between two conflicting trees. The simplest way is to divide the available space by the number of trees whenever two trees collide, and then move each tree so that its and its neighboring trees are separated by that distance. For example, in the figure above, there is a distance N between the trees on the right and the trees on the left, and there are three trees between them. If we take the distance n/3 between the first tree and the distance N /3 between the trees on the left, and the next tree and the distance N /3 between the trees, and so on, we get a tree that satisfies principle 6.
Every simple algorithm we’ve looked at so far in this article has found a flaw, and this one is no exception. If we had to move all the trees between every two conflicting trees, we would introduce another O(n^2) operation into the algorithm.
The solution to this problem is similar to the shift problem we solved earlier, we introduce mods, instead of moving each subtree in the middle every time there is a conflict, we save the value of the tree we need to move in the middle and apply it after we have placed all the nodes.
In order to correctly calculate the distance we need to move the middle node, we need to be able to find the number of trees between the two nodes conflict, when we only have two trees, obviously, all conflicts occur between ZuoShuHe right tree, as any tree, find out what tree caused the conflict has become a challenge.
In order to cope with this challenge, we will introduce a default the ancestors of the variables, and the tree data structure to add another member, we call it the ancestor, ancestor either point to their own, or point to which it belongs the root of the tree, when we need to find a belong to which a tree node, if this attribute is set up to use it, Otherwise, use default_ancestor.
When we place the first child of a node tree, we put the default_ancestor pointing in the direction of the subtree, assuming that if clashed under a tree, so it must be with the first tree, when we place the second tree, we distinguish between two kinds of circumstances, if the second is not the first tree KeZi deep, we traverse the right contour, Set the ancestor property to the root of the second tree. Otherwise, the second tree will be deeper than the first. This means that anything that conflicts with the next tree will be placed in the second tree, so we just need to set the default_ancestor to point to it.
Without further ado, let’s take a look at a tree rendering algorithm of O(n) time complexity proposed by Buchheim:
See the next section:)
conclusion
In this article, I left out a few things because I felt it was more important to try and present a logical progression for the final algorithm, rather than reloading the article with pure code. If you want to see more details, or to see the data structure of the tree used in each code listing, you can go to github.com/llimllib/py… The repository downloads the source code for each algorithm, some basic tests, and the code used to generate the tree images for this article.
reference
1 K. Marriott, NP-Completeness of Minimal Width Unordered Tree Layout, Journal of Graph Algorithms and Applications, Vol. 8, No. 3, pp. 295-312 (2004). www.emis.de/journals/JG…
2 D. E. Knuth, Optimum binary search trees, Acta Informatica 1 (1971)
3 C. Wetherell, A. Shannon, Tidy Drawings of Trees, IEEE Transactions on Software Engineering. Volume 5, Issue 5
4 E. M. Reingold, J. S Tilford, Tidier Drawings of Trees, IEEE Transactions on Software Engineering. Volume 7, Issue 2
5 C. Buchheim, M. J Unger, and S. Leipert. Improving Walker’s algorithm to run in linear time. In Proc. Graph Drawing (GD), 2002. Citeseerx.ist.psu.edu/viewdoc/dow…
The translator’s personal play
Algorithm detailed decomposition
Although the author has spent so much space to extract the final algorithm, but directly put out, most of the probability is still not understand, so translators try to break down, want to directly see the original can click on listing12.py.
The node class is as follows, be sure to take a closer look at the right() and left() methods:
// Tree node class
class DrawTree {
constructor(tree, parent = null, depth = 0, number = 1) {
// Node name
this.name = tree.name;
/ / coordinates
this.x = -1;
this.y = depth;
/ / child nodes
this.children = tree.children.map((child, index) = > {
return new DrawTree(child, this, depth + 1, index + 1);
});
/ / the parent node
this.parent = parent;
// thread node, which points to the next contour node
this.thread = null;
// The difference between x positioned according to the left sibling and x positioned according to the middle of the child node
this.mod = 0;
// Point either to itself or to the root of the tree
this.ancestor = this;
// Record the allocated offset
this.change = this.shift = 0;
// The left-most sibling node
this._lmost_sibling = null;
// This is its position index in sibling nodes 1... n
this.number = number;
}
// Returns the thread node if the thread is associated, otherwise returns the rightmost child node, which is the next node in the tree's right contour
right() {
return (
this.thread ||
(this.children.length > 0
? this.children[this.children.length - 1]
: null)); }Returns the thread node if the thread is associated, otherwise returns the leftmost child node, which is the next node in the tree's left contour
left() {
return (
this.thread || (this.children.length > 0 ? this.children[0] : null)); }// Get the previous sibling node
left_brother() {
let n = null;
if (this.parent) {
for (let i = 0; i < this.parent.children.length; i++) {
let node = this.parent.children[i];
if (node === this) {
return n;
} else{ n = node; }}}return n;
}
// Get the first sibling node of the same level, or null if the first sibling is itself
get_lmost_sibling() {
if(!this._lmost_sibling &&
this.parent &&
this! = =this.parent.children[0]) {this._lmost_sibling = this.parent.children[0];
}
return this._lmost_sibling;
}
// The first sibling of the same level
get leftmost_sibling() {
return this.get_lmost_sibling(); }}Copy the codeTo enter the first recursion, the processing is as follows:
1. The current node is a leaf node and has no left sibling. X is set to 0
2. The current node is a leaf node and has a left sibling. X is the x of the left sibling plus the spacing, that is, the location is based on the left sibling
3. The current node is a non-leaf node and has no left brother. X is the x of the first child node plus the x of the last child node divided by 2
4. The current node is a non-leaf node and has a left sibling. X is the x of the left sibling plus the spacing, and mod is set as the difference between x and the child node
// The first recursion
const firstwalk = (v, distance = 1) = > {
if (v.children.length === 0) {
// If the current node is a leaf node and there is a left sibling, then its x-coordinate is equal to its left sibling's x-coordinate plus distance
if (v.leftmost_sibling) {
v.x = v.left_brother().x + distance;
} else {
// The current node is a leaf node with no left sibling, so the x-coordinate is 0
v.x = 0; }}else {
// Recurse the child nodes first
v.children.forEach((child) = > {
firstwalk(child);
});
// The midpoint of the child node
let midpoint =
(v.children[0].x + v.children[v.children.length - 1].x) / 2;
/ / left brothers
let w = v.left_brother();
if (w) {
// There is a left sibling node whose x-coordinate is set to the x-coordinate of its left sibling plus the spacing distance
v.x = w.x + distance;
// Also record the offset (the difference between the x coordinate and the midpoint of the child node)
v.mod = v.x - midpoint;
} else {
// There is no left sibling node, the x-coordinate is directly the midpoint of the child nodev.x = midpoint; }}return v;
};
Copy the codeThe second recursion adds the mod value to x so that the parent node is still centered on the child node:
// The second pass
const second_walk = (v, m = 0, depth = 0) = > {
// The initial x value plus the mods of all parent nodes (not including their own mods)
v.x += m;
v.y = depth;
v.children.forEach((child) = > {
second_walk(child, m + v.mod, depth + 1);
});
};
Copy the codeThe whole process is two recursions:
const buchheim = (tree) = > {
let dt = firstwalk(tree);
second_walk(dt);
return dt;
};
Copy the codeNode position after the first recursion:
Node position after the second recursion:
The subtrees that are obviously in conflict are G and P, and the subtree P has to move to the right by a certain distance. How do we calculate that distance?
1. Enter the second layer of subtree G and P, find the right-most child node F of subtree G in this layer, find the left-most child node I of subtree P in this layer, compare their X coordinates, the sum of the original X value plus the mod value of their ancestor node, and find that there is no crossover, so enter the next layer.
2. Enter the third layer, find the right-most child node E of subtree G in this layer, and the left-most child node J of subtree P in this layer. Compare their x, and find that there is crossover
3. Repeat until you reach the bottom.
So how to find the most left or right node of each layer in the fastest way? Of course, it can be directly recursive, but the time complexity is nonlinear, so the concept of thread mentioned above is introduced.
Node in the diagram above G as an example to introduce the thread connection process, after you come back from the child nodes of the C because there is no left C brothers, don’t deal with, so to F node recursive, followed by processing since coming back from F node F node, the brothers left C it, because each tree has, medial and lateral so we set up four Pointers:
VInnerLeft is the left sibling of the current node, vOuterLeft is the leftmost sibling of the current node, of course for F both Pointers point to C, vInnerRight and vOuterRight both point to the current node initially.
Next we set the thread from the outside of the shallow tree to the inside of the deep tree:
1. Since both C and F nodes have child nodes, this layer cannot determine which tree is deep and which is shallow, so it moves down one layer and updates four Pointers at the same time. Here, the left() or right() method of the node is used:
There are four hands, how to determine whether there is the next layer, because we want to check node conflict is based on the inside of the two trees are compared, so it only need to check the inside of the two node pointer to judge whether there is the next layer, we can stop, just go to the shallow tree tree node will not conflict, deeper So check whether both vinnerleft.right () and vinnerright.left () exist.
2. After moving down one layer, it is found that the leaf node of F has been reached. Then we will judge and repeat our principle:
Set the thread from the outside of the shallow tree to the inside of the deep tree
The shallow tree is the F subtree, and the deep tree is the C subtree, so the outside of F is set to the inside of C, that is, the E node and the A node are connected by thread.
Specific judgment rules are as follows:
2.1. If the vinnerLeft.right () node exists and vouterRight.right () node does not exist, vouterRight.right () node does not exist, Set the thread thread property on the vOuterRight node to the vinnerLeft.right () node, which is exactly what it is, so e.Read points to A.
2.2. If vouterleft.left () does not exist and vinnerright.left () does not exist, Set the thread property on the vOuterLeft node to point to the vinnerright.left () node, which obviously does not meet the criteria.
For all other nodes, this method is used to judge, and finally the thread node connection in the tree is:
Because we are after the sequence traversal tree, so the earlier the lower nodes of thread connection, such as processing when O nodes will connect the nodes I and J, so in the back processing nodes, the P has reached the node I, but because of the thread I node, so to some extent, it is not “leaf node”, So I can’t be connected to any other node.
// The first recursion
const firstwalk = (v, distance = 1) = > {
if (v.children.length === 0) {
// ...
} else {
v.children.forEach((child) = > {
firstwalk(child);
apportion(child);// ++
});
// ...
}
// ...
}
const apportion = (v) = > {
let leftBrother = v.left_brother();
// Only if there is a left brother
if (leftBrother) {
// Four Pointers to nodes
let vInnerRight = v;// Right subtree left outline
let vOuterRight = v;// Right subtree right outline
let vInnerLeft = leftBrother;// The left sibling of the current node, the right outline of the left subtree
let vOuterLeft = v.leftmost_sibling;// The leftmost sibling of the current node, the left contour of the left subtree
// All the way to the leaf node
while(vInnerLeft.right() && vInnerRight.left()) {
// Update the pointer
vInnerLeft = vInnerLeft.right()
vInnerRight = vInnerRight.left()
vOuterLeft = vOuterLeft.left()
vOuterRight = vOuterRight.right()
}
// Set the thread from the outside of the shallow tree to the inside of the deep tree
if(vInnerLeft.right() && ! vOuterRight.right()) { vOuterRight.thread = vInnerLeft.right(); }else {
if(vInnerRight.left() && ! vOuterLeft.left()) { vOuterLeft.thread = vInnerRight.left(); }}}};Copy the codeWhen thread nodes are connected, then we can judge whether there is a crossover between two trees according to the contour. Similarly, because we are traversal after order, when we judge whether there is a conflict between a subtree, the node threads below it must have been connected and can be directly used.
The logic of judging according to contour is also in the apportion method:
// The first recursion
const firstwalk = (v, distance = 1) = > {
if (v.children.length === 0) {
// ...
} else {
v.children.forEach((child) = > {
firstwalk(child);
apportion(child, distance);// distance++
});
// ...
}
// ...
}
const apportion = (v, distance) = > {
let leftBrother = v.left_brother();
if (leftBrother) {
// ...
// Go down from the current node to determine if there is a conflict with the left subtree
while(vInnerLeft.right() && vInnerRight.left()) {
// ...
// Left node minus right node
let shift = vInnerLeft.x + distance - vInnerRight.x
if (shift > 0) {
// If the value is greater than 0, the tree on the right will move to the right
move_subtree(v, shift)
}
}
// ...}}// Move the subtree
const move_subtree = (v, shift) = > {
v.x += shift// move itself
v.mod += shift// Descendant node moves
}
Copy the codeTaking node P as an example, the process is as follows:
Vinnerleft.right () exists (h.right ()=F), vinnerright.left () exists (p.left ()=I), so move down one layer:
By comparing the difference of x coordinates of F and I nodes, it can be found that there is no conflict between them, so proceed to the next layer:
This comparison will find that E and J nodes conflict, so the subtree P needs to move to the right a certain distance as a whole.
Of course, the above code is problematic because a node’s true final x-coordinate is plus the mod values of all its ancestors, so we add four variables to add the mod values:
const apportion = (v, distance) = > {
if (leftBrother) {
// Four Pointers to nodes
// ...
Mod - (vInnerRight. X + parent node. Mod), parent node. Mod can be removed. So it doesn't matter if you don't include a mod for the ancestor node of the face
let sInnerRight = vInnerRight.mod;
let sOuterRight = vOuterRight.mod;
let sInnerLeft = vInnerLeft.mod;
let sOuterLeft = vOuterLeft.mod;
// Go down from the current node to determine if there is a conflict with the left subtree
while (vInnerLeft.right() && vInnerRight.left()) {
// ...
// The left node is subtracted from the right node
let shift = vInnerLeft.x + sInnerLeft + distance - (vInnerRight.x + sInnerRight);
if (shift > 0) {
// ...
// shift, sInnerRight, sOuterRight should also be added
sInnerRight += shift;
sOuterRight += shift;
}
// Add the current layer node mod
sInnerRight += vInnerRight.mod;
sOuterRight += vOuterRight.mod;
sInnerLeft += vInnerLeft.mod;
sOuterLeft += vOuterLeft.mod;
}
// ...}};Copy the codeThe effect is as follows:
But there is still have problem, why, for example for node E, it is tired with the node mod value of F, H, but the problem is not E H node’s ancestors, they just produced through a thread dotted line connection, with the actual mod value of F and G should be node, this to do, or in the case, We assume that mod values for some nodes are as follows:
Then the actual mod value to be accumulated for node A should be:
B.mod + C.mod + G.mod = 1 + 2 + 3 = 6
Copy the codeBut because of the thread connection, the actual cumulative mod value becomes:
E.mod + F.mod + H.mod = 0 + 4 + 0 = 4
Copy the codeIt would be nice if we could set a special mod value on thread nodes E and H to compensate for the difference, since there are no children below them anyway, so whatever mod value we set for them doesn’t matter. What about this particular mod value? It is very simple, for example, when F is first processed, it has left node C, so do thread connection judgment for the nodes below them, because they all have children, so move down one level, and F subtree is finished, C subtree is not, and vinnerleft.right () &&! The condition of vouterright.right () connects E to A. For C and F, the ancestor is the same, so the mod value of the ancestor is irrelevant. For A, the mod value that it really adds is B.mod + C.mod. According to the thread connection, the mod value it will add is E.mod + F.mod. The operation results of the two formulas should be the same, so e.mod is obviously equal to B.Mod + C.MOD -F.mod, namely sInnerLeft – sOuterRight. Modify the code as follows:
// Set the thread from the outside of the shallow tree to the inside of the deep tree
if(vInnerLeft.right() && ! vOuterRight.right()) { vOuterRight.thread = vInnerLeft.right();// Fixed mods stacking error due to threading, deep tree subtracting shallow tree
vOuterRight.mod += sInnerLeft - sOuterRight// ++
} else {
if(vInnerRight.left() && ! vOuterLeft.left()) { vOuterLeft.thread = vInnerRight.left(); vOuterLeft.mod += sInnerRight - sOuterLeft// ++}}Copy the codeThe effect is as follows:
Conflict is not here, but the location of the H should center, is obviously want to move to the right, how much mobile, subtree P moved to the right shift distance, the distance need to split to G, H, P on the spacing between three nodes, assuming that the two conflict between subtree of fruit tree number n, then the shift/(n + 1), We can just move H to the right by this distance.
Which is, in other words, we must first find a clash between two KeZi tree, can fix them between the trees, the picture above you can see the conflict is E, and J node for J node, we must know it belongs to the top of the current subtree P, it can be as long as you can find the E nodes belonging to a tree, we can see at a glance is G nodes, but the code without eyes, We can just go up and find it, but we can’t do that for linear time.
We set an ancestor attribute for each node, which initially points to itself. For E node, although it belongs to vInnerLeft node in the conflict judgment, it belongs to vOuterRight node in the tree it belongs to, so in the thread connection stage, We can set the ancestor of the vOuterRight node of each layer to point at the top node V, but this pointing does not always meet our requirements. For example, the N node in the figure above, its ancestor successfully points at the P node, but for the E node, Its ancestor refers to its parent node F, but we need G, so let’s set another variable named default_ancestor. If the ancestor of a node does not meet our requirements, the node named default_ancestor is used. The cursor is then updated as it returns from each child. If the former child is not as deep as the latter child, then the default_ancestor updates to point to the latter child because if the right subtree conflicts with the left, So it must be with the deeper one.
const firstwalk = (v, distance = 1) = > {
if (v.children.length === 0) {
// ...
} else {
let default_ancestor = v.children[0]// ++ initially points to the first child node
v.children.forEach((child) = > {
firstwalk(child);
default_ancestor = apportion(child, distance, default_ancestor);// Update the default_ancestor after each child}); }}const apportion = (v, distance, default_ancestor) = > {
let leftBrother = v.left_brother();
if (leftBrother) {
// ...
while (vInnerLeft.right() && vInnerRight.left()) {
// ...
// Each layer of right contour nodes below node v is associated with v
vOuterRight.ancestor = v;// ++
// ...
}
// ...
if(vInnerLeft.right() && ! vOuterRight.right()) {// ...
} else {
// ...
default_ancestor = v// If the previous node is not as deep as the current node, then default_ancestor points to the current node}}return default_ancestor;// ++
}
Copy the codeThen we can find the root node of the conflicting node in the left tree:
const apportion = (v, distance, default_ancestor) = > {
let leftBrother = v.left_brother();
if (leftBrother) {
// ...
while (vInnerLeft.right() && vInnerRight.left()) {
// ...
let shift = vInnerLeft.x + sInnerLeft + distance - (vInnerRight.x + sInnerRight);
if (shift > 0) {
// Find the root node of the vInnerLeft node
let _ancestor = ancestor(vInnerLeft, v, default_ancestor)// ++
move_subtree(v, shift);
// ...
}
// ...
}
// ...
}
return default_ancestor;// ++
}
// Find the root node to which the node belongs
const ancestor = (vInnerLeft, v, default_ancestor) = > {
// If the node pointed by the vInnerLeft ancestor is the brother of the V node, then it meets the requirements
if (v.parent.children.includes(vInnerLeft.ancestor)) {
return vInnerLeft.ancestor;
} else {
// Otherwise use the node pointed to by the default_ancestor
return default_ancestor
}
}
Copy the codeAfter finding out the conflict which is two trees, we can find the subtree is between the two trees, and then put the shift to a they can, but we still can’t directly through them, that’s right, or to keep linear time complexity, so only the first share data saved to the root node of the two conflict, Then wait for all of their siblings to recursively complete the setup again.
const firstwalk = (v, distance = 1) = > {
if (v.children.length === 0) {
// ...
} else {
let default_ancestor = v.children[0]
v.children.forEach((child) = > {
firstwalk(child);
default_ancestor = apportion(child, distance, default_ancestor);
});
// Add shift allocation to the x and mod values of the intermediate nodes
execute_shifts(v)// ++
// ...}}const apportion = (v, distance, default_ancestor) = > {
let leftBrother = v.left_brother();
if (leftBrother) {
// ...
while (vInnerLeft.right() && vInnerRight.left()) {
// ...
if (shift > 0) {
let _ancestor = ancestor(vInnerLeft, v, default_ancestor)
move_subtree(_ancestor, v, shift);// ++
// ...
}
// ...
}
// ...
}
return default_ancestor;// ++
}
const execute_shifts = (v) = > {
let change = 0
let shift = 0
// Traverses the child nodes from back to front
for(let i = v.children.length - 1; i >= 0; i--) {
let node = v.children[i]
node.x += shift
node.mod += shift
change += node.change// change is usually a negative value
shift += node.shift + change// The further to the left, the smaller the shift value added to the node}}const move_subtree = (leftV, v, shift) = > {
let subTrees = v.number - leftV.number// Index subtracts to get the number of nodes separated
let average = shift / subTrees// Bisect the offset
v.shift += shift// The full shift value is added to the shift property of the v node
v.change -= average// The node to the left of v has a decreasing offset from right to left, so minus average is added
leftV.change += average// v.change subtracted average, in order not to affect the node left of leftV, here needs to restore
// ...
};
Copy the codeIn the following figure, take a look at the process. Assume that the shift calculated by P node is 3, then P. tumber-g. tumber = 4-1 = 3, and the apportionment value of the middle node is 3/3 = 1. To have the same distance between nodes G and P, H needs to move 1 to the right. If there are more nodes, and so on, because the node to the right has moved itself by 1 and has been pushed to the right by the n nodes in front by n * 1, we store these two values on nodes G and P:
Then execute the execute_shifts method to traverse the children of Q from back to front:
Change: change + p2. change=0 + 0 =0; change: change + p2. change=0 + 0 =0; change: change + p2. change=0; shift + P2.shift + change = 0 + 0 + 0 = 0
Change: change + p.change = 0 + (-1) = -1, change + p.change = 0 + (-1) = -1, change + p.change = 0 + (-1) = -1 shift + P.shift + change = 0 + 3 + (-1) = 2
Change: change + h2. change = -1 + 0 = -1, shift: change + h2. change = -1 + 0 = -1 shift + H2.shift + change = 2 + 0 + (-1) = 1
Change: change + H change = -1 + 0 = -1, change H change: change + H change = -1 + 0 = -1, change H change: change + H change = -1 + 0 = -1, change H change: shift + H.shift + change = 1 + 0 + (-1) = 0
Shift: shift + G change = -1 + 1 = 0, shift: shift + G change + G change = 0, shift + G change + G change = 0
Change: change + g0.change = 0 + 0 = 0; change: change + g0.change = 0 + 0 = 0; shift + G0.shift + change = 0 + 0 + 0 = 0
The above is the translator’s post-mortem understanding, the final effect:
Let’s switch x and y:
Implement mind mapping
The above algorithm cannot be directly applied to mind mapping, because the size of each node in the tree considered above is the same, and the width and height of each node in mind mapping may be different. Therefore, some modifications need to be made on the basis of the above algorithm, because this paper is very long, so I will not go into details. Online Example wanglin2.github. IO /tree_layout… , complete code at github.com/wanglin2/tr… .
Refer to the link
1. Native javascript tree layout algorithm
2. Tree interface rendering algorithm (2) simple and clear first-second
3. Tree interface rendering algorithm (iii) grinding apportion
4. Tree Interface Rendering algorithm (Summary)
5.A Node-positioning Algorithm for General Trees