1593

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

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

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

4

18 回答 18

727

您（和/或您的公司）似乎对家谱应该是什么存在根本性的误解。

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

在我们的案例中，我也假设您的案例中的问题来自GEDCOM格式，该格式对家庭应该是什么非常固执己见。然而，这种格式包含一些关于家谱的真正样子的严重误解。

GEDCOM 有很多问题，例如与同性关系不相容、乱伦等……这在现实生活中发生的频率比你想象的要多（尤其是当时间回到 1700-1800 时）。

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

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

至于这种特定情况，我建议删除断言，因为它们并不普遍。

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

于 2011-06-01T08:25:09.467 回答
563

放松你的断言。

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

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

于 2011-05-28T19:20:12.750 回答
224

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

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

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

于 2011-06-01T09:58:15.493 回答
115

我猜你有一些价值可以唯一地识别一个你可以作为支票基础的人。

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

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

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

添加一个is_same_for_out()函数，它告诉程序的输出生成部分，所有进入B内部的链接都应该用于A数据的呈现。

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

以此为基础，您可以进行代码同步A并B避免不一致。

这个解决方案肯定不是完美的，但它是第一种方法。

于 2011-05-28T18:50:16.297 回答
84

您应该专注于真正为您的软件带来价值的东西。花在为 ONE 消费者服务上的时间是否值得购买许可证？可能不会。

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

于 2011-06-01T08:51:56.160 回答
79

您应该设置Atreides家族（现代的Dune或古代的Oedipus Rex）作为测试用例。使用经过清理的数据作为测试用例不会发现错误。

于 2011-06-01T16:10:42.817 回答
59

这就是为什么像“Go”这样的语言没有断言的原因之一。它们经常用于处理您可能没有想到的情况。你应该只断言不可能的，而不是简单的不可能的。这样做会使断言声名狼藉。每次打字assert(，走开十分钟，好好想想。

在您特别令人不安的情况下，在极少数但可能的情况下，这样的断言是虚假的，既可以想象又令人震惊。因此，请在您的应用程序中处理它，如果只是说“此软件不是为处理您呈现的场景而设计的”。

断言你的曾、曾、曾曾祖父不可能成为你的父亲是一件合理的事情。

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

于 2011-06-01T06:10:44.323 回答
41

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

于 2011-05-28T18:55:14.640 回答
37

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

但是，您似乎在断言一个人与其祖先之一之间只有一条路径。这将保证没有循环，但是太严格了。从生物学上讲，后代是有向无环图（DAG）。你的情况肯定是一个退化的情况，但这种事情总是发生在更大的树上。

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

但是，您也确实倾向于得到无效的周期，只是坏数据。如果您正在遍历树，则必须处理循环。您可以在每个单独的算法中或在加载时执行此操作。我是在加载时完成的。

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

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

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

于 2011-06-01T18:39:33.890 回答
36

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

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

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

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

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

谈到家谱，家庭和血统，确实很少有普遍性。几乎任何关于规范的严格假设都表明，谁可以成为姨妈，谁可以嫁给谁，或者孩子如何被合法化以实现继承的目的，都可能因世界或历史上的某个例外而被打破。

于 2011-06-01T14:12:54.887 回答
20

撇开潜在的法律影响不谈，您似乎需要将家谱上的“节点”视为前任人，而不是假设该节点可以是唯一的人。

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

于 2011-05-28T18:49:45.733 回答
13

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

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

于 2011-06-01T19:55:59.480 回答
8

你的家谱应该使用有向关系。这样你就没有循环了。

于 2011-06-01T12:22:18.103 回答
5

家谱数据是循环的，不适合非循环图，所以如果你有针对循环的断言，你应该删除它们。

在不创建自定义视图的情况下在视图中处理此问题的方法是将循环父级视为“幽灵”父级。换句话说，当一个人同时是同一个人的父亲和祖父时，祖父节点正常显示，但父亲节点被渲染为具有简单标签的“幽灵”节点（“见祖父” ) 并指向祖父。

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

于 2012-12-12T19:08:20.373 回答
4

最重要的是 to avoid creating a problem，所以我认为你应该使用直接关系来避免循环。

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

最后我不得不说recheck your data structure。也许那里出了问题（也许双向链表可以解决您的问题）。

于 2011-06-06T06:12:48.280 回答
4

断言无法在现实中生存

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

循环族图

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

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

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

如何处理

将周期定义为范围外

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

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

允许手动关系

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

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

小心手动关系。有一种诱惑是让它们完全可配置，从而创建一个完全可配置的数据模型。这将不起作用：您的软件将无法扩展，您会遇到奇怪的错误，最终用户界面将变得无法使用。这种反模式被称为“软编码”，“The Daily WTF”充满了这方面的例子。

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

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

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

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

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

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

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

  • 您的软件不会在多达 100 亿个成员的图表上崩溃（无论有多少互连）
  • 您的软件可按 O(node-of-nodes) 和 O(number-of-edges^2) 扩展
  • 您的软件可以保存和重新加载多达 100 亿个成员的每个家庭图

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

于 2015-01-26T14:17:42.517 回答
3

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

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

于 2011-12-02T10:19:49.353 回答
-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
于 2012-01-13T04:39:52.480 回答