首页 文章

家谱软件中的循环

提问于
浏览
1594

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

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

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

18 回答

  • 84

    放松你的断言 .

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

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

  • 564

    您应该将Atreides系列(现代,Dune或古代,俄狄浦斯雷克斯)设置为测试用例 . 通过使用已清理的数据作为测试用例,您不会发现错误 .

  • 3

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

    你_7617_t存在什么 . 显然它们确实存在,所以你的断言是无效的 . 你可以解决这个断言,但真正的错误在于断言本身 . 断言应该被删除 .

  • 5

    这就是像"Go"这样的语言没有断言的原因之一 . 它们常用于处理您可能没有想到的案例 . You should only assert the impossible, not simply the unlikely . 做后者是断言声誉不好的原因 . 每次你输入 assert( ,走开十分钟,真的想一想 .

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

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

    如果我是为一家受雇来测试你的软件的测试公司工作的,我当然会介绍这种情况 . 为什么?每个少年而又聪明的'user'都会做同样的事情并且在结果_70614中津津乐道 .

  • 4

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

  • 224

    断言不能在现实中存活下来

    通常,断言在与现实世界数据的接触中无法生存 . 它是软件工程过程的一部分,用于决定您要处理哪些数据以及哪些数据超出范围 .

    循环族图

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

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

    当你考虑surrogates或"fuzzy fatherhood"时,事情变得更加奇怪 .

    如何处理

    将周期定义为超出范围

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

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

    允许手动关系

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

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

    小心手动关系 . 有一种诱惑使它们完全可配置,因此创建了一个完全可配置的数据模型 . 这不起作用:您的软件无法扩展,您将获得奇怪的错误,最后用户界面将变得无法使用 . 这种反模式称为"soft coding""The daily WTF"就是一个例子 .

    制作数据模型更灵活,跳过断言,测试不变量

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

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

    使用测试数据生成器检查异常测试用例 . 有HaskellErlangC的快速检查库 . 对于Java / Scala,有ScalaCheckNyaya . 一个测试想法是模拟随机填充,让它随机杂交,然后让你的软件先导入然后导出结果 . 期望的是,输出中的所有连接也在输入中,反之亦然 .

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

    • 叔叔留下了叔叔,即使你添加更多"romantic relations"

    • 每个孩子都有父母

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

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

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

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

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

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

  • 13

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

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

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

  • 20

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

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

  • 36

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

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

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

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

  • 59

    最重要的是 avoid creating a problem ,所以我相信你应该 use a direct relation 避免有一个循环 .

    正如@markmywords所说, #include "fritzl.h".

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

  • -3

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

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

  • 115

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

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

    假设: A 有自己女儿的孩子 .

    A 将自己添加到程序中 AB . 一旦担任父亲的角色,让我们称之为男朋友 .

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

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

    从中构建,您可以使用代码同步 AB 来避免不一致 .

    This solution is surely not perfect, but is a first approach.

  • 79

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

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

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

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

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

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

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

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

  • 8

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

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

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

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

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

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

  • 4

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

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

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

  • 41

    你应该专注于 what really makes value for your software . 花在为一个消费者工作的时间是否值得许可证的价格?可能不是 .

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

  • 37

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

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

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

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

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

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

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

相关问题