问题标签 [family-tree]

假设我有一个无环有向图，例如家庭“树”（不是真正的树，因为孩子有 2 个父母）。我想将此图的表示形式放在关系数据库中，以便快速计算节点的所有祖先和节点的所有后代。你会如何表示这个图表？您将如何查询所有后代？您将如何插入和删除节点和关系？你对数据做了什么假设？

对于您运行查询祖先和后代的语句数量，最佳解决方案将具有最佳大 O，在select/insert/delete总运行时间中，最佳大 O 打破平局，并因空间要求而打破平局。

我的同事向我提出了这个问题。我有一个解决方案，但在最坏的情况下它是指数级的，所以我想看看其他人会如何解决它。

编辑

明确的关系数据库。如果您使用带有内置传递闭包的图形数据库，这个问题是微不足道的（而且很无聊）。

假设我的 familyTree.pl 文件中有以下代码：

现在，我想得到以下问题的答案：

我怎样才能问上面的问题来序言？

我能想出的唯一解决方案是迭代已知的关系类型，将 (Tom, Bob) 或 (Lisa, Emily) 作为参数并检查哪一个返回 true。但; 当已知关系类型的数量不止几个和/或给定的两个人之间存在连锁关系（即：Lisa 和 Emily：Lisa 是 Emily 的男朋友的母亲）时，这种解决方案似乎是在浪费时间。

我正在用 Java 创建一个家谱程序，或者至少尝试这样做。我开发了几个类：

• 人 - 名称性别年龄等的获取者和设置者
• FamilyMember - 扩展 Person 获取器和设置器以设置父母和孩子
• Family - 由多个家庭成员和添加删除成员的方法组成
• FamilyTree 是设置关系的主要类。

我有两个主要问题：

1）我需要设置人与人之间的关系。目前我正在做：

上面的示例用于设置母子关系。

这看起来很笨拙。实现所有关系变得非常冗长。关于如何以较少程序的方式实现多个关系的任何想法？

2）我必须能够显示家谱。我怎样才能做到这一点？是否有任何自定义课程可以让生活更轻松？

谢谢你的时间...

我正在创建一个家谱程序。我的问题是如何定位节点？最初我将根定位在屏幕的中心，如果它是一个完美的二叉树并且级别非常低，它就可以正常工作。然而，大多数情况下并非如此。这是一个示例树：-

如您所见，主要问题在于节点的位置。如果一个节点有很多子节点并且它的相邻节点也有很多子节点，它们往往会重叠。（主要问题）我在 Silverlight 中使用 Canvas 使用节点的绝对定位。如果您不是 Silverlight 开发人员，您可能不会关心 Silverlight 和 Canvas 部分。我只需要如何定位节点的逻辑。

通过知道树的总层数，可以很容易地计算出树的高度，但树的宽度是困扰我的问题。我如何计算树的宽度（画布的总宽度）

有人可以给我一些关于如何设置画布宽度以及哪些逻辑最适合节点定位的一般指导方针。

注意：-我不是要整个算法，这不是我的作业。我已经有了算法和数据库。我只需要节点定位部分的指南。

提前致谢 ：）

我正在从事一个家谱项目。我一直在尝试找到一个用于创建家谱的 jquery 插件。

是否有现有的 PHP、Javascript 甚至命令行工具可以在 HTML 中构建家族树（最好）或者至少为它创建一个图像？多个父母是必需的。我已经在谷歌上搜索了几个小时，但无济于事。

例如，谷歌组织结构图是理想的，但它只允许每个节点最多有一个父节点。我需要两个父母才有可能。

无论这个网站做什么也是完美的：http: //www.familyecho.com/，但它似乎不是用 javascript 完成的，而且他们没有发布实际创建可视化的代码。

即使连接到外部网站以使用其 API 生成可视化效果也是完美的。

我需要在 php 和 MySQL 中建立一个家谱。我对那里缺乏开源可定制的 html 家谱构建软件感到非常惊讶，但我离题了。我花了很多时间阅读有关存储 MySQL 有向图和家谱的信息。一切对我来说都是有意义的：有一个带有节点（人）的表和一个带有边（关系）的表。

我唯一的问题是我不确定存储不一定相邻的关系的最佳方式，例如兄弟姐妹和祖父母关系。起初我认为这没什么大不了的，因为我可以无形地强制执行可以解决这些连接的父母（每个人都有父母）。

但是，我还需要能够存储可能没有共同父母的关系，例如浪漫伴侣。我读过的所有内容都暗示了亲子关系，但是由于浪漫的伴侣没有共同的父母（希望如此），我不确定如何将其存储在边表中。我应该使用不同的表，还是什么？如果它在同一张表中，我该如何表示？只要我在不熟悉的关系中这样做，我也可以和家人一起这样做。

总结一下，三个问题：

• 我如何表示横向关系？
• 如果横向关系有共同的父母，我该如何存储？这应该family是存储其他横向关系的桌子上的标志吗？
• 如何在孩子距离两个或更多边缘（祖父母）但直接父母不可用的情况下存储父子关系？

感谢任何帮助，如果有人对一些 javascript/html 家谱构建软件有任何建议，那就太好了。

我正在尝试使用 MVC3 和 SQL Server 2008 创建一个家谱网站（供个人使用），但是我对 MVC3（使用 Razor 和实体框架）相对较新，但对 SQL Server 非常了解。我非常沮丧，并且很想使用 WebForms 开发网站，因为我非常熟悉这项技术。

我的问题是我分为以下两种方法，但我坚持如何使用 MVC3 和实体框架来实现：1）使用包含个人信息的 Person 表和一个桥接表来存储 Person 表上持有的个人之间的关系.

2）嵌套集将所有信息存储在一张表上。

有人可以请给我一些关于如何开始的指导，最好使用嵌套集方法，因为我希望读取层次结构的性能尽可能快，因为这将是该站点的主要目的。

我希望我提供了足够的信息，如果没有，请向我询问更多详细信息。

我正在为入门级 CS 课程整理一个问题集，并提出了一个表面上看起来非常简单的问题：

你会得到一份名单，上面有他们父母的姓名、出生日期和死亡日期。你有兴趣找出谁在他们一生中的某个时刻是父母、祖父母、曾祖父母等。设计一个算法，用这个信息将每个人标记为一个整数（0 表示这个人从来没有孩子，1 表示此人是父母，2 表示此人是祖父母，以此类推）

为简单起见，您可以假设族图是一个 DAG，其无向版本是一棵树。

这里有趣的挑战是你不能只看树的形状来确定这些信息。例如，我有 8 个曾曾祖父母，但由于我出生时他们都不在世，所以在他们的有生之年，他们都不是曾曾祖父母。

对于这个问题，我能想出的最佳算法运行时间为 O(n ² )，其中 n 是人数。这个想法很简单——从每个人开始一个 DFS，在该人死亡日期之前出生的家谱中找到最远的后代。但是，我很确定这不是问题的最佳解决方案。例如，如果图只是两个父母和他们的 n 个孩子，那么问题可以在 O(n) 中轻松解决。我希望的是某种算法，它要么优于 O(n ² )，要么其运行时间在图形的形状上被参数化，这使得它对于宽图快速，在最坏的情况下优雅地降级到 O(n ² ) -案子。

我是一些家谱软件（用 C++ 和 Qt 编写）的开发人员。直到我的一位客户给我寄了一份错误报告，我才发现问题。问题是客户有两个孩子和自己的女儿，结果他因为错误不能使用我的软件。

这些错误是我关于正在处理的家庭图的各种断言和不变量的结果（例如，经过一个循环后，程序声明 X 不能既是 Y 的父亲又是祖父）。

如何在不删除所有数据断言的情况下解决这些错误？