家谱软件中的循环

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

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

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

#1楼

系谱数据是循环的&＃xff0c;不适合非循环图&＃xff0c;所以如果你有针对周期的断言&＃xff0c;你应该删除它们。

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

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

#2楼

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

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

循环家庭图

关于家庭“树”&＃xff08;实际上它是完整的图表&＃xff0c;包括周期&＃xff09;&＃xff0c;有一个很好的轶事&＃xff1a;

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

当你考虑到代理人或“模糊的父亲”时&＃xff0c;事情变得更加奇怪。

如何处理

将周期定义为超出范围

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

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

允许手动关系

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

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

小心手动关系。 有一种诱惑&＃xff0c;使它们完全可配置&＃xff0c;从而创建一个完全可配置的数据模型。 这不起作用&＃xff1a;您的软件无法扩展&＃xff0c;您将遇到奇怪的错误&＃xff0c;最后用户界面将无法使用。 这种反模式被称为“软编码” &＃xff0c;而“每日WTF”则充满了这样的例子。

使您的数据模型更灵活&＃xff0c;跳过断言&＃xff0c;测试不变量

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

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

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

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

• 即使你增加了更多的“浪漫关系”&＃xff0c;叔叔也会留下叔叔
• 每个孩子都有父母
• 两代人口中至少有一个祖父母

或者他们可以是技术性的&＃xff1a;

• 您的软件不会在高达100亿成员的图表上崩溃&＃xff08;无论有多少互连&＃xff09;
• 您的软件按O&＃xff08;节点数&＃xff09;和O&＃xff08;边数&＃61; 2&＃xff09;进行扩展
• 您的软件可以保存并重新加载每个家庭图表&＃xff0c;最多可达100亿成员

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

#3楼

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

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

#4楼

我猜你有一些价值&＃xff0c;可以唯一地识别你可以作为支票基础的人。

这是一个棘手的问题。 假设你想保持结构为树&＃xff0c;我建议&＃xff1a;

假设&＃xff1a; A有孩子和他自己的女儿。

A将自己添加到A和B 。 一旦担任父亲的角色&＃xff0c;我们称之为男朋友。

添加一个is_same_for_out()函数&＃xff0c;该函数告诉程序的输出生成部分&＃xff0c;所有进入B内部的链接应该在数据呈现时转到A

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

从中构建&＃xff0c;您可以使用代码同步A和B来避免不一致。

这个解决方案肯定不是完美的&＃xff0c;但这是第一种方法。

#5楼

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

#6楼

放松你的断言。

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

相反&＃xff0c;将其从错误“无法添加关系”更改为带有“无论如何添加”的警告。

#7楼

这就是为什么像“Go”这样的语言没有断言的原因之一。 它们习惯于处理你可能没有想过的案例。 你应该只断言不可能的&＃xff0c;而不仅仅是不可能的 。 做后者是断言声誉不好的原因。 每次你输入assert(走开十分钟并真正考虑它。

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

断言你的伟大&＃xff0c;伟大&＃xff0c;伟大的祖父是你的父亲是不可能的是一个合理的事情。

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

#8楼

看来你&＃xff08;和/或你的公司&＃xff09;对家谱应该是什么有一个根本的误解。

让我澄清一点&＃xff0c;我也为一家公司&＃xff08;其中一个产品&＃xff09;的产品组合中的家族树工作&＃xff0c;我们一直在努力解决类似的问题。

在我们的案例中&＃xff0c;问题&＃xff0c;我也假设你的情况&＃xff0c;来自GEDCOM格式&＃xff0c;该格式对于一个家庭应该是什么非常自以为是。 然而&＃xff0c;这种格式包含了一些关于家谱真正看起来的严重错误观念。

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

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

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

至于这个具体的情况&＃xff0c;我建议删除断言&＃xff0c;因为它们并不普遍存在。

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

#9楼

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

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

#10楼

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

据我所知&＃xff0c;即使是基督徒也接受堂兄弟之间的婚姻&＃xff08;以及子女&＃xff09;&＃xff0c;这会将家谱变成家庭DAG。

故事的寓意是&＃xff1a;选择正确的数据结构。

#11楼

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

#12楼

愚蠢问题的另一个模拟严肃答案&＃xff1a;

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

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

例如&＃xff1a; http &＃xff1a; //en.wikipedia.org/wiki/Cousin_marriage

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

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

#13楼

您应该将Atreides系列&＃xff08;现代&＃xff0c; Dune或古代&＃xff0c; Oedipus Rex &＃xff09;设置为测试用例。 通过使用已清理的数据作为测试用例&＃xff0c;您找不到错误。

#14楼

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

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

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

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

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

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

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

#15楼

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

你在这里断言的是&＃xff0c;不存在乱伦关系。 显然它们确实存在&＃xff0c;所以你的断言是无效的。 你可以解决这个断言&＃xff0c;但真正的错误在于断言本身。 断言应该被删除。

#16楼

最重要的是avoid creating a problem &＃xff0c;所以我认为你应该使用直接关系来避免出现问题。

正如&＃64;markmywords所说&＃xff0c; &＃xff03;include“fritzl.h”。

最后我要说recheck your data structure 。 也许那里出了问题&＃xff08;也许双向链表解决了你的问题&＃xff09;。

#17楼

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

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

#18楼

复制父&＃xff08;或使用符号链接/引用&＃xff09;。

例如&＃xff0c;如果您使用的是分层数据库&＃xff1a;

$ #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/Father4 directories, 1 file