Rendering a dynamically created family graph with no overlapping using a depth first search?

Question

I want to generate this:

With this data structure (ids are random, btw not sequential):

var tree = [     { "id": 1, "name": "Me", "dob": "1988", "children": [4], "partners" : [2,3], root:true, level: 0, "parents": [5,6] },     { "id": 2, "name": "Mistress 1", "dob": "1987", "children": [4], "partners" : [1], level: 0, "parents": [] },     { "id": 3, "name": "Wife 1", "dob": "1988", "children": [5], "partners" : [1], level: 0, "parents": [] },     { "id": 4, "name": "son 1", "dob": "", "children": [], "partners" : [], level: -1, "parents": [1,2] },     { "id": 5, "name": "daughter 1", "dob": "", "children": [7], "partners" : [6], level: -1, "parents": [1,3] },     { "id": 6, "name": "daughter 1s boyfriend", "dob": "", "children": [7], "partners" : [5], level: -1, "parents": [] },     { "id": 7, "name": "son (bottom most)", "dob": "", "children": [], "partners" : [], level: -2, "parents": [5,6] },     { "id": 8, "name": "jeff", "dob": "", "children": [1], "partners" : [9], level: 1, "parents": [10,11] },     { "id": 9, "name": "maggie", "dob": "", "children": [1], "partners" : [8], level: 1, "parents": [] },     { "id": 10, "name": "bob", "dob": "", "children": [8], "partners" : [11], level: 2, "parents": [12] },     { "id": 11, "name": "mary", "dob": "", "children": [], "partners" : [10], level: 2, "parents": [] },     { "id": 12, "name": "john", "dob": "", "children": [10], "partners" : [], level: 3, "parents": [] },     { "id": 13, "name": "robert", "dob": "", "children": [9], "partners" : [], level: 2, "parents": [] },     { "id": 14, "name": "jessie", "dob": "", "children": [9], "partners" : [], level: 2, "parents": [15,16] },     { "id": 15, "name": "raymond", "dob": "", "children": [14], "partners" : [], level: 3, "parents": [] },     { "id": 16, "name": "betty", "dob": "", "children": [14], "partners" : [], level: 3, "parents": [] }, ]; 

To give a description of the data structure, the root/starting node (me) is defined. Any partner (wife,ex) is on the same level. Anything below becomes level -1, -2. Anything above is level 1, 2, etc. There are properties for parents, siblings, children and partners which define the ids for that particular field.

In my previous question, eh9 described how he would solve this. I am attempting to do this, but as I've found out, it isn't an easy task.

My first attempt is rendering this by levels from the top down. In this more simplistic attempt, I basically nest all of the people by levels and render this from the top down.

My second attempt is rendering this with one of the ancestor nodes using a depth-first search.

My main question is: How can I actually apply that answer to what I currently have? In my second attempt I'm trying to do a depth first traversal but how can I even begin to account for calculating the distances necessary to offset the grids to make it consistent with how I want to generate this?

Also, is my understanding/implementation of depth-first ideal, or can I traverse this differently?

The nodes obviously overlap in my second example since I have no offsetting/distance calculation code, but I'm lost as to actually figuring out how I can begin that.

Here is a description of the walk function I made, where I am attempting a depth first traversal:

// this is used to map nodes to what they have "traversed". So on the first call of "john", dict would internally store this: // dict.getItems() = [{ '12': [10] }] // this means john (id=10) has traversed bob (id=10) and the code makes it not traverse if its already been traversed.  var dict = new Dictionary;  walk( nested[0]['values'][0] ); // this calls walk on the first element in the "highest" level. in this case it's "john"  function walk( person, fromPersonId, callback ) {      // if a person hasn't been defined in the dict map, define them     if ( dict.get(person.id) == null ) {         dict.set(person.id, []);           if ( fromPersonId !== undefined || first ) {              var div = generateBlock ( person, {                 // this offset code needs to be replaced                 top: first ? 0 : parseInt( $(getNodeById( fromPersonId ).element).css('top'), 10 )+50,                 left: first ? 0 : parseInt( $(getNodeById( fromPersonId ).element).css('left'), 10 )+50             });              //append this to the canvas             $(canvas).append(div);              person.element = div;         }     }      // if this is not the first instance, so if we're calling walk on another node, and if the parent node hasn't been defined, define it     if ( fromPersonId !== undefined ) {         if ( dict.get(fromPersonId) == null ) {             dict.set(fromPersonId, []);         }          // if the "caller" person hasn't been defined as traversing the current node, define them         // so on the first call of walk, fromPersonId is null         // it calls walk on the children and passes fromPersonId which is 12         // so this defines {12:[10]} since fromPersonId is 12 and person.id would be 10 (bob)         if ( dict.get(fromPersonId).indexOf(person.id) == -1 )             dict.get(fromPersonId).push( person.id );     }      console.log( person.name );      // list of properties which house ids of relationships     var iterable = ['partners', 'siblings', 'children', 'parents'];     iterable.forEach(function(property) {         if ( person[property] ) {             person[property].forEach(function(nodeId) {                 // if this person hasnt been "traversed", walk through them                 if ( dict.get(person.id).indexOf(nodeId) == -1 )                     walk( getNodeById( nodeId ), person.id, function() {                         dict.get(person.id).push( nodeId );                     });             });         }     });   } 

}

Requirements/restrictions:

1. This is for an editor and would be similar to familyecho.com. Pretty much any business rules not defined can be assumed through that.
2. In-family breeding isn't supported as it would make this way too complex. Don't worry about this.
3. Multiple partners are supported so this isn't as easy as a traditional "family tree" with just 2 parents and 1 child.
4. There is only one "root" node, which is just the starting node.

Notes: familyecho.com seems to "hide" a branch if there's lots of leaf nodes and there's a collision. May need to implement this.

Answer 1

Although an answer has been posted (and accepted), I thought there is no harm in posting what I worked upon this problem last night.

I approached this problem more from a novice point of view rather than working out with existing algorithms of graph/tree traversal.

My first attempt is rendering this by levels from the top down. In this more simplistic attempt, I basically nest all of the people by levels and render this from the top down.

This was exactly my first attempt as well. You could traverse the tree top-down, or bottom-up or starting from the root. As you have been inspired by a particular website, starting from the root seems to be a logical choice. However, I found the bottom-up approach to be simpler and easier to understand.

Here is a crude attempt:

Plotting the data:

1. We start from the bottom-most layer and work our way upwards. As mentioned in the question that you are trying to work it out via an editor, we can store all related properties in the object array as we build the tree.

We cache the levels and use that to walk up the tree:

// For all level starting from lowest one levels.forEach(function(level) {     // Get all persons from this level     var startAt = data.filter(function(person) {         return person.level == level;     });     startAt.forEach(function(start) {         var person = getPerson(start.id);         // Plot each person in this level         plotNode(person, 'self');         // Plot partners         plotPartners(person);         // And plot the parents of this person walking up         plotParents(person);     }); }); 

Where, getPerson gets the object from the data based on its id.

2. As we are walking up, we plot the node itself, its parents (recursively) and its partners. Plotting partners is not really required, but I did it here just so that plotting the connectors could be easy. If a node has already been plotted, we simply skip that part.

This is how we plot the partners:

/* Plot partners for the current person */ function plotPartners(start) {     if (! start) { return; }     start.partners.forEach(function(partnerId) {         var partner = getPerson(partnerId);         // Plot node         plotNode(partner, 'partners', start);         // Plot partner connector         plotConnector(start, partner, 'partners');     }); } 

And the parents recursively:

/* Plot parents walking up the tree */ function plotParents(start) {     if (! start) { return; }     start.parents.reduce(function(previousId, currentId) {         var previousParent = getPerson(previousId),              currentParent = getPerson(currentId);         // Plot node         plotNode(currentParent, 'parents', start, start.parents.length);         // Plot partner connector if multiple parents         if (previousParent) { plotConnector(previousParent, currentParent, 'partners'); }         // Plot parent connector         plotConnector(start, currentParent, 'parents');         // Recurse and plot parent by walking up the tree         plotParents(currentParent);         return currentId;     }, 0); } 

Where we use reduce to simplify plotting a connector between two parents as partners.

3. This is how we plot a node itself:

Where, we reuse the coordinates for each unique level via the findLevel utility function. We maintain a map of levels and check that to arrive at the top position. Rest is determined on the basis of relationships.

/* Plot a single node */ function plotNode() {     var person = arguments[0], relationType = arguments[1], relative = arguments[2], numberOfParents = arguments[3],          node = get(person.id), relativeNode, element = {}, thisLevel, exists      ;     if (node) { return; }     node = createNodeElement(person);      // Get the current level     thisLevel = findLevel(person.level);     if (! thisLevel) {          thisLevel = { 'level': person.level, 'top': startTop };          levelMap.push(thisLevel);      }     // Depending on relation determine position to plot at relative to current person     if (relationType == 'self') {         node.style.left = startLeft + 'px';          node.style.top = thisLevel.top + 'px';     } else {         relativeNode = get(relative.id);     }     if (relationType == 'partners') {         // Plot to the right         node.style.left = (parseInt(relativeNode.style.left) + size + (gap * 2)) + 'px';             node.style.top = parseInt(relativeNode.style.top) + 'px';      }     if (relationType == 'children') {         // Plot below         node.style.left = (parseInt(relativeNode.style.left) - size) + 'px';             node.style.top = (parseInt(relativeNode.style.top) + size + gap) + 'px';                                 }     if (relationType == 'parents') {         // Plot above, if single parent plot directly above else plot with an offset to left         if (numberOfParents == 1) {              node.style.left = parseInt(relativeNode.style.left) + 'px';              node.style.top = (parseInt(relativeNode.style.top) - gap - size) + 'px';                                 } else {             node.style.left = (parseInt(relativeNode.style.left) - size) + 'px';              node.style.top = (parseInt(relativeNode.style.top) - gap - size) + 'px';                                                     }     }      // Avoid collision moving to right     while (exists = detectCollision(node)) {          node.style.left = (exists.left + size + (gap * 2)) + 'px';      }      // Record level position     if (thisLevel.top > parseInt(node.style.top)) {         updateLevel(person.level, 'top', parseInt(node.style.top));     }     element.id = node.id; element.left = parseInt(node.style.left); element.top = parseInt(node.style.top);      elements.push(element);      // Add the node to the DOM tree     tree.appendChild(node);  } 

Here to keep it simple, I used a very crude collision detection to move nodes to right when one already exists. In a much sophisticated app, this would move nodes dynamically to the left or right to maintain a horizontal balance.

Lastly, we add that node to the DOM.

4. Rest are all helper functions.

The important ones are:

function detectCollision(node) {     var element = elements.filter(function(elem) {          var left = parseInt(node.style.left);         return ((elem.left == left || (elem.left < left && left < (elem.left + size + gap))) && elem.top == parseInt(node.style.top));     });     return element.pop(); } 

Above is a simple detection of collision taking into account the gap between the nodes.

And, to plot the connectors:

function plotConnector(source, destination, relation) {     var connector = document.createElement('div'), orientation, start, stop,          x1, y1, x2, y2, length, angle, transform     ;      orientation = (relation == 'partners') ? 'h' : 'v';     connector.classList.add('asset');     connector.classList.add('connector');     connector.classList.add(orientation);     start = get(source.id); stop = get(destination.id);     if (relation == 'partners') {         x1 = parseInt(start.style.left) + size; y1 = parseInt(start.style.top) + (size/2);         x2 = parseInt(stop.style.left); y2 = parseInt(stop.style.top);         length = (x2 - x1) + 'px';          connector.style.width = length;         connector.style.left = x1 + 'px';         connector.style.top = y1 + 'px';     }     if (relation == 'parents') {         x1 = parseInt(start.style.left) + (size/2); y1 = parseInt(start.style.top);         x2 = parseInt(stop.style.left) + (size/2); y2 = parseInt(stop.style.top) + (size - 2);          length = Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));         angle  = Math.atan2(y2 - y1, x2 - x1) * 180 / Math.PI;         transform = 'rotate(' + angle + 'deg)';           connector.style.width = length + 'px';         connector.style.left = x1 + 'px';         connector.style.top = y1 + 'px';         connector.style.transform = transform;     }     tree.appendChild(connector); } 

I used two different connectors, a horizontal one to connect partners, and an angled one to connect parent-child relationships. This turned out to be a very tricky part for me, i.e. to plot inverted ] horizontal connectors. This is why to keep it simple, I simply rotated a div to make it look like an angled connector.

5. Once the entire tree is drawn/plotted, there could be nodes which go off-screen due to negative positions (because we are traversing bottom-up). To offset this, we simply check if there are any negative positions, and then shift the entire tree downwards.

Here is the complete code with a fiddle demo.

Fiddle Demo: http://jsfiddle.net/abhitalks/fvdw9xfq/embedded/result/

---

This is for an editor and would be similar to

Creating an editor:

The best way to test if it works, is to have an editor which allows you to create such trees/graphs on the fly and see if it plots successfully.

So, I also created a simple editor to test out. The code remains exactly the same, however has been re-factored a little to fit with the routines for the editor.

Fiddle Demo with Editor: http://jsfiddle.net/abhitalks/56whqh0w/embedded/result

Snippet Demo with Editor (view full-screen):

var sampleData = [  		{ "id":  1, "name": "Me", "children": [4], "partners" : [2,3], root:true, level: 0, "parents": [8,9] },  		{ "id":  2, "name": "Mistress", "children": [4], "partners" : [1], level: 0, "parents": [] },  		{ "id":  3, "name": "Wife", "children": [5], "partners" : [1], level: 0, "parents": [] },  		{ "id":  4, "name": "Son", "children": [], "partners" : [], level: -1, "parents": [1,2] },  		{ "id":  5, "name": "Daughter", "children": [7], "partners" : [6], level: -1, "parents": [1,3] },  		{ "id":  6, "name": "Boyfriend", "children": [7], "partners" : [5], level: -1, "parents": [] },  		{ "id":  7, "name": "Son Last", "children": [], "partners" : [], level: -2, "parents": [5,6] },  		{ "id":  8, "name": "Jeff", "children": [1], "partners" : [9], level: 1, "parents": [10,11] },  		{ "id":  9, "name": "Maggie", "children": [1], "partners" : [8], level: 1, "parents": [13,14] },  		{ "id": 10, "name": "Bob", "children": [8], "partners" : [11], level: 2, "parents": [12] },  		{ "id": 11, "name": "Mary", "children": [], "partners" : [10], level: 2, "parents": [] },  		{ "id": 12, "name": "John", "children": [10], "partners" : [], level: 3, "parents": [] },  		{ "id": 13, "name": "Robert", "children": [9], "partners" : [14], level: 2, "parents": [] },  		{ "id": 14, "name": "Jessie", "children": [9], "partners" : [13], level: 2, "parents": [15,16] },  		{ "id": 15, "name": "Raymond", "children": [14], "partners" : [16], level: 3, "parents": [] },  		{ "id": 16, "name": "Betty", "children": [14], "partners" : [15], level: 3, "parents": [] },  	],   	data = [], elements = [], levels = [], levelMap = [],   	tree = document.getElementById('tree'), people = document.getElementById('people'), selectedNode,   	startTop, startLeft, gap = 32, size = 64  ;    /* Template object for person */  function Person(id) {  	this.id = id ? id : '';  	this.name = id ? id : '';  	this.partners = [];  	this.siblings = [];  	this.parents = [];  	this.children = [];  	this.level = 0;  	this.root = false;  }    /* Event listeners */  tree.addEventListener('click', function(e) {  	if (e.target.classList.contains('node')) {  		selectedNode = e.target;   		select(selectedNode);  		document.getElementById('title').textContent = selectedNode.textContent;  		fillPeopleAtLevel();  	}  });  document.getElementById('save').addEventListener('click', function() {  	var pname = document.getElementById('pname').value;  	if (pname.length > 0) {  		data.forEach(function(person) {  			if (person.id == selectedNode.id) {  				person.name = pname;  				selectedNode.textContent = pname;  				document.getElementById('title').textContent = pname;  			}  		});  	}  });  document.getElementById('add').addEventListener('click', function() {  	addPerson(document.getElementById('relation').value);  	plotTree();  });   document.getElementById('addExisting').addEventListener('click', function() {  	attachParent();  	plotTree();  });   document.getElementById('clear').addEventListener('click', startFresh);   document.getElementById('sample').addEventListener('click', function() {  	data = sampleData.slice();  	plotTree();  });   document.getElementById('download').addEventListener('click', function() {    if (data.length > 1) {      var download = JSON.stringify(data, null, 4);      var payload = "text/json;charset=utf-8," + encodeURIComponent(download);      var a = document.createElement('a');      a.href = 'data:' + payload;      a.download = 'data.json';      a.innerHTML = 'click to download';      var container = document.getElementById('downloadLink');      container.appendChild(a);    }  });     /* Initialize */  function appInit() {  	// Approximate center of the div  	startTop = parseInt((tree.clientHeight / 2) - (size / 2));   	startLeft = parseInt((tree.clientWidth / 2) - (size / 2));   }    /* Start a fresh tree */  function startFresh() {  	var start, downloadArea = document.getElementById('downloadLink');  	// Reset Data Cache  	data = [];       appInit();      while (downloadArea.hasChildNodes()) { downloadArea.removeChild(downloadArea.lastChild); }  	  	// Add a root "me" person to start with  	start = new Person('P01'); start.name = 'Me'; start.root = true;  	data.push(start);  	  	// Plot the tree  	plotTree();  	  	// Pre-select the root node  	selectedNode = get('P01');   	document.getElementById('title').textContent = selectedNode.textContent;  }    /* Plot entire tree from bottom-up */  function plotTree() {  	// Reset other cache and DOM  	elements = [], levels = [], levelMap = []  	while (tree.hasChildNodes()) { tree.removeChild(tree.lastChild); }    	// Get all the available levels from the data  	data.forEach(function(elem) {  		if (levels.indexOf(elem.level) === -1) { levels.push(elem.level); }  	});  	  	// Sort the levels in ascending order  	levels.sort(function(a, b) { return a - b; });    	// For all level starting from lowest one  	levels.forEach(function(level) {  		// Get all persons from this level  		var startAt = data.filter(function(person) {  			return person.level == level;  		});  		startAt.forEach(function(start) {  			var person = getPerson(start.id);  			// Plot each person in this level  			plotNode(person, 'self');  			// Plot partners  			plotPartners(person);  			// And plot the parents of this person walking up  			plotParents(person);  		});  		  	});  	  	// Adjust coordinates to keep the tree more or less in center  	adjustNegatives();  	  }    /* Plot partners for the current person */  function plotPartners(start) {  	if (! start) { return; }  	start.partners.forEach(function(partnerId) {  		var partner = getPerson(partnerId);  		// Plot node  		plotNode(partner, 'partners', start);  		// Plot partner connector  		plotConnector(start, partner, 'partners');  	});  }    /* Plot parents walking up the tree */  function plotParents(start) {  	if (! start) { return; }  	start.parents.reduce(function(previousId, currentId) {  		var previousParent = getPerson(previousId),   			currentParent = getPerson(currentId);  		// Plot node  		plotNode(currentParent, 'parents', start, start.parents.length);  		// Plot partner connector if multiple parents  		if (previousParent) { plotConnector(previousParent, currentParent, 'partners'); }  		// Plot parent connector  		plotConnector(start, currentParent, 'parents');  		// Recurse and plot parent by walking up the tree  		plotParents(currentParent);  		return currentId;  	}, 0);  }    /* Plot a single node */  function plotNode() {  	var person = arguments[0], relationType = arguments[1], relative = arguments[2], numberOfParents = arguments[3],   		node = get(person.id), relativeNode, element = {}, thisLevel, exists   	;  	if (node) { return; }  	node = createNodeElement(person);   	// Get the current level  	thisLevel = findLevel(person.level);  	if (! thisLevel) {   		thisLevel = { 'level': person.level, 'top': startTop };   		levelMap.push(thisLevel);   	}  	// Depending on relation determine position to plot at relative to current person  	if (relationType == 'self') {  		node.style.left = startLeft + 'px';   		node.style.top = thisLevel.top + 'px';  	} else {  		relativeNode = get(relative.id);  	}  	if (relationType == 'partners') {  		// Plot to the right  		node.style.left = (parseInt(relativeNode.style.left) + size + (gap * 2)) + 'px';	  		node.style.top = parseInt(relativeNode.style.top) + 'px';   	}  	if (relationType == 'children') {  		// Plot below  		node.style.left = (parseInt(relativeNode.style.left) - size) + 'px';	  		node.style.top = (parseInt(relativeNode.style.top) + size + gap) + 'px'; 							  	}  	if (relationType == 'parents') {  		// Plot above, if single parent plot directly above else plot with an offset to left  		if (numberOfParents == 1) {   			node.style.left = parseInt(relativeNode.style.left) + 'px';   			node.style.top = (parseInt(relativeNode.style.top) - gap - size) + 'px';						  		} else {  			node.style.left = (parseInt(relativeNode.style.left) - size) + 'px';   			node.style.top = (parseInt(relativeNode.style.top) - gap - size) + 'px';											  		}  	}  	  	// Avoid collision moving to right  	while (exists = detectCollision(node)) {   		node.style.left = (exists.left + size + (gap * 2)) + 'px';   	}    	// Record level position  	if (thisLevel.top > parseInt(node.style.top)) {  		updateLevel(person.level, 'top', parseInt(node.style.top));  	}  	element.id = node.id; element.left = parseInt(node.style.left); element.top = parseInt(node.style.top);   	elements.push(element);  	  	// Add the node to the DOM tree  	tree.appendChild(node);   }    /* Helper Functions */    function createNodeElement(person) {  	var node = document.createElement('div');   	node.id = person.id;   	node.classList.add('node'); node.classList.add('asset');   	node.textContent = person.name;   	node.setAttribute('data-level', person.level);  	return node;  }    function select(selectedNode) {  	var allNodes = document.querySelectorAll('div.node');  	[].forEach.call(allNodes, function(node) {  		node.classList.remove('selected');  	});  	selectedNode.classList.add('selected');  }    function get(id) { return document.getElementById(id); }    function getPerson(id) {  	var element = data.filter(function(elem) {  		return elem.id == id;  	});  	return element.pop();  }    function fillPeopleAtLevel() {  	if (!selectedNode) return;  	var person = getPerson(selectedNode.id), level = (person.level + 1), persons, option;  	while (people.hasChildNodes()) { people.removeChild(people.lastChild); }  	data.forEach(function(elem) {  		if (elem.level === level) {  			option = document.createElement('option');  			option.value = elem.id; option.textContent = elem.name;  			people.appendChild(option);  		}  	});  	return persons;  }    function attachParent() {  	var parentId = people.value, thisId = selectedNode.id;  	updatePerson(thisId, 'parents', parentId);  	updatePerson(parentId, 'children', thisId);  }    function addPerson(relationType) {  	var newId = 'P' + (data.length < 9 ? '0' + (data.length + 1) : data.length + 1),   		newPerson = new Person(newId), thisPerson;  	;  	thisPerson = getPerson(selectedNode.id);  	// Add relation between originating person and this person  	updatePerson(thisPerson.id, relationType, newId);	  	switch (relationType) {  		case 'children':   			newPerson.parents.push(thisPerson.id);   			newPerson.level = thisPerson.level - 1;   			break;  		case 'partners':   			newPerson.partners.push(thisPerson.id);   			newPerson.level = thisPerson.level;   			break;  		case 'siblings':   			newPerson.siblings.push(thisPerson.id);   			newPerson.level = thisPerson.level;   			// Add relation for all other relatives of originating person  			newPerson = addRelation(thisPerson.id, relationType, newPerson);  			break;  		case 'parents':   			newPerson.children.push(thisPerson.id);   			newPerson.level = thisPerson.level + 1;   			break;  	}  	  	data.push(newPerson);  }    function updatePerson(id, key, value) {  	data.forEach(function(person) {  		if (person.id === id) {  			if (person[key].constructor === Array) { person[key].push(value); }  			else { person[key] = value; }  		}  	});  }    function addRelation(id, relationType, newPerson) {  	data.forEach(function(person) {   		if (person[relationType].indexOf(id) != -1) {  			person[relationType].push(newPerson.id);  			newPerson[relationType].push(person.id);  		}  	});  	return newPerson;  }    function findLevel(level) {  	var element = levelMap.filter(function(elem) {  		return elem.level == level;  	});  	return element.pop();  }     function updateLevel(id, key, value) {  	levelMap.forEach(function(level) {  		if (level.level === id) {  			level[key] = value;  		}  	});  }    function detectCollision(node) {  	var element = elements.filter(function(elem) {   		var left = parseInt(node.style.left);  		return ((elem.left == left || (elem.left < left && left < (elem.left + size + gap))) && elem.top == parseInt(node.style.top));  	});  	return element.pop();  }    function adjustNegatives() {   	var allNodes = document.querySelectorAll('div.asset'),   		minTop = startTop, diff = 0;  	for (var i=0; i < allNodes.length; i++) {  		if (parseInt(allNodes[i].style.top) < minTop) { minTop = parseInt(allNodes[i].style.top); }  	};  	if (minTop < startTop) {  		diff = Math.abs(minTop) + gap;   		for (var i=0; i < allNodes.length; i++) {  			allNodes[i].style.top = parseInt(allNodes[i].style.top) + diff + 'px';  		};  	}  }    function plotConnector(source, destination, relation) {  	var connector = document.createElement('div'), orientation, start, stop,   		x1, y1, x2, y2, length, angle, transform  	;   	orientation = (relation == 'partners') ? 'h' : 'v';  	connector.classList.add('asset');  	connector.classList.add('connector');  	connector.classList.add(orientation);  	start = get(source.id); stop = get(destination.id);  	if (relation == 'partners') {  		x1 = parseInt(start.style.left) + size; y1 = parseInt(start.style.top) + (size/2);  		x2 = parseInt(stop.style.left); y2 = parseInt(stop.style.top);  		length = (x2 - x1) + 'px';  		  		connector.style.width = length;  		connector.style.left = x1 + 'px';  		connector.style.top = y1 + 'px';  	}  	if (relation == 'parents') {  		x1 = parseInt(start.style.left) + (size/2); y1 = parseInt(start.style.top);  		x2 = parseInt(stop.style.left) + (size/2); y2 = parseInt(stop.style.top) + (size - 2);  		  		length = Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));  		angle  = Math.atan2(y2 - y1, x2 - x1) * 180 / Math.PI;  		transform = 'rotate(' + angle + 'deg)';   		  		connector.style.width = length + 'px';  		connector.style.left = x1 + 'px';  		connector.style.top = y1 + 'px';  		connector.style.transform = transform;  	}  	tree.appendChild(connector);  }  		  /* App Starts Here */  appInit();  startFresh();

* { box-sizing: border-box; padding: 0; margin: 0; }  html, body { width: 100vw; height: 100vh; overflow: hidden; font-family: sans-serif; font-size: 0.9em; }  #editor { float: left; width: 20vw; height: 100vh; overflow: hidden; overflow-y: scroll; border: 1px solid #ddd; }  #tree { float: left; width: 80vw; height: 100vh; overflow: auto; position: relative; }  h2 { text-align: center; margin: 12px; color: #bbb; }  fieldset { margin: 12px; padding: 8px 4px; border: 1px solid #bbb; }  legend { margin: 0px 8px; padding: 4px; }  button, input, select { padding: 4px; margin: 8px 0px;  }  button { min-width: 64px; }  div.node {  	width: 64px; height: 64px; line-height: 64px;  	background-color: #339; color: #efefef;  	font-family: sans-serif; font-size: 0.7em;  	text-align: center; border-radius: 50%;   	overflow: hidden; position: absolute; cursor: pointer;  }   div.connector { position: absolute; background-color: #333; z-index: -10; }  div.connector.h { height: 2px; background-color: #ddd; }  div.connector.v { height: 1px; background-color: #66d; -webkit-transform-origin: 0 100%; transform-origin: 0 100%; }  div[data-level='0'] { background-color: #933; }  div[data-level='1'], div[data-level='-1'] { background-color: #393; }  div[data-level='2'], div[data-level='-2'] { background-color: #333; }  div.node.selected { background-color: #efefef; color: #444; }

<div id="editor">  	<h2 id="title">Me</h2>  	<div>  		<fieldset>  			<legend>Change Name</legend>  			<label>Name: <input id="pname" type="text" /></label>  			<br /><button id="save">Ok</button>  		</fieldset>  		<fieldset>  			<legend>Add Nodes</legend>  			<label for="relation">Add: </label>  			<select id="relation">  				<option value="partners">Partner</option>  				<option value="siblings">Sibling</option>  				<option value="parents">Parent</option>  				<option value="children">Child</option>  			</select>  			<button id="add">Ok</button><br />  			<label for="relation">Add: </label>  			<select id="people"></select>  			<button id="addExisting">As Parent</button>  		</fieldset>  		<fieldset>  			<legend>Misc</legend>  			<button id="clear">Clear</button>&nbsp;&nbsp;<button id="sample">Load Sample</button>              <br/><button id="download">Download Data</button>  		</fieldset>          <fieldset id="downloadLink"></fieldset>  	</div>  </div>  <div id="tree"></div>

---

This is all a very crude attempt and beyond doubts an un-optimized one. What I particularly couldn't get done are:

1. Getting inverted [ or ] shaped horizontal connectors for parent-child relationships.
2. Getting the tree to be horizontally balanced. i.e. dynamically figuring out which is the heavier side and then shifting those nodes to the left.
3. Getting the parent to centrally align with respect to children especially multiple children. Currently, my attempt simply pushes everything to right in order.

Hope it helps. And posting it here so that I too can refer to it when needed.

Answer 2

As you show it, your tree data will not allow you to draw the diagram. You are in fact missing some information there:

• tree should really be an object (dictionary) mapping the id to the person's data. Otherwise, it is costly to go from the id, as given in children for instance, back to the child's data.
• there is duplicate information since children are associated with both parent. This actually lead to incorrect data in the example you sent ('daugher1' is a child of 'wife', but a parent of 'me', and 'mary' is presumably mother of 'jeff'; jessie is a partner of robert; so are raymond and betty)

In my attempt (https://jsfiddle.net/61q2ym7q/), I am therefore converting your tree to a graph, and then doing various stages of computation to achieve a layout.

This is inspired by the Sugiyama algorithm, but simplified, since that algorithm is very tricky to implement. Still, the various stages are:

• organize nodes into layers, using depth-first search. We do this in two steps by making sure that parents are always on a layer above their parent, and then trying to shorten the links when there is more than one layer between child and parent. This is the part where I am not using the exact Sugiyama algorithm, which uses a complex notion of cut points.

• then sort the nodes into each layer to minimize crossing of edges. I use the barycenter method for this

• finally, while preserving the order above, assign a specific x coordinate for each node, again using the barycenter method

There are lots of things that can be improved in this code (efficiency, by merging some of the loops for instance) and also in the final layout. But I tried to keep it simpler to make it easier to follow...