家谱软件中的循环问题

Question

家谱软件中的循环问题

c++graphcycleassertionsfamily-tree

1590

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

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

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

- Partick Höse

220

你应该在创作软件时，将雷·史蒂文斯的歌曲放在心中。 - Peter K.

30

如果你追溯家族谱系足够久，你会发现这个问题比你想象中要频繁。放弃使用树形结构或许会很痛苦，但最终会更加正确。 - Thomas

55

在家谱图中，不应该为不太可能发生的事情添加断言，只有不可能的事情才需要添加。循环是显然不可能的事情，没有人能通过任何方式成为自己的祖先。这些其他的主张都是虚假的，应该被删除。 - pgod

44

在宠物饲养领域，这不是一个愚蠢的问题。祖孙、父女、母子、兄妹之间的亲戚关系是常规技术，宠物饲养者也需要家谱软件。所谓“纯种”真是胡说八道。 - kaleissin

31

在维多利亚时期的英国，表兄妹间结婚非常普遍，尤其是在上层社会中（这是保持财富在家族内部的绝佳方式）。例如，查尔斯·达尔文就和他的表姐艾玛·韦奇伍德结婚了。任何家谱软件都需要支持这种情况。 - rtperson

显示剩余11条评论

18个回答

563

放宽你的断言。

不是通过改变规则，这些规则对于99.9%的客户在捕捉输入数据错误方面非常有用。

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

- Ben Voigt

143

当遇到一个非常不可能的情况，也就是说，用户通常只会犯错误时，向用户显示警告是个好主意。那是良好的反馈。但是如果用户真正确定他们想要继续，就让用户继续。所以我认为这是一个好答案，即使它没有涉及具体实现细节。 - thomasrutter

15

好的回答！我只是想知道，这种软件如何处理“我是自己的爷爷”（http://www.youtube.com/watch?v=eYlJH81dSiw）这种情况？ - Zaur Nasibov

4

这不是一个真正的答案，因为我认为问题实际上来自于遍历树？但这是一个很好的建议。 - bdwakefield

3

这个问题是“如何解决这些错误，而不需要删除所有数据断言？” 我相信我已经回答了这个问题。 - Ben Voigt

2

@Ben 这取决于断言的目的。如果它们防止出现无限循环或致命错误，那么您实际上建议删除这些断言。如果它们只是为了警告用户潜在的错误，则您的答案是正确的。 - rm999

显示剩余2条评论

224

家谱的问题在于：它们不是树。它们是有向无环图，或者称为 DAG。如果我正确理解了人类繁殖生物学的原理，就不会出现循环。

据我所知，即使基督教徒也接受表兄妹之间的婚姻（和后代），这将使家族谱变成一个家族 DAG。

寓意是：选择合适的数据结构。

- exDM69

7

为了进行离体和性繁殖，需要进一步限制每个节点最多只能有1或2个节点指向它。为了更贴近实际情况，可能允许在父亲方面存在多条虚线表示不确定的后代（母亲总是清楚的，但只有DNA测试可以确保父亲身份，即使是今天也很少进行测试），或者如果考虑到收养，则两者都可以使用。 - manixrock

7

@manixrock - 由于这个问题涉及到罕见情况，我想强调并非总是清楚谁是母亲。收养、遗弃婴儿、代孕母亲等都会使事情更加复杂。 - Peter Recore

9

它不一定是无环的，对吧？男人娶祖母。 - Ed Ropple

13

男人娶自己的祖母并不会使他成为自己的祖父，也不会增加循环。如果他们有孩子，那么这将是一个非循环的普通图边缘。 - exDM69

11

实际上有两个 ADG。一个是亲属关系图，另一个是法律关系图。通常相同，但偏离程度可能超出人们的预期。 - JSacksteder

显示剩余2条评论

115

我猜您有一些唯一识别人物的价值信息可以作为验证依据。

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

假设这样： A 和他自己的女儿生了孩子。

A 以 A 和 B 的身份添加到程序中。在父亲的角色中，我们称之为男朋友。

添加一个 is_same_for_out() 函数，告诉您的程序输出生成部分，所有指向内部的链接从 B 应该改为在数据呈现时指向 A。

这会给用户带来额外的工作量，但我认为实现和维护都相对容易。

在此基础上，您可以通过编写代码同步更新 A 和 B 来避免不一致性。

这个解决方案肯定不完美，但是这是初步的尝试。

- Eduard Thamm

9

可能这样的“代理”节点确实是一个合适的解决方案。但我不知道如何在不冒犯用户的情况下将它们放入用户界面。我可以告诉你，编写处理真实人员（尤其是你的客户）的软件并不容易。 - Partick Höse

6

这句话的意思是：B的新儿子将会成为他自己的叔叔。我会考虑要求全额退款！ - Bo Persson

3

然后他意识到自己也是他自己的母亲，于是招募年轻的自己进入时间机构？ - Null Set

2

数据在同一系统内的复制（和同步）是不良实践。这表明解决方案是次优的，应重新考虑。如果需要创建额外的（重复的）节点，请将其指示为代理，并将数据读取和写入委托给原始节点。 - Bert Goethals

84

你应该关注于真正为你的软件创造价值的事情。把时间花在让它适用于一个客户身上是否值得支付许可证费？很可能不是。

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

- christopheml

3

非常正确，但也要考虑其他可能存在的问题，类似那些人提出的麻烦。 - Prof. Falken

2

当然。原因是：如果这是一个非关键应用程序上的罕见边缘情况，您不需要修复或实现任何内容。如果它真的会影响到您的用户，那么解决它就有价值。 - christopheml

10

也许每个人的家族历史中都存在一些乱伦事件，如果深入挖掘家族历史，这个障碍可能会浮出水面。 - datenwolf

1

制作一些奇怪情况（如近亲王室、弗里茨尔等）的家谱树是软件的有效用途。 - Bulwersator

1

一个家谱软件如果不允许表亲堂兄妹结婚是没有用的。几乎所有的家庭都至少有一个这样的情况。这就是为什么我认为原始例子是为了效果而虚构的原因。 - Fuzzy76

79

你应该设置阿特雷德家族（包括现代版的沙丘或古代版的俄狄浦斯·雷克斯）作为一个测试案例。你不会通过使用经过处理的数据作为测试案例来发现缺陷。

- user779752

2

很遗憾，太多人首先考虑的是“可以”的数据，而不是破坏他们系统的边缘情况。 - sjas

59

这就是为什么像“Go”这样的语言没有断言的原因之一。它们通常用于处理你可能没有考虑到的情况。你只应该断言不可能的事情，而不仅仅是不太可能发生的事情。后者才是导致断言声名狼藉的原因。每次当你输入assert(时，离开十分钟并且认真考虑一下。

在你特别困扰的情况下，这样的断言在极少但可能的情况下是虚假的，这既可想而知又令人震惊。因此，如果只是为了说“这个软件没有设计来处理你提出的场景”，那么在你的应用程序中处理它。

将你曾祖父作为父亲视为不可能是合理的。

如果我在一家测试公司工作，被聘请测试你的软件，我肯定会提出那种情况。为什么？每个少年但聪明的“用户”都会做完全相同的事情并乐于看到结果的“错误报告”。

- Tim Post

5

同意“何时使用断言”的观点，但不明白它与“某些语言具有断言，Go没有”有什么关系。 - phooji

2

@Red Hue - 有时编译器会让不可能的事情变得可能。某些版本的gcc在abs()实现中认为-10 == 10。 - Tim Post

2

@Red Hue：断言的整个意义在于记录和测试应始终为真（或假）的条件。它有助于防止您（和其他人）以使得这些不可能的情况出现的方式“修复”事物，因为那样会明确地（而不是隐晦地）破坏应用程序。如果出现“不可能”的情况有正当理由，则您已经断言过多了。 - cHao

1

@cHao @Tim Post 我只是想了解为什么Go不支持断言是件好事，因为您们大多数人都认为断言很重要。 - Arlen

5

拥有断言（或类似于断言的代码）是不相关的。在像Go这样的语言中，代码可以并且将对数据结构做出假设；但它只是不能使用断言来记录和强制执行这些假设。最重要的是：该应用程序存在错误。 - Tommy McGuire

显示剩余4条评论

41

我很讨厌评论这样一个混乱的情况，但是不改变所有不变量的最简单方法是在您的图表中创建一个幽灵顶点，作为一个代理人回到乱伦父亲。

- Sean

37

所以，我已经对家谱软件进行了一些工作。我认为你试图解决的问题是需要能够在不进入无限循环的情况下遍历树-换句话说，树必须是非循环的。

然而，看起来你断言一个人和他们的祖先之间只有一条路径。这将确保没有循环，但过于严格。从生物学角度来看，后代是一个有向无环图（DAG）。你所拥有的情况肯定是退化的情况，但这种情况在更大的树上经常发生。

例如，如果你看一下第n代中有2^n个祖先，如果没有重叠，那么在公元1000年，你会拥有比当时还活着的人更多的祖先。因此，必须有重叠。

然而，你也会得到无效的循环，只是坏数据。如果你正在遍历树，则必须处理循环。你可以在每个单独的算法中或在加载时执行此操作。我是在加载时完成的。

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

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

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

- tfinniga

小心那些假设；当人们适应时，一个男性和一个女性的父母并不是必然的，或者是认为自己是父母的女同性恋者，在不久的将来，他们甚至可能真正成为女孩的生物学父母。就此而言，如果我们将多莉应用于人类，即使假设“一个人有两个明显的父母”也是错误的。 - Agrajag

1

@Agrajag，是的，这就是我在循环检测中指定“从生物学角度来看”的原因。即使从生物学上讲，也存在许多可能的问题，比如代孕母亲和人工授精。如果您还允许收养和其他非生物学方法来定义父母，则可能在树中有一个有效的真实循环 - 例如，当某人年老体弱无法照顾自己时，他们收养了他们的祖父母。对人们家庭生活进行假设总是很复杂的。但是，在编写软件时，您需要做出一些假设。 - tfinniga

36

对于一个愚蠢的问题，另一个嘲讽性的模拟回答：

真正的答案是使用适当的数据结构。人类的家谱不能完全用没有循环的纯树来表达。你应该使用某种图形。此外，在继续处理这个问题之前，与人类学家交谈，因为在试图建立家谱模型时，即使在“西方父权制一夫一妻制”的最简单情况下，也有很多类似错误的地方。

即使我们想忽略本地禁忌关系（如本文所述），也有很多完全合法且完全意想不到的方法可以将循环引入家谱中。

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

基本上，堂兄婚姻不仅普遍而且被期望，这是人类从成千上万的小家庭群体走向全球60亿人口的原因。它不能以其他方式工作。

当涉及到家谱、家庭和血统时，真正的普遍规律非常少。几乎任何关于规范的严格假设，比如谁可以成为姑妈，或者谁可以嫁给谁，或者孩子如何被合法化以便继承，都可能被世界上某个地方或历史上的某个例外所推翻。

- user437212

9

你的评论让我想到了一夫多妻制。只建模性繁殖的家谱软件可能需要为精子和卵子附加名称，但更广泛的家庭结构定义则不需要。 - Steve Kalemkiewicz

家谱软件通常允许在模型中有多个配偶。如何在视图中显示模型因所提供的“模式”而异，即使在同一程序中也是如此。 - Todd Hopkinson

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Bert Goethals · Accepted Answer

看起来您（或您所在的公司）对家谱的理解存在根本性误解。

让我澄清一下，我也在一家公司工作，该公司的产品之一就是家谱，我们一直在努力解决类似的问题。

这个问题，在我们的情况下，我认为在您的情况下也是如此，源于GEDCOM格式，这个格式非常关注一个家庭应该是什么样子。然而，这个格式包含了一些关于一个家谱真正应该长什么样的严重误解。

GEDCOM存在很多问题，例如与同性关系、乱伦等不兼容……这在现实生活中比您想象的要更加普遍（尤其是回到18世纪和19世纪时期）。

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

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

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

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