Zyklen in der Stammbaumsoftware

1594

Ich bin der Entwickler einer Stammbaum-Software (geschrieben in C ++ und Qt). Ich hatte keine Probleme, bis mir einer meiner Kunden einen Fehlerbericht schickte. Das Problem ist, dass der Kunde zwei Kinder mit seiner eigenen Tochter hat und daher meine Software aufgrund von Fehlern nicht verwenden kann.

Diese Fehler sind das Ergebnis meiner verschiedenen Behauptungen und Invarianten bezüglich des Familiengraphen, der verarbeitet wird (zum Beispiel besagt das Programm nach einem Zyklus, dass X nicht sowohl Vater als auch Großvater von Y sein kann).

Wie kann ich diese Fehler beheben, ohne alle Datenzusicherungen zu entfernen?

Partick Höse
quelle
30
Wenn Sie Ihren Stammbaum weit genug zurückverfolgen, werden Sie dieses Problem weitaus häufiger treffen, als Sie möchten. Das Aufgeben der Baumdarstellung kann schmerzhaft sein, wäre aber letztendlich korrekter.
Thomas
55
Sie sollten keine Behauptungen für unwahrscheinliche Dinge hinzufügen, nur für unmögliche Dinge. Zyklen sind die offensichtlichen Dinge, die in einem Stammbaumdiagramm nicht möglich sind ... niemand kann mit irgendeiner Methode sein eigener Vorfahr sein. Diese anderen Behauptungen sind nur Schwindel und sollten entfernt werden.
pgod
44
Dies ist in der Welt der Tierzucht überhaupt keine dumme Frage. Tochter zu Vater, Mutter zu Sohn, Schwester zu Bruder, Enkel zu Großeltern ist dort Standardtechnik, und Tierzüchter benötigen ebenfalls Stammbaumsoftware. "Reinrassig" meine ¤% # &.
Kaleissin
31
Das Heiraten der ersten Cousins ​​war im viktorianischen England sehr verbreitet, insbesondere in der Oberschicht (dies war eine hervorragende Möglichkeit, Geld in der Familie zu behalten). Charles Darwin heiratete zum Beispiel seine erste Cousine, Emma Wedgwood. Jede Stammbaumsoftware muss solche Situationen unterstützen.
Person

Antworten:

727

Es scheint, dass Sie (und / oder Ihr Unternehmen) ein grundlegendes Missverständnis darüber haben, was ein Stammbaum sein soll.

Lassen Sie mich klarstellen, ich arbeite auch für ein Unternehmen, das (als eines seiner Produkte) einen Stammbaum in seinem Portfolio hat, und wir haben mit ähnlichen Problemen zu kämpfen.

Das Problem in unserem Fall, und ich nehme auch Ihren Fall an, kommt vom GEDCOM- Format, das äußerst einschätzend darüber ist, was eine Familie sein sollte. Dieses Format enthält jedoch einige schwerwiegende Missverständnisse darüber, wie ein Stammbaum wirklich aussieht.

GEDCOM hat viele Probleme, wie Inkompatibilität mit gleichgeschlechtlichen Beziehungen, Inzest usw. Was im wirklichen Leben häufiger vorkommt, als Sie sich vorstellen können (insbesondere, wenn Sie in die Zeit zwischen 1700 und 1800 zurückkehren).

Wir haben unseren Stammbaum nach dem Vorbild der realen Welt modelliert: Ereignisse (z. B. Geburten, Hochzeiten, Verlobungen, Gewerkschaften, Todesfälle, Adoptionen usw.). Wir schränken diese nicht ein, außer für logisch unmögliche (zum Beispiel kann man nicht der eigene Elternteil sein, Beziehungen brauchen zwei Personen usw.)

Das Fehlen von Validierungen gibt uns eine "realere", einfachere und flexiblere Lösung.

In diesem speziellen Fall würde ich vorschlagen, die Behauptungen zu entfernen, da sie nicht allgemein gültig sind.

Für die Anzeige von Problemen (die auftreten werden) würde ich empfehlen, denselben Knoten so oft wie nötig zu zeichnen und auf die Duplizierung hinzuweisen, indem alle Kopien bei Auswahl einer davon beleuchtet werden.

Bert Goethals
quelle
32
Dies scheint der richtige Ansatz zu sein, und es ist einfach genug, ihn zu erweitern, um komplexere Probleme zu erkennen. Sie können eine Reihe von "A ist vor B passiert" -Beziehungen zwischen Ereignissen ausarbeiten. Zum Beispiel, dass eine Person vor anderen Ereignissen geboren wurde, an denen sie beteiligt war. Dies ist ein gerichteter Graph. Sie können dann überprüfen, ob das Diagramm keine Zyklen enthält. Siehe diese Frage auf StackOverflow. Dies sollte in Ordnung sein, bis die Zeitreise erfunden ist.
Paul Harrison
41
@ Paul-Harrison Wenn es nur so einfach wäre. In älteren Datensätzen (auch neuen) gibt es Datumsinkonsistenzen. Taufe vor der Geburt, Mehrlingsgeburten usw. In offiziellen Aufzeichnungen gibt es also Zeitreisen. Wir erlauben diese inkonsistenten Daten. Benutzer können angeben, was die Anwendung bei Duplikaten als "Geburtsurkunde" betrachten soll. Und wir werden defekte Zeitleisten anzeigen, wenn sie gefunden werden.
Bert Goethals
38
@ ben-voigt GEDCOM ist ein Format, das von der Kirche Jesu Christi der Heiligen der Letzten Tage erstellt wurde. Die Spezifikation besagt eindeutig, dass die Ehe (MARR) zwischen Männern und Frauen stattfinden soll. Für gleichgeschlechtliche Ehen oder Inzest sollte das ASSO-Tag (ASSOCIATES) verwendet werden, das auch verwendet wird, um Freundschaft anzuzeigen oder Nachbarn zu sein. Es ist klar, dass die gleichgeschlechtliche Ehe innerhalb dieser Spezifikation eine Beziehung zweiter Klasse ist. Eine neutralere Spezifikation würde keine Beziehungen zwischen Männern und Frauen erfordern.
Bert Goethals
1
@ Bert Goethals: Sie verwechseln GEDCOM mit bestimmten Programmen, die keine gleichgeschlechtliche Ehe unterstützen (PAF, Legacy). GEDCOM schließt Konstrukte wie "0 @ F1 @ FAM / 1 HUSB @ I1 @ / 1 HUSB @ I2 @" nicht aus und unterstützt daher gleichgeschlechtliche Ehen, wenn Ihre Software dies wünscht.
Pierre
1
@Pierre Sie können das System in der Tat betrügen. Dies geht direkt aus den 5.5.1-Dokumenten hervor: "MARR {MARRIAGE}: = Ein rechtliches, allgemeines oder übliches Ereignis zur Schaffung einer Familieneinheit aus einem Mann und einer Frau als Ehemann und Ehefrau." ( homepages.rootsweb.ancestry.com/~pmcbride/gedcom/55gcappa.htm ) Wie Sie sehen können, gibt es hier keine gleichgeschlechtliche Ehe.
Bert Goethals
563

Entspannen Sie Ihre Behauptungen.

Nicht durch Ändern der Regeln, die für 99,9% Ihrer Kunden wahrscheinlich sehr hilfreich sind, um Fehler bei der Eingabe ihrer Daten zu erkennen.

Ändern Sie es stattdessen von einem Fehler "Beziehung kann nicht hinzugefügt werden" in eine Warnung mit "ohnehin hinzufügen".

Ben Voigt
quelle
143
Wenn eine sehr unwahrscheinliche Situation auftritt , dh wenn ein Benutzer dies normalerweise nur versehentlich tut, ist es eine gute Idee, dem Benutzer eine Warnung anzuzeigen. Das ist gutes Feedback. Aber dann lassen Sie den Benutzer fortfahren, wenn er wirklich sicher ist, dass er möchte. Ich denke, das ist eine gute Antwort, auch wenn es nicht in die Irre geht.
Thomasrutter
15
Gute Antwort! Ich frage mich nur, wie diese Art von Software mit der Situation "Ich bin mein eigener Opa" ( youtube.com/watch?v=eYlJH81dSiw ) umgehen wird .
Zaur Nasibov
4
Dies ist keine wirkliche Antwort, weil ich denke, dass das Problem darin besteht, den Baum tatsächlich zu durchqueren? Es ist jedoch ein guter Vorschlag.
Bdwakefield
3
@bdwakefield: Die Frage lautete: "Wie kann ich diese Fehler beheben, ohne alle Datenzusicherungen zu entfernen?" Ich glaube, ich habe das beantwortet.
Ben Voigt
2
@ Ben Es kommt darauf an, wofür die Behauptungen sind. Wenn sie das Auftreten von Endlosschleifen oder schwerwiegenden Fehlern verhindern, schlagen Sie effektiv vor, die Behauptungen zu entfernen. Wenn sie nur dazu da sind, einen Benutzer vor einem möglichen Fehler zu warnen, ist Ihre Antwort gut.
rm999
224

Hier ist das Problem mit Stammbäumen: Sie sind keine Bäume. Sie sind gerichtete azyklische Graphen oder DAGs. Wenn ich die Prinzipien der Biologie der menschlichen Fortpflanzung richtig verstehe, wird es keine Zyklen geben.

Soweit ich weiß, akzeptieren sogar die Christen Ehen (und damit Kinder) zwischen Cousins, was den Stammbaum in eine Familien-DAG verwandeln wird.

Die Moral der Geschichte lautet: Wählen Sie die richtigen Datenstrukturen.

exDM69
quelle
7
Es würde eine weitere Einschränkung jedes Knotens erfordern, auf den 1 oder 2 maximale Knoten für die In-vitro- und sexuelle Reproduktion zeigen. Um dem wirklichen Leben treu zu bleiben, können Sie mehrere gestrichelte Linien für eine ungewisse Abstammung auf der Vaterseite zulassen (es ist immer klar, wer die Mutter ist, aber nur DNA-Tests können sicherstellen, wer der Vater ist, und das wird bis heute selten durchgeführt). oder auch für beide wird die Adoption berücksichtigt.
Manixrock
7
@manixrock - da es sich bei dieser Frage um seltene Fälle handelt, möchte ich behaupten, dass nicht immer klar ist, wer die Mutter ist. Adoptionen, verlassene Babys, Leihmütter usw. können die Sache komplizieren.
Peter Recore
9
Es ist nicht unbedingt azyklisch, oder? Mann-heiratet-Großmutter.
Ed Ropple
13
Ein Mann, der seine Großmutter heiratet, wird sich nicht zu seinem eigenen Großvater machen und einen Zyklus hinzufügen. Wenn sie Kinder haben, handelt es sich um eine nicht zyklische reguläre Grafikkante.
exDM69
11
Es sind eigentlich ZWEI ADGs. Es gibt das Abstammungsdiagramm und das Rechtsbeziehungsdiagramm. Normalerweise das gleiche, aber divergierend mehr als man erwarten könnte.
JSacksteder
115

Ich vermute, dass Sie einen Wert haben, der eine Person eindeutig identifiziert, auf die Sie Ihre Schecks stützen können.

Dies ist eine schwierige Frage. Angenommen, Sie möchten die Struktur als Baum behalten, schlage ich Folgendes vor:

Nehmen wir an: Ahat Kinder mit seiner eigenen Tochter.

Afügt sich dem Programm als Aund als hinzu B. Sobald wir in der Rolle des Vaters sind, nennen wir es Freund.

Fügen Sie eine is_same_for_out()Funktion hinzu, die dem ausgabeerzeugenden Teil Ihres Programms mitteilt, dass alle Bintern zugehörigen Links Abei der Präsentation von Daten aufgerufen werden sollen .

Dies bedeutet zusätzliche Arbeit für den Benutzer, aber ich denke, die IT wäre relativ einfach zu implementieren und zu warten.

Darauf aufbauend könnten Sie an der Codesynchronisierung arbeiten Aund BInkonsistenzen vermeiden.

Diese Lösung ist sicherlich nicht perfekt, aber ein erster Ansatz.

Eduard Thamm
quelle
9
Wahrscheinlich sind solche "Proxy" -Knoten tatsächlich eine geeignete Lösung. Ich habe jedoch keine Ahnung, wie diese in die Benutzeroberfläche eingefügt werden können, ohne den Benutzer zu beleidigen. Ich kann Ihnen sagen, dass das Schreiben von Software, die sich mit echten Menschen (insbesondere Ihren Kunden) befasst, nicht einfach ist.
Partick Höse
6
Es endet nie - B's neuer Sohn wird sein eigener Onkel sein. Ich würde eine volle Rückerstattung für das Programm in Betracht ziehen!
Bo Persson
3
@ Will A: Und dann merkt er, dass er auch seine eigene Mutter ist und rekrutiert sein jüngeres Ich in die Zeitagentur?
Null gesetzt
2
Das Duplizieren (und Synchronisieren) von Daten innerhalb eines Systems ist eine schlechte Praxis. Es zeigt an, dass die Lösung nicht optimal ist und überdacht werden sollte. Wenn zusätzliche (doppelte) Knoten erstellt werden müssen, geben Sie diese als Proxy an und delegieren Sie die Lese- und Schreibvorgänge an den ursprünglichen Knoten.
Bert Goethals
84

Sie sollten sich darauf konzentrieren, was für Ihre Software wirklich wertvoll ist . Ist die Zeit, die dafür aufgewendet wird, dass es für EINEN Verbraucher funktioniert, den Preis der Lizenz wert? Wahrscheinlich nicht.

Ich rate Ihnen, sich bei diesem Kunden zu entschuldigen, ihm mitzuteilen, dass seine Situation für Ihre Software nicht in Frage kommt, und ihm eine Rückerstattung zu gewähren.

christopheml
quelle
3
Sehr richtig. Aber auch andere potenzielle Probleme mit ähnlichen Problemen abwägen, die andere angesprochen haben.
Prof. Falken Vertrag verletzt
2
Na sicher. Die Begründung lautet: Wenn es sich bei einer nicht kritischen Anwendung um einen seltenen Randfall handelt, müssen Sie nichts reparieren oder implementieren. Wenn es Ihren Benutzern wirklich weh tut, ist es sinnvoll, daran zu arbeiten.
Christopheml
10
Wahrscheinlich hat jeder irgendwo in seiner / ihrer Abstammung Inzest. Sie werden also diese Beule treffen, wenn man die Familiengeschichte (zu) tief gräbt.
Datenwolf
1
Das Erstellen eines Stammbaums aus einer seltsamen Situation (Inzuchtkönig, Fritzl usw.) ist eine gültige Verwendung von Software.
Bulwersator
1
Eine Stammbaum-Software, die es zweiten Cousins ​​nicht erlaubt, zu heiraten, ist nutzlos. Fast alle Familien haben mindestens einen Fall davon. Aus diesem Grund denke ich, dass das ursprüngliche Beispiel die Wirkung wieder gut macht.
Fuzzy76
79

Sie sollten die Atreides- Familie (entweder modern, Dune oder alt, Ödipus Rex ) als Testfall eingerichtet haben. Sie finden keine Fehler, wenn Sie bereinigte Daten als Testfall verwenden.

user779752
quelle
2
Leider denken viel zu viele Menschen zuerst an "OK" -Daten anstatt an Randfälle, die ihre Systeme beschädigen.
Sjas
59

Dies ist einer der Gründe, warum Sprachen wie "Go" keine Behauptungen haben. Sie werden verwendet, um Fälle zu behandeln, an die Sie wahrscheinlich nicht allzu oft gedacht haben. Sie sollten nur das Unmögliche behaupten, nicht einfach das Unwahrscheinliche . Letzteres zu tun, gibt Behauptungen einen schlechten Ruf. assert(Gehen Sie jedes Mal , wenn Sie tippen , zehn Minuten weg und denken Sie wirklich darüber nach.

In Ihrem besonders beunruhigenden Fall ist es sowohl denkbar als auch entsetzlich, dass eine solche Behauptung unter seltenen, aber möglichen Umständen falsch wäre. Behandeln Sie es daher in Ihrer App, wenn Sie nur sagen "Diese Software wurde nicht für das von Ihnen vorgestellte Szenario entwickelt".

Es ist vernünftig zu behaupten, dass Ihr Ur-Ur-Ur-Großvater Ihr Vater als unmöglich ist.

Wenn ich für eine Testfirma gearbeitet hätte, die beauftragt wurde, Ihre Software zu testen, hätte ich dieses Szenario natürlich vorgestellt. Warum? Jeder jugendliche, aber intelligente "Benutzer" wird genau das Gleiche tun und sich über den daraus resultierenden "Fehlerbericht" freuen.

Tim Post
quelle
5
Stimmen Sie dem Argument zu, wann Behauptungen verwendet werden sollen. Ich verstehe nicht, wie es sich auf "einige Sprachen haben Behauptungen, Go nicht" bezieht.
Phooji
2
@ Red Hue - manchmal machen Compiler das Unmögliche möglich. Einige Versionen von gcc denken -10 == 10 in der abs () - Implementierung.
Tim Post
2
@ Red Hue: Der springende Punkt bei Behauptungen ist, Bedingungen zu dokumentieren und zu testen, die immer wahr (oder falsch) sein sollten. Es hilft Ihnen (und anderen), Dinge nicht so zu "reparieren", dass diese unmöglichen Fälle auftreten, da sie dann die App explizit (anstatt subtil) brechen würden. Wenn es einen gültigen Grund für das Auftreten eines "unmöglichen" Falls gibt, haben Sie zu viel behauptet.
CHao
1
@cHao @Tim Post Ich versuche nur zu verstehen, warum es gut ist, keine Behauptungen zu haben, da die meisten von Ihnen der Meinung sind, dass es wichtig ist, Behauptungen zu haben.
Arlen
5
Behauptungen (oder Assertions-ähnlicher Code) sind irrelevant. Code in Sprachen wie Go kann und wird Annahmen über die Struktur von Daten treffen. Es kann diese Annahmen einfach nicht mit Behauptungen dokumentieren und durchsetzen. Fazit: Die Anwendung hat einen Fehler.
Tommy McGuire
41

Ich hasse es, eine solche vermasselte Situation zu kommentieren, aber der einfachste Weg, nicht alle Ihre Invarianten neu auszulösen, besteht darin, einen Phantomscheitelpunkt in Ihrem Diagramm zu erstellen, der als Proxy für den inzestuösen Vater fungiert.

Sean
quelle
37

Also habe ich einige Arbeiten an Stammbaumsoftware durchgeführt. Ich denke, das Problem, das Sie lösen möchten, ist, dass Sie in der Lage sein müssen, auf dem Baum zu laufen, ohne in Endlosschleifen zu geraten - mit anderen Worten, der Baum muss azyklisch sein.

Es sieht jedoch so aus, als würden Sie behaupten, dass es nur einen Weg zwischen einer Person und einem ihrer Vorfahren gibt. Das garantiert, dass es keine Zyklen gibt, ist aber zu streng. Biologisch gesehen ist die Nachkommenschaft ein gerichteter azyklischer Graph (DAG). Der Fall, den Sie haben, ist sicherlich ein entarteter Fall, aber so etwas passiert immer bei größeren Bäumen.

Wenn Sie sich zum Beispiel die 2 ^ n Vorfahren ansehen, die Sie in Generation n haben, wenn es keine Überlappung gab, dann hätten Sie 1000 n. Chr. Mehr Vorfahren als Menschen am Leben waren. Es muss also Überschneidungen geben.

Sie neigen jedoch auch dazu, Zyklen zu erhalten, die ungültig sind, nur schlechte Daten. Wenn Sie den Baum durchqueren, müssen Zyklen behandelt werden. Sie können dies in jedem einzelnen Algorithmus oder unter Last tun. Ich habe es unter Last gemacht.

Das Finden echter Zyklen in einem Baum kann auf verschiedene Arten erfolgen. Der falsche Weg besteht darin, jeden Vorfahren einer bestimmten Person zu markieren. Wenn beim Überqueren die Person, zu der Sie als Nächstes wechseln möchten, bereits markiert ist, schneiden Sie den Link ab. Dadurch werden potenziell genaue Beziehungen getrennt. Der richtige Weg, dies zu tun, besteht darin, von jedem Individuum auszugehen und jeden Vorfahren mit dem Pfad zu diesem Individuum zu markieren. Wenn der neue Pfad den aktuellen Pfad als Unterpfad enthält, handelt es sich um einen Zyklus, der unterbrochen werden sollte. Sie können Pfade als Vektor <bool> (MFMF, MFFFMF usw.) speichern, was den Vergleich und die Speicherung sehr schnell macht.

Es gibt einige andere Möglichkeiten, Zyklen zu erkennen, z. B. das Senden von zwei Iteratoren und das Überprüfen, ob sie jemals mit dem Teilmengen-Test kollidieren. Am Ende habe ich jedoch die lokale Speichermethode verwendet.

Beachten Sie auch, dass Sie den Link nicht wirklich trennen müssen. Sie können ihn einfach von einem normalen Link in einen "schwachen" Link ändern, dem einige Ihrer Algorithmen nicht folgen. Sie sollten auch vorsichtig sein, wenn Sie auswählen, welcher Link als schwach markiert werden soll. Manchmal können Sie herausfinden, wo der Zyklus unterbrochen werden soll, indem Sie sich die Geburtsdaten ansehen. Oft können Sie jedoch nichts herausfinden, da so viele Daten fehlen.

tfinniga
quelle
Vorsicht bei diesen Annahmen; eine männliche und eine weibliche Elternteil ist nicht gegeben , wenn die Menschen anpassen, oder lesibans , die sich als Eltern betrachten, in der nahen Zukunft können sie sogar in der Lage sein , wirklich zu sein , biologisch die Eltern, atleast von Mädchen. Wenn wir Dolly auf Menschen anwenden, ist sogar die Annahme "eine Person hat zwei verschiedene Eltern" falsch.
Agrajag
1
@Agrajag, ja, deshalb habe ich "biologisch gesehen" für die Zykluserkennung angegeben. Auch biologisch gibt es viele mögliche Probleme, wie Leihmütter und künstliche Befruchtung. Wenn Sie auch Adoptionen und andere nicht-biologische Methoden zur Definition von Eltern zulassen, ist es möglich, einen gültigen Zyklus in einem Baum zu haben. Beispielsweise adoptiert möglicherweise jemand seine Großeltern, wenn sie alt werden und nicht mehr in der Lage sind, für sich selbst zu sorgen . Annahmen über das Familienleben der Menschen zu treffen, ist immer kompliziert. Aber wenn Sie Software schreiben, müssen Sie einige Annahmen treffen ..
tfinniga
36

Eine weitere falsche Antwort auf eine dumme Frage:

Die eigentliche Antwort lautet: Verwenden Sie eine geeignete Datenstruktur. Die menschliche Genealogie kann nicht vollständig mit einem reinen Baum ohne Zyklen ausgedrückt werden. Sie sollten eine Art Diagramm verwenden. Sprechen Sie auch mit einem Anthropologen, bevor Sie fortfahren, da es viele andere Orte gibt, an denen ähnliche Fehler beim Modellieren der Genealogie gemacht werden könnten, selbst im einfachsten Fall der "westlichen patriarchalischen monogamen Ehe".

Selbst wenn wir die hier diskutierten lokal tabuisierten Beziehungen ignorieren möchten, gibt es viele völlig legale und völlig unerwartete Möglichkeiten, Zyklen in einen Stammbaum einzuführen.

Zum Beispiel: http://en.wikipedia.org/wiki/Cousin_marriage

Grundsätzlich ist die Cousinehe nicht nur üblich und zu erwarten, sondern auch der Grund, warum Menschen von Tausenden kleiner Familiengruppen auf eine Weltbevölkerung von 6 Milliarden Menschen übergegangen sind. Es kann nicht anders funktionieren.

Es gibt wirklich sehr wenige Universalien, wenn es um Genealogie, Familie und Abstammung geht. Fast jede strenge Annahme über Normen, die darauf hindeuten, wer eine Tante sein kann oder wer wen heiraten kann oder wie Kinder zum Zwecke der Vererbung legitimiert werden, kann durch eine Ausnahme irgendwo auf der Welt oder in der Geschichte verärgert werden.

clvrmnky
quelle
9
Ihr Kommentar hat mich an Polygamie denken lassen. Genealogie-Software, die nur die sexuelle Fortpflanzung modelliert, erfordert möglicherweise einen Namen, der dem Sperma und der Eizelle zugeordnet ist, breitere Definitionen der Familienstruktur jedoch nicht.
Steve Kalemkiewicz
Genealogie-Software erlaubt oft mehr als einen Ehepartner im Modell. Wie Sie das Modell in der Ansicht anzeigen, variiert stark, selbst innerhalb eines Programms, abhängig vom bereitgestellten "Modus".
Todd Hopkinson
20

Abgesehen von möglichen rechtlichen Auswirkungen scheint es sicher, dass Sie einen 'Knoten' in einem Stammbaum als Vorgänger-Person behandeln müssen, anstatt davon auszugehen, dass der Knoten die einzige Person sein kann.

Lassen Sie den Baumknoten eine Person sowie die Nachfolger einschließen - und dann können Sie einen weiteren Knoten tiefer im Baum haben, der dieselbe Person mit unterschiedlichen Nachfolgern enthält.

Will A.
quelle
13

Einige Antworten haben Wege aufgezeigt, um die Behauptungen / Invarianten beizubehalten, aber dies scheint ein Missbrauch von Behauptungen / Invarianten zu sein. Behauptungen sollen sicherstellen, dass etwas, das wahr sein sollte, wahr ist, und Invarianten sollen sicherstellen, dass sich etwas, das sich nicht ändern sollte, nicht ändert.

Was Sie hier behaupten, ist, dass es keine inzestuösen Beziehungen gibt. Offensichtlich sie tun exist, so dass Ihre Behauptung ist ungültig. Sie können diese Behauptung umgehen, aber der eigentliche Fehler liegt in der Behauptung selbst. Die Behauptung sollte entfernt werden.

kerkeslager
quelle
8

Ihr Stammbaum sollte gerichtete Beziehungen verwenden. Auf diese Weise haben Sie keinen Zyklus.

Patrick Cornelissen
quelle
5

Genealogische Daten sind zyklisch und passen nicht in ein azyklisches Diagramm. Wenn Sie also Aussagen gegen Zyklen haben, sollten Sie diese entfernen.

Die Möglichkeit, dies in einer Ansicht zu handhaben, ohne eine benutzerdefinierte Ansicht zu erstellen, besteht darin, das zyklische übergeordnete Element als "Geister" -Eltern zu behandeln. Mit anderen Worten, wenn eine Person sowohl Vater als auch Großvater derselben Person ist, wird der Großvaterknoten normal angezeigt, aber der Vaterknoten wird als "Geister" -Knoten gerendert, der eine einfache Bezeichnung wie ("siehe Großvater") hat. ) und zeigt auf den Großvater.

Um Berechnungen durchführen zu können, müssen Sie möglicherweise Ihre Logik verbessern, um zyklische Diagramme zu verarbeiten, sodass ein Knoten bei einem Zyklus nicht mehr als einmal besucht wird.

Tyler Durden
quelle
4

Das Wichtigste ist avoid creating a problem, also glaube ich, dass Sie eine direkte Beziehung verwenden sollten , um einen Zyklus zu vermeiden.

Wie @markmywords sagte, #include "fritzl.h".

Zum Schluss muss ich noch sagen recheck your data structure. Vielleicht läuft dort etwas schief (vielleicht löst eine bidirektionale verknüpfte Liste Ihr Problem).

Nasser Hadjloo
quelle
4

Behauptungen überleben die Realität nicht

Normalerweise überleben Behauptungen den Kontakt mit Daten aus der realen Welt nicht. Es ist Teil des Software-Engineering-Prozesses, zu entscheiden, mit welchen Daten Sie sich befassen möchten und welche nicht.

Zyklische Familiendiagramme

In Bezug auf Stammbäume (tatsächlich handelt es sich um vollständige Diagramme, einschließlich Zyklen) gibt es eine schöne Anekdote:

Ich heiratete eine Witwe, die eine erwachsene Tochter hatte. Mein Vater, der uns oft besuchte, verliebte sich in meine Stieftochter und heiratete sie. Infolgedessen wurde mein Vater mein Sohn und meine Tochter meine Mutter. Einige Zeit später gab ich meiner Frau einen Sohn, der der Bruder meines Vaters war, und meines Onkels. Die Frau meines Vaters (die auch meine Tochter und meine Mutter ist) hat einen Sohn. Infolgedessen bekam ich einen Bruder und einen Enkel in derselben Person. Meine Frau ist jetzt meine Großmutter, weil sie die Mutter meiner Mutter ist. Ich bin also der Ehemann meiner Frau und gleichzeitig der Stiefenkel meiner Frau. Mit anderen Worten, ich bin mein eigener Opa.

Noch seltsamer wird es, wenn man Leihmütter oder "Fuzzy Fatherhood" berücksichtigt.

Wie gehe ich damit um?

Definieren Sie Zyklen als außerhalb des Gültigkeitsbereichs

Sie könnten entscheiden, dass Ihre Software solche seltenen Fälle nicht behandeln soll. In diesem Fall sollte der Benutzer ein anderes Produkt verwenden. Dies macht den Umgang mit den häufigeren Fällen viel robuster, da Sie mehr Aussagen und ein einfacheres Datenmodell beibehalten können.

Fügen Sie in diesem Fall Ihrer Software einige gute Import- und Exportfunktionen hinzu, damit der Benutzer bei Bedarf problemlos auf ein anderes Produkt migrieren kann.

Manuelle Beziehungen zulassen

Sie können dem Benutzer erlauben, manuelle Beziehungen hinzuzufügen. Diese Beziehungen sind keine "erstklassigen Bürger", dh die Software nimmt sie unverändert, überprüft sie nicht und behandelt sie nicht im Hauptdatenmodell.

Der Benutzer kann dann seltene Fälle von Hand bearbeiten. Ihr Datenmodell bleibt weiterhin recht einfach und Ihre Behauptungen bleiben erhalten.

Seien Sie vorsichtig mit manuellen Beziehungen. Es besteht die Versuchung, sie vollständig konfigurierbar zu machen und somit ein vollständig konfigurierbares Datenmodell zu erstellen. Dies wird nicht funktionieren: Ihre Software wird nicht skaliert, Sie werden seltsame Fehler bekommen und schließlich wird die Benutzeroberfläche unbrauchbar. Dieses Anti-Pattern wird "Soft Coding" genannt , und "The Daily WTF" ist voller Beispiele dafür.

Machen Sie Ihr Datenmodell flexibler, überspringen Sie Zusicherungen und testen Sie Invarianten

Der letzte Ausweg wäre, Ihr Datenmodell flexibler zu gestalten. Sie müssten fast alle Aussagen überspringen und Ihr Datenmodell auf einem vollständigen Diagramm basieren. Wie das obige Beispiel zeigt, ist es leicht möglich, Ihr eigener Großvater zu sein, sodass Sie sogar Zyklen haben können.

In diesem Fall sollten Sie Ihre Software ausführlich testen. Sie mussten fast alle Behauptungen überspringen, daher besteht eine gute Chance für zusätzliche Fehler.

Verwenden Sie einen Testdatengenerator, um ungewöhnliche Testfälle zu überprüfen. Es gibt schnelle Überprüfung Bibliotheken für Haskell , Erlang oder C . Für Java / Scala gibt es ScalaCheck und Nyaya . Eine Testidee wäre, eine zufällige Population zu simulieren, sie zufällig kreuzen zu lassen und dann Ihre Software zuerst das Ergebnis importieren und dann exportieren zu lassen. Die Erwartung wäre, dass alle Verbindungen im Ausgang auch im Eingang sind und umgekehrt.

Ein Fall, in dem eine Eigenschaft gleich bleibt, wird als Invariante bezeichnet. In diesem Fall ist die Invariante die Menge der "romantischen Beziehungen" zwischen den Individuen in der simulierten Population. Versuchen Sie, so viele Invarianten wie möglich zu finden und testen Sie sie mit zufällig generierten Daten. Invarianten können funktional sein, z.

  • Ein Onkel bleibt ein Onkel, auch wenn Sie mehr "romantische Beziehungen" hinzufügen.
  • Jedes Kind hat einen Elternteil
  • Eine Bevölkerung mit zwei Generationen hat mindestens einen Großelternteil

Oder sie können technisch sein:

  • Ihre Software stürzt in einem Diagramm mit bis zu 10 Milliarden Mitgliedern nicht ab (unabhängig von der Anzahl der Verbindungen).
  • Ihre Software skaliert mit O (Anzahl der Knoten) und O (Anzahl der Kanten ^ 2).
  • Ihre Software kann jedes Familiendiagramm mit bis zu 10 Milliarden Mitgliedern speichern und neu laden

Wenn Sie die simulierten Tests ausführen, werden Sie viele seltsame Eckfälle finden. Das Reparieren wird viel Zeit in Anspruch nehmen. Außerdem verlieren Sie viele Optimierungen, Ihre Software läuft viel langsamer. Sie müssen entscheiden, ob es sich lohnt und ob dies im Rahmen Ihrer Software liegt.

stefan.schwetschke
quelle
3

Anstatt alle Behauptungen zu entfernen, sollten Sie dennoch nach Dingen suchen, bei denen eine Person ihr eigener Elternteil ist, oder nach anderen unmöglichen Situationen und einen Fehler darstellen. Möglicherweise wird eine Warnung ausgegeben, wenn dies unwahrscheinlich ist, sodass der Benutzer weiterhin häufige Eingabefehler erkennen kann. Diese Funktion funktioniert jedoch, wenn alles korrekt ist.

Ich würde die Daten in einem Vektor mit einer permanenten Ganzzahl für jede Person speichern und die Eltern und Kinder in persönlichen Objekten speichern, wobei das besagte int der Index des Vektors ist. Dies wäre ziemlich schnell zwischen den Generationen (aber langsam für Dinge wie die Suche nach Namen). Die Objekte befinden sich in der Reihenfolge, in der sie erstellt wurden.

ctype.h
quelle
-3

Dupliziere den Vater (oder benutze Symlink / Referenz).

Wenn Sie beispielsweise eine hierarchische Datenbank verwenden:

$ #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
numerisch
quelle
3
Der ln -sBefehl funktioniert nicht so. Die Auflösung des Links Family/Son/Fatherwird Family/Son/Daughter/Fathervon Family/Sonunten gesucht, wo sich der Link befindet, nicht von .wo Sie den ln -sBefehl ausgegeben haben .
Musiphil
48
Das Klonen ist durch die Genfer Konventionen verboten
MikeIsrael