Frage Zyklen in der Stammbaum-Software


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

Diese Fehler sind das Ergebnis meiner verschiedenen Behauptungen und Invarianten über den Familiengraph, der gerade verarbeitet wird (zum Beispiel, nach dem Laufen eines Zyklus, sagt das Programm, dass X nicht Vater und Großvater von Y sein kann).

Wie kann ich diese Fehler beheben, ohne alle Datenbestätigungen zu entfernen?


1594
2018-05-28 18:39


Ursprung


Antworten:


Es scheint, dass Sie (und / oder Ihre Firma) 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 Familienstammbaum in seinem Portfolio hat, und wir haben mit ähnlichen Problemen gekämpft.

Das Problem, in unserem Fall, und ich nehme Ihren Fall auch an, kommt von der GEDCOM Format, das extrem eigensinnig ist, was eine Familie sein sollte. Dieses Format enthält jedoch einige schwerwiegende Missverständnisse darüber, wie ein Familienstammbaum wirklich aussieht.

GEDCOM hat viele Probleme, wie Inkompatibilität mit gleichgeschlechtlichen Beziehungen, Inzest, etc ... Was im wirklichen Leben passiert häufiger als Sie sich vorstellen (vor allem wenn Sie zurück in die Zeit um 1700-1800 gehen).

Wir haben unseren Familienstammbaum nach dem modelliert, was in der realen Welt passiert: Ereignisse (z. B. Geburten, Hochzeiten, Verlobung, Gewerkschaften, Todesfälle, Adoptionen usw.). Wir beschränken diese nicht, außer auf logisch unmögliche (zum Beispiel kann man nicht der eigene Elternteil sein, die Beziehungen brauchen zwei Personen, etc ...)

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

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

Für die Anzeige von Problemen (die sich ergeben) würde ich vorschlagen, den gleichen Knoten so oft wie nötig zu zeichnen, indem man auf die Duplizierung hinweist, indem man alle Kopien aufleuchtet, wenn man eine davon auswählt.


727
2018-06-01 08:25



Entspanne deine Behauptungen.

Nicht, indem Sie die Regeln ändern, die für 99,9% Ihrer Kunden wahrscheinlich sehr hilfreich sind, um Fehler bei der Eingabe ihrer Daten zu finden.

Stattdessen ändern Sie es von einem Fehler "kann keine Beziehung hinzufügen" zu einer Warnung mit einem "Add Anyway".


564
2018-05-28 19:20



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

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

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


224
2018-06-01 09:58



Ich schätze, dass Sie einen Wert haben, der eine Person eindeutig identifiziert, auf der Sie Ihre Schecks basieren können.

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

Angenommen das: A hat Kinder mit seiner eigenen Tochter.

A fügt sich dem Programm als A und wie B. Einmal in der Rolle des Vaters, nennen wir es einen Freund.

Füge hinzu ein is_same_for_out() Funktion, die dem Output-Generierungsteil Ihres Programms mitteilt, dass alle Links gehen B intern sollte gehen A bei Vorlage von Daten.

Dies wird dem Benutzer zusätzliche Arbeit bringen, aber ich denke, IT wäre relativ einfach zu implementieren und zu warten.

Davon ausgehend könnten Sie an der Code-Synchronisierung arbeiten A und B um Inkonsistenzen zu vermeiden.

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


115
2018-05-28 18:50



Sie sollten sich auf konzentrieren Was wirklich Wert für Ihre Software macht. Ist die Zeit, die damit verbracht 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 zu sagen, dass seine Situation für Ihre Software nicht in Frage kommt, und ihm eine Rückerstattung zu gewähren.


84
2018-06-01 08:51



Du hättest das einrichten sollen Atreides Familie (entweder modern, Düneoder alt, Oedipus rex) als Testfall. Sie finden keine Fehler, wenn Sie sanierte Daten als Testfall verwenden.


79
2018-06-01 16:10



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 nur das Unwahrscheinliche. Letztere machen Behauptungen einen schlechten Ruf. Jedes Mal, wenn Sie tippen assert(Geh für zehn Minuten weg und Ja wirklich Denk 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 gefälscht wäre. Also, behandeln Sie es in Ihrer App, wenn Sie nur sagen "Diese Software wurde nicht entwickelt, um das Szenario zu behandeln, das Sie vorgestellt haben".

Es ist eine vernünftige Sache, zu behaupten, dass dein großer Ururgroßvater dein Vater als unmöglich sei.

Wenn ich für ein Testunternehmen arbeiten würde, das beauftragt wurde, Ihre Software zu testen, hätte ich dieses Szenario natürlich vorgestellt. Warum? Jeder jugendliche, aber intelligente 'Benutzer' wird es tun genau dasselbe und genieße den resultierenden 'Fehlerbericht'.


59
2018-06-01 06:10



Ich hasse es, zu solch einer vermasselten Situation Stellung zu nehmen, aber der einfachste Weg, nicht alle Invarianten neu zu justieren, ist, einen Phantom-Eckpunkt in Ihrem Graphen zu erstellen, der als Proxy für den inzestuösen Vater dient.


41
2018-05-28 18:55



Also habe ich etwas an der Stammbaum-Software gearbeitet. Ich denke, das Problem, das Sie zu lösen versuchen, ist, dass Sie in der Lage sein müssen, den Baum zu durchlaufen, ohne in endlose Schleifen zu geraten - mit anderen Worten, der Baum muss azyklisch sein.

Es sieht jedoch so aus, als würden Sie behaupten, dass es nur einen Pfad zwischen einer Person und einem ihrer Vorfahren gibt. Das garantiert, dass es keine Zyklen gibt, aber zu streng. Biologisch gesehen ist Abstieg eine gerichteter azyklischer Graph(DAG). Der Fall, den Sie haben, ist sicherlich ein degenerierter Fall, aber diese Art von Ding passiert die ganze Zeit auf größeren Bäumen.

Wenn Sie sich zum Beispiel die 2 ^ n Vorfahren ansehen, die Sie bei Generation n haben, wenn es keine Überlappung gäbe, dann hätten Sie in 1000 AD mehr Vorfahren als lebende Menschen. Also, es muss Überschneidungen geben.

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

Das Finden von echten Zyklen in einem Baum kann auf verschiedene Arten erfolgen. Der falsche Weg besteht darin, jeden Vorfahren einer bestimmten Person zu markieren, und wenn die Person, die Sie als nächsten betreten möchten, bereits markiert ist, dann schneiden Sie den Link ab. Dies wird potentiell genaue Beziehungen trennen. Der richtige Weg, dies zu tun, besteht darin, bei jedem Individuum zu beginnen 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 ein paar andere Möglichkeiten, Zyklen zu erkennen, z. B. zwei Iteratoren auszusenden und zu sehen, ob sie jemals mit dem Subset-Test kollidieren, aber am Ende habe ich die lokale Speichermethode verwendet.

Beachten Sie auch, dass Sie die Verknüpfung nicht wirklich trennen müssen. Sie können sie einfach von einer normalen Verbindung zu einer "schwachen" Verbindung ändern, auf die einige Ihrer Algorithmen nicht folgen. Sie sollten auch darauf achten, welchen Link Sie als schwach markieren möchten. Manchmal können Sie herausfinden, wo der Zyklus unterbrochen werden sollte, indem Sie nach Geburtsdatumsinformationen suchen, aber oft können Sie nichts herausfinden, weil so viele Daten fehlen.


37
2018-06-01 18:39



Eine weitere gespielte ernsthafte Antwort auf eine dumme Frage:

Die wirkliche Antwort ist, 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 Graphen verwenden. Sprechen Sie auch mit einem Anthropologen, bevor Sie weitermachen, denn es gibt viele andere Orte, an denen ähnliche Fehler gemacht werden könnten, um eine Genealogie zu modellieren, sogar im einfachsten Fall einer "patriarchalischen monogamen Ehe".

Auch wenn wir lokale Tabu-Beziehungen, wie hier diskutiert, ignorieren wollen, gibt es viele vollkommen legale und völlig unerwartete Wege, Zyklen in einen Stammbaum einzuführen.

Beispielsweise: http://en.wikipedia.org/wiki/Cousin_marriage

Grundsätzlich ist Cousin-Ehe nicht nur üblich und erwartet, es ist der Grund, warum Menschen von Tausenden von kleinen Familiengruppen zu einer weltweiten Bevölkerung von 6 Milliarden Menschen geworden sind. Es kann nicht anders funktionieren.

Es gibt wirklich sehr wenige Universalien, wenn es um Genealogie, Familie und Herkunft geht. Fast jede strenge Annahme von Normen, die darauf schließen lassen, wer eine Tante sein kann oder wer wen heiraten kann oder wie Kinder zum Zweck der Erbschaft legitimiert werden, kann durch irgendeine Ausnahme in der Welt oder in der Geschichte gestört werden.


36
2018-06-01 14:12