Рендеринг динамически создаваемого семейного графа без перекрытия с использованием поиска в глубину?
Я хочу создать это:
С этой структурой данных (идентификаторы случайные, кстати, не последовательные):
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 и т. Д. Существуют свойства для родителей, братьев и сестер, детей и партнеров, которые определяют идентификаторы для этой конкретной области.
В моем предыдущем вопросе eh9 описал, как он решит это. Я пытаюсь это сделать, но, как я выяснил, это нелегкая задача.
Моя первая попытка рендеринга по уровням сверху вниз. В этой более упрощенной попытке я в основном вкладываю всех людей по уровням и отображаю их сверху вниз.
Моя вторая попытка сделать это с одним из узлов-предков, используя поиск в глубину.
Мой главный вопрос: как я могу применить этот ответ к тому, что у меня есть? Во второй попытке я пытаюсь сделать первый обход глубины, но как я могу даже начать рассчитывать расстояния, необходимые для смещения сеток, чтобы это соответствовало тому, как я хочу это генерировать?
Кроме того, мое понимание / реализация идеала глубины в первую очередь, или я могу пройти по-другому?
Очевидно, что во втором примере узлы перекрываются, поскольку у меня нет кода вычисления смещения / расстояния, но я заблудился, пытаясь понять, как я могу это начать.
Вот описание функции обхода, которую я сделал, где я пытаюсь сначала пройти глубину:
// 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. Через это можно предположить практически любые не определенные бизнес-правила.
- Разведение в семье не поддерживается, так как это может сделать его слишком сложным. Не беспокойся об этом.
- Поддерживается несколько партнеров, так что это не так просто, как традиционное "семейное древо" с двумя родителями и одним ребенком.
- Существует только один "корневой" узел, который является только начальным узлом.
Примечания: familyecho.com, кажется, "скрывает" ветвь, если много листовых узлов и есть коллизия. Возможно, потребуется реализовать это.
5 ответов
Хотя ответ был опубликован (и принят), я подумал, что нет ничего плохого в том, чтобы опубликовать то, что я работал над этой проблемой вчера вечером.
Я подошел к этой проблеме больше с точки зрения новичка, а не работал с существующими алгоритмами обхода графа / дерева.
Моя первая попытка рендеринга по уровням сверху вниз. В этой более упрощенной попытке я в основном вкладываю всех людей по уровням и отображаю их сверху вниз.
Это была именно моя первая попытка. Вы можете пройти по дереву сверху вниз или снизу вверх или начиная с корня. Поскольку вы были вдохновлены конкретным веб-сайтом, начинать с корня кажется логичным выбором. Тем не менее, я обнаружил, что восходящий подход проще и понятнее.
Вот грубая попытка:
Построение данных:
- Мы начинаем с самого нижнего слоя и движемся вверх. Как упоминалось в вопросе о том, что вы пытаетесь решить это с помощью редактора, мы можем сохранять все связанные свойства в массиве объектов при построении дерева.
Мы кешируем уровни и используем их для перехода по дереву:
// 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,
- Когда мы идем вверх, мы строим сам узел, его родителей (рекурсивно) и его партнеров. Составление графиков партнеров на самом деле не требуется, но я сделал это здесь просто для того, чтобы прокладка разъемов была простой. Если узел уже построен, мы просто пропускаем эту часть.
Вот как мы строим партнеров:
/* 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);
}
Где мы используем reduce упростить построение соединителя между двумя родителями в качестве партнеров.
- Вот как мы строим сам узел:
Где мы повторно используем координаты для каждого уникального уровня через 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/
Это для редактора и будет похоже на
Создание редактора:
Лучший способ проверить, работает ли он, - это иметь редактор, который позволяет вам создавать такие деревья / графики на лету и видеть, удачно ли он строит графики.
Итак, я также создал простой редактор для тестирования. Код остается точно таким же, однако был немного переработан, чтобы соответствовать процедурам редактора.
Демонстрация скрипки с редактором: 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> <button id="sample">Load Sample</button>
<br/><button id="download">Download Data</button>
</fieldset>
<fieldset id="downloadLink"></fieldset>
</div>
</div>
<div id="tree"></div>Это все очень грубая попытка, и, несомненно, неоптимизированная. Что я не смог сделать, так это:
- Перевернутый
[или же]фасонные горизонтальные соединители для отношений родитель-ребенок. - Привести дерево в горизонтальное положение. т.е. динамически выясняя, какая сторона тяжелее, а затем смещая эти узлы влево.
- Заставить родителей ориентироваться на детей, особенно на нескольких детей. В настоящее время моя попытка просто приводит все в порядок.
Надеюсь, поможет. И разместить его здесь, чтобы я тоже мог ссылаться на него при необходимости.
Как вы показываете, данные вашего дерева не позволят вам нарисовать диаграмму. Вы фактически упускаете некоторую информацию там:
- Дерево действительно должно быть объектом (словарем), отображающим идентификатор на данные человека. В противном случае, это слишком дорого, чтобы перейти от идентификатора, как указано в
childrenнапример, вернуться к данным ребенка. - есть дублирующаяся информация, так как дети связаны с обоими родителями. Это на самом деле приводит к неверным данным в отправленном вами примере ("daugher1" - ребенок "жены", но родитель "меня", а "mary" - предположительно мать "Джеффа"; Джесси - партнер Роберта; как и Рэймонд и Бетти)
В моей попытке ( https://jsfiddle.net/61q2ym7q/) я поэтому преобразовываю ваше дерево в граф, а затем выполняю различные этапы вычислений для достижения макета.
Это основано на алгоритме Сугиямы, но упрощено, поскольку этот алгоритм очень сложен в реализации. Тем не менее, различные этапы:
организовать узлы в слои, используя поиск в глубину. Мы делаем это в два этапа, следя за тем, чтобы родители всегда находились на уровне выше своего родителя, а затем пытаясь укоротить ссылки, когда существует более одного слоя между дочерним элементом и родителем. Это та часть, где я не использую точный алгоритм Сугиямы, который использует сложное понятие точек разреза.
затем отсортируйте узлы в каждом слое, чтобы минимизировать пересечение ребер. Я использую метод барицентра для этого
наконец, сохраняя порядок выше, назначьте конкретную координату х для каждого узла, снова используя метод барицентра
Есть много вещей, которые можно улучшить в этом коде (эффективность, например, путем объединения некоторых циклов), а также в окончательном макете. Но я старался сделать это проще, чтобы легче было следовать...
Это не так уж далеко от того, как алгоритм Sugiyama используется для разметки иерархий классов, так что вы можете взглянуть на статьи, которые обсуждают это. Здесь есть глава, посвященная Сугияме и другим алгоритмам иерархической компоновки.
Я бы выложил верхнюю и нижнюю половинки дерева независимо. Что касается верхней половины, то следует признать, что в ее полностью населенной форме это все полномочия двух, так что у вас есть два родителя, четыре бабушки и дедушки, шестнадцать прабабушек и т.д.
Выполняя поиск в глубину, пометьте каждый узел а) его номером слоя и б) порядком сортировки. Ваша структура данных не включает пол, и вам это действительно нужно как по стилистическим соображениям, так и для определения порядка сортировки. К счастью, все данные генеалогии включают пол.
Мы будем помечать отцов буквой "А", а матерей - буквой "В". Бабушке и дедушке добавляется еще одно письмо, поэтому вы получите:
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
Добавляйте узлы в список для каждого слоя по мере продвижения. Сортируйте каждый слой по ключам пола (если не используете отсортированные списки). Начните макет с слоя с наибольшим номером и расположите узлы слева (AAAAA) справа (BBBBB), оставляя пробелы для любых отсутствующих узлов. Стилистически решите, хотите ли вы свернуть вокруг отсутствующих узлов и, если да, то насколько, (хотя я бы рекомендовал сначала реализовать простоватую версию).
Разложите слои в порядке убывания. Если не происходит свертывание / корректировка позиций, позиции нижнего уровня могут быть вычислены напрямую. Если вы подстраиваетесь, вам нужно сослаться на положение родителей в предыдущем слое и расположить ребенка под ним.
Нижняя половина диаграммы может быть выполнена аналогичным образом, за исключением того, что вместо сортировки по полу вы, вероятно, захотите отсортировать по порядку рождения и создать ключи из того, что, например, у старшего ребенка старшего ребенка есть ключ "11" в то время как старшему ребенку второго старшего ребенка "21" и т. д.
Вы могли бы сделать это с помощью библиотеки графов, такой как cola.js, но вы могли бы использовать лишь небольшую часть ее функциональности и некоторые из стилевых элементов, которые вы хотите (например, держать отца и мать близко друг к другу), возможно, потребуется добавить отдельно, так что я подозреваю, что это так же просто собрать с нуля, если вам не нужны другие функции из библиотеки.
Говоря о стиле, для родительского соединителя принято использовать другой стиль линии (традиционно это двойная линия). Кроме того, вы не хотите, чтобы узел "Хозяйка" располагался поверх края "я" / "жена".
ps С узлами фиксированного размера вы можете использовать простую сетку для вашей системы координат.
Из того, что я могу видеть - не глядя на код, который у вас есть (пока) - у вас есть DAG (визуальное представление - это другой вопрос, сейчас я говорю только о структуре данных). Каждый узел имеет максимум 2 входящих соединения и не имеет ограничений на соединения, идущие к другим узлам (у одного может быть произвольное число дочерних, но у нас есть информация о максимум 2 родителях для каждого человека / узла).
Тем не менее, будут узлы, у которых нет родителей (в данном случае это "Джон", "Раймонд", "Бетти", "Госпожа 1", "Жена 1" и "Дочь 1 парень"). Если вы сделаете BFS на графике, начиная с этих узлов - который будет составлять уровень 0 - вы получите узлы для каждого уровня. Правильный уровень должен быть обновлен на лету, хотя.
Что касается визуального представления, я не эксперт, но IMO это может быть достигнуто с помощью сетки (как в виде таблицы). Каждая строка содержит узлы определенного уровня. Элементы в данной строке расположены на основе отношений с другими элементами в той же строке, в строке x - 1и в ряду x + 1,
Чтобы лучше объяснить идею, я полагаю, что лучше добавить псевдокод (но не JS, поскольку это не моя сила):
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;
}
В конце процедуры у вас будет матрица узлов, где строка i содержит узлы уровня i, Вам просто нужно представить их в виде сетки (или как вы выберете макет).
Дайте мне знать, если что-то неясно.
Это не тривиальный вопрос, и он включает в себя большой объем исследований в алгоритмах рисования графов.
Наиболее выдающийся подход к решению этой проблемы заключается в удовлетворении ограничений. Но не пытайтесь реализовать это самостоятельно (если вы не хотите изучать что-то новое и тратить месяцы на отладку)
Я не могу рекомендовать эту библиотеку достаточно высоко: cola.js ( GitHub)
Конкретный пример, который может быть очень близок к тому, что вам нужно, это сетка.