使用深度优先搜索呈现不重叠的动态创建的家庭图？
Rendering a dynamically created family graph with no overlapping using a depth first search?
我想生成这个：
使用此数据结构（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": [] },
];
为了描述数据结构，定义了root/starting节点（me）。任何伴侣（妻子，前任）都处于同一水平。下面的任何东西都变成-1，-2级。上面的任何东西都是级别 1、2 等。有 parents、兄弟姐妹、children 和 partners 的属性它定义了该特定字段的 ID。
在我之前的 , eh9 他将如何解决这个问题。我正在尝试这样做，但正如我发现的那样，这不是一件容易的事。
我的 first attempt 正在从上到下逐层渲染。在这个更简单的尝试中，我基本上按级别嵌套所有人，并从上到下渲染。
我的 second attempt 正在使用 depth-first 搜索使用其中一个祖先节点渲染它。
我的主要问题是：我怎样才能真正将这个答案应用到我目前拥有的东西上？在我的第二次尝试中，我尝试进行深度优先遍历，但我什至如何开始计算偏移网格所需的距离以使其与我想要生成它的方式一致？
此外，我的 understanding/implementation 或者 depth-first 是理想的吗，或者我可以用不同的方式遍历它吗？
我的第二个示例中的节点明显重叠，因为我没有 offsetting/distance 计算代码，但我不知道如何开始计算。
下面是我创建的 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 );
});
});
}
});
}
}
Requirements/restrictions:
- 这适用于编辑器，类似于 familyecho.com。几乎所有未定义的业务规则都可以通过它来假设。
- In-family 繁殖不受支持，因为这会使这种方式过于复杂。这个不用担心。
- 支持多个合作伙伴，因此这不像传统的 "family tree" 那样简单，只有 2 parents 和 1 child。
- 只有一个"root"节点，也就是起始节点。
注释: 如果有很多叶节点并且发生冲突，familyecho.com 似乎是 "hide" 一个分支。可能需要实现这个。
这不是一个小问题，它涉及大量的图形绘制算法研究。
这个问题最突出的方法是通过约束满足。但是不要尝试自己实现它（除非你想学习新东西并花几个月的调试时间）
可能非常接近您需要的特定 example 是网格布局。
这与 Sugiyama 算法用于布局 class 层次结构的方式相差无几，因此您可能想看看 papers that discuss that. There's a book chapter that covers Sugiyama and other hierarchical layout algorithms here。
我会独立地布置树的上半部分和下半部分。关于上半部分要认识到的是，在其完全填充的形式中，它是 2 的所有幂，所以你有两个 parents，四个 grandparents，十六个 great-grandparents，等等
在您进行 depth-first 搜索时，用 a) 图层编号和 b) 整理顺序标记每个节点。您的数据结构不包括性别，出于风格原因和确定整理顺序，您确实需要它。幸运的是，所有家谱数据都包括性别。
我们将用 "A" 标记父亲，用 "B" 标记母亲。 Grandparents 得到另一个字母附加，所以你得到：
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) 布置节点，为任何缺失的节点留出空隙。在风格上，决定是否要围绕缺失的节点折叠，如果是，折叠多少（尽管我建议首先实施 simple-minded 版本）。
按降序排列图层。如果没有collapsing/adjusting个位置，可以直接计算下层位置。如果你正在调整，你需要参考上一层的 parents 位置并将 child 居中。
图表的下半部分可以用类似的方式完成，除了不是按性别排序，你可能想按出生顺序排序并从中构建你的键，例如最年长的 child 的最年长的 child 的密钥为“11”，而第二大的 child 的最年长的 child 为“21” 等
你可以使用像 cola.js 这样的图形库来做到这一点，但你只会使用它的一小部分功能和你想要的一些风格元素（例如让父亲和母亲靠在一起） ，可能需要单独添加，所以我怀疑从头开始构建它很容易，除非您需要库中的其他功能。
说到样式，parent 连接器通常使用不同的线条样式（传统上是双线）。此外，您不希望 "Mistress" 节点位于 "me" / "wife" 边缘之上。
p.s。使用固定大小的节点，您可以为坐标系使用一个简单的网格。
正如您展示的那样，您的树数据不允许您绘制图表。你实际上在那里遗漏了一些信息：
- tree 实际上应该是 object（字典）将 id 映射到人的数据。否则，从
children 中给出的 id 返回到 child 的数据是昂贵的。
- 存在重复信息，因为 children 与 parent 相关联。这实际上会导致您发送的示例中的数据不正确（'daugher1' 是 'wife' 的 child，但是 'me' 的 parent，以及 'mary' 大概是 'jeff' 的母亲；jessie 是 robert 的伴侣；raymond 和 betty 也是）
在我的尝试 (https://jsfiddle.net/61q2ym7q/) 中，我因此将您的树转换为图形，然后进行各个阶段的计算以实现布局。
这是受 Sugiyama 算法的启发，但经过简化，因为该算法实施起来非常棘手。不过，各个阶段是：
使用 depth-first 搜索将节点组织成层。我们通过确保 parent 始终位于它们的 parent 之上的一层，然后在 child 和 child 之间存在不止一层时尝试缩短链接parent。这是我没有使用精确的 Sugiyama 算法的部分，它使用了复杂的切点概念。
然后将节点分类到每一层中，以尽量减少边的交叉。我为此使用重心法
最后，在保留上述顺序的同时，再次使用重心法为每个节点分配一个特定的 x 坐标
此代码（效率，例如通过合并一些循环）以及最终布局中有很多地方可以改进。但我试图让它更简单，让它更容易理解......
据我所知 - 不看你那里的代码（现在） - 你有一个 DAG （视觉表示是另一回事，现在我只谈论数据结构).每个节点最多有 2 个传入连接，并且对连接到其他节点没有限制（一个节点可以有任意数量的子节点，但我们有每个 person/node 最多有 2 个父节点的信息）。
也就是说，会有没有父节点的节点（在这种情况下是 "john"、"raymond"、"betty"、"mistress 1"、"wife 1"，和 "daughter 1 boyfriend"）。如果您从这些节点开始在图表上执行 BFS - 这将构成级别 0 - 您将获得每个级别的节点。不过必须即时更新正确的级别。
关于视觉表示，我不是专家，但 IMO 可以通过网格（如 table-like 视图）视图来实现。每行包含特定级别的节点。给定行中的元素根据与同一行、行 x - 1 和行 x + 1.
中其他元素的关系进行排列
为了更好地解释这个想法，我想最好加入一些 pseudo-code（不是 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 的节点。您只需要在 gridview（或您选择的任何布局）中表示它们。
如果有任何不清楚的地方，请告诉我。
虽然已经发布了一个答案（并被接受），但我认为发布我昨晚在这个问题上所做的工作没有什么坏处。
我更多地是从新手的角度来解决这个问题，而不是使用现有的 graph/tree 遍历算法。
My first attempt is rendering this by levels from the top down. In
this more simplistic attempt, I basically nest all of the people by
levels and render this from the top down.
这也是我的第一次尝试。您可以遍历树 top-down 或 bottom-up 或从根开始。当您受到某个特定网站的启发时，从根开始似乎是一个合乎逻辑的选择。但是，我发现 bottom-up 方法更简单、更容易理解。
这是一个粗略的尝试：
绘制数据：
- 我们从 bottom-most 层开始，一路向上。正如您尝试通过编辑器解决问题中提到的那样，我们可以在构建树时将所有相关属性存储在 object 数组中。
我们缓存关卡并使用它来遍历树：
// 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从数据中获取object。
- 当我们向上走时，我们绘制节点本身、它的 parents（递归地）和它的伙伴。绘制合作伙伴并不是真正需要的，但我在这里这样做只是为了让绘制连接器变得容易。如果已经绘制了一个节点，我们只需跳过该部分。
这就是我们绘制合作伙伴的方式：
/* 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');
});
}
并且 parent 递归：
/* 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 来简化绘制两个 parent 之间的连接器作为合作伙伴。
- 这就是我们绘制节点本身的方式：
其中，我们通过 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);
}
我使用了两种不同的连接器，一种是水平的连接伙伴，另一种是倾斜的连接 parent-child 关系。这对我来说是一个非常棘手的部分，即绘制倒置的 ] 水平连接器。这就是为什么要保持简单，我只是旋转了一个 div 使其看起来像一个有角度的连接器。
- 一旦整个树为 drawn/plotted，可能会有节点由于负位置而变为 off-screen（因为我们正在遍历 bottom-up）。为了抵消这一点，我们只需检查是否有任何负位置，然后将整个树向下移动。
这是带有 fiddle 演示的完整代码。
Fiddle 演示：http://jsfiddle.net/abhitalks/fvdw9xfq/embedded/result/
This is for an editor and would be similar to
正在创建编辑器：
测试它是否有效的最佳方法是使用一个编辑器，它允许您即时创建这样的 trees/graphs 并查看它是否成功绘制。
所以，我也创建了一个简单的编辑器来测试。代码保持完全相同，但是 re-factored 稍微适合编辑器的例程。
Fiddle 编辑器演示：http://jsfiddle.net/abhitalks/56whqh0w/embedded/result
带有编辑器的片段演示（视图 full-screen）：
var sampleData = [
{ "id": 1, "name": "Me", "children": [4], "partners" : [2,3], root:true, level: 0, "parents": [8,9] },
{ "id": 2, "name": "Mistress", "children": [4], "partners" : [1], level: 0, "parents": [] },
{ "id": 3, "name": "Wife", "children": [5], "partners" : [1], level: 0, "parents": [] },
{ "id": 4, "name": "Son", "children": [], "partners" : [], level: -1, "parents": [1,2] },
{ "id": 5, "name": "Daughter", "children": [7], "partners" : [6], level: -1, "parents": [1,3] },
{ "id": 6, "name": "Boyfriend", "children": [7], "partners" : [5], level: -1, "parents": [] },
{ "id": 7, "name": "Son Last", "children": [], "partners" : [], level: -2, "parents": [5,6] },
{ "id": 8, "name": "Jeff", "children": [1], "partners" : [9], level: 1, "parents": [10,11] },
{ "id": 9, "name": "Maggie", "children": [1], "partners" : [8], level: 1, "parents": [13,14] },
{ "id": 10, "name": "Bob", "children": [8], "partners" : [11], level: 2, "parents": [12] },
{ "id": 11, "name": "Mary", "children": [], "partners" : [10], level: 2, "parents": [] },
{ "id": 12, "name": "John", "children": [10], "partners" : [], level: 3, "parents": [] },
{ "id": 13, "name": "Robert", "children": [9], "partners" : [14], level: 2, "parents": [] },
{ "id": 14, "name": "Jessie", "children": [9], "partners" : [13], level: 2, "parents": [15,16] },
{ "id": 15, "name": "Raymond", "children": [14], "partners" : [16], level: 3, "parents": [] },
{ "id": 16, "name": "Betty", "children": [14], "partners" : [15], level: 3, "parents": [] },
],
data = [], elements = [], levels = [], levelMap = [],
tree = document.getElementById('tree'), people = document.getElementById('people'), selectedNode,
startTop, startLeft, gap = 32, size = 64
;
/* Template object for person */
function Person(id) {
this.id = id ? id : '';
this.name = id ? id : '';
this.partners = [];
this.siblings = [];
this.parents = [];
this.children = [];
this.level = 0;
this.root = false;
}
/* Event listeners */
tree.addEventListener('click', function(e) {
if (e.target.classList.contains('node')) {
selectedNode = e.target;
select(selectedNode);
document.getElementById('title').textContent = selectedNode.textContent;
fillPeopleAtLevel();
}
});
document.getElementById('save').addEventListener('click', function() {
var pname = document.getElementById('pname').value;
if (pname.length > 0) {
data.forEach(function(person) {
if (person.id == selectedNode.id) {
person.name = pname;
selectedNode.textContent = pname;
document.getElementById('title').textContent = pname;
}
});
}
});
document.getElementById('add').addEventListener('click', function() {
addPerson(document.getElementById('relation').value);
plotTree();
});
document.getElementById('addExisting').addEventListener('click', function() {
attachParent();
plotTree();
});
document.getElementById('clear').addEventListener('click', startFresh);
document.getElementById('sample').addEventListener('click', function() {
data = sampleData.slice();
plotTree();
});
document.getElementById('download').addEventListener('click', function() {
if (data.length > 1) {
var download = JSON.stringify(data, null, 4);
var payload = "text/json;charset=utf-8," + encodeURIComponent(download);
var a = document.createElement('a');
a.href = 'data:' + payload;
a.download = 'data.json';
a.innerHTML = 'click to download';
var container = document.getElementById('downloadLink');
container.appendChild(a);
}
});
/* Initialize */
function appInit() {
// Approximate center of the div
startTop = parseInt((tree.clientHeight / 2) - (size / 2));
startLeft = parseInt((tree.clientWidth / 2) - (size / 2));
}
/* Start a fresh tree */
function startFresh() {
var start, downloadArea = document.getElementById('downloadLink');
// Reset Data Cache
data = [];
appInit();
while (downloadArea.hasChildNodes()) { downloadArea.removeChild(downloadArea.lastChild); }
// Add a root "me" person to start with
start = new Person('P01'); start.name = 'Me'; start.root = true;
data.push(start);
// Plot the tree
plotTree();
// Pre-select the root node
selectedNode = get('P01');
document.getElementById('title').textContent = selectedNode.textContent;
}
/* Plot entire tree from bottom-up */
function plotTree() {
// Reset other cache and DOM
elements = [], levels = [], levelMap = []
while (tree.hasChildNodes()) { tree.removeChild(tree.lastChild); }
// Get all the available levels from the data
data.forEach(function(elem) {
if (levels.indexOf(elem.level) === -1) { levels.push(elem.level); }
});
// Sort the levels in ascending order
levels.sort(function(a, b) { return a - b; });
// For all level starting from lowest one
levels.forEach(function(level) {
// Get all persons from this level
var startAt = data.filter(function(person) {
return person.level == level;
});
startAt.forEach(function(start) {
var person = getPerson(start.id);
// Plot each person in this level
plotNode(person, 'self');
// Plot partners
plotPartners(person);
// And plot the parents of this person walking up
plotParents(person);
});
});
// Adjust coordinates to keep the tree more or less in center
adjustNegatives();
}
/* Plot partners for the current person */
function plotPartners(start) {
if (! start) { return; }
start.partners.forEach(function(partnerId) {
var partner = getPerson(partnerId);
// Plot node
plotNode(partner, 'partners', start);
// Plot partner connector
plotConnector(start, partner, 'partners');
});
}
/* Plot parents walking up the tree */
function plotParents(start) {
if (! start) { return; }
start.parents.reduce(function(previousId, currentId) {
var previousParent = getPerson(previousId),
currentParent = getPerson(currentId);
// Plot node
plotNode(currentParent, 'parents', start, start.parents.length);
// Plot partner connector if multiple parents
if (previousParent) { plotConnector(previousParent, currentParent, 'partners'); }
// Plot parent connector
plotConnector(start, currentParent, 'parents');
// Recurse and plot parent by walking up the tree
plotParents(currentParent);
return currentId;
}, 0);
}
/* Plot a single node */
function plotNode() {
var person = arguments[0], relationType = arguments[1], relative = arguments[2], numberOfParents = arguments[3],
node = get(person.id), relativeNode, element = {}, thisLevel, exists
;
if (node) { return; }
node = createNodeElement(person);
// Get the current level
thisLevel = findLevel(person.level);
if (! thisLevel) {
thisLevel = { 'level': person.level, 'top': startTop };
levelMap.push(thisLevel);
}
// Depending on relation determine position to plot at relative to current person
if (relationType == 'self') {
node.style.left = startLeft + 'px';
node.style.top = thisLevel.top + 'px';
} else {
relativeNode = get(relative.id);
}
if (relationType == 'partners') {
// Plot to the right
node.style.left = (parseInt(relativeNode.style.left) + size + (gap * 2)) + 'px';
node.style.top = parseInt(relativeNode.style.top) + 'px';
}
if (relationType == 'children') {
// Plot below
node.style.left = (parseInt(relativeNode.style.left) - size) + 'px';
node.style.top = (parseInt(relativeNode.style.top) + size + gap) + 'px';
}
if (relationType == 'parents') {
// Plot above, if single parent plot directly above else plot with an offset to left
if (numberOfParents == 1) {
node.style.left = parseInt(relativeNode.style.left) + 'px';
node.style.top = (parseInt(relativeNode.style.top) - gap - size) + 'px';
} else {
node.style.left = (parseInt(relativeNode.style.left) - size) + 'px';
node.style.top = (parseInt(relativeNode.style.top) - gap - size) + 'px';
}
}
// Avoid collision moving to right
while (exists = detectCollision(node)) {
node.style.left = (exists.left + size + (gap * 2)) + 'px';
}
// Record level position
if (thisLevel.top > parseInt(node.style.top)) {
updateLevel(person.level, 'top', parseInt(node.style.top));
}
element.id = node.id; element.left = parseInt(node.style.left); element.top = parseInt(node.style.top);
elements.push(element);
// Add the node to the DOM tree
tree.appendChild(node);
}
/* Helper Functions */
function createNodeElement(person) {
var node = document.createElement('div');
node.id = person.id;
node.classList.add('node'); node.classList.add('asset');
node.textContent = person.name;
node.setAttribute('data-level', person.level);
return node;
}
function select(selectedNode) {
var allNodes = document.querySelectorAll('div.node');
[].forEach.call(allNodes, function(node) {
node.classList.remove('selected');
});
selectedNode.classList.add('selected');
}
function get(id) { return document.getElementById(id); }
function getPerson(id) {
var element = data.filter(function(elem) {
return elem.id == id;
});
return element.pop();
}
function fillPeopleAtLevel() {
if (!selectedNode) return;
var person = getPerson(selectedNode.id), level = (person.level + 1), persons, option;
while (people.hasChildNodes()) { people.removeChild(people.lastChild); }
data.forEach(function(elem) {
if (elem.level === level) {
option = document.createElement('option');
option.value = elem.id; option.textContent = elem.name;
people.appendChild(option);
}
});
return persons;
}
function attachParent() {
var parentId = people.value, thisId = selectedNode.id;
updatePerson(thisId, 'parents', parentId);
updatePerson(parentId, 'children', thisId);
}
function addPerson(relationType) {
var newId = 'P' + (data.length < 9 ? '0' + (data.length + 1) : data.length + 1),
newPerson = new Person(newId), thisPerson;
;
thisPerson = getPerson(selectedNode.id);
// Add relation between originating person and this person
updatePerson(thisPerson.id, relationType, newId);
switch (relationType) {
case 'children':
newPerson.parents.push(thisPerson.id);
newPerson.level = thisPerson.level - 1;
break;
case 'partners':
newPerson.partners.push(thisPerson.id);
newPerson.level = thisPerson.level;
break;
case 'siblings':
newPerson.siblings.push(thisPerson.id);
newPerson.level = thisPerson.level;
// Add relation for all other relatives of originating person
newPerson = addRelation(thisPerson.id, relationType, newPerson);
break;
case 'parents':
newPerson.children.push(thisPerson.id);
newPerson.level = thisPerson.level + 1;
break;
}
data.push(newPerson);
}
function updatePerson(id, key, value) {
data.forEach(function(person) {
if (person.id === id) {
if (person[key].constructor === Array) { person[key].push(value); }
else { person[key] = value; }
}
});
}
function addRelation(id, relationType, newPerson) {
data.forEach(function(person) {
if (person[relationType].indexOf(id) != -1) {
person[relationType].push(newPerson.id);
newPerson[relationType].push(person.id);
}
});
return newPerson;
}
function findLevel(level) {
var element = levelMap.filter(function(elem) {
return elem.level == level;
});
return element.pop();
}
function updateLevel(id, key, value) {
levelMap.forEach(function(level) {
if (level.level === id) {
level[key] = value;
}
});
}
function detectCollision(node) {
var element = elements.filter(function(elem) {
var left = parseInt(node.style.left);
return ((elem.left == left || (elem.left < left && left < (elem.left + size + gap))) && elem.top == parseInt(node.style.top));
});
return element.pop();
}
function adjustNegatives() {
var allNodes = document.querySelectorAll('div.asset'),
minTop = startTop, diff = 0;
for (var i=0; i < allNodes.length; i++) {
if (parseInt(allNodes[i].style.top) < minTop) { minTop = parseInt(allNodes[i].style.top); }
};
if (minTop < startTop) {
diff = Math.abs(minTop) + gap;
for (var i=0; i < allNodes.length; i++) {
allNodes[i].style.top = parseInt(allNodes[i].style.top) + diff + 'px';
};
}
}
function plotConnector(source, destination, relation) {
var connector = document.createElement('div'), orientation, start, stop,
x1, y1, x2, y2, length, angle, transform
;
orientation = (relation == 'partners') ? 'h' : 'v';
connector.classList.add('asset');
connector.classList.add('connector');
connector.classList.add(orientation);
start = get(source.id); stop = get(destination.id);
if (relation == 'partners') {
x1 = parseInt(start.style.left) + size; y1 = parseInt(start.style.top) + (size/2);
x2 = parseInt(stop.style.left); y2 = parseInt(stop.style.top);
length = (x2 - x1) + 'px';
connector.style.width = length;
connector.style.left = x1 + 'px';
connector.style.top = y1 + 'px';
}
if (relation == 'parents') {
x1 = parseInt(start.style.left) + (size/2); y1 = parseInt(start.style.top);
x2 = parseInt(stop.style.left) + (size/2); y2 = parseInt(stop.style.top) + (size - 2);
length = Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
angle = Math.atan2(y2 - y1, x2 - x1) * 180 / Math.PI;
transform = 'rotate(' + angle + 'deg)';
connector.style.width = length + 'px';
connector.style.left = x1 + 'px';
connector.style.top = y1 + 'px';
connector.style.transform = transform;
}
tree.appendChild(connector);
}
/* App Starts Here */
appInit();
startFresh();
* { box-sizing: border-box; padding: 0; margin: 0; }
html, body { width: 100vw; height: 100vh; overflow: hidden; font-family: sans-serif; font-size: 0.9em; }
#editor { float: left; width: 20vw; height: 100vh; overflow: hidden; overflow-y: scroll; border: 1px solid #ddd; }
#tree { float: left; width: 80vw; height: 100vh; overflow: auto; position: relative; }
h2 { text-align: center; margin: 12px; color: #bbb; }
fieldset { margin: 12px; padding: 8px 4px; border: 1px solid #bbb; }
legend { margin: 0px 8px; padding: 4px; }
button, input, select { padding: 4px; margin: 8px 0px; }
button { min-width: 64px; }
div.node {
width: 64px; height: 64px; line-height: 64px;
background-color: #339; color: #efefef;
font-family: sans-serif; font-size: 0.7em;
text-align: center; border-radius: 50%;
overflow: hidden; position: absolute; cursor: pointer;
}
div.connector { position: absolute; background-color: #333; z-index: -10; }
div.connector.h { height: 2px; background-color: #ddd; }
div.connector.v { height: 1px; background-color: #66d; -webkit-transform-origin: 0 100%; transform-origin: 0 100%; }
div[data-level='0'] { background-color: #933; }
div[data-level='1'], div[data-level='-1'] { background-color: #393; }
div[data-level='2'], div[data-level='-2'] { background-color: #333; }
div.node.selected { background-color: #efefef; color: #444; }
<div id="editor">
<h2 id="title">Me</h2>
<div>
<fieldset>
<legend>Change Name</legend>
<label>Name: <input id="pname" type="text" /></label>
<br /><button id="save">Ok</button>
</fieldset>
<fieldset>
<legend>Add Nodes</legend>
<label for="relation">Add: </label>
<select id="relation">
<option value="partners">Partner</option>
<option value="siblings">Sibling</option>
<option value="parents">Parent</option>
<option value="children">Child</option>
</select>
<button id="add">Ok</button><br />
<label for="relation">Add: </label>
<select id="people"></select>
<button id="addExisting">As Parent</button>
</fieldset>
<fieldset>
<legend>Misc</legend>
<button id="clear">Clear</button> <button id="sample">Load Sample</button>
<br/><button id="download">Download Data</button>
</fieldset>
<fieldset id="downloadLink"></fieldset>
</div>
</div>
<div id="tree"></div>
这都是一次非常粗糙的尝试，毫无疑问是一次 un-optimized。我特别不能完成的是：
- 为 parent-child 关系获取倒
[ 或 ] 形状的水平连接器。
- 使树水平平衡。即动态找出哪个是较重的一侧，然后将这些节点向左移动。
- 让 parent 相对于 children 尤其是多个 children 居中对齐。目前，我的尝试只是将所有内容按顺序推到正确位置。
希望对您有所帮助。并张贴在这里，以便我也可以在需要时参考。
我想生成这个：
使用此数据结构（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": [] },
];
为了描述数据结构，定义了root/starting节点（me）。任何伴侣（妻子，前任）都处于同一水平。下面的任何东西都变成-1，-2级。上面的任何东西都是级别 1、2 等。有 parents、兄弟姐妹、children 和 partners 的属性它定义了该特定字段的 ID。
在我之前的
我的 first attempt 正在从上到下逐层渲染。在这个更简单的尝试中，我基本上按级别嵌套所有人，并从上到下渲染。
我的 second attempt 正在使用 depth-first 搜索使用其中一个祖先节点渲染它。
我的主要问题是：我怎样才能真正将这个答案应用到我目前拥有的东西上？在我的第二次尝试中，我尝试进行深度优先遍历，但我什至如何开始计算偏移网格所需的距离以使其与我想要生成它的方式一致？
此外，我的 understanding/implementation 或者 depth-first 是理想的吗，或者我可以用不同的方式遍历它吗？
我的第二个示例中的节点明显重叠，因为我没有 offsetting/distance 计算代码，但我不知道如何开始计算。
下面是我创建的 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 );
});
});
}
});
}
}
Requirements/restrictions:
- 这适用于编辑器，类似于 familyecho.com。几乎所有未定义的业务规则都可以通过它来假设。
- In-family 繁殖不受支持，因为这会使这种方式过于复杂。这个不用担心。
- 支持多个合作伙伴，因此这不像传统的 "family tree" 那样简单，只有 2 parents 和 1 child。
- 只有一个"root"节点，也就是起始节点。
注释: 如果有很多叶节点并且发生冲突，familyecho.com 似乎是 "hide" 一个分支。可能需要实现这个。
这不是一个小问题，它涉及大量的图形绘制算法研究。
这个问题最突出的方法是通过约束满足。但是不要尝试自己实现它（除非你想学习新东西并花几个月的调试时间）
可能非常接近您需要的特定 example 是网格布局。
这与 Sugiyama 算法用于布局 class 层次结构的方式相差无几，因此您可能想看看 papers that discuss that. There's a book chapter that covers Sugiyama and other hierarchical layout algorithms here。
我会独立地布置树的上半部分和下半部分。关于上半部分要认识到的是，在其完全填充的形式中，它是 2 的所有幂，所以你有两个 parents，四个 grandparents，十六个 great-grandparents，等等
在您进行 depth-first 搜索时，用 a) 图层编号和 b) 整理顺序标记每个节点。您的数据结构不包括性别，出于风格原因和确定整理顺序，您确实需要它。幸运的是，所有家谱数据都包括性别。
我们将用 "A" 标记父亲，用 "B" 标记母亲。 Grandparents 得到另一个字母附加，所以你得到：
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) 布置节点，为任何缺失的节点留出空隙。在风格上，决定是否要围绕缺失的节点折叠，如果是，折叠多少（尽管我建议首先实施 simple-minded 版本）。
按降序排列图层。如果没有collapsing/adjusting个位置，可以直接计算下层位置。如果你正在调整，你需要参考上一层的 parents 位置并将 child 居中。
图表的下半部分可以用类似的方式完成，除了不是按性别排序，你可能想按出生顺序排序并从中构建你的键，例如最年长的 child 的最年长的 child 的密钥为“11”，而第二大的 child 的最年长的 child 为“21” 等
你可以使用像 cola.js 这样的图形库来做到这一点，但你只会使用它的一小部分功能和你想要的一些风格元素（例如让父亲和母亲靠在一起） ，可能需要单独添加，所以我怀疑从头开始构建它很容易，除非您需要库中的其他功能。
说到样式，parent 连接器通常使用不同的线条样式（传统上是双线）。此外，您不希望 "Mistress" 节点位于 "me" / "wife" 边缘之上。
p.s。使用固定大小的节点，您可以为坐标系使用一个简单的网格。
正如您展示的那样，您的树数据不允许您绘制图表。你实际上在那里遗漏了一些信息：
- tree 实际上应该是 object（字典）将 id 映射到人的数据。否则，从
children中给出的 id 返回到 child 的数据是昂贵的。 - 存在重复信息，因为 children 与 parent 相关联。这实际上会导致您发送的示例中的数据不正确（'daugher1' 是 'wife' 的 child，但是 'me' 的 parent，以及 'mary' 大概是 'jeff' 的母亲；jessie 是 robert 的伴侣；raymond 和 betty 也是）
在我的尝试 (https://jsfiddle.net/61q2ym7q/) 中，我因此将您的树转换为图形，然后进行各个阶段的计算以实现布局。
这是受 Sugiyama 算法的启发，但经过简化，因为该算法实施起来非常棘手。不过，各个阶段是：
使用 depth-first 搜索将节点组织成层。我们通过确保 parent 始终位于它们的 parent 之上的一层，然后在 child 和 child 之间存在不止一层时尝试缩短链接parent。这是我没有使用精确的 Sugiyama 算法的部分，它使用了复杂的切点概念。
然后将节点分类到每一层中，以尽量减少边的交叉。我为此使用重心法
最后，在保留上述顺序的同时，再次使用重心法为每个节点分配一个特定的 x 坐标
此代码（效率，例如通过合并一些循环）以及最终布局中有很多地方可以改进。但我试图让它更简单，让它更容易理解......
据我所知 - 不看你那里的代码（现在） - 你有一个 DAG （视觉表示是另一回事，现在我只谈论数据结构).每个节点最多有 2 个传入连接，并且对连接到其他节点没有限制（一个节点可以有任意数量的子节点，但我们有每个 person/node 最多有 2 个父节点的信息）。
也就是说，会有没有父节点的节点（在这种情况下是 "john"、"raymond"、"betty"、"mistress 1"、"wife 1"，和 "daughter 1 boyfriend"）。如果您从这些节点开始在图表上执行 BFS - 这将构成级别 0 - 您将获得每个级别的节点。不过必须即时更新正确的级别。
关于视觉表示，我不是专家，但 IMO 可以通过网格（如 table-like 视图）视图来实现。每行包含特定级别的节点。给定行中的元素根据与同一行、行 x - 1 和行 x + 1.
为了更好地解释这个想法，我想最好加入一些 pseudo-code（不是 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 的节点。您只需要在 gridview（或您选择的任何布局）中表示它们。
如果有任何不清楚的地方，请告诉我。
虽然已经发布了一个答案（并被接受），但我认为发布我昨晚在这个问题上所做的工作没有什么坏处。
我更多地是从新手的角度来解决这个问题，而不是使用现有的 graph/tree 遍历算法。
My first attempt is rendering this by levels from the top down. In this more simplistic attempt, I basically nest all of the people by levels and render this from the top down.
这也是我的第一次尝试。您可以遍历树 top-down 或 bottom-up 或从根开始。当您受到某个特定网站的启发时，从根开始似乎是一个合乎逻辑的选择。但是，我发现 bottom-up 方法更简单、更容易理解。
这是一个粗略的尝试：
绘制数据：
- 我们从 bottom-most 层开始，一路向上。正如您尝试通过编辑器解决问题中提到的那样，我们可以在构建树时将所有相关属性存储在 object 数组中。
我们缓存关卡并使用它来遍历树：
// 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从数据中获取object。
- 当我们向上走时，我们绘制节点本身、它的 parents（递归地）和它的伙伴。绘制合作伙伴并不是真正需要的，但我在这里这样做只是为了让绘制连接器变得容易。如果已经绘制了一个节点，我们只需跳过该部分。
这就是我们绘制合作伙伴的方式：
/* 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');
});
}
并且 parent 递归：
/* 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 来简化绘制两个 parent 之间的连接器作为合作伙伴。
- 这就是我们绘制节点本身的方式：
其中，我们通过 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);
}
我使用了两种不同的连接器，一种是水平的连接伙伴，另一种是倾斜的连接 parent-child 关系。这对我来说是一个非常棘手的部分，即绘制倒置的 ] 水平连接器。这就是为什么要保持简单，我只是旋转了一个 div 使其看起来像一个有角度的连接器。
- 一旦整个树为 drawn/plotted，可能会有节点由于负位置而变为 off-screen（因为我们正在遍历 bottom-up）。为了抵消这一点，我们只需检查是否有任何负位置，然后将整个树向下移动。
这是带有 fiddle 演示的完整代码。
Fiddle 演示：http://jsfiddle.net/abhitalks/fvdw9xfq/embedded/result/
This is for an editor and would be similar to
正在创建编辑器：
测试它是否有效的最佳方法是使用一个编辑器，它允许您即时创建这样的 trees/graphs 并查看它是否成功绘制。
所以，我也创建了一个简单的编辑器来测试。代码保持完全相同，但是 re-factored 稍微适合编辑器的例程。
Fiddle 编辑器演示：http://jsfiddle.net/abhitalks/56whqh0w/embedded/result
带有编辑器的片段演示（视图 full-screen）：
var sampleData = [
{ "id": 1, "name": "Me", "children": [4], "partners" : [2,3], root:true, level: 0, "parents": [8,9] },
{ "id": 2, "name": "Mistress", "children": [4], "partners" : [1], level: 0, "parents": [] },
{ "id": 3, "name": "Wife", "children": [5], "partners" : [1], level: 0, "parents": [] },
{ "id": 4, "name": "Son", "children": [], "partners" : [], level: -1, "parents": [1,2] },
{ "id": 5, "name": "Daughter", "children": [7], "partners" : [6], level: -1, "parents": [1,3] },
{ "id": 6, "name": "Boyfriend", "children": [7], "partners" : [5], level: -1, "parents": [] },
{ "id": 7, "name": "Son Last", "children": [], "partners" : [], level: -2, "parents": [5,6] },
{ "id": 8, "name": "Jeff", "children": [1], "partners" : [9], level: 1, "parents": [10,11] },
{ "id": 9, "name": "Maggie", "children": [1], "partners" : [8], level: 1, "parents": [13,14] },
{ "id": 10, "name": "Bob", "children": [8], "partners" : [11], level: 2, "parents": [12] },
{ "id": 11, "name": "Mary", "children": [], "partners" : [10], level: 2, "parents": [] },
{ "id": 12, "name": "John", "children": [10], "partners" : [], level: 3, "parents": [] },
{ "id": 13, "name": "Robert", "children": [9], "partners" : [14], level: 2, "parents": [] },
{ "id": 14, "name": "Jessie", "children": [9], "partners" : [13], level: 2, "parents": [15,16] },
{ "id": 15, "name": "Raymond", "children": [14], "partners" : [16], level: 3, "parents": [] },
{ "id": 16, "name": "Betty", "children": [14], "partners" : [15], level: 3, "parents": [] },
],
data = [], elements = [], levels = [], levelMap = [],
tree = document.getElementById('tree'), people = document.getElementById('people'), selectedNode,
startTop, startLeft, gap = 32, size = 64
;
/* Template object for person */
function Person(id) {
this.id = id ? id : '';
this.name = id ? id : '';
this.partners = [];
this.siblings = [];
this.parents = [];
this.children = [];
this.level = 0;
this.root = false;
}
/* Event listeners */
tree.addEventListener('click', function(e) {
if (e.target.classList.contains('node')) {
selectedNode = e.target;
select(selectedNode);
document.getElementById('title').textContent = selectedNode.textContent;
fillPeopleAtLevel();
}
});
document.getElementById('save').addEventListener('click', function() {
var pname = document.getElementById('pname').value;
if (pname.length > 0) {
data.forEach(function(person) {
if (person.id == selectedNode.id) {
person.name = pname;
selectedNode.textContent = pname;
document.getElementById('title').textContent = pname;
}
});
}
});
document.getElementById('add').addEventListener('click', function() {
addPerson(document.getElementById('relation').value);
plotTree();
});
document.getElementById('addExisting').addEventListener('click', function() {
attachParent();
plotTree();
});
document.getElementById('clear').addEventListener('click', startFresh);
document.getElementById('sample').addEventListener('click', function() {
data = sampleData.slice();
plotTree();
});
document.getElementById('download').addEventListener('click', function() {
if (data.length > 1) {
var download = JSON.stringify(data, null, 4);
var payload = "text/json;charset=utf-8," + encodeURIComponent(download);
var a = document.createElement('a');
a.href = 'data:' + payload;
a.download = 'data.json';
a.innerHTML = 'click to download';
var container = document.getElementById('downloadLink');
container.appendChild(a);
}
});
/* Initialize */
function appInit() {
// Approximate center of the div
startTop = parseInt((tree.clientHeight / 2) - (size / 2));
startLeft = parseInt((tree.clientWidth / 2) - (size / 2));
}
/* Start a fresh tree */
function startFresh() {
var start, downloadArea = document.getElementById('downloadLink');
// Reset Data Cache
data = [];
appInit();
while (downloadArea.hasChildNodes()) { downloadArea.removeChild(downloadArea.lastChild); }
// Add a root "me" person to start with
start = new Person('P01'); start.name = 'Me'; start.root = true;
data.push(start);
// Plot the tree
plotTree();
// Pre-select the root node
selectedNode = get('P01');
document.getElementById('title').textContent = selectedNode.textContent;
}
/* Plot entire tree from bottom-up */
function plotTree() {
// Reset other cache and DOM
elements = [], levels = [], levelMap = []
while (tree.hasChildNodes()) { tree.removeChild(tree.lastChild); }
// Get all the available levels from the data
data.forEach(function(elem) {
if (levels.indexOf(elem.level) === -1) { levels.push(elem.level); }
});
// Sort the levels in ascending order
levels.sort(function(a, b) { return a - b; });
// For all level starting from lowest one
levels.forEach(function(level) {
// Get all persons from this level
var startAt = data.filter(function(person) {
return person.level == level;
});
startAt.forEach(function(start) {
var person = getPerson(start.id);
// Plot each person in this level
plotNode(person, 'self');
// Plot partners
plotPartners(person);
// And plot the parents of this person walking up
plotParents(person);
});
});
// Adjust coordinates to keep the tree more or less in center
adjustNegatives();
}
/* Plot partners for the current person */
function plotPartners(start) {
if (! start) { return; }
start.partners.forEach(function(partnerId) {
var partner = getPerson(partnerId);
// Plot node
plotNode(partner, 'partners', start);
// Plot partner connector
plotConnector(start, partner, 'partners');
});
}
/* Plot parents walking up the tree */
function plotParents(start) {
if (! start) { return; }
start.parents.reduce(function(previousId, currentId) {
var previousParent = getPerson(previousId),
currentParent = getPerson(currentId);
// Plot node
plotNode(currentParent, 'parents', start, start.parents.length);
// Plot partner connector if multiple parents
if (previousParent) { plotConnector(previousParent, currentParent, 'partners'); }
// Plot parent connector
plotConnector(start, currentParent, 'parents');
// Recurse and plot parent by walking up the tree
plotParents(currentParent);
return currentId;
}, 0);
}
/* Plot a single node */
function plotNode() {
var person = arguments[0], relationType = arguments[1], relative = arguments[2], numberOfParents = arguments[3],
node = get(person.id), relativeNode, element = {}, thisLevel, exists
;
if (node) { return; }
node = createNodeElement(person);
// Get the current level
thisLevel = findLevel(person.level);
if (! thisLevel) {
thisLevel = { 'level': person.level, 'top': startTop };
levelMap.push(thisLevel);
}
// Depending on relation determine position to plot at relative to current person
if (relationType == 'self') {
node.style.left = startLeft + 'px';
node.style.top = thisLevel.top + 'px';
} else {
relativeNode = get(relative.id);
}
if (relationType == 'partners') {
// Plot to the right
node.style.left = (parseInt(relativeNode.style.left) + size + (gap * 2)) + 'px';
node.style.top = parseInt(relativeNode.style.top) + 'px';
}
if (relationType == 'children') {
// Plot below
node.style.left = (parseInt(relativeNode.style.left) - size) + 'px';
node.style.top = (parseInt(relativeNode.style.top) + size + gap) + 'px';
}
if (relationType == 'parents') {
// Plot above, if single parent plot directly above else plot with an offset to left
if (numberOfParents == 1) {
node.style.left = parseInt(relativeNode.style.left) + 'px';
node.style.top = (parseInt(relativeNode.style.top) - gap - size) + 'px';
} else {
node.style.left = (parseInt(relativeNode.style.left) - size) + 'px';
node.style.top = (parseInt(relativeNode.style.top) - gap - size) + 'px';
}
}
// Avoid collision moving to right
while (exists = detectCollision(node)) {
node.style.left = (exists.left + size + (gap * 2)) + 'px';
}
// Record level position
if (thisLevel.top > parseInt(node.style.top)) {
updateLevel(person.level, 'top', parseInt(node.style.top));
}
element.id = node.id; element.left = parseInt(node.style.left); element.top = parseInt(node.style.top);
elements.push(element);
// Add the node to the DOM tree
tree.appendChild(node);
}
/* Helper Functions */
function createNodeElement(person) {
var node = document.createElement('div');
node.id = person.id;
node.classList.add('node'); node.classList.add('asset');
node.textContent = person.name;
node.setAttribute('data-level', person.level);
return node;
}
function select(selectedNode) {
var allNodes = document.querySelectorAll('div.node');
[].forEach.call(allNodes, function(node) {
node.classList.remove('selected');
});
selectedNode.classList.add('selected');
}
function get(id) { return document.getElementById(id); }
function getPerson(id) {
var element = data.filter(function(elem) {
return elem.id == id;
});
return element.pop();
}
function fillPeopleAtLevel() {
if (!selectedNode) return;
var person = getPerson(selectedNode.id), level = (person.level + 1), persons, option;
while (people.hasChildNodes()) { people.removeChild(people.lastChild); }
data.forEach(function(elem) {
if (elem.level === level) {
option = document.createElement('option');
option.value = elem.id; option.textContent = elem.name;
people.appendChild(option);
}
});
return persons;
}
function attachParent() {
var parentId = people.value, thisId = selectedNode.id;
updatePerson(thisId, 'parents', parentId);
updatePerson(parentId, 'children', thisId);
}
function addPerson(relationType) {
var newId = 'P' + (data.length < 9 ? '0' + (data.length + 1) : data.length + 1),
newPerson = new Person(newId), thisPerson;
;
thisPerson = getPerson(selectedNode.id);
// Add relation between originating person and this person
updatePerson(thisPerson.id, relationType, newId);
switch (relationType) {
case 'children':
newPerson.parents.push(thisPerson.id);
newPerson.level = thisPerson.level - 1;
break;
case 'partners':
newPerson.partners.push(thisPerson.id);
newPerson.level = thisPerson.level;
break;
case 'siblings':
newPerson.siblings.push(thisPerson.id);
newPerson.level = thisPerson.level;
// Add relation for all other relatives of originating person
newPerson = addRelation(thisPerson.id, relationType, newPerson);
break;
case 'parents':
newPerson.children.push(thisPerson.id);
newPerson.level = thisPerson.level + 1;
break;
}
data.push(newPerson);
}
function updatePerson(id, key, value) {
data.forEach(function(person) {
if (person.id === id) {
if (person[key].constructor === Array) { person[key].push(value); }
else { person[key] = value; }
}
});
}
function addRelation(id, relationType, newPerson) {
data.forEach(function(person) {
if (person[relationType].indexOf(id) != -1) {
person[relationType].push(newPerson.id);
newPerson[relationType].push(person.id);
}
});
return newPerson;
}
function findLevel(level) {
var element = levelMap.filter(function(elem) {
return elem.level == level;
});
return element.pop();
}
function updateLevel(id, key, value) {
levelMap.forEach(function(level) {
if (level.level === id) {
level[key] = value;
}
});
}
function detectCollision(node) {
var element = elements.filter(function(elem) {
var left = parseInt(node.style.left);
return ((elem.left == left || (elem.left < left && left < (elem.left + size + gap))) && elem.top == parseInt(node.style.top));
});
return element.pop();
}
function adjustNegatives() {
var allNodes = document.querySelectorAll('div.asset'),
minTop = startTop, diff = 0;
for (var i=0; i < allNodes.length; i++) {
if (parseInt(allNodes[i].style.top) < minTop) { minTop = parseInt(allNodes[i].style.top); }
};
if (minTop < startTop) {
diff = Math.abs(minTop) + gap;
for (var i=0; i < allNodes.length; i++) {
allNodes[i].style.top = parseInt(allNodes[i].style.top) + diff + 'px';
};
}
}
function plotConnector(source, destination, relation) {
var connector = document.createElement('div'), orientation, start, stop,
x1, y1, x2, y2, length, angle, transform
;
orientation = (relation == 'partners') ? 'h' : 'v';
connector.classList.add('asset');
connector.classList.add('connector');
connector.classList.add(orientation);
start = get(source.id); stop = get(destination.id);
if (relation == 'partners') {
x1 = parseInt(start.style.left) + size; y1 = parseInt(start.style.top) + (size/2);
x2 = parseInt(stop.style.left); y2 = parseInt(stop.style.top);
length = (x2 - x1) + 'px';
connector.style.width = length;
connector.style.left = x1 + 'px';
connector.style.top = y1 + 'px';
}
if (relation == 'parents') {
x1 = parseInt(start.style.left) + (size/2); y1 = parseInt(start.style.top);
x2 = parseInt(stop.style.left) + (size/2); y2 = parseInt(stop.style.top) + (size - 2);
length = Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
angle = Math.atan2(y2 - y1, x2 - x1) * 180 / Math.PI;
transform = 'rotate(' + angle + 'deg)';
connector.style.width = length + 'px';
connector.style.left = x1 + 'px';
connector.style.top = y1 + 'px';
connector.style.transform = transform;
}
tree.appendChild(connector);
}
/* App Starts Here */
appInit();
startFresh();
* { box-sizing: border-box; padding: 0; margin: 0; }
html, body { width: 100vw; height: 100vh; overflow: hidden; font-family: sans-serif; font-size: 0.9em; }
#editor { float: left; width: 20vw; height: 100vh; overflow: hidden; overflow-y: scroll; border: 1px solid #ddd; }
#tree { float: left; width: 80vw; height: 100vh; overflow: auto; position: relative; }
h2 { text-align: center; margin: 12px; color: #bbb; }
fieldset { margin: 12px; padding: 8px 4px; border: 1px solid #bbb; }
legend { margin: 0px 8px; padding: 4px; }
button, input, select { padding: 4px; margin: 8px 0px; }
button { min-width: 64px; }
div.node {
width: 64px; height: 64px; line-height: 64px;
background-color: #339; color: #efefef;
font-family: sans-serif; font-size: 0.7em;
text-align: center; border-radius: 50%;
overflow: hidden; position: absolute; cursor: pointer;
}
div.connector { position: absolute; background-color: #333; z-index: -10; }
div.connector.h { height: 2px; background-color: #ddd; }
div.connector.v { height: 1px; background-color: #66d; -webkit-transform-origin: 0 100%; transform-origin: 0 100%; }
div[data-level='0'] { background-color: #933; }
div[data-level='1'], div[data-level='-1'] { background-color: #393; }
div[data-level='2'], div[data-level='-2'] { background-color: #333; }
div.node.selected { background-color: #efefef; color: #444; }
<div id="editor">
<h2 id="title">Me</h2>
<div>
<fieldset>
<legend>Change Name</legend>
<label>Name: <input id="pname" type="text" /></label>
<br /><button id="save">Ok</button>
</fieldset>
<fieldset>
<legend>Add Nodes</legend>
<label for="relation">Add: </label>
<select id="relation">
<option value="partners">Partner</option>
<option value="siblings">Sibling</option>
<option value="parents">Parent</option>
<option value="children">Child</option>
</select>
<button id="add">Ok</button><br />
<label for="relation">Add: </label>
<select id="people"></select>
<button id="addExisting">As Parent</button>
</fieldset>
<fieldset>
<legend>Misc</legend>
<button id="clear">Clear</button> <button id="sample">Load Sample</button>
<br/><button id="download">Download Data</button>
</fieldset>
<fieldset id="downloadLink"></fieldset>
</div>
</div>
<div id="tree"></div>
这都是一次非常粗糙的尝试，毫无疑问是一次 un-optimized。我特别不能完成的是：
- 为 parent-child 关系获取倒
[或]形状的水平连接器。 - 使树水平平衡。即动态找出哪个是较重的一侧，然后将这些节点向左移动。
- 让 parent 相对于 children 尤其是多个 children 居中对齐。目前，我的尝试只是将所有内容按顺序推到正确位置。
希望对您有所帮助。并张贴在这里，以便我也可以在需要时参考。