使用深度优先search渲染一个dynamic创build的家庭graphics，不重叠？

我想要生成这个：

有了这个数据结构（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 描述了他将如何解决这个问题。 我试图做到这一点，但正如我所发现的，这不是一件容易的事情。

我的第一个尝试是由上而下的级别渲染。 在这个更简单的尝试中，我基本上是将所有的人按照层次嵌套在一起，并从上到下呈现出来。

我的第二个尝试是使用深度优先search与其中一个祖先节点进行渲染。

我的主要问题是 ：我怎样才能将这个答案实际应用于我目前的？ 在我的第二次尝试中，我试图进行一次深度优先遍历，但是我怎么才能开始计算抵消网格所需的距离，使其与我想要生成的网格一致？

另外，我理解/实现深度优先的理想，还是我可以用不同的方式进行探索？

在我的第二个例子中，节点显然是重叠的，因为我没有偏移/距离计算代码，但是我实际上搞不清楚如何开始这个。

这里是我所做的漫游函数的描述，我正在尝试深度优先遍历：

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

}

要求/限制：

1. 这是一个编辑器，将类似于familyecho.com。 几乎任何未定义的业务规则都可以通过这个假设来设定。
2. 不支持家庭养殖，因为这会使这种方式过于复杂。 不要担心这个。
3. 支持多个合作伙伴，所以这不像一个只有两个父母和一个孩子的传统“家谱”那么简单。
4. 只有一个“根”节点，这只是起始节点。

注意 ：如果有许多叶节点并且有碰撞，familyecho.com似乎“隐藏”一个分支。 可能需要执行此操作。

Answer 1

虽然答案已经发布（并被接受），但我认为昨晚发布我的这个问题的工作没有什么坏处。

我从新手的angular度来看待这个问题，而不是用现有的图/树遍历algorithm。

我的第一个尝试是由上而下的级别渲染。 在这个更简单的尝试中，我基本上是将所有的人按照层次嵌套在一起，并从上到下呈现出来。

这也是我的第一次尝试。 您可以自上而下或自下而上或从根开始。 正如你从一个特定的网站的启发，从根开始似乎是一个合乎逻辑的select。 但是，我发现自下而上的方法更简单，更易于理解。

这是一个粗略的尝试：

绘制数据：

1. 我们从最底层开始，向上工作。 正如你正在试图通过编辑器解决这个问题所提到的那样，我们可以在构build树时将所有相关属性存储在对象数组中。

我们caching这些关卡，并使用它来遍历树：

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

其中， getPerson根据它的id从数据中获取对象。

2. 当我们走了，我们绘制节点本身，它的父母（recursion）和它的伙伴。 绘制合作伙伴并不是必须的，但是我在这里做了这个，以便绘制连接器可以很容易。 如果一个节点已经被绘制，我们简单地跳过这个部分。

这就是我们如何策划合作伙伴：

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

父母recursion地：

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

我们在哪里使用reduce来简化绘制作为合作伙伴的父母之间的连接器。

3. 这是我们如何绘制一个节点本身：

其中，我们通过findLevel实用程序函数重用每个唯一级别的坐标。 我们维护一个水平的地图，并检查到达top位置。 rest是根据关系决定的。

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

这里为了简单起见，我使用了非常粗略的碰撞检测来在节点已经存在的情况下将节点移动到正确的位置。 在一个非常复杂的应用程序中，这会dynamic地向左或向右移动节点以保持水平的平衡。

最后，我们将该节点添加到DOM。

4. rest都是帮手function。

重要的是：

 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，使它看起来像一个有angular度的连接器。

5. 一旦整个树被绘制/绘制，可能有节点由于负位置而离开屏幕（因为我们正在自下而上）。 为了弥补这一点，我们只是检查是否有任何负面的立场，然后将整个树向下移动。

这里是一个小提琴演示的完整代码。

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

---

这是一个编辑器，将是类似的

创build一个编辑器：

testing它是否有效的最好方法是有一个编辑器，允许您即时创build这样的树/图并查看它是否成功地绘制。

所以，我也创build了一个简单的编辑器来testing。 代码保持完全一样，但重新考虑了一点，以适应编辑器的例程。

小提琴与编辑演示： http : //jsfiddle.net/abhitalks/56whqh0w/embedded/result

带编辑器的片段演示（查看全屏幕）：

 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> 

Answer 2

如你所示，你的树形数据将不允许你绘制图表。 你实际上错过了一些信息：

• 树实际上应该是一个对象（字典）的ID映射到个人的数据。 否则，从children身上得到的身份证件到children身份certificate文件都是昂贵的。
• 有重复的信息，因为孩子与父母都有关系。 这实际上会导致您发送的示例中的数据不正确（'daugher1'是'wife'的孩子，而是'我'的父母，'mary'可能是'jeff'的母亲; jessie是robert的合伙人;雷蒙德和贝蒂也是）

在我的尝试（ https://jsfiddle.net/61q2ym7q/ ）中，我因此将您的树转换为graphics，然后进行各种计算阶段来实现布局。

这是从杉山algorithm的启发，但简化，因为该algorithm是非常棘手的实施。 不过，各个阶段是：

• 使用深度优先search将节点组织成图层。 我们通过确保父母始终位于父母上方的某个图层上，然后尝试缩短父母之间存在多个图层的链接，分两步进行操作。 这是我没有使用确切的Sugiyamaalgorithm的部分，它使用了一个复杂的切点概念。

• 然后将节点sorting到每个层以最小化边的交叉。 我为此使用重心方法

• 最后，在保留上面的顺序的同时，为每个节点分配一个特定的x坐标，再次使用重心方法

在这个代码中有很多东西可以被改进（比如效率，通过合并一些循环），也可以在最终的布局中。 但是，我试图让它更容易跟随…

Answer 3

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 gg-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 eg 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 (eg 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.

ps With fixed size nodes, you can get away with a simple grid for your coordinate system.

Answer 4

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.

Answer 5

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.