提问



我是一些家庭树软件的开发者(用C ​​++和Qt编写)。在我的一位客户向我邮寄错误报告之前,我没有遇到任何问题。问题是客户有两个子和自己的女儿,因此,他不能因为错误而使用我的软件。


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


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

最佳参考


看来你(和/或你的公司)对家谱应该是什么有一个根本的误解。


让我澄清一下,我也为一家公司(其产品之一)的产品组合中的家族树工作,我们一直在努力解决类似的问题。


在我们的案例中,问题,我也假设你的情况,来自GEDCOM格式,该格式对于一个家庭应该是什么非常自以为是。然而,这种格式包含了一些关于家谱真实情况的严重误解。[14]


GEDCOM有许多问题,例如与同性关系,乱伦等不相容......在现实生活中发生的事情比你想象的更频繁(尤其是回到1700-1800时)。


我们已经将我们的家谱模型化为现实世界中发生的事件:事件(例如,出生,婚礼,订婚,工会,死亡,收养等)。我们对这些没有任何限制,除了逻辑上不可能的(例如,一个人不能成为自己的父,关系需要两个人等等)


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


至于这个具体的情况,我建议删除断言,因为它们并不普遍。


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

其它参考1


放松你的断言。


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


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

其它参考2


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


据我所知,即使是基督徒也接受堂兄弟之间的婚姻(以及子女),这会将家谱变成家庭DAG。


故事的寓意是:选择正确的数据结构。

其它参考3


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


这是一个棘手的问题。假设你想保持结构树,我建议:


假设:A有自己女儿的子。


A将自己作为AB添加到程序中。曾经担任过父亲的角色,让我们称之为男朋友。


添加is_same_for_out()函数,该函数告诉程序的输出生成部分,在内部进行B的所有链接都应该在数据表示时转到A


这将为用户做一些额外的工作,但我想IT的实施和维护相对容易。


建立起来,您可以使用代码同步AB来避免不一致。


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

其它参考4


您应该专注于真正为您的软件创造价值的东西。花在为一个消费者工作的时间是否值得许可证的价格?可能不是。


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

其它参考5


您应该将Atreides系列(现代, Dune 或古代, Oedipus Rex )设置为测试用例。使用经过消毒的数据作为测试用例,你不会发现错误。[15] [16]

其它参考6


这就是为什么像Go这样的语言没有断言的原因之一。他们习惯于处理你可能没想过的案例,而且经常会这样。你应该只断言不可能的事情,而不仅仅是不可能的事情。。做后者是断言声誉不好的原因。你键入assert(的时间,走开十分钟,真的想一想。


在你特别令人不安的情况下,这种说法在罕见但可能的情况下是虚假的,这是可以想象的,也是令人震惊的。因此,在您的应用程序中处理它,如果只是说此软件不是为处理您提供的场景而设计的。


断言你伟大的,伟大的,曾祖父是你父亲的不可能是合理的事情。


如果我为一家受雇来测试你的软件的测试公司工作,我当然会提出这种情况。为什么?每个少年但聪明的用户都会做完全相同的事情,并在最终的错误报告中津津乐道。

其它参考7


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

其它参考8


所以,我已经在家庭树软件上做了一些工作。我认为你要解决的问题是你需要能够在没有无限循环的情况下走树 - 换句话说,树需要是非周期性的。


然而,看起来你断言一个人和他们的祖先之间只有一条路径。这将保证没有周期,但是过于严格。从生物学角度讲,下降是有向无环图(DAG)你所拥有的案件肯定是一个堕落的案例,但这种事情一直在大树上发生。[17]


例如,如果你看一下n代的2 ^ n个祖先,如果没有重叠,那么你在1000个AD中的祖先比活着的人多。所以,必须重叠。


但是,您也倾向于获得无效的循环,只是错误的数据。如果您遍历树,则必须处理循环。您可以在每个单独的算法中或在加载时执行此操作。我在加载时执行此操作。


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


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


另请注意,您不需要实际切断链接,只需将其从普通链接更改为弱链接,而不是某些算法。在选择标记为弱的链接时,您还需要注意;有时你可以通过查看出生日期信息来确定周期应该被打破的地方,但通常你无法找出任何东西,因为缺少了太多的数据。

其它参考9


对于一个愚蠢的问题,另一个模拟严肃


真正的答案是,使用适当的数据结构。使用没有循环的纯树无法完全表达人类谱系。你应该使用某种图形。此外,在进一步讨论此事之前,先与人类学家交谈,因为即使在最简单的西方父权制一夫一妻婚姻案例中,也有许多其他地方可以尝试对家谱进行模拟。


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


例如:http://en.wikipedia.org/wiki/Cousin_marriage [18]


基本上,堂兄婚姻不仅是普遍的和预期的,而且是人类从数千个小家庭群体变成全球60亿人口的原因。它不能以任何其他方式工作。


在家谱,家庭和血统方面,真的很少有普遍性。几乎所有关于规范的严格假设都暗示着阿姨可以成为谁,或者谁可以嫁给谁,或者如何将子合法化为继承目的,可能会被世界或历史上的某个例外所困扰。

其它参考10


除了潜在的法律含义之外,您肯定需要将家族树上的节点视为前任人,而不是假设该节点可以是唯一的人。


让树节点包括一个人以及后继者 - 然后您可以在树的下方有另一个节点,其中包含具有不同后继者的同一个人。

其它参考11


一些答案已经显示了保持断言/不变量的方法,但这似乎是对断言/不变量的误用。断言是为了确保应该是真实的东西,并且不变量是为了确保不应该改变的东西不会改变。


你在这里断言的是乱伦的关系不存在。显然他们做存在,所以你的断言是无效的。你可以解决这个断言,但真正的错误在于断言本身。断言应该被删除。

其它参考12


你的家谱应该使用直接关系。这样你就不会有一个循环。

其它参考13


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


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


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

其它参考14


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


正如@markmywords所说, #includefritzl.h。


最后我要说recheck your data structure。也许在那里出现问题(也许双向链表解决了你的问题)。

其它参考15


断言不能在现实中生存



通常断言不会在与现实世界数据的接触中存活下来。它是软件工程过程的一部分,决定了您想要处理哪些数据以及哪些数据超出范围。


循环族图



关于家庭树(实际上它是完整的图表,包括周期),有一个很好的轶事:



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



当你考虑到代理人或模糊的父亲时,事情变得更加奇怪。 [19]


如何处理



将周期定义为超出范围



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


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


允许手动关系



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


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


小心手动关系。有一种诱惑使它们完全可配置,因此创建了一个完全可配置的数据模型。这不起作用:您的软件无法扩展,您将获得奇怪的错误,最后用户界面将变得无法使用。这种反模式被称为软编码,而每日WTF则充满了这样的例子。[20] [21]


使您的数据模型更加灵活,跳过断言,测试不变量



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


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


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


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



  • 即使你增加了更多的浪漫关系,叔叔也会留下叔叔。

  • 每个子都有父

  • 两代人口中至少有一个祖父



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



  • 您的软件不会在最多100亿成员的图表上崩溃(无论有多少互连)

  • 您的软件按O(节点数)和O(边数= 2)进行扩展

  • 您的软件可以保存并重新加载每个家庭图表,最多可达100亿会员



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

其它参考16


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


我会将数据存储在一个带有每个人的永久整数的向量中,并将父对象和子对象存储在人对象中,其中所述int是向量的索引。这种情况在几代人之间相当快(但对于名字搜索这样的事情来说很慢)。对象将按照创建时的顺序排列。

其它参考17


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


例如,如果您使用的是分层数据库:


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