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

by

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.

  1. 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.

  1. 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.

  1. 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.

  1. 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="https://stackoverflow.com/questions/34539786/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.

Leave a Comment

tech