家谱软件中的循环

Question

我是一些家谱软件（用 C++ 和 Qt 编写）的开发人员。在我的一位客户向我邮寄错误报告之前，我没有遇到任何问题。问题是，客户有两个孩子，还有他们自己的女儿，因此，他因为错误而无法使用我的软件。

这些错误是我对正在处理的家庭图的各种断言和不变量的结果（例如，在走了一个周期后，程序指出 X 不能既是 Y 的父亲又是祖父）。

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

Answer 1

看来您（和/或您的公司）对家谱应该是什么有一个根本性的误解。

让我澄清一下，我也为一家公司工作，该公司的产品组合中有一个家谱（作为其产品之一），我们一直在努力解决类似的问题。

在我们的例子中，我假设你的例子也是如此，问题来自 GEDCOM 格式对于家庭应该是什么样子有着非常固执的看法。然而，这种格式对于家谱的真实面貌存在一些严重的误解。

GEDCOM 存在许多问题，例如同性关系不兼容、乱伦等……这在现实生活中发生的频率比您想象的要高（特别是当时间回到 1700-1800 年时）。

我们将家谱建模为现实世界中发生的事件：事件（例如出生、婚礼、订婚、结合、死亡、收养等）。我们不对这些施加任何限制，除了逻辑上不可能的限制（例如，一个人不能是自己的父母，关系需要两个人，等等......）

缺乏验证给了我们一个更“真实的世界”，更简单、更灵活的解决方案。

对于这个具体案例，我建议删除这些断言，因为它们并不普遍成立。

为了显示问题（将会出现），我建议根据需要多次绘制相同的节点，通过在选择其中一个副本时点亮所有副本来暗示重复。

Answer 2

放松你的断言。

不是通过更改规则，这很可能对 99.9% 的客户发现输入数据时的错误非常有帮助。

相反，将其从错误“无法添加关系”更改为带有“无论如何添加”的警告。

Answer 3

这是家谱的问题：它们不是树。它们是有向无环图或 DAG。如果我正确理解了人类生殖的生物学原理，就不会有任何循环。

据我所知，即使是基督徒也接受表兄弟之间的婚姻（因此也接受孩子），这会将家谱变成家庭 DAG。

这个故事的寓意是：选择正确的数据结构。

Answer 4

我猜你有一些值可以唯一地识别一个人，你可以根据这个值进行检查。

这是一个棘手的问题。假设您想保持结构为树，我建议这样做：

假设：A 有自己的女儿和孩子。

A 将自己作为 A 和 B 添加到程序中。一旦扮演了父亲的角色，我们就称其为男朋友吧。

添加一个 is_same_for_out() 函数，它告诉程序的输出生成部分，所有在内部转到 B 的链接都应该在演示时转到 A的数据。

这会给用户带来一些额外的工作，但我想 IT 会相对容易实施和维护。

在此基础上，您可以对 A 和 B 进行代码同步，以避免不一致。

这个解决方案当然并不完美，但它是第一种方法。

Answer 5

您应该关注真正为您的软件带来价值的因素。使其为一名消费者工作所花费的时间值得许可证的价格吗？可能不会。

我建议您向该客户道歉，告诉他他的情况超出了您的软件的范围，并向他退款。

Answer 6

您应该已经设置了 Atreides 系列（现代的，沙丘，或古代俄狄浦斯王）作为测试用例。使用清理后的数据作为测试用例不会发现错误。

Answer 7

这就是像“Go”这样的语言没有断言的原因之一。它们常常用来处理您可能没有想到的情况。 你应该只断言不可能的事情，而不仅仅是不可能的事情。后者会给断言带来坏名声。每次你输入 assert(，走开十分钟，真正思考一下。

在你特别令人不安的情况下，这样的断言是可以想象的，也是令人震惊的因此，在你的应用程序中处理它，如果只是说“这个软件不是为了处理你提出的场景”而

断言你的曾曾祖父是你的父亲是不可能的 。

。如果我在一家受雇测试您的软件的测试公司工作，我当然会提出这种情况，为什么每个年轻但聪明的“用户”都会做同样的事情 并享受由此产生的“错误报告”。

Answer 8

我讨厌评论这种搞砸的情况，但不重新调整所有不变量的最简单方法是在图表中创建一个虚拟顶点，充当乱伦父亲的代理。

Answer 9

因此，我在家谱软件方面做了一些工作。我认为你想要解决的问题是你需要能够在不陷入无限循环的情况下遍历树 - 换句话说，树需要是非循环的。

然而，您似乎断言一个人与其祖先之一之间只有一条路径。这将保证没有循环，但过于严格。从生物学上来说，后代是一个有向无环图 (DAG)。你遇到的情况肯定是一个退化的情况，但这种情况在较大的树上经常发生。

例如，如果您查看第 n 代的 2^n 个祖先，如果没有重叠，那么您在公元 1000 年拥有的祖先比活着的人还要多。所以，一定有重叠。

然而，您也往往会得到无效的周期，只是错误的数据。如果要遍历树，则必须处理循环。您可以在每个单独的算法中或在加载时执行此操作。我是在负载上做的。

可以通过多种方式找到树中的真实循环。错误的方法是标记给定个体的每个祖先，并且在遍历时，如果您要进入的下一个人已经被标记，则切断链接。这将切断潜在的准确关系。正确的方法是从每个个体开始，并用通往该个体的路径标记每个祖先。如果新路径包含当前路径作为子路径，那么它是一个循环，应该被打破。您可以将路径存储为矢量（MFMF、MFFFMF 等）这使得比较和存储非常快。

还有其他一些方法可以检测循环，例如发送两个迭代器并查看它们是否与子集测试发生冲突，但我最终使用了本地存储方法。

另请注意，您不需要实际切断链接，您只需将其从正常链接更改为“弱”链接，某些算法不会遵循该链接。在选择将哪个链接标记为弱链接时，您还需要小心；有时，您可以通过查看出生日期信息来找出应该在哪里打破循环，但通常您无法找出任何信息，因为丢失了太多数据。

Answer 10

对于一个愚蠢问题的另一个模拟严肃答案：

真正的答案是，使用适当的数据结构。人类的谱系不能用没有循环的纯树来完全表达。您应该使用某种图表。另外，在进一步讨论之前，请先咨询一下人类学家，因为在尝试建立家谱模型时，还有很多其他地方可能会犯类似的错误，即使是在最简单的“西方父权制一夫一妻制婚姻”的情况下。

即使我们想忽略此处讨论的当地禁忌关系，也有很多完全合法且完全出乎意料的方法可以将循环引入家谱中。

例如： http://en.wikipedia.org/wiki/Cousin_marriage

基本上，表兄弟婚姻是这不仅是普遍现象和预期，也是人类从数千个小家庭群体发展到全球 60 亿人口的原因。它不能以任何其他方式工作。

当涉及到家谱、家庭和血统时，确实很少有共性。几乎任何关于姨妈可以是谁、谁可以嫁给谁、或者孩子如何为了继承而合法化的规范的严格假设，都可能会因世界或历史上某个地方的某些例外而被推翻。

Answer 11

除了潜在的法律影响之外，您似乎确实需要将家谱上的“节点”视为前辈，而不是假设该节点可以是唯一的人。

让树节点包含一个人和后继者 - 然后您可以在树的更深处拥有另一个节点，其中包含同一个人和不同的后继者。

Answer 12

一些答案已经展示了保留断言/不变量的方法，但这似乎是对断言/不变量的滥用。断言是为了确保应该为真的东西是真的，不变量是为了确保不应该改变的东西不会改变。

你在这里断言的是乱伦关系不存在。显然它们确实存在，所以你的断言是无效的。您可以解决此断言，但真正的错误在于断言本身。应删除该断言。

Answer 13

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

Answer 14

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

在视图中处理此问题而不创建自定义视图的方法是将循环父级视为“幽灵”父级。换句话说，当一个人既是同一个人的父亲又是祖父时，祖父节点会正常显示，但父亲节点会呈现为“幽灵”节点，具有简单的标签，如（“参见祖父”） ）并指向祖父。

为了进行计算，您可能需要改进处理循环图的逻辑，以便在存在循环时不会多次访问节点。

Answer 15

最重要的是避免产生问题，因此我认为您应该使用直接关系来避免出现循环。

正如 @markmywords 所说，#include "fritzl.h"。

最后我不得不说重新检查您的数据结构。也许那里出了问题（也许双向链表可以解决您的问题）。

Answer 16

断言无法在现实中幸存下来

通常断言在与现实世界数据接触后就无法幸存。这是软件工程过程的一部分，需要决定要处理哪些数据以及哪些数据超出范围。

循环家庭图

关于家庭“树”（实际上它是完整的图，包括循环），有一个很好的轶事：

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

当你考虑到代理人或“模糊的父亲身份”时，事情会变得更加奇怪。

如何处理这种情况

将周期定义为超出范围

您可以决定您的软件不应处理此类罕见情况。如果发生这种情况，用户应该使用不同的产品。这使得处理更常见的情况更加稳健，因为您可以保留更多断言和更简单的数据模型。

在这种情况下，请向您的软件添加一些良好的导入和导出功能，以便用户可以在必要时轻松迁移到不同的产品。

允许手动关系

您可以允许用户添加手动关系。这些关系不是“一等公民”，即软件按原样接受它们，不检查它们，也不在主数据模型中处理它们。

然后，用户可以手动处理罕见的情况。您的数据模型仍然非常简单，您的断言也将继续存在。

小心手动关系。人们很想使它们完全可配置，从而创建一个完全可配置的数据模型。这是行不通的：你的软件将无法扩展，你会遇到奇怪的错误，最后用户界面将变得无法使用。这种反模式称为“软编码”，并且"The daily WTF" 充满了这方面的例子。

让你的数据模型更加灵活，跳过断言，测试不变量

最后的手段是让你的数据模型更加灵活。您必须跳过几乎所有断言，并将数据模型建立在完整的图表上。正如上面的例子所示，你很容易成为自己的祖父，所以你甚至可以拥有自行车。

在这种情况下，您应该广泛测试您的软件。您必须跳过几乎所有断言，因此很有可能出现其他错误。

使用测试数据生成器检查异常测试用例。有 Haskell、Erlang 或 C 。对于 Java / Scala 有 ScalaCheck 和 尼亚亚。一个测试想法是模拟随机群体，让它随机杂交，然后让您的软件首先导入然后导出结果。期望的是，输出中的所有连接也在输入中，反之亦然。

属性保持不变的情况称为不变量。在这种情况下，不变量是模拟群体中个体之间的“浪漫关系”集合。尝试找到尽可能多的不变量并使用随机生成的数据对其进行测试。不变量可以是功能性的，例如：

• 即使添加更多“浪漫关系”，叔叔仍然是叔叔
• 每个孩子都有父母
• 一个两代人的人口至少有一个祖父母

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

• 您的软件不会崩溃在多达 100 亿个成员的图表上（无论有多少互连）
• 您的软件可通过 O（节点数）和 O（边数 ^ 2）进行扩展
• 您的软件可以保存并重新加载每个家庭图100亿会员

通过运行模拟测试，你会发现很多奇怪的极端情况。修复它们将花费大量时间。而且你会失去很多优化，你的软件运行速度会慢很多。您必须决定是否值得以及这是否在您的软件范围内。

Answer 17

您仍然应该检查诸如一个人是他/她自己的父母或其他不可能的情况并提出错误，而不是删除所有断言。如果不太可能，可能会发出警告，以便用户仍然可以检测到常见的输入错误，但如果一切正确，它就会起作用。

我将数据存储在一个向量中，每个人都有一个永久整数，并将父母和孩子存储在个人对象中，其中所述 int 是向量的索引。这在几代人之间进行起来会非常快（但对于姓名搜索之类的事情来说会很慢）。这些对象将按照它们创建的时间顺序排列。

Answer 18

复制父亲（或使用符号链接/引用）。

例如，如果您使用分层数据库：

$ #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