题 家谱软件中的循环


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

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

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


1594
2018-05-28 18:39


起源


听起来你应该将软件的销售限制在那些避免陷入棘手的家庭状况的人身上!如何与自己的女儿生孩子 - 我希望你在谈论他的儿媳! - Will A
显然,你应该记录Ray Stevens的歌曲。 - Peter K.
这可能是您需要问自己的情况之一: 我真的想和那个人做生意吗?  另一种解决方案是对他提出刑事指控。毕竟,乱伦在世界大部分地区是被禁止的。最后,你的软件无论如何都会被打破,因为你可以(在法律上)在家谱中有周期:堂兄弟可以在大多数(所有?)西方国家结婚。 - sbi
你不应该为不太可能的事情添加断言,只是不可能的事情。循环是家族树图中不可能的明显事物......没有人可以通过任何方法成为他自己的祖先。这些其他断言只是假的,应该删除。 - pgod
也许下次你会尝试一个更抽象的例子。这里的人不能忽视乱伦部分,只是关闭它,即使它是关于树状数据表示的有效问题。 - stesch


答案:


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

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

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

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

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

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

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

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


727
2018-06-01 08:25



这看起来是正确的方法,并且很容易扩展以检测更复杂的问题。你可以在事件之间找出一组“A之前发生过的事情”。例如,一个人在涉及他们的任何其他事件之前出生。这是一个有向图。然后,您可以检查图表是否包含循环。 在StackOverflow上查看此问题。  这应该是好的,直到时间旅行发明。 - Paul Harrison
@ paul-harrison如果只是那么简单。在旧记录(甚至是新记录)中,存在日期不一致。出生前的洗礼,多次出生记录等......所以在某种程度上,在官方记录中,有时间旅行。我们允许这种不一致的数据。我们允许用户在重复的情况下指出应用程序应该考虑“出生记录”。如果找到,我们将指出破碎的时间表。 - Bert Goethals
@ ben-voigt GEDCOM是由耶稣基督后期圣徒教会创建的一种格式。该规范明确规定婚姻(MARR)应介于男女之间。对于同性婚姻或乱伦,应使用ASSO标签(ASSOCIATES),也用于表示友谊或是邻居。很明显,同性婚姻是本规范中的二等关系。一个更中性的规范不会要求男性女性关系。 - Bert Goethals
@Bert Goethals:你让GEDCOM对某些不支持同性婚姻的节目感到困惑(PAF,Legacy)。 GEDCOM并不排除诸如“0 @ F1 @ FAM / 1 HUSB @ I1 @ / 1 HUSB @ I2 @”之类的结构,因此如果您的软件选择支持,则支持同性婚姻。 - Pierre
@Pierre你可以欺骗系统。这直接来自5.5.1文档:“MARR {MARRIAGE}:=一个法律,普通法或习惯性的事件,即创建一个男人和一个女人的家庭单位作为丈夫和妻子。” (homepages.rootsweb.ancestry.com/~pmcbride/gedcom/55gcappa.htm)正如你所看到的,这里没有同性婚姻。 - Bert Goethals


放松你的断言。

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

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


564
2018-05-28 19:20



遇到一个 非常不可能 情况,即用户所在的情况 平时 只做错误,向用户显示警告是个好主意。这是很好的反馈。但是,如果他们是,那么让用户继续前进 真 确定他们想要。所以我认为这是一个很好的答案,即使它没有进入如何的细节。 - thomasrutter
好答案!我只是想知道,这种软件将如何处理“我是我自己的爷爷”(youtube.com/watch?v=eYlJH81dSiw)情况? - Zaur Nasibov
这不是一个真正的答案,因为我认为问题来自实际遍历树?但是,这是一个很好的建议。 - bdwakefield
@bdwakefield:问题是“如何在不删除所有数据断言的情况下解决这些错误?”我相信我已经回答了这个问题。 - Ben Voigt
@Ben这取决于断言的用途。如果它们阻止无限循环或致命错误发生,那么您实际上建议删除断言。如果他们只是在那里警告用户潜在的错误,那么你的回答是好的。 - rm999


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

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

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


224
2018-06-01 09:58



对于体外和有性生殖,需要进一步限制每个节点具有指向它的1或2个最大节点。虽然对现实生活更加真实,但你可能会允许多条虚线表示父亲方面的不确定性下降(总是很清楚母亲是谁,但只有DNA测试可以确保父亲是谁,即使在今天也很少这样做),或者甚至两者都是采用被考虑在内。 - manixrock
@manixrock - 因为这个问题是关于罕见的情况,我想断言并不总是清楚母亲是谁。收养,遗弃的婴儿,代孕妈妈等都可能使问题复杂化。 - Peter Recore
它不一定是非循环的,是吗?曼结婚祖母。 - Ed Ropple
男人嫁给他的祖母不会让自己成为自己的祖父并增加一个周期。如果他们有孩子,那将是一个非循环的常规图形边缘。 - exDM69
它实际上是两个ADG。有父母图和法律关系图。通常是相同的,但不止一个人可能会发生分歧。 - JSacksteder


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

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

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

A 将自己加入到该计划中 A 并作为 B。一旦担任父亲的角色,让我们称之为男朋友。

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

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

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

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


115
2018-05-28 18:50



可能这种“代理”节点确实是合适的解决方案。但是我不知道如何在不冒犯用户的情况下将这些放在用户界面中。我可以告诉你,编写处理真人(特别是你的客户)的软件并不容易。 - Partick Höse
它永远不会结束 - B的新儿子将是他自己的叔叔。我会考虑全额退款! - Bo Persson
Jup这是一种搞砸的情况。在C ++中可以使用内联序列吗? - Eduard Thamm
@Will A:然后意识到他也是他自己的母亲,并将他年轻的自己招募到时间机构? - Null Set
在一个系统内复制(和同步)数据是不好的做法。它表明该解决方案是次优的,应该重新考虑。如果需要创建额外(重复)节点,请将其指定为代理并将数据读写和写入委托给原始节点。 - Bert Goethals


你应该专注于 什么才能真正为您的软件带来价值。花在为一个消费者工作的时间是否值得许可证的价格?可能不是。

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


84
2018-06-01 08:51



非常真实。但也要考虑其他潜在的问题以及其他人带来的类似问题。 - Prof. Falken
当然。原因是:如果它是非关键应用程序的罕见边缘情况,则不需要修复或实现任何操作。如果它真的伤害了你的用户,那么就有价值。 - christopheml
可能每个人都有一些在他/她的祖先某处乱伦的情况。所以,如果有人挖掘家族历史(太深),你就会遇到这种情况。 - datenwolf
制作一些奇怪情况的家谱树(inbreed皇室,Fritzl等)是软件的有效使用。 - Bulwersator
一个不允许第二代堂兄结婚的家庭树软件是没用的。几乎所有家庭至少有一例。这就是为什么我认为最初的例子是为了效果。 - Fuzzy76


你应该设置 阿特雷德 家庭(现代, 沙丘或者古老的, 俄狄浦斯雷克斯)作为测试案例。通过使用已清理的数据作为测试用例,您不会发现错误。


79
2018-06-01 16:10



可悲的是,有太多人首先想到的是'ok'数据而不是破坏他们系统的边缘情况。 - sjas


这就是为什么像“Go”这样的语言没有断言的原因之一。他们习惯于处理你可能没想过的案例。 你应该只断言不可能的,而不仅仅是不可能的。做后者是断言声誉不好的原因。每次打字 assert(,走开十分钟  想一想。

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

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

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


59
2018-06-01 06:10



别忘了冷冻精子...... - Prof. Falken
同意“何时使用断言”的论点;看不出它与“某些语言有断言有什么关系,Go没有。” - phooji
@Red Hue - 有时编译器会让不可能的......变得可能。某些版本的gcc在abs()实现中认为-10 == 10。 - Tim Post♦
@Red Hue:断言的全部内容是记录和测试应该始终为真(或错误)的条件。它有助于让你(和其他人)以某种方式“修复”这些不可能的情况,因为他们明确地(而不是巧妙地)打破了应用程序。如果有一个“不可能”的案例出现的正当理由,那么你已经断言了太多。 - cHao
断言(或类似断言的代码)是无关紧要的。像Go这样的语言代码可以并且将对数据结构做出假设;它只是不能用断言记录和执行这些假设。底线:应用程序有一个bug。 - Tommy McGuire


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


41
2018-05-28 18:55





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

然而,看起来你断言一个人和他们的祖先之间只有一条路。这将保证没有周期,但是太严格了。从生物学角度讲,后代是一种 有向无环图(DAG)。你拥有的案例当然是一个堕落的案例,但这种事情一直在大树上发生。

例如,如果你看一下n代的2 ^ n个祖先,如果没有重叠,那么你在公元1000年就会有更多的祖先活着。所以,必须有重叠。

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

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

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

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


37
2018-06-01 18:39



小心这些假设;一个男性和一个女性父母在人们适应时不是给定的,或者认为自己是父母的莱斯班人,在不久的将来他们甚至可能真的能够 是 在生物学上,父母,至少是女孩。就此而言,如果我们将小车应用于人类,即使是“一个人有两个不同的父母”的假设也是如此。 - Agrajag
@Agrajag,是的,这就是我为循环检测指定“生物学上说”的原因。即使在生物学上,也存在许多可能的问题,例如代孕母亲和人工授精。如果你也允许采用其他非生物学方法来定义父母,那么就有可能在树中有一个有效的真实周期 - 例如,也许有人在他们变老并且不再能够照顾自己时采用他们的祖父母。对人们的家庭生活做出假设总是很复杂。但是在编写软件时,你需要做出一些假设。 - tfinniga