使用深度优先搜索渲染动态创建的族图而不重叠？

我想生成这个:

使用此数据结构(ID是随机的,顺便说一下,不是顺序的):

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": [] },
];

为了描述数据结构,定义了根/起始节点(me).任何伴侣(妻子,前妻)都处于同一水平.下面的任何东西都变成-1级,-2级.以上任何内容都是1,2级等.父母,兄弟姐妹,孩子和合作伙伴都有属性,用于定义该特定字段的ID.

在我之前的问题中,eh9 描述了他将如何解决这个问题.我试图这样做,但正如我发现的那样,这不是一件容易的事.

我的第一次尝试是从上到下按级别渲染.在这个更简单的尝试中,我基本上按级别嵌套所有人,并从上到下渲染它.

我的第二次尝试是使用深度优先搜索使用其中一个祖先节点进行渲染.

我的主要问题是:我怎样才能真正将答案应用到我现有的答案中？在我的第二次尝试中,我正在尝试进行深度优先遍历,但我怎么能开始考虑计算抵消网格所需的距离以使其与我想要生成的方式一致？

另外,我是深度优先理想的理解/实现,还是我能以不同的方式遍历它？

在我的第二个例子中,节点明显重叠,因为我没有偏移/距离计算代码,但是我真的想知道如何开始这个.

这是我所做的walk函数的描述,我在尝试深度优先遍历:

// 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 );
                    });
            });
        }
    });


}

}

要求/限制:

这是一个编辑器,类似于familyecho.com.几乎所有未定义的业务规则都可以通过它来实现.

不支持家庭育种,因为它会使这种方式过于复杂.别担心这个.

支持多个合作伙伴,因此这不像只有2个父母和1个孩子的传统"家谱"那么容易.

只有一个"根"节点,它只是起始节点.

注意:如果有很多叶子节点并且存在碰撞,familyecho.com似乎"隐藏"了一个分支.可能需要实现这一点.

虽然答案已经发布(并被接受),但我认为昨晚发布我对这个问题所做的工作没有任何害处.

我从新手的角度更多地解决了这个问题,而不是使用现有的图形/树遍历算法.

我的第一次尝试是从上到下按级别渲染.在这个更简单的尝试中,我基本上按级别嵌套所有人,并从上到下渲染它.

这也是我的第一次尝试.您可以从上到下,从下到上或从根开始遍历树.由于您受到特定网站的启发,从根本位置开始似乎是一个合乎逻辑的选择.但是,我发现自下而上的方法更简单,更容易理解.

这是一个粗略的尝试:

绘制数据:

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:

在哪里,我们通过findLevel效用函数重用每个唯一级别的坐标.我们维护一个水平图并检查到达该top位置.休息是根据关系确定的.

/* 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); 
}

为了简单起见,我使用了一个非常粗略的碰撞检测,在已经存在的情况下将节点移动到右边.在一个非常复杂的应用程序中,这将动态向左或向右移动节点以保持水平平衡.

最后,我们将该节点添加到DOM.

休息是所有辅助功能.

重要的是:

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 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);
}

我使用了两个不同的连接器,一个用于连接伙伴的水平连接器,另一个用于连接父子关系的连接器.这对我来说是一个非常棘手的部分,即绘制倒置]水平连接器.这就是为什么要保持简单,我只需旋转div使其看起来像一个有角度的连接器.

绘制/绘制整个树后,可能会有由于负位置而离屏的节点(因为我们正在自下而上遍历).为了抵消这一点,我们只需检查是否有任何负面位置,然后向下移动整个树.

这是完整的代码与小提琴演示.

小提琴演示:http://jsfiddle.net/abhitalks/fvdw9xfq/embedded/result/

这是一个编辑器,类似于

创建编辑器:

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; }

	
Me
	

		

			
Change Name
			Name: 
			
Ok
		
		

			
Add Nodes
			Add: 
			
				Partner
				Sibling
				Parent
				Child
			
			Ok

			Add: 
			
			As Parent
		
		

			
Misc
			Clear  Load Sample
            
Download Data
		
        

	

getItemsByLevel(Graph graph)
{
    Node[,] result = new Node[,];
    var orphans = graph.getOrphans();
    var visiting = new HashMap();
    var visited = new HashMap();
    var queue = new Queue();

    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;
}