Rendering a dynamically created family graph with no overlapping using a depth first search?
JavascriptGraphFamily TreeGenealogyJavascript Problem Overview
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:
- This is for an editor and would be similar to familyecho.com. Pretty much any business rules not defined can be assumed through that.
- In-family breeding isn't supported as it would make this way too complex. Don't worry about this.
- Multiple partners are supported so this isn't as easy as a traditional "family tree" with just 2 parents and 1 child.
- 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.
Javascript Solutions
Solution 1 - Javascript
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:
- 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.
- 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.
- 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.
- 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.
- 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> <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:
- Getting inverted
[or]shaped horizontal connectors for parent-child relationships. - 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.
- 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.
Solution 2 - Javascript
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
childrenfor 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...
Solution 3 - Javascript
This is not that far from how the Sugiyama algorithm is used to layout class hierarchies, so you might want to take a look at papers that discuss that. There's a book chapter that covers Sugiyama and other hierarchical layout algorithms here.
I'd lay out the upper and lower halves of the tree independently. The thing to recognize about the upper half is that, in its fully populated form, it's all powers of two, so you have two parents, four grandparents, sixteen great-grandparents, etc.
As you do your depth-first search, tag each node with a) it's layer number and b) its collating order. Your data structure doesn't include gender and you really need this both for stylistic reasons and to figure out the collating order. Fortunately, all genealogy data includes gender.
We'll tag fathers with "A" and mothers with "B". Grandparents get another letter appended, so you get:
> father jeff - A, layer 1 > mother maggie - B, layer 1 > paternal grandfather bob - AA, layer 2 > paternal grandmother mary - AB, layer 2 > paternal grandfather robert - BA, layer 2 > paternal grandmother jessie - BB, layer 2 > g-g-father john - AAA, layer 3 > etc
Add the nodes to a list for each layer as you go. Sort each layer by their gender keys (unless using sorted lists). Start your layout at the layer with the highest number and lay out the nodes from left (AAAAA) to right (BBBBB), leaving gaps for any missing nodes. Stylistically, decide if you want to collapse around missing nodes and, if so, by how much (although I'd recommend implementing the simple-minded version first).
Lay out the layers in descending order. If there's no collapsing/adjusting of positions, lower layer positions can be computed directly. If you're adjusting, you'll need to refer to the parents position in the previous layer and center the child under that.
The lower half of the diagram can be done in a similar fashion, except that instead of sorting by gender, you'd probably want to sort by birth order and build up your keys from that e.g. eldest child of eldest child has key "11" while eldest child of the second eldest child is "21" etc.
You could do this with a graph library like cola.js, but you'd only be using a sliver of its functionality and some of the stylistic elements that you want (e.g. keep father & mother close together), would probably need to be added separately, so I suspect it's as easy to build from scratch unless you need other functionality from the library.
Speaking of style, it's customary to use a different line style for the parent connector (traditionally it's a double line). Also, you don't want the "Mistress" node laid out on top of the "me" / "wife" edge.
p.s. With fixed size nodes, you can get away with a simple grid for your coordinate system.
Solution 4 - Javascript
This is not trivial question and it involves large corpus of research in graph drawing algorithms.
The most prominent approach for this problem is through constraints satisfaction. But don't try to implement this on your own (unless you want to learn something new and spend months debugging)
I cannot recommend highly enough this library: cola.js (GitHub)
The particular example that may be very close to what you need is grid layout.
Solution 5 - Javascript
From what I can see - without looking at the code you have there (for now) - you have a DAG (the visual representation is another matter, now I'm talking only about the data structure). Each node has a maximum of 2 incoming connections and no constraint on connections going to other nodes (one can have an arbitrary number of children but we have info on a maximum of 2 parents for each person/node).
That being said, there will be nodes that do not have parents (in this case are "john", "raymond", "betty", "mistress 1", "wife 1", and "daughter 1 boyfriend"). If you do a BFS on the graph starting from these nodes - which would compose level 0 - you get the nodes for each level. The correct level has to be updated on the fly though.
Regarding the visual representation, I'm no expert, but IMO it can be achieved via a grid (as in, a table-like one) view. Each row contains the nodes of a certain level. The elements in a given row are arranged based on the relationship with the other elements in the same row, in row x - 1, and in row x + 1.
To better explain the idea I guess it's better to put in some pseudo-code (not JS though as it's not my strength):
getItemsByLevel(Graph graph)
{
Node[,] result = new Node[,];
var orphans = graph.getOrphans();
var visiting = new HashMap();
var visited = new HashMap();
var queue = new Queue<Node>();
queue.pushAll(orphans);
while(!queue.isEmpty())
{
var currentNode = queue.pop();
if(currentNode.relatedNodes.areNotBeingVisited()) // the nodes that should be on the same level
{
// the level of the current node was not right
currentNode.level++;
queue.push(currentNode);
}
else
{
var children = currentNode.children;
foreach(var child in children)
{
child.level = currentNode.level + 1;
queue.push(child);
}
visited.insert(currentNode);
result[currentNode.level, lastOfRow] = currentNode;
}
}
return result;
}
In the end of the procedure you're going to have a matrix of nodes where row i contains the nodes of level i. You just have to represent them in the gridview (or whatever you choose as layout).
Let me know if anything's unclear.