我是一些家谱软件(用C++和Qt编写)的开发人员。直到我的一位客户给我邮寄了一份错误报告,我才发现问题。问题是,客户有两个孩子和自己的女儿,因此,由于错误,他无法使用我的软件。

这些错误是我对正在处理的族图的各种断言和不变量的结果(例如,在走完一个循环后,程序声明X不能既是Y的父亲又是Y的祖父)。

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


当前回答

所以,我在家谱软件上做了一些工作。我认为你要解决的问题是你需要能够在树上行走而不陷入无限循环——换句话说,树需要是非循环的。

然而,你似乎在断言一个人和他们的祖先之间只有一条路。这将保证没有周期,但过于严格。从生物学上讲,后代是一个有向无环图(DAG)。你的情况当然是一个退化的情况,但这种情况在更大的树上总是发生。

例如,如果你看看你在第n代的祖先,如果没有重叠,那么你在公元1000年的祖先会比活着的人多。所以,必须有重叠。

然而,您也会得到无效的循环,只是坏数据。如果您正在遍历树,那么必须处理循环。您可以在每个单独的算法中或在加载时执行此操作。我是负重做的。

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

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

还需要注意的是,您不需要实际切断链接,只需将其从正常链接更改为“弱”链接,而某些算法不会遵循该链接。在选择将哪个链接标记为弱链接时,您也需要小心;有时,你可以通过查看出生日期信息来找出应该打破这个周期的地方,但通常你什么都搞不清楚,因为缺少了太多数据。

其他回答

这就是为什么像“Go”这样的语言没有断言的原因之一。它们被用来处理那些你可能没有想到的案例,所有这些都太频繁了。你只应该断言不可能,而不仅仅是不可能。做后者会给断言带来坏名声。每次你输入assert(,走开十分钟,认真思考一下。

在你特别令人不安的案例中,在罕见但可能的情况下,这样的断言是假的,这是可以想象的,也是令人震惊的。因此,在你的应用程序中处理它,如果只是说“这个软件不是为处理你所呈现的场景而设计的”。

断言你的曾、曾、曾祖父是你的父亲是不可能的,这是合理的做法。

如果我是为一家被雇佣来测试你的软件的测试公司工作的话,我当然会提出这种情况。为什么?每一个年轻而聪明的“用户”都会做同样的事情,并对由此产生的“错误报告”津津乐道。

你应该把Atreides家族(现代的Dune,或古代的Oedipus Rex)作为一个测试案例。通过使用经过净化的数据作为测试用例,您不会发现错误。

你应该关注真正为你的软件创造价值的东西。为一个消费者提供服务所花费的时间是否值得许可证的价格?可能不会。

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

对一个愚蠢问题的另一个假装严肃的回答:

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

即使我们想忽略这里所讨论的当地禁忌关系,也有很多完全合法和完全意想不到的方法将循环引入家谱。

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

基本上,近亲结婚不仅是普遍的和意料之中的,也是人类从数千个小家庭群体发展到全球60亿人口的原因。它不能以任何其他方式工作。

在家谱、家族和血统方面,真的很少有普遍性。几乎任何关于姨妈可以是谁,谁可以嫁给谁,或者孩子如何合法继承的规范的严格假设,都可能被世界或历史上的某个地方的某些例外所打乱。

最重要的是避免产生问题,所以我认为你应该使用直接关系来避免循环。

正如@markmywords所说,#包括“fritzl.h”。

最后,我不得不说重新检查您的数据结构。也许那边出了问题(也许双向链接列表解决了您的问题)。