I wanna understand Buchheim's Tree Drawing Algorithm in JavaScript

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!!!

Thanks for reading!

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"
      @addChild="addNode"
    />
  </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: {
    addNode (parentNode) {

      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"
    />

    <g @click="addChild">
      <circle
        :cx="width/2" :cy="height+2*lineLength" :r="radius"
      />
      <line
        :x1="width/2-(radius/2)" :y1="height+2*lineLength"
        :x2="width/2+(radius/2)" :y2="height+2*lineLength"
      />
      <line
        :x1="width/2" :y1="height+2*lineLength-(radius/2)"
        :x2="width/2" :y2="height+2*lineLength+(radius/2)"
      />
    </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),
      radius: this.node.totalWidth/10,
      lineLength: this.node.totalWidth/10
    }
  },

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

  methods: {
    addChild () {
      this.$emit('addChild', this.node);
    }
  }
}
</script> 

Firstly, welcome to the forums.

While we are primarily here to help people with their Free Code Camp progress, we are open to people on other paths, too. Some of what you are asking is pretty trivial in the Free Code Camp context, so you might find that if you’re not getting the instruction and material you need in your current studies, the FCC curriculum will really help you get started. At a modest guess I’d say investing a 4-5 hours working through the curriculum here will really pay off. You can find the curriculum at https://www.freecodecamp.org/learn.

With your current questions, we don’t have enough context to know what you already know or don’t know, so it is impossible to guide you without just telling you the answer (which we won’t do).

Please provide some example of what you’ve tried (related to the algorithm) and I’m sure you’ll get more help. What specifically do you not understand about the algorithm?

Happy coding :slight_smile:

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