[c++] Zyklen in der Stammbaum-Software


Answers

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".

Question

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?




Behauptungen überleben die Realität nicht

In der Regel überleben Behauptungen den Kontakt mit realen Daten nicht. Es ist ein Teil des Prozesses der Softwareentwicklung, zu entscheiden, mit welchen Daten Sie umgehen möchten und welche nicht.

Zyklische Familiengrafiken

In Bezug auf die Familie "Bäume" (in der Tat sind es ausgewachsene Grafiken, 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 wurde meine Mutter. Einige Zeit später gab ich meiner Frau einen Sohn, der der Bruder meines Vaters und meines Onkels war. Die Frau meines Vaters (die auch meine Tochter und meine Mutter ist) bekam einen Sohn. Als Ergebnis bekam ich einen Bruder und einen Enkel in derselben Person. Meine Frau ist jetzt meine Großmutter, weil sie die Mutter meiner Mutter ist. So bin ich der Ehemann meiner Frau und gleichzeitig der Stiefkelkel meiner Frau. Mit anderen Worten, ich bin mein eigener Opa.

Die Dinge werden noch seltsamer, wenn man surrogates oder "fuzzy vaterhood" berücksichtigt.

Wie man damit umgeht

Definieren Sie Zyklen als außerhalb des Geltungsbereichs

Sie könnten entscheiden, dass Ihre Software solche seltenen Fälle nicht behandeln sollte. Wenn ein solcher Fall auftritt, sollte der Benutzer ein anderes Produkt verwenden. Dies macht den Umgang mit den häufiger auftretenden Fällen wesentlich robuster, da Sie mehr Assertions und ein einfacheres Datenmodell behalten können.

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

Erlaube manuelle Beziehungen

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

Der Benutzer kann dann seltene Fälle von Hand behandeln. Ihr Datenmodell wird immer noch ziemlich einfach bleiben und Ihre Behauptungen werden überleben.

Sei vorsichtig mit manuellen Beziehungen. Es besteht die Versuchung, sie vollständig konfigurierbar zu machen und somit ein vollständig konfigurierbares Datenmodell zu erstellen. Das wird nicht funktionieren: Ihre Software wird nicht skalieren, Sie werden seltsame Fehler bekommen und schließlich wird die Benutzeroberfläche unbrauchbar. Dieses Anti-Pattern nennt sich "Soft Coding" und "The Daily WTF" ist voll von Beispielen dafür.

Machen Sie Ihr Datenmodell flexibler, überspringen Sie Assertionen, testen Sie Invarianten

Der letzte Ausweg wäre, Ihr Datenmodell flexibler zu machen. Sie müssten fast alle Assertionen überspringen und Ihr Datenmodell auf einem vollständigen Graphen aufbauen. Wie das obige Beispiel zeigt, ist es leicht möglich, Ihr eigener Großvater zu sein, so dass Sie sogar Fahrräder haben können.

In diesem Fall sollten Sie Ihre Software ausgiebig testen. Sie mussten fast alle Behauptungen überspringen, so dass es gute Chancen für weitere Fehler gibt.

Verwenden Sie einen Testdatengenerator, um ungewöhnliche Testfälle zu überprüfen. Es gibt Schnellcheck-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 willkürlich zu durchkreuzen, dann Ihre Software zuerst importieren und dann das Ergebnis exportieren zu lassen. Die Erwartung wäre, dass alle Verbindungen im Ausgang auch im Eingang und umgekehrt sind.

Ein Fall, in dem eine Eigenschaft gleich bleibt, wird Invariante genannt. 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 diese mit zufällig generierten Daten. Invarianten können funktional sein, zB:

  • 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 wird nicht auf einem Graphen mit bis zu 10 Milliarden Mitgliedern abstürzen (egal wie viele Verbindungen)
  • Ihre Software skaliert mit O (Anzahl der Knoten) und O (Anzahl der Kanten ^ 2)
  • Ihre Software kann jeden Familiendiagramm mit bis zu 10 Milliarden Mitgliedern speichern und erneut laden

Wenn Sie die simulierten Tests ausführen, werden Sie viele seltsame Eckenfälle finden. Sie zu reparieren wird viel Zeit in Anspruch nehmen. Auch Sie werden eine Menge Optimierungen verlieren, Ihre Software wird viel langsamer laufen. Sie müssen entscheiden, ob es sich lohnt und ob dies im Umfang Ihrer Software liegt.




Ein paar Antworten haben Wege gezeigt, die Behauptungen / Invarianten zu behalten, 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 existieren sie, also ist Ihre Behauptung ungültig. Sie können diese Behauptung umgehen, aber der eigentliche Fehler ist in der Behauptung selbst. Die Behauptung sollte entfernt werden.




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: A hat Kinder mit seiner eigenen Tochter.

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

Fügen Sie eine is_same_for_out() -Funktion hinzu, die dem Ausgabe-erzeugenden Teil Ihres Programms mitteilt, dass alle Links, die intern zu B gehen, bei der Präsentation von Daten zu A gehen sollen.

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

A könnten Sie Code A und B synchronisieren, um Inkonsistenzen zu vermeiden.

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




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.

Zum Beispiel: 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.




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

Um dies in einer Ansicht zu handhaben, ohne eine benutzerdefinierte Ansicht zu erstellen, behandeln Sie das zyklische übergeordnete Element als "gespenstisches" übergeordnetes Element. Mit anderen Worten, wenn eine Person für dieselbe Person sowohl Vater als auch Großvater ist, dann wird der Großvaterknoten normal gezeigt, aber der Vaterknoten wird als ein "Geist" -Knoten dargestellt, der eine einfache Bezeichnung hat ("siehe Großvater"). ) und zeigt auf den Großvater.

Um Berechnungen durchzuführen, müssen Sie möglicherweise Ihre Logik verbessern, um zyklische Graphen zu verarbeiten, so dass ein Knoten nicht mehr als einmal besucht wird, wenn ein Zyklus vorliegt.




Du Atreides die Atreides Familie (entweder modern, Atreides oder uralt, Ödipus Rex ) als Testfall einrichten sollen. Sie finden keine Fehler, wenn Sie sanierte Daten als Testfall verwenden.




Duplizieren Sie den Vater (oder verwenden Sie Symlink / Referenz).

Zum Beispiel, wenn Sie 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



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.




Related