家譜軟體中的循環

我是一些家庭樹軟體的開發者（用C ​​++和Qt編寫）。 在我的一位客戶向我郵寄錯誤報告之前，我沒有遇到任何問題。 問題是客戶有兩個孩子和自己的女兒，是以，他因錯誤而無法使用我的軟體。

這些錯誤是我處理家族圖的各種斷言和不變量的結果（例如，在走一個循環之後，程式聲明X不能同時是Y的父親和祖父）。

如何在不删除所有資料斷言的情況下解決這些錯誤？

#1樓

系譜資料是循環的，不适合非循環圖，是以如果你有針對周期的斷言，你應該删除它們。

在不建立自定義視圖的情況下在視圖中處理此方法的方法是将循環父級視為“ghost”父級。 換句話說，當一個人同時是同一個人的父親和祖父時，則正常顯示祖父節點，但父節點被渲染為具有簡單标簽的“幽靈”節點（“看到祖父”） ）并指向祖父。

為了進行計算，您可能需要改進邏輯以處理循環圖，以便在存在循環時不會多次通路節點。

#2樓

斷言不能在現實中存活下來

通常斷言在與現實世界資料的接觸中無法生存。 它是軟體工程過程的一部分，用于決定您要處理哪些資料以及哪些資料超出範圍。

循環家庭圖

關于家庭“樹”（實際上它是完整的圖表，包括周期），有一個很好的轶事：

我娶了一個有一個成年女兒的寡婦。 經常拜訪我們的父親愛上了我的繼女，并娶了她。 結果，我的父親成了我的兒子，我的女兒成了我的母親。 一段時間後，我給了我的妻子一個兒子，他是我父親的兄弟，還有我的叔叔。 我父親的妻子（也是我的女兒和母親）有一個兒子。 結果，我和同一個人有了一個兄弟和一個孫子。 我的妻子現在是我的祖母，因為她是我母親的母親。 是以我是我妻子的丈夫，同時也是我妻子的繼孫。 換句話說，我是我自己的爺爺。

當你考慮到代理人或“模糊的父親”時，事情變得更加奇怪。

如何處理

将周期定義為超出範圍

您可以決定您的軟體不應該處理這種罕見的情況。 如果發生這種情況，使用者應使用不同的産品。 這使得處理更常見的情況更加健壯，因為您可以保留更多的斷言和更簡單的資料模型。

在這種情況下，請為您的軟體添加一些良好的導入和導出功能，以便使用者可以在必要時輕松遷移到其他産品。

允許手動關系

您可以允許使用者添加手動關系。 這些關系不是“一等公民”，即軟體按原樣使用它們，不檢查它們，也不在主資料模型中處理它們。

然後，使用者可以手動處理罕見情況。 您的資料模型仍将非常簡單，您的斷言将繼續存在。

小心手動關系。 有一種誘惑，使它們完全可配置，進而建立一個完全可配置的資料模型。 這不起作用：您的軟體無法擴充，您将遇到奇怪的錯誤，最後使用者界面将無法使用。 這種反模式被稱為“軟編碼” ，而“每日WTF”則充滿了這樣的例子。

使您的資料模型更靈活，跳過斷言，測試不變量

最後的手段是使您的資料模型更加靈活。 您必須跳過幾乎所有斷言并将資料模型建立在完整的圖表上。 如上例所示，很容易成為你自己的祖父，是以你甚至可以有周期。

在這種情況下，您應該廣泛測試您的軟體。 您必須跳過幾乎所有斷言，是以很有可能會出現其他錯誤。

使用測試資料生成器檢查異常測試用例。 有Haskell ， Erlang或C的快速檢查庫。 對于Java / Scala，有ScalaCheck和Nyaya 。 一個測試的想法是模拟随機群體，讓它随機雜交，然後讓你的軟體首先導入，然後導出結果。 期望的是，輸出中的所有連接配接也在輸入中，反之亦然。

屬性保持不變的情況稱為不變量。 在這種情況下，不變量是模拟群體中個體之間的“浪漫關系”集。 嘗試盡可能多地找到不變量，并使用随機生成的資料對其進行測試。 不變量可以起作用，例如：

• 即使你增加了更多的“浪漫關系”，叔叔也會留下叔叔
• 每個孩子都有父母
• 兩代人口中至少有一個祖父母

或者他們可以是技術性的：

• 您的軟體不會在高達100億成員的圖表上崩潰（無論有多少互連）
• 您的軟體按O（節點數）和O（邊數= 2）進行擴充
• 您的軟體可以儲存并重新加載每個家庭圖表，最多可達100億成員

通過運作模拟測試，您會發現許多奇怪的角落情況。 修複它們将花費大量時間。 此外，您将失去很多優化，您的軟體運作速度會慢得多。 您必須決定，是否值得，以及這是否屬于您的軟體範圍。

#3樓

除了潛在的法律含義之外，您肯定需要将家族樹上的“節點”視為前任人，而不是假設該節點可以是唯一的人。

讓樹節點包含一個人以及後繼者 - 然後您可以在樹的下方有另一個節點，其中包含具有不同後繼者的同一個人。

#4樓

我猜你有一些價值，可以唯一地識别你可以作為支票基礎的人。

這是一個棘手的問題。 假設你想保持結構為樹，我建議：

假設：

A

有孩子和他自己的女兒。

A

将自己添加到

A

和

B

。 一旦擔任父親的角色，我們稱之為男朋友。

添加一個

is_same_for_out()

函數，該函數告訴程式的輸出生成部分，所有進入

B

内部的連結應該在資料呈現時轉到

A

這将為使用者做一些額外的工作，但我想IT的實施和維護相對容易。

從中建構，您可以使用代碼同步

A

和

B

來避免不一緻。

這個解決方案肯定不是完美的，但這是第一種方法。

#5樓

我讨厭對這種搞砸的情況發表評論，但不重新調整所有不變量的最簡單方法是在圖形中建立一個虛拟頂點，作為代理回到亂倫的父親身上。

#6樓

放松你的斷言。

不是通過更改規則，這些規則很可能對99.9％的客戶在輸入資料時發現錯誤非常有幫助。

相反，将其從錯誤“無法添加關系”更改為帶有“無論如何添加”的警告。

#7樓

這就是為什麼像“Go”這樣的語言沒有斷言的原因之一。 它們習慣于處理你可能沒有想過的案例。 你應該隻斷言不可能的，而不僅僅是不可能的 。 做後者是斷言聲譽不好的原因。 每次你輸入

assert(

走開十分鐘并真正考慮它。

在你特别令人不安的情況下，這種說法在罕見但可能的情況下是虛假的，這是可以想象的，也是令人震驚的。 是以，在您的應用程式中處理它，如果隻是說“此軟體不是為處理您提供的場景而設計的”。

斷言你的偉大，偉大，偉大的祖父是你的父親是不可能的是一個合理的事情。

如果我在一家受雇于測試軟體的測試公司工作，我當然會提出這種情況。 為什麼？ 每個少年而又聰明的“使用者”都會做同樣的事情，并在最終的“錯誤報告”中津津樂道。

#8樓

看來你（和/或你的公司）對家譜應該是什麼有一個根本的誤解。

讓我澄清一點，我也為一家公司（其中一個産品）的産品組合中的家族樹工作，我們一直在努力解決類似的問題。

在我們的案例中，問題，我也假設你的情況，來自GEDCOM格式，該格式對于一個家庭應該是什麼非常自以為是。 然而，這種格式包含了一些關于家譜真正看起來的嚴重錯誤觀念。

GEDCOM有許多問題，例如與同性關系，亂倫等不相容......在現實生活中發生的事情比你想象的更頻繁（尤其是回到1700-1800時）。

我們已經将我們的家譜模型化為現實世界中發生的事件：事件（例如，出生，婚禮，訂婚，工會，死亡，收養等）。 我們對這些沒有任何限制，除了邏輯上不可能的（例如，一個不能是一個人自己的父母，關系需要兩個人等等）

缺乏驗證為我們提供了一個更“現實世界”，更簡單，更靈活的解決方案。

至于這個具體的情況，我建議删除斷言，因為它們并不普遍存在。

為了顯示問題（将出現），我建議根據需要多次繪制相同的節點，通過在選擇其中一個副本時點亮所有副本來暗示重複。

#9樓

您應該專注于真正為您的軟體創造價值的東西 。 花在為一個消費者工作的時間是否值得許可證的價格？ 可能不是。

我建議你向這位客戶道歉，告訴他他的情況超出了你的軟體的範圍并向他退款。

#10樓

這是家庭樹的問題：它們不是樹木。 它們是有向無環圖或DAG。 如果我正确了解人類生殖生物學的原理，就不會有任何循環。

據我所知，即使是基督徒也接受堂兄弟之間的婚姻（以及子女），這會将家譜變成家庭DAG。

故事的寓意是：選擇正确的資料結構。

#11樓

你的家譜應該使用直接關系。 這樣你就不會有一個循環。

#12樓

愚蠢問題的另一個模拟嚴肅答案：

真正的答案是，使用适當的資料結構。 使用沒有循環的純樹無法完全表達人類譜系。 你應該使用某種圖形。 此外，在進一步讨論之前，先與人類學家交談，因為即使在最簡單的“西方父權制一夫一妻婚姻”案例中，也有很多其他地方可以嘗試類似的家譜模型。

即使我們想忽略這裡讨論的本地禁忌關系，也有很多完全合法且完全出乎意料的方法将循環引入家譜。

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

基本上，表親婚姻不僅是普遍的和預期的，它是人類從數千個小家庭群體變成全球60億人口的原因。 它不能以任何其他方式工作。

在家譜，家庭和血統方面，确實很少有普遍性。 幾乎任何關于規範的嚴格假設都暗示着阿姨可以成為誰，或者誰可以嫁給誰，或者如何将兒童合法化為繼承目的，可能會被世界或曆史上的某個例外所困擾。

#13樓

您應該将Atreides系列（現代， Dune或古代， Oedipus Rex ）設定為測試用例。 通過使用已清理的資料作為測試用例，您找不到錯誤。

#14樓

是以，我在家庭樹軟體方面做了一些工作。 我認為你要解決的問題是你需要能夠在不進入無限循環的情況下走樹 - 換句話說，樹需要是非周期性的。

然而，看起來你斷言一個人和他們的祖先之間隻有一條路。 這将保證沒有周期，但是太嚴格了。 從生物學角度講，後代是有向無環圖 （DAG）。 你所擁有的案例當然是一個堕落的案例，但這種事情一直發生在較大的樹上。

例如，如果你看一下n代的2 ^ n個祖先，如果沒有重疊，那麼你在公元1000年就會有更多的祖先，而不是有人活着。 是以，必須有重疊。

但是，您也傾向于獲得無效的循環，隻是錯誤的資料。 如果您正在周遊樹，則必須處理循環。 您可以在每個單獨的算法中或在加載時執行此操作。 我是在加載時做的。

在樹中查找真實循環可以通過幾種方式完成。 錯誤的方法是從給定的個體标記每個祖先，并且當周遊時，如果已經标記了要進入下一個的人，則切斷連結。 這将切斷潛在的準确關系。 正确的方法是從每個人開始，并用每個人的路徑标記每個祖先。 如果新路徑包含目前路徑作為子路徑，那麼它是一個循環，應該被打破。 您可以将路徑存儲為vector <bool>（MFMF，MFFFMF等），這使得比較和存儲非常快。

還有一些其他方法可以檢測周期，例如發送兩個疊代器并檢視它們是否與子集測試發生沖突，但我最終使用了本地存儲方法。

另請注意，您不需要實際切斷連結，隻需将其從普通連結更改為“弱”連結，而不是某些算法。 在選擇标記為弱的連結時，您還需要注意; 有時你可以通過檢視出生日期資訊來确定周期應該被打破的地方，但是由于缺少這麼多資料，你常常無法弄清楚。

#15樓

一些答案已經顯示了保持斷言/不變量的方法，但這似乎是對斷言/不變量的誤用。 斷言是為了確定應該為真的東西是真的，并且不變量是為了確定不應該改變的東西不會改變。

你在這裡斷言的是，不存在亂倫關系。 顯然它們确實存在，是以你的斷言是無效的。 你可以解決這個斷言，但真正的錯誤在于斷言本身。 斷言應該被删除。

#16樓

最重要的是

avoid creating a problem

，是以我認為你應該使用直接關系來避免出現問題。

正如@markmywords所說， ＃include“fritzl.h”。

最後我要說

recheck your data structure

。 也許那裡出了問題（也許雙向連結清單解決了你的問題）。

#17樓

你應該仍然檢查一個人是他/她自己的父母或其他不可能的情況，并提出錯誤，而不是删除所有的斷言。 如果使用者不太可能仍然檢測到常見的輸入錯誤，可能會發出警告，但如果一切正确，它都會起作用。

我将資料存儲在一個帶有每個人的永久整數的向量中，并将父對象和子對象存儲在人對象中，其中所述int是向量的索引。 這在幾代人之間會很快（但對于名字搜尋這樣的事情來說很慢）。 對象将按照建立時的順序排列。

#18樓

複制父（或使用符号連結/引用）。

例如，如果您使用的是分層資料庫：

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