家庭树软件中的循环
我是一些家族树软件（使用C ++和Qt编写）的开发人员。 直到我的一个客户邮寄给我一个错误报告，我才有了问题。 问题是客户有两个孩子和他们自己的女儿，结果，他因为错误而无法使用我的软件。
这些错误是我的各种关于正在处理的家族图的断言和不变式的结果（例如，在循环之后，程序指出X不能既是父亲也是Y的祖父）。
我怎样才能解决这些错误，而不删除所有的数据断言？
看来你（和/或你的公司）对家庭树应该是什么有根本的误解。
让我澄清一下，我也为一家公司（其产品之一）中的家族树工作，我们一直在努力解决类似的问题。
在我们的情况下，我们也假定你的情况来自于GEDCOM格式，这个格式对于一个家庭应该是非常有见地的 。 然而，这种格式包含了一些严重的家庭树看起来像什么样的错误观念。
GEDCOM有很多问题，比如与同性关系不协调，乱伦等等……现实生活中发生的事情比你想象的要多（尤其是1700-1800时间）。
我们模拟了我们的家谱，看看在现实世界中发生了什么：事件（例如出生，婚礼，订婚，工会，死亡，收养等等）。 除了逻辑上不可能的东西（例如，不能是自己的父母，关系需要两个人，等等），我们不会对这些做任何限制。
缺乏validation给了我们一个更“现实世界”，更简单，更灵活的解决scheme。
至于这个具体情况，我build议删除这个断言，因为它们并不普遍。
为了显示问题（会出现），我build议根据需要多次绘制相同的节点，通过点亮所有副本来select其中的一个来暗示重复。
放松你的断言。
而不是通过改变规则，而这些规则对于99.9％的客户在input数据方面犯错而言可能非常有帮助。
相反，将其从“无法添加关系”错误更改为带有“添加”的警告。
这是家庭树问题：他们不是树木。 它们是有向无环图或DAG。 如果我正确理解人类生殖生物学的原理，就不会有任何循环。
据我所知，甚至基督徒也接受表兄弟之间的婚姻（也就是孩子），这将把家谱变成一个家族的DAG。
故事的寓意是：select正确的数据结构。
我想你有一些价值，可以唯一标识一个你可以根据你的支票的人。
这是一个棘手的问题。 假设你想保持结构树，我build议这样做：
假设： A有自己的女儿有孩子。
A将自己添加到程序中作为A和B 一旦在父亲的angular色，我们称之为男朋友。
添加一个is_same_for_out()函数，它告诉你的程序的输出生成部分，所有到内部的链接都应该在数据的显示上到达A
这会为用户带来一些额外的工作，但是我认为IT实现和维护相对容易。
从此构build，您可以使用代码同步A和B来避免不一致。
这个解决scheme肯定不是完美的，但是是第一种方法。
你应该专注于真正为你的软件创造价值的东西 。 是花费在为一个消费者工作的时间值得的牌照的价格？ 可能不是。
我build议你向这个客户道歉，告诉他他的情况超出了你的软件的范围，并给他退款。
你应该build立Atreides家族（现代， 沙丘 ，或古代， 俄狄浦斯雷克斯 ）作为testing案例。 通过将清理过的数据用作testing用例，您不会发现错误。
这就是“Go”这样的语言没有断言的原因之一。 它们被用来处理你可能没有经常想到的事情。 你只应该断言不可能的事情，而不是简单的不可能的事情 。 做后者是声称坏名声。 每当你inputassert( ，走开十分钟， 真的想一想。
在你特别令人不安的情况下，这种说法在罕见但可能的情况下是假的，这是可想而不可的。 因此，在你的应用程序中处理它，如果只是说“这个软件不是为了处理你提供的场景而devise的”。
断言你伟大，伟大，曾祖父为你的父亲是不可能的，这是一件合理的事情。
如果我正在为一家被聘用来testing你的软件的testing公司工作，当然我会提出这种情况。 为什么？ 每个less年但聪明的“用户”将会在最终的“错误报告”中做同样的事情并津津乐道。
我讨厌评论这样一个错误的情况，但是最简单的方法是不要调整所有的不variables，就是在图中创build一个幻影顶点，作为代理给乱伦爸爸。
所以，我在家谱软件上做了一些工作。 我想你要解决的问题是你需要能够走路，而不会陷入无限循环 – 换句话说，树需要是非循环的。
然而，看起来你认为一个人和一个祖先之间只有一条路。 这将保证没有周期，但太严格。 从生物学angular度来说，后代是一个有向无环图 （DAG）。 你的情况肯定是一个退化的情况，但这种事情总是在大树上发生。
例如，如果你看看你在n世代的2 ^ n祖先，如果没有重叠，那么在公元1000年你就会有更多的祖先。 所以，必须重叠。
但是，你也倾向于获得无效的周期，只是不好的数据。 如果您正在遍历树，则必须处理循环。 您可以在每个单独的algorithm中或加载时执行此操作。 我做了负载。
在树中寻找真正的周期可以通过几种方法来完成。 错误的方法是标记给定个体的每一个祖先，当遍历时，如果你要下一步的人已经被标记了，那么切断链接。 这将切断准确的关系。 要做到这一点的正确方法是从每个人开始，并标记每个祖先与个人的path。 如果新path包含当前path作为子path，那么这是一个循环，应该被打破。 您可以将path存储为vector<bool>（MFMF，MFFFMF等），这使得比较和存储速度非常快。
还有其他几种检测周期的方法，例如发送两个迭代器，看看它们是否与子集testing冲突，但是我最终使用了本地存储方法。
另外请注意，您不需要切断链接，只需将其从常规链接更改为“弱”链接，而不是由某些algorithm所遵循。 您在select标记为弱的链接时还要小心; 有时你可以通过查看出生date信息来找出周期应该被破坏的位置，但是由于丢失了太多的数据，通常你不能弄清楚什么。
对于一个愚蠢的问题的另一个模拟认真的答案：
真正的答案是，使用适当的数据结构。 人类谱系不能完全用无循环的纯树来expression。 你应该使用某种graphics。 另外，在进一步讨论这个问题之前，还要和一个人类学家谈一谈，因为还有很多其他的地方，即使在最简单的“西方父权制一夫一妻制婚姻”的例子中，也可以用类似的方法来模仿家谱。
即使我们想要忽略这里讨论的地方禁忌关系，也有很多完全合法的和完全意想不到的方法来将周期引入家谱。
例如： http : //en.wikipedia.org/wiki/Cousin_marriage
基本上，表亲婚姻不仅是普遍的，而且是预料之中的，这也是人类从数千个小家庭走向全世界60亿人口的原因。 它不能以其他方式工作。
关于族谱，家族和血统，实际上几乎没有什么共性。 几乎任何严格的假设，关于规范谁能代表婶婶，谁可以娶谁，或者如何以inheritance为目的合法化儿童的规范，都可能会被世界或历史上的某个例外所打破。
撇开潜在的法律影响，当然似乎你需要把家庭树上的“节点”当作前任者，而不是假设节点可以是唯一的一个人。
让树节点包括一个人以及后继者 – 然后你可以在包含具有不同后继者的同一个人的树下更深的另一个节点。
一些答案已经显示了保持断言/不variables的方法，但这似乎是断言/不variables的滥用。 断言是要确保应该是真实的东西是真实的，不variables是确保不应该改变的东西不会改变。
你在这里断言的是，不存在乱伦的关系。 显然他们确实存在，所以你的断言是无效的。 你可以解决这个断言，但真正的错误在于断言本身。 该断言应该被删除。
你的家庭树应该使用定向关系。 这样你就不会有一个循环。
家谱数据是循环的，不适合一个非循环图，所以如果你有循环的断言，你应该删除它们。
在不创build自定义视图的情况下处理此视图的方法是将循环父项视为“重影”父项。 换句话说，当一个人既是父亲又是同一个人的祖父时，则正常地显示祖父节点，而父节点被呈现为具有简单标签的“虚拟”节点，如“看祖父” ），并指向祖父。
为了进行计算，您可能需要改进处理循环图的逻辑，以便在有循环的情况下节点不会被访问多次。
最重要的是avoid creating a problem ，所以我相信你应该用直接的关系来避免一个循环。
正如@markmywords所说， #include“fritzl.h”。
最后我不得不说recheck your data structure 。 也许有什么地方出错了（也许一个双向链表解决你的问题）。
断言不能生存下去
通常，断言在与现实世界数据的接触中不能存活。 这是软件工程过程的一部分，可以决定你想要处理哪些数据，哪些数据超出范围。
循环的家庭图
关于家庭“树”（事实上它是完整的图，包括周期），有一个很好的轶事：
我嫁给一个有一个长大的女儿的寡妇。 我常常拜访我们的父亲，爱上了我的继女，嫁给了她。 结果，我的父亲成了我的儿子，我的女儿成了我的母亲。 过了一段时间，我给了我的妻子一个儿子，他是我父亲的兄弟，还有我的叔叔。 我父亲的妻子（也是我的女儿和我的母亲）有一个儿子。 结果，我在同一个人身上find了一个兄弟和一个孙子。 我的妻子现在是我的祖母，因为她是我母亲的母亲。 所以我是我妻子的丈夫，同时也是我妻子的后孙。 换句话说，我是我自己的爷爷。
当你把代理人或“模糊的父亲”考虑在内时，情况会变得更加奇怪。
如何处理
将周期定义为超出范围
你可以决定你的软件不应该处理这种罕见的情况。 如果发生这种情况，用户应该使用不同的产品。 这使得处理更常见的情况更加健壮，因为您可以保留更多的断言和更简单的数据模型。
在这种情况下，为您的软件添加一些良好的导入和导出function，以便用户在必要时可以轻松迁移到其他产品。
允许手动关系
您可以允许用户添加手动关系。 这些关系并不是“一stream的公民”，即软件将其视为现状，不检查它们，也不会在主要数据模型中处理它们。
用户然后可以手动处理罕见的情况。 你的数据模型仍然保持相当简单，你的断言将继续存在。
小心手动关系。 有一个诱惑，使他们完全可configuration，从而创build一个完全可configuration的数据模型。 这是行不通的：你的软件不能扩展，你会得到奇怪的错误，最终用户界面将变得无法使用。 这种反模式被称为“软编码” ， “日常WTF”就是这样的例子。
使您的数据模型更加灵活，跳过断言，testing不variables
最后的办法是让你的数据模型更加灵活。 您将不得不跳过几乎所有的断言，并将您的数据模型build立在一个完整的图上。 如上例所示，很容易成为自己的祖父，所以你甚至可以有周期。
在这种情况下，你应该广泛地testing你的软件。 你必须跳过几乎所有的断言，所以很有可能会出现更多的错误。
使用testing数据生成器来检查exception的testing用例。 有Haskell ， Erlang或C的快速检查库。 对于Java / Scala，有ScalaCheck和Nyaya 。 一个testing的想法是模拟一个随机的人口，让它随机杂交，然后让你的软件首先导入，然后导出结果。 所期望的是，输出中的所有连接也都是input，反之亦然。
一个属性保持不变的情况称为不variables。 在这种情况下，不variables是模拟人群中个体之间的“浪漫关系”。 尽量find尽可能多的不variables，并用随机生成的数据进行testing。 不variables可以是function性的，例如：
- 一个叔叔留下叔叔，即使你增加了更多的“浪漫关系”
- 每个孩子都有一个父母
- 两代人至less有一个祖父母
或者他们可以是技术性的：
- 你的软件不会在一个图表上崩溃多达100亿的成员（不pipe有多less互连）
- 你的软件用O（节点数）和O（边数^ 2）
- 您的软件可以保存和重新加载每个家庭graphics高达100亿成员
通过运行模拟testing，你会发现很多奇怪的angular落案例。 修复它们将花费很多时间。 你也将失去很多优化，你的软件运行速度会慢很多。 你必须决定，如果它是值得的，如果这是在你的软件的范围。
不要删除所有的断言，你仍然应该检查一个人是否是他/她自己的父母或其他不可能的情况，并提出错误。 如果可能性不大，可能会发出警告，因此用户仍然可以检测到常见的input错误，但是如果一切正确的话，它将会工作。
我会将数据存储在一个具有永久整数的向量中，并存储父对象和子对象，其中int表示向量的索引。 这将是非常快的代之间（但像名称search的东西慢）。 对象将按照创build时的顺序排列。
复制父亲（或使用符号链接/引用）。
例如，如果您正在使用分层数据库：
$ #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
