3
\$\begingroup\$

I'd like to have a discussion on the data model (mostly) for a tree with nodes having multiple children and multiple parents.

I already have a working algorithm, but I'm looking for improvements. The things to keep in mind are the feasibility of the algorithm and the performances. Here is the data I'm using currently:

I have an Array that contains an Array for each level. Every level Array contains at each index a node (which is an object containing required data). So it looks as follow:

var treeData = [
  [{
    level: 0,
    index: 0,
    label: 'root',
    children: [{
      level: 1,
      index: 0
    }, {
      level: 1,
      index: 1
    }]
  }],
  [{
    level: 1,
    index: 0,
    label: 'node1',
    parents: [{
      level: 0,
      index: 0
    }],
    children: [{
      level: 2,
      index: 0
    }]
  }, {
    level: 1,
    index: 1,
    label: 'node2',
    parents: [{
      level: 0,
      index: 0
    }],
    children: [{
      level: 2,
      index: 0
    }]
  }],
  [{
    level: 2,
    index: 0,
    label: 'node3',
    parents: [{
      level: 1,
      index: 0
    }, {
      level: 1,
      index: 1
    }],
  }]
];

I listed the key points of performance that I have in mind bellow. I'll explain basically how it works on my algorithm, the current performances of the data model I use (form my algorithm point of view) and mark the performance of every key point from my point of view.

Note: Memory should not be a problem.

Access to a node (performance: 5/5)

Currently: Instant =)

Because of the access via index, there is no search to access a node.

ie: Only requires node[level][index].


Calculation of a node x and y position (performance: 4/5)

Note: Requires that a node knows its previous sibling, its parents and children.

Currently: correct because of the instant node access

A node do not have information about its previous sibling in its data. So currently I need to use a "trick" and there is a prerequisite of every node in a level being in the correct order ! Meaning I can use the following code from node at level 1 and index 1 to access its previous sibling which is level 1 and index 0: node[node.level][node.index - 1].

I'll mark it 4/5 because I'd have loved the nodes to automatically adapt their position to their neighbor. So That when I insert, I don't have to recalculate, the nodes will adapt themselves. But I didn't come up with a solution to this yet.


Insertion of a node (performance: 0/5)

Note: Not yet perfectly available, mostly because there is no tree balancing algorithm.

Currently: A shame, hard to implement, and possibly very long.

The insertion is the weakness of the data model I'm using. I think it's the worst way to handle an insertion. And that's what makes me think I need to change the data model, because depending on the operation, the performances are very unbalanced.

Here is what I need to do to insert a node:

  • Insert (not push) the node at its level (meaning I need to search its correct position into the level)
  • And recalculate ALL indices.

Yes, recalculate ALL indices. The reason being that every node keeps its index and the indices of each of its parents and children. Also after this step I need to recalculate all positions. Used on big trees, it could take lots of time.


Deletion of a node (performance: 0/5)

Note: Not yet implemented

Currently: I haven't implemented it yet, but I guess it'd work the same way as the insertion. A node removed requires to recalculate all indices at the level and spread it to every affected parents and children.


Questions

  • What would be the most balanced data model ?
  • Do you find any algorithm improvements ?

Here is my implementation: JSFiddle

I'm using Javascript, SVG and VueJS.

Note: There are some issues on the insertion and links curves.

Note: I can detail more the algorithm if you feel it's needed.

/*** COMPONENTS ***/
var nodeTemplate = {
  template: '#node-template',
  props: ['node']
};

var linkTemplate = {
  template: '#link-template',
  props: ['link'],
  methods: {
    getPath
  }
};

/** DATA + SERVICE **/

var data = [
      [{
        level: 0,
        index: 0,
        label: 'root',
        children: [{
          level: 1,
          index: 0
        }, {
          level: 1,
          index: 1
        }]
      }],
      [{
        level: 1,
        index: 0,
        label: 'node1',
        parents: [{
          level: 0,
          index: 0
        }],
        children: [{
          level: 2,
          index: 0
        }]
      }, {
        level: 1,
        index: 1,
        label: 'node2',
        parents: [{
          level: 0,
          index: 0
        }],
        children: [{
          level: 2,
          index: 0
        }]
      }],
      [{
        level: 2,
        index: 0,
        label: 'node3',
        parents: [{
          level: 1,
          index: 0
        }, {
          level: 1,
          index: 1
        }],
      }]
    ];

var treeService = {
  data: data,
  verticalSpacing: 50,
  componentMargin: 25,
  componentHeight: 50,
  componentWidth: 100,
  svgWidth: 0,
  svgHeight: 0,
  svgPadding: {
    top: 50,
    bottom: 0,
    left: 0,
    right: 0
  }
};

/***** ALGO DRAW TREE *****/

/** START TOOLS FUNCTIONS **/
function hasParents(node) {
  return node.parents && node.parents.length > 0;
}

function hasChildren(node) {
  return node.children && node.children.length > 0;
}

function firstParent(node) {
  var firstParent = node;
  var savedX = treeService.svgWidth + treeService.svgPadding.left + treeService.svgPadding.right;

  if (hasParents(node)) {
    node.parents.forEach(function(parent) {
      if (treeService.data[parent.level][parent.index].x < savedX) {
        savedX = treeService.data[parent.level][parent.index].x;
        firstParent = treeService.data[parent.level][parent.index];
      }
    });
  }
  return firstParent;
}

function lastParent(node) {
  var lastParent = node;
  var savedX = 0;

  if (hasParents(node)) {
    node.parents.forEach(function(parent) {
      if (treeService.data[parent.level][parent.index].x > savedX) {
        savedX = treeService.data[parent.level][parent.index].x;
        lastParent = treeService.data[parent.level][parent.index];
      }
    });
  }
  return lastParent;
}

function firstChild(node) {
  var firstChild = node;
  var savedX = treeService.svgWidth + treeService.svgPadding.left + treeService.svgPadding.right;

  if (hasChildren(node)) {
    node.children.forEach(function(child) {
      if (treeService.data[child.level][child.index].x < savedX) {
        savedX = treeService.data[child.level][child.index].x;
        firstChild = treeService.data[child.level][child.index];
      }
    });
  }
  return firstChild;
}

function lastChild(node) {
  var lastChild = node;
  var savedX = 0;

  if (hasChildren(node)) {
    node.children.forEach(function(child) {
      if (treeService.data[child.level][child.index].x > savedX) {
        savedX = treeService.data[child.level][child.index].x;
        lastChild = treeService.data[child.level][child.index];
      }
    });
  }
  return lastChild;
}

function isSameNode(node1, node2) {
  return node1.level == node2.level && node1.index == node2.index;
}

function areSiblings(node1, node2) {
	var siblings = false;
  
	node1.parents.forEach(function(parent1) {
    node2.parents.forEach(function(parent2) {
			if (parent1.level == parent2.level && parent1.index == parent2.index) {
      	siblings = true;
        return;
      }
    });
    if (siblings) {
    	return;
    }
  });
  return siblings;
}

function getParentPosition(node) {
	var index = 0;
  
	for (var i = 1; node.index - i >= 0; ++i) {
  	if (areSiblings(node, treeService.data[node.level][node.index - i])) {
    	++index;
    }
  }

  return index;
}

function hasPreviousSibling(node) {
  // if node is not first child of its first parent
  return getParentPosition(node) != 0;
}

/** END TOOLS FUNCTIONS **/

function calculateWeight(level, index) {
  var node = treeService.data[level][index];

  node.weight = 0;
  if (hasChildren(node)) {
    node.children.forEach(function(child) {
      node.weight += calculateWeight(child.level, child.index);
    });
  } else {
    node.weight = 1;
  }
  return node.weight;
}

function calculateSvgSize() {
  treeService.svgWidth = (treeService.data[0][0].weight * (treeService.componentWidth + treeService.componentMargin)) + treeService.svgPadding.left + treeService.svgPadding.right;
  treeService.svgHeight = (treeService.data.length * treeService.componentHeight) + ((treeService.data.length - 1) * treeService.verticalSpacing) + treeService.svgPadding.top + treeService.svgPadding.bottom;
}

function calculatePositionX(tree, node) {
  var result = 0;

  // root
  if (!node.parents || node.parents.length == 0) {
    result = (treeService.svgWidth / 2);
  } else {
    var firstParent = tree[node.parents[0].level][node.parents[0].index];
    var lastParent = tree[node.parents[node.parents.length - 1].level][node.parents[node.parents.length - 1].index];
    var previousSibling = tree[node.level][node.index - 1];
    var halfComponentSize = (treeService.componentWidth + treeService.componentMargin) / 2;

    var centerX = (firstParent.x + lastParent.x) / 2;
    var halfSiblingSize = firstParent.weight * halfComponentSize;
    var halfOwnSpace = node.weight * halfComponentSize;

    if (hasPreviousSibling(node)) {
      var previousEnd = previousSibling.x + (previousSibling.weight * halfComponentSize);
    }

    result = halfOwnSpace;

    if (hasPreviousSibling(node)) {
      result += previousEnd;
    } else {
      result += centerX - halfSiblingSize;
    }
  }

  return result;
}

function placeNodes(tree) {
  treeService.data.forEach(function(level, levelIndex) {
    level.forEach(function(node, nodeIndex) {
      node.x = calculatePositionX(tree, node) + treeService.svgPadding.left;
      node.y = ((treeService.verticalSpacing + treeService.componentHeight) * levelIndex) + (treeService.componentHeight / 2) + treeService.svgPadding.top;
    });
  });
}

function rePlaceRoot() {
  var halfComponentSize = (treeService.componentWidth + treeService.componentMargin) / 2;

  var centerX = (treeService.svgWidth / 2);
  var firstChildHalfSpace = treeService.data[1][0].weight * halfComponentSize;
  var lastChildHalfSpace = treeService.data[1][treeService.data[1].length - 1].weight * halfComponentSize;

  treeService.data[0][0].x = ((treeService.svgWidth - firstChildHalfSpace - lastChildHalfSpace) / 2) + firstChildHalfSpace;
}

function calculateFullTree() {
  calculateWeight(0, 0);
  calculateSvgSize();
  placeNodes(treeService.data);
  rePlaceRoot();
}

calculateFullTree();

/** CREATE VUE **/

function getAllNodes(tree) {
  var nodes = [];

  tree.forEach(function(level) {
    level.forEach(function(node) {
      nodes.push(node);
    });
  });
  return nodes;
}

function getAllLinks(tree) {
  var links = [];

  tree.forEach(function(level) {
    level.forEach(function(node) {
      if (hasChildren(node)) {
        node.children.forEach(function(child) {
          var childNode = tree[child.level][child.index];

          links.push({
          	id: 'link' + node.level + node.index + childNode.level + childNode.index,
            start: {
              x: node.x,
              y: node.y
            },
            end: {
              x: childNode.x,
              y: childNode.y
            }
          });
        });
      }
    });
  });
  return links;
}

function getPath(link) {
  var moveTo = 'M' + link.start.x + ',' + link.start.y;
  var verticalFirst = 'V' + (link.end.y - (treeService.verticalSpacing / 2) - (treeService.componentHeight / 2));
  var horizontal = 'H' + link.end.x;
  var verticalSecond = 'V' + link.end.y;

  return moveTo + verticalFirst + horizontal + verticalSecond;
}

/** START RANDOM **/

function reCalculateIndices(newNodeLevel, newNodeIndex) {
  treeService.data.forEach(function(level) {
    level.forEach(function(node) {
      if (node.level == newNodeLevel && node.index >= newNodeIndex) {
        ++node.index;
      }
      if (hasParents(node)) {
        node.parents.forEach(function(parent) {
          if (parent.level == newNodeLevel && parent.index >= newNodeIndex) {
            ++parent.index;
          }
        });
      }
      if (hasChildren(node)) {
        node.children.forEach(function(child) {
          if (child.level == newNodeLevel && child.index >= newNodeIndex) {
            ++child.index;
          }
        });
      }
    });
  });
}

var index = 0;

function random(min, max) {
  return Math.floor(Math.random() * (max - min + 1)) + min;
}

function insertRandomNode() {
	var newNodeLevel = random(1, treeService.data.length);
  var newNodeIndex = 0;
  
  if (treeService.data[newNodeLevel]) {
    newNodeIndex = random(0, treeService.data[newNodeLevel].length);
  }

  reCalculateIndices(newNodeLevel, newNodeIndex);

  // Add a parent to the newNode
  var parents = [];
  var parentLevel = newNodeLevel - 1;
  var parentIndex = random(0, treeService.data[parentLevel].length - 1);

  parents.push({
    level: parentLevel,
    index: parentIndex
  });
  if (!treeService.data[parentLevel][parentIndex].children) {
    treeService.data[parentLevel][parentIndex].children = [];
  }
  
  treeService.data[parentLevel][parentIndex].children.push({
    level: newNodeLevel,
    index: newNodeIndex
  });

  // Add a child to the newNode
  var children = [];
  if (newNodeLevel < treeService.data.length - 1) {
    var childLevel = random(newNodeLevel + 1, treeService.data.length - 1);
    var childIndex = random(0, treeService.data[childLevel].length - 1);

		children.push({
      level: childLevel,
      index: childIndex
    });
    treeService.data[childLevel][childIndex].parents.push({
      level: newNodeLevel,
      index: newNodeIndex
    });
  }

  var newNode = {
    level: newNodeLevel,
    index: newNodeIndex,
    label: 'random' + index++,
    parents: parents,
    children: children,
    x: 0,
    y: 0,
    weight: 0
  };

  if (!treeService.data[newNodeLevel]) {
    treeService.data.$set(newNodeLevel, []);
  }
  treeService.data[newNodeLevel].splice(newNodeIndex, 0, newNode);
  calculateFullTree();
}

/** END RANDOM **/

new Vue({
  el: '#container',
  data: {
    service: treeService
  },
  methods: {
    getAllNodes,
    getAllLinks,
    insertRandomNode
  },
  components: {
    'node-template': nodeTemplate,
    'link-template': linkTemplate
  }
});
.link {
  fill: none;
  stroke: #ccc;
  stroke-width: 1px;
}
.node rect {
  fill: #DFF3FF;
  stroke: #49ACEE;
}
<script src="https://cdnjs.cloudflare.com/ajax/libs/vue/1.0.24/vue.min.js"></script>

<script type="x-template" id="node-template">
  <g class="node" transform="translate({{node.x - 50}}, {{node.y - 25}})">
    <rect x="0" y="0" height="50" width="100"></rect>
    <text x="5" y="15">{{node.label}}</text>
    <text x="5" y="30">treePos: [{{node.level}}][{{node.index}}]</text>
    <text x="5" y="45">weight: {{node.weight}}</text>
  </g>
</script>

<script type="x-template" id="link-template">
  <path id="{{link.id}}" class="link" v-bind:d="getPath(link)">
</script>

<div id="container">
  <button v-on:click="insertRandomNode()">Insert random</button>
  <svg v-bind:width="service.svgWidth" v-bind:height="service.svgHeight + 10">
    <link-template v-for="link in getAllLinks(service.data)" v-bind:link="link"></link-template>
    <node-template v-for="node in getAllNodes(service.data)" v-bind:node="node"></node-template>
  </svg>
</div>

\$\endgroup\$
  • \$\begingroup\$ Hello, So if I understand, a node at level l can only have parents at level l-1 and can only have childs at level l+1, right ? \$\endgroup\$ – webNeat Jun 9 '16 at 14:17
  • \$\begingroup\$ No. That's how my insertion work, because it is incomplete. But the link algorithm can handle more: jsfiddle.net/46fp0u38/1 So a node can have children at level l+n and parents at level l-n. Although I don't think it should be allowed for a node to be at level 3, for example, and have its only parent at level 1. It should have at least one parent at the level l-1 \$\endgroup\$ – Elfayer Jun 9 '16 at 14:26
  • \$\begingroup\$ Ok, if so, does the attribut level actually have a meaning or it's just used as index in addition to index ? \$\endgroup\$ – webNeat Jun 9 '16 at 17:49
  • \$\begingroup\$ The level is an index that goes from top of the tree (0) to the end of the tree (treeData.length - 1). At this point, you have located an array of nodes (the nodes of the level index). At this level you have treeData[level].length - 1 nodes. \$\endgroup\$ – Elfayer Jun 10 '16 at 6:41
  • \$\begingroup\$ So you are really talking about a graph structure and not a tree? \$\endgroup\$ – Mike Brant Jun 17 '16 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.