我想生成这个：
使用此数据结构（ID是随机的，顺便说一下，不是顺序的）：
var tree = [
{ "id": 1, "name": "Me", "dob": "1988", "children": [4], "partners" : [2,3], root:true, level: 0, "parents": [5,6] },
{ "id": 2, "name": "Mistress 1", "dob": "1987", "children": [4], "partners" : [1], level: 0, "parents": [] },
{ "id": 3, "name": "Wife 1", "dob": "1988", "children": [5], "partners" : [1], level: 0, "parents": [] },
{ "id": 4, "name": "son 1", "dob": "", "children": [], "partners" : [], level: -1, "parents": [1,2] },
{ "id": 5, "name": "daughter 1", "dob": "", "children": [7], "partners" : [6], level: -1, "parents": [1,3] },
{ "id": 6, "name": "daughter 1s boyfriend", "dob": "", "children": [7], "partners" : [5], level: -1, "parents": [] },
{ "id": 7, "name": "son (bottom most)", "dob": "", "children": [], "partners" : [], level: -2, "parents": [5,6] },
{ "id": 8, "name": "jeff", "dob": "", "children": [1], "partners" : [9], level: 1, "parents": [10,11] },
{ "id": 9, "name": "maggie", "dob": "", "children": [1], "partners" : [8], level: 1, "parents": [] },
{ "id": 10, "name": "bob", "dob": "", "children": [8], "partners" : [11], level: 2, "parents": [12] },
{ "id": 11, "name": "mary", "dob": "", "children": [], "partners" : [10], level: 2, "parents": [] },
{ "id": 12, "name": "john", "dob": "", "children": [10], "partners" : [], level: 3, "parents": [] },
{ "id": 13, "name": "robert", "dob": "", "children": [9], "partners" : [], level: 2, "parents": [] },
{ "id": 14, "name": "jessie", "dob": "", "children": [9], "partners" : [], level: 2, "parents": [15,16] },
{ "id": 15, "name": "raymond", "dob": "", "children": [14], "partners" : [], level: 3, "parents": [] },
{ "id": 16, "name": "betty", "dob": "", "children": [14], "partners" : [], level: 3, "parents": [] },
];
为了描述数据结构，定义了根/起始节点（me） . 任何伴侣（妻子，前妻）都处于同一水平 . 下面的任何东西都变成-1级，-2级 . 以上任何内容都是1,2级等 . 有 parents, siblings, children 和 partners 的属性定义了该特定字段的ID .
在我之前question，eh9 described他将如何解决这个问题 . 我试图这样做，但是因为我很容易完成任务 .
我的first attempt从上到下按级别渲染 . 在这个更简单的尝试中，我基本上按级别嵌套所有人，并从上到下渲染它 .
我的second attempt使用深度优先搜索使用其中一个祖先节点进行渲染 .
My main question is ：我怎样才能真正将答案应用到我现有的答案中？在我的第二次尝试中，我正在尝试进行深度优先遍历，但我怎么能开始考虑计算抵消网格所需的距离以使其与我想要生成的方式一致？
另外，我是深度优先理想的理解/实现，还是我能以不同的方式遍历它？
在我的第二个例子中，节点明显重叠，因为我没有偏移/距离计算代码，但是我真的想知道如何开始这个 .
这是我所做的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 . 几乎所有未定义的业务规则都可以通过它来实现 .
-
家庭育种并不担心这一点 .
-
支持多个合作伙伴，因此这不仅仅是传统的"family tree"只有2个父母和1个孩子 .
-
只有一个"root"节点，它只是起始节点 .
Notes ：如果's lots of leaf nodes and there'发生碰撞，familyecho.com似乎"hide"分支 . 可能需要实现这一点 .
5 回答
虽然答案已经发布（并被接受），但我认为昨晚发布我对这个问题所做的工作没有任何害处 .
我从新手的角度更多地解决了这个问题，而不是使用现有的图形/树遍历算法 .
这也是我的第一次尝试 . 您可以从上到下，从下到上或从根开始遍历树 . 由于您受到特定网站的启发，从根本位置开始似乎是一个合乎逻辑的选择 . 但是，我发现自下而上的方法更简单，更容易理解 .
这是一个粗略的尝试：
绘制数据：
我们缓存级别并使用它来走树：
其中，
getPerson基于其id从数据中获取对象 .这是我们策划合作伙伴的方式：
父母递归地说：
我们使用
reduce来简化两个父母之间的连接器作为合作伙伴的情节 .其中，我们通过
findLevel实用程序函数重用每个唯一级别的坐标 . 我们维护一个水平图并检查是否到达top位置 . 休息是根据关系确定的 .为了简单起见，我使用了一个非常粗略的碰撞检测，在已经存在的情况下将节点移动到右边 . 在一个非常复杂的应用程序中，这将动态向左或向右移动节点以保持水平 balancer .
最后，我们将该节点添加到DOM .
重要的是：
以上是考虑到节点之间的间隙的简单碰撞检测 .
并且，绘制连接器：
我使用了两个不同的连接器，一个用于连接伙伴的水平连接器，另一个用于连接父子关系的连接器 . 对我来说这对我来说是一个非常棘手的部分，即绘制倒置
]水平连接器 . 这就是为什么要保持简单，我只需旋转div使其看起来像一个有角度的连接器 .这是完整的代码与小提琴演示 .
Fiddle Demo: http://jsfiddle.net/abhitalks/fvdw9xfq/embedded/result/
创建编辑器：
测试它是否有效的最佳方法是使用一个编辑器，允许您动态创建这样的树/图并查看它是否成功绘制 .
所以，我还创建了一个简单的编辑器来测试 . 代码保持完全相同，但是已经重新考虑了一些以适应编辑器的例程 .
Fiddle Demo with Editor: http://jsfiddle.net/abhitalks/56whqh0w/embedded/result
Snippet Demo with Editor (view full-screen):
这是一次非常粗暴的尝试，并且无疑是一种未经优化的尝试 . 我特别不能做的是：
为父子关系获取倒置的
[或]形水平连接器 .使树水平 balancer . 即，动态地确定哪个是较重的一侧，然后将这些节点向左移动 .
让父母集体对齐儿童，特别是多个孩子 . 目前，我的尝试只是按顺序将所有内容推向正确 .
希望能帮助到你 . 并在此处发布，以便我也可以在需要时参考它 .
当您显示它时，您的树数据将不允许您绘制图表 . 你实际上在那里遗漏了一些信息：
tree应该是将id映射到人员数据的对象（字典） . 否则，从例如
children中给出的id返回到孩子的数据是很昂贵的 .由于子项与父项相关联，因此存在重复信息 . 这实际上导致您发送的示例中的数据不正确（'daugher1'是'wife'的子项，但是'me'的父项，'mary'可能是'jeff'的母亲; jessie是罗伯特的合作伙伴;因此是raymond和betty）
在我的尝试（https://jsfiddle.net/61q2ym7q/）中，我因此将您的树转换为图形，然后进行各种计算阶段以实现布局 .
这受Sugiyama算法的启发，但是简化了，因为该算法实现起来非常棘手 . 不过，各个阶段是：
使用深度优先搜索将节点组织到图层中 . 我们通过确保父项始终位于父项之上的层上，然后在子项和父项之间存在多个层时尝试缩短链接来分两步执行此操作 . 这是我没有使用精确Sugiyama算法的部分，该算法使用复杂的切割点概念 .
然后将节点排序到每个层中以最小化边的交叉 . 我使用重心方法
最后，在保留上面的顺序的同时，再次使用重心方法为每个节点分配一个特定的x坐标
在这段代码中有很多东西可以改进（效率，例如通过合并一些循环）以及最终布局 . 但是我试图让它更容易遵循......
这与Sugiyama算法用于布局类层次结构的方式相差不远，因此您可能需要查看讨论它的papers . 有一章书涵盖Sugiyama和其他分层布局算法here .
我会独立地布置树的上半部分和下半部分 . 关于上半部分的认识是，在其完全填充的形式中，它是2的所有权力，所以你有两个父母，四个祖父母，十六个曾祖父母等 .
当您进行深度优先搜索时，使用a）标记每个节点的层编号和b）其整理顺序 . 您的数据结构不包含性别，出于风格原因和确定整理顺序，您确实需要这样做 . 幸运的是，所有家谱数据都包括性别 .
我们用“A”标记父亲，用“B”标记母亲 . 祖父母又附上另一封信，所以你得到：
随时将节点添加到每个图层的列表中 . 按性别键对每个图层进行排序（除非使用已排序的列表） . 在具有最大编号的图层处开始布局，并将节点从左侧（AAAAA）布置到右侧（BBBBB），为任何丢失的节点留下间隙 . 从风格上来说，决定是否要在丢失的节点周围进行折叠，如果是这样，请考虑多少（虽然我建议首先实现简单的版本） .
按降序排列图层 . 如果没有折叠/调整位置，则可以直接计算下层位置 . 如果你正在调整，你需要引用前一层中的父母位置，并将孩子置于其中心 .
图表的下半部分可以以类似的方式完成，除了不按性别排序，您可能希望按出生顺序排序并根据出生顺序 Build 密钥 . 长子的长子有“11”，而第二个长子的长子是“21”等 .
您可以使用像cola.js这样的图形库来执行此操作，但是您只需要使用其功能的一小部分以及您想要的一些风格元素（例如，保持父亲和母亲紧密相连），可能需要添加另外，所以我怀疑从头开始构建很容易，除非你需要库中的其他功能 .
说到样式，习惯上为父连接器使用不同的线型（传统上它是双线） . 此外，您不希望“Mistress”节点位于“我”/“妻子”边缘之上 .
附：使用固定大小的节点，您可以为坐标系统提供简单的网格 .
这不是一个小问题，它涉及图形绘制算法的大量研究 .
解决这个问题最突出的方法是通过约束满足 . 但是不要试图自己实现这个（除非你想学习新东西并花几个月的时间调试）
我不能高度推荐这个库：cola.js（GitHub）
特别是example可能非常接近您所需要的是网格布局 .
从我所看到的 - 没有看到你那里的代码（现在） - 你有一个DAG（视觉表示是另一回事，现在我只谈论数据结构） . 每个节点最多有2个传入连接，并且对连接到其他节点的连接没有约束（一个可以有任意数量的子节点，但我们有每个人/节点最多2个父节点的信息） .
话虽如此，将会有没有父节点的节点（在这种情况下是"john"，"raymond"，"betty"，"mistress 1"，"wife 1"和"daughter 1 boyfriend"） . 如果你从这些节点开始在图表上做BFS - 这将组成0级 - 你得到每个级别的节点 . 必须尽快更新正确的级别 .
关于视觉表示，我不是专家，但是IMO可以通过网格（如在桌面式中）视图来实现 . 每行包含特定级别的节点 . 给定行中的元素基于与同一行，行
x - 1和行x + 1中的其他元素的关系排列 .为了更好地解释这个想法，我想最好放入一些伪代码（不是JS，因为它不是我的力量）：
在过程结束时，您将拥有一个节点矩阵，其中行
i包含级别i的节点 . 您只需要在gridview中表示它们（或者您选择的任何布局） .如果有什么不清楚，请告诉我 .