Par*_*öse 1594 c++ graph cycle assertions family-tree
我是一些家庭树软件的开发者(用C ++和Qt编写).在我的一位客户向我邮寄错误报告之前,我没有遇到任何问题.问题是客户有两个孩子和自己的女儿,因此,他因错误而无法使用我的软件.
这些错误是我处理家族图的各种断言和不变量的结果(例如,在走一个循环之后,程序声明X不能同时是Y的父亲和祖父).
如何在不删除所有数据断言的情况下解决这些错误？
Ber*_*als 727
看来你(和/或你的公司)对家谱应该是什么有一个根本的误解.
让我澄清一点,我也为一家公司(其产品之一)的产品组合中的家族树工作,我们一直在努力解决类似的问题.
在我们的案例中,问题,我也假设你的情况,来自GEDCOM格式,该格式对于一个家庭应该是什么非常自以为是.然而,这种格式包含了一些关于家谱真正看起来的严重错误观念.
GEDCOM有许多问题,例如与同性关系,乱伦等不相容......在现实生活中发生的事情比你想象的更频繁(特别是在1700-1800之后回归).
我们已经将我们的家谱模型化为现实世界中发生的事件:事件(例如,出生,婚礼,订婚,工会,死亡,收养等).我们对这些没有任何限制,除了逻辑上不可能的(例如,一个不能是一个人自己的父母,关系需要两个人等等)
缺乏验证为我们提供了一个更"现实世界",更简单,更灵活的解决方案.
至于这个具体的情况,我建议删除断言,因为它们并不普遍存在.
为了显示问题(将出现),我建议根据需要多次绘制相同的节点,通过在选择其中一个副本时点亮所有副本来暗示重复.
Ben*_*igt 563
放松你的断言.
不是通过更改规则,这些规则很可能对99.9%的客户在输入数据时发现错误非常有帮助.
相反,将其从错误"无法添加关系"更改为带有"无论如何添加"的警告.
exD*_*M69 224
这是家庭树的问题:它们不是树木.它们是有向无环图或DAG.如果我正确理解人类生殖生物学的原理,就不会有任何循环.
据我所知,即使是基督徒也接受堂兄弟之间的婚姻(以及子女),这会将家谱变成家庭DAG.
故事的寓意是:选择正确的数据结构.
小智 115
我猜你有一些价值,可以唯一地识别你可以作为支票基础的人.
这是一个棘手的问题.假设你想保持结构为树,我建议:
假设这个:A有孩子和他自己的女儿.
A将自己添加到程序A中B.一旦担任父亲的角色,我们称之为男朋友.
添加一个is_same_for_out()函数,告诉程序的输出生成部分,所有B内部链接都应该在A数据表示时进行.
这将为用户做一些额外的工作,但我想IT的实施和维护相对容易.
从此开始,您可以处理代码同步A并B避免不一致.
这个解决方案肯定不是完美的,但这是第一种方法.
chr*_*eml 84
您应该专注于真正为您的软件创造价值的东西.花在为一个消费者工作的时间是否值得许可证的价格？可能不是.
我建议你向这位客户道歉,告诉他他的情况超出了你的软件的范围并给他退款.
Tim*_*ost 59
这就是为什么像"Go"这样的语言没有断言的原因之一.它们习惯于处理你可能没有想过的案例.你应该只断言不可能的,而不仅仅是不可能的.做后者是断言声誉不好的原因.每次打字assert(,走开十分钟,真的想一想.
在你特别令人不安的情况下,这种说法在罕见但可能的情况下是虚假的,这是可以想象的,也是令人震惊的.因此,在您的应用程序中处理它,如果只是说"此软件不是为处理您提供的场景而设计的".
断言你的伟大,伟大,伟大的祖父是你的父亲是不可能的是一个合理的事情.
如果我在一家受雇于测试软件的测试公司工作,我当然会提出这种情况.为什么？每个少年而又聪明的"用户"都会做同样的事情,并在最终的"错误报告"中津津乐道.
tfi*_*iga 37
所以,我在家庭树软件方面做了一些工作.我认为你要解决的问题是你需要能够在没有无限循环的情况下走树 - 换句话说,树需要是非周期性的.
然而,看起来你断言一个人和他们的祖先之间只有一条路.这将保证没有周期,但是太严格了.从生物学角度讲,后代是有向无环图(DAG).你所拥有的案例当然是一个堕落的案例,但这种事情一直在大树上发生.
例如,如果你看一下n代的2 ^ n个祖先,如果没有重叠,那么你在公元1000年就会有更多的祖先,而不是有人活着.所以,必须有重叠.
但是,您也倾向于获得无效的循环,只是错误的数据.如果您正在遍历树,则必须处理循环.您可以在每个单独的算法中或在加载时执行此操作.我是在加载时做的.
在树中查找真实循环可以通过几种方式完成.错误的方法是从给定的个体标记每个祖先,并且当遍历时,如果已经标记了要进入下一个的人,则切断链接.这将切断潜在的准确关系.正确的方法是从每个人开始,并用每个人的路径标记每个祖先.如果新路径包含当前路径作为子路径,那么它是一个循环,应该被打破.您可以将路径存储为vector <bool>(MFMF,MFFFMF等),这使得比较和存储非常快.
还有一些其他方法可以检测周期,例如发送两个迭代器并查看它们是否与子集测试发生冲突,但我最终使用了本地存储方法.
另请注意,您不需要实际切断链接,只需将其从普通链接更改为"弱"链接,而不是某些算法.在选择标记为弱的链接时,您还需要注意; 有时您可以通过查看出生日期信息来确定周期应该被打破的位置,但通常您无法弄清楚任何因为缺少这么多数据.
小智 36
愚蠢问题的另一个模拟严肃答案:
真正的答案是,使用适当的数据结构.使用没有循环的纯树无法完全表达人类谱系.你应该使用某种图形.此外,在进一步讨论之前,先与人类学家交谈,因为即使在最简单的"西方父权制一夫一妻婚姻"案例中,也有很多其他地方可以尝试类似的家谱模型.
即使我们想忽略这里讨论的本地禁忌关系,也有很多完全合法且完全出乎意料的方法将循环引入家谱.
例如:http://en.wikipedia.org/wiki/Cousin_marriage
基本上,表亲婚姻不仅是普遍的和预期的,它是人类从数千个小家庭群体变成全球60亿人口的原因.它不能以任何其他方式工作.
在家谱,家庭和血统方面,确实很少有普遍性.几乎任何关于规范的严格假设都暗示着姨妈可以成为谁,或者谁可以嫁给谁,或者如何将儿童合法化为继承目的,可以在世界或历史的某个地方被某种例外所困扰.
Wil*_*l A 20
除了潜在的法律含义之外,您肯定需要将家族树上的"节点"视为前任人,而不是假设该节点可以是唯一的人.
让树节点包含一个人以及后继者 - 然后您可以在树的下方有另一个节点,其中包含具有不同后继者的同一个人.
ker*_*ger 13
一些答案已经显示了保持断言/不变量的方法,但这似乎是对断言/不变量的误用.断言是为了确保应该为真的东西是真的,并且不变量是为了确保不应该改变的东西不会改变.
你在这里断言的是,不存在乱伦关系.显然它们确实存在,所以你的断言是无效的.你可以解决这个断言,但真正的错误在于断言本身.断言应该被删除.
系谱数据是循环的,不适合非循环图,因此如果您对循环有断言,则应删除它们.
在不创建自定义视图的情况下在视图中处理此方法的方法是将循环父级视为"ghost"父级.换句话说,当一个人同时是同一个人的父亲和祖父时,则正常显示祖父节点,但父节点被渲染为具有简单标签的"幽灵"节点("看到祖父") )并指向祖父.
为了进行计算,您可能需要改进逻辑以处理循环图,以便在存在循环时不会多次访问节点.
| 归档时间： |
|
| 查看次数： |
225392 次 |
| 最近记录： |