家谱软件中的循环问题

1590

我是一名家谱软件的开发人员(使用C++和Qt编写)。我之前没有遇到问题,直到有一位客户给我发送了一个错误报告。问题在于该客户有两个孩子都与自己的女儿生过孩子,导致我的软件出现错误而无法使用。

这些错误是因为我在处理家庭图表时使用了各种断言和不变量(例如,在遍历循环后,程序会声明X不能同时是Y的父亲和祖父)。

我如何解决这些错误而不必删除所有数据断言?


220
你应该在创作软件时,将雷·史蒂文斯的歌曲放在心中。 - Peter K.
30
如果你追溯家族谱系足够久,你会发现这个问题比你想象中要频繁。放弃使用树形结构或许会很痛苦,但最终会更加正确。 - Thomas
55
在家谱图中,不应该为不太可能发生的事情添加断言,只有不可能的事情才需要添加。循环是显然不可能的事情,没有人能通过任何方式成为自己的祖先。这些其他的主张都是虚假的,应该被删除。 - pgod
44
在宠物饲养领域,这不是一个愚蠢的问题。祖孙、父女、母子、兄妹之间的亲戚关系是常规技术,宠物饲养者也需要家谱软件。所谓“纯种”真是胡说八道。 - kaleissin
31
在维多利亚时期的英国,表兄妹间结婚非常普遍,尤其是在上层社会中(这是保持财富在家族内部的绝佳方式)。例如,查尔斯·达尔文就和他的表姐艾玛·韦奇伍德结婚了。任何家谱软件都需要支持这种情况。 - rtperson
显示剩余11条评论
18个回答

20

除了可能存在的法律影响之外,显然您需要将家谱上的“节点”视为前任人物,而不是假设该节点可以是唯一的人物。

让家谱节点包括一个人以及他们的后代,然后您可以在树的深处再添加另一个节点,其中包含相同的人但具有不同的后代。


13
一些回答展示了如何保持断言/不变量,但这似乎是滥用了断言/不变量。断言用于确保本应为真的内容确实为真,而不变量用于确保不应改变的内容没有发生改变。
在此你所断言的是乱伦关系不存在。显然,它们是存在的,因此你的断言无效。你可以绕过此断言,但真正的错误在于断言本身。应该删除该断言。

8

你的家谱应该使用有向关系。这样就不会出现循环了。


5

家谱数据是循环的,不适合于非循环图,因此如果您有反对循环的断言,则应将其删除。

在不创建自定义视图的情况下处理此问题的方法是将循环父级视为“虚拟”父级。换句话说,当一个人既是某人的父亲又是祖父时,祖父节点会正常显示,而父亲节点则呈现为具有简单标签(如“见祖父”)的“虚拟”节点,并指向祖父。

为了进行计算,您可能需要改进逻辑以处理循环图,这样如果有循环,则不会访问节点超过一次。


4

断言无法经受现实的考验

通常情况下,断言很难经受住与真实世界数据的接触。在软件工程的过程中,决定要处理哪些数据以及哪些数据超出范围是其中的一部分。

循环家族图

关于家庭“树”(实际上是包括循环在内的完全图),有一个有趣的轶事:

我娶了一位寡妇,她有一个成年女儿。我父亲经常来看我们,爱上了我的继女并娶了她。结果,我的父亲成了我的儿子,我的女儿成了我的母亲。一段时间后,我给我的妻子生了一个儿子,他是我父亲和我的叔叔。我的父亲的妻子(也是我的女儿和我的母亲)生了一个儿子。因此,我在同一个人身上得到了兄弟和孙子。我的妻子现在是我的祖母,因为她是我母亲的母亲。换句话说,我是我的妻子的丈夫,同时也是我的妻子的继孙子。换句话说,我是自己的祖父。

当你考虑到代孕或“模糊父亲身份”时,事情变得更加奇怪。
如何处理这种情况:
1. 将循环定义为超出范围
您可以决定您的软件不处理这种罕见情况。如果出现这种情况,用户应使用其他产品。这使得处理更常见的情况更加健壮,因为您可以保留更多的断言和更简单的数据模型。
在这种情况下,向您的软件添加一些良好的导入和导出功能,以便用户在必要时可以轻松迁移到其他产品。
2. 允许手动关系
您可以允许用户添加手动关系。这些关系不是“一等公民”,即软件按原样采用它们,不检查它们并且不在主数据模型中处理它们。
然后,用户可以手动处理罕见情况。您的数据模型仍将保持相当简单,并且您的断言将幸存。
请小心手动关系。有一种诱惑是使它们完全可配置,从而创建一个完全可配置的数据模型。这是行不通的:你的软件将无法扩展,你会遇到奇怪的错误,最后用户界面将变得难以使用。这种反模式被称为 "软编码", "The daily WTF" 上有很多例子。
使您的数据模型更灵活,跳过断言,测试不变量是最后的选择。您必须跳过几乎所有断言,并基于完整的图形构建您的数据模型。正如上面的示例所示,很容易成为自己的祖父母,因此甚至可以有循环。
在这种情况下,您应该广泛测试您的软件。您必须跳过几乎所有断言,因此可能会出现其他错误的机会。
使用测试数据生成器来检查不寻常的测试用例。HaskellErlangC都有快速检查库。对于Java/Scala,有ScalaCheckNyaya。一个测试想法是模拟一个随机人口,让它随机交配,然后让你的软件先导入,然后再导出结果。期望是,输出中的所有连接也在输入中,反之亦然。
保持属性不变的情况称为不变量。在这种情况下,不变量是模拟人口中个体之间的“浪漫关系”集。尝试找到尽可能多的不变量,并使用随机生成的数据进行测试。不变量可以是功能性的,例如:
  • 即使你增加更多的“浪漫关系”,叔叔仍然是叔叔
  • 每个孩子都有父母
  • 有两代人的人口至少有一个祖父母

或者它们可以是技术性的:

  • 您的软件在多达10亿成员的图表上不会崩溃(无论有多少互连)
  • 您的软件具有O(节点数)和O(边数^2)的可扩展性
  • 您的软件可以保存和重新加载多达10亿成员的每个家庭图表

通过运行模拟测试,您将发现许多奇怪的角落案例。修复它们需要很长时间。此外,您会失去很多优化,您的软件将运行得更慢。您必须决定是否值得,并且是否属于您的软件范围。


4
最重要的事情是要避免创建问题,因此我认为您应该使用直接关系以避免出现循环。
正如@markmywords所说,#include "fritzl.h"
最后我必须说重新检查您的数据结构。也许有些地方出了问题(也许双向链表可以解决您的问题)。

3

不要移除所有断言,仍然应检查诸如一个人是他/她自己的父母或其他不可能的情况,并呈现出错误。如果不太可能,可以发出警告,以便用户仍然可以检测常见的输入错误,但如果一切正确,它将正常工作。

我会将数据存储在向量中,每个人都有一个永久的整数,将父母和孩子存储在个人对象中,其中该 int 是向量的索引。这将很快地在各个世代之间转换(但对于诸如名称搜索之类的事情则较慢)。这些对象将按创建时间顺序排列。


-3

复制父级 (或使用符号链接 / 引用)。

例如,如果您正在使用分层数据库:

$ #each person node has two nodes representing its parents.
$ mkdir Family
$ mkdir Family/Son
$ mkdir Family/Son/Daughter
$ mkdir Family/Son/Father
$ mkdir Family/Son/Daughter/Father
$ ln -s Family/Son/Daughter/Father Family/Son/Father
$ mkdir Family/Son/Daughter/Wife
$ tree Family
Family
└── Son
    ├── Daughter
    │   ├── Father
    │   └── Wife
    └── Father -> Family/Son/Daughter/Father

4 directories, 1 file

3
“ln -s” 命令不是这样工作的;链接“Family/Son/Father”的解析将从链接所在的“Family/Son”下寻找“Family/Son/Daughter/Father”,而不是从您发出“ln -s”命令的“.”目录中寻找。 - musiphil
48
《日内瓦公约》禁止克隆。 - MikeIsrael

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接