# Why Buchheim’s algorithm?

In this article, the author says that Buchheim’s algorithm is the best amongst other tree drawing algorithms.

According to the original paper, Buchheim’s algorithm is actually an improved version of Walker’s algorithm, so that it runs in O(N) insted of O(N^2).

# What have I done?

So far, I’ve implemented the outline UI using Vue.js (You can see code bellow).
But I failed to implement the most important part, Buchheim’s algorithm.

The UI is reactive, so it updates the tree drawing if x-coordinates of nodes has updated.
So the work left to be done is implementing Buchheim’s algorithm for updating those x-coordinates of each nodes of the tree.

# I would like to ask you …

To implement Buchheim’s algorithm in JavaScript, so that I can learn by using it!

My final goal is not just having implementation of the algorithm, but actually understand how the algorithm works, but currently I struggle to understand how each part of the algorithm works because I have never seen the algorithm in action!

If you could help me out, I really appreciate it!!!

# CODE for UI

### TreeGUI.vue

Please implement buchheim() located below the Node class decralation.

``````<template>
<div>
<svg x="0px" y="0px" width="1000px" height="1000px" viewBox="0 0 1000 1000">
<NodeGUI
v-for="node in data.nodes"
:key="node.id"
:node="node"
/>
</svg>
</div>
</template>

<script>
import NodeGUI from './NodeGUI';

class Node {
constructor (parent) {
// Area of the whole node object, including the rectangle, add button and etc.
this.totalWidth = 100;
this.totalHeight = 80;

// (x, y) that will be caluclated
this.x = -1;
let spacer = 10;
this.y = (parent) ? parent.y + this.totalHeight + spacer: 0;

this.parent = parent;
this.children = [];
}
}

// +++++++++++++++++++++++++++++++++++++
// Tree Positioning Algorithm
// This will update x-coordinate of each node
// function buchheim(node) {
//   firstwalk(node);
//   secondwalk(node);
// }
// +++++++++++++++++++++++++++++++++++++

export default {
name: 'TreeGUI',

components: {
NodeGUI
},

data () {
return {
data: {
// Nodes of the tree
nodes: [
new Node(null)
]
}
}
},

methods: {

let newNode = new Node(parentNode);

parentNode.children.push(newNode);
this.data.nodes.push(newNode);

// Update position (x-coordinate) of each node, every time when new node is added
// buchheim(this.data.nodes[0]);
}
}
}
</script>
``````

### NodeGUI.vue

``````<template>
<g
:transform="transform"
fill="none" stroke="#4B4B4B" :stroke-width="strokeWidth"
>
<rect
x="0" y="0"
:width="width" :height="height"
rx="10" ry="10"
/>

<line
:x1="width/2" :y1="height"
:x2="width/2" :y2="height+lineLength"
/>

<circle
/>
<line
/>
<line
/>
</g>
</g>

</template>

<script>
export default {
name: 'NodeGUI',

props: [
'node'
],

data () {
return {
strokeWidth: this.node.totalWidth/20,
width: this.node.totalWidth,
height: this.node.totalHeight-(3*this.node.totalWidth/10),
lineLength: this.node.totalWidth/10
}
},

computed: {
transform () {
return `translate(\${this.node.x},\${this.node.y})`;
}
},

methods: {
}
}
}
</script>
``````

First of all, thank you for your advice!

Well, I know reccursion, and I can follow the flow of this Buchheim’s algorithm.
So far, I understand the outline of this algorithm.

BUCHHEIM() cosists of two functions, FIRSTWALK() and SECONDWALK().
Both are reccursive.
FIRSTWALK() computes Preliminary-X-Coordinate and Mod of each node.
SECONDWALK() uses caliculated prelim-x and mod to compute Final-X-Coordinate of each node.

SECONDWALK() is fairly simple, but FIRSTWALK() is not.
Specifically, APPORTION() is very difficult to understand.
I read the pesudo code of this APPORTION() function, but I have no idea what it does.
It looks like updating Mod, but how?

I tried to be more specifc, I hope this helps.
Thanks!

1 Like