c++ beste - Zyklen in der Stammbaum-Software




mac genealogie (16)

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

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

Abschließend muss ich noch recheck your data structure . Vielleicht läuft da etwas schief (vielleicht löst eine bidirektionale Liste Ihr Problem).

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.


Anstatt alle Behauptungen zu entfernen, sollten Sie immer noch nach Dingen wie einer Person suchen, die ihre eigenen Eltern oder andere unmögliche Situationen ist, und einen Fehler anzeigen. Vielleicht eine Warnung ausgeben, wenn es unwahrscheinlich ist, so dass der Benutzer immer noch häufige Eingabefehler entdecken kann, aber es wird funktionieren, 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 int der Index des Vektors ist. Das wäre ziemlich schnell zwischen den Generationen zu gehen (aber langsam für Dinge wie Namensrecherchen). Die Objekte würden in der Reihenfolge ihrer Erstellung stehen.


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.


Dies ist einer der Gründe, warum Sprachen wie "Go" keine Behauptungen haben. Sie werden verwendet, um Fälle zu bearbeiten, 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 Assert assert( gehen Sie für 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 gefälscht wäre. Behandeln Sie es also in Ihrer App, um nur zu sagen: "Diese Software wurde nicht für das von Ihnen präsentierte Szenario entwickelt".

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 genau das gleiche machen und den resultierenden 'Fehlerbericht' genießen.


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 die Abstammung ein 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.


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

Lassen Sie mich klarstellen, dass ich auch für eine Firma arbeite, die (als eines ihrer Produkte) einen Familienstammbaum in ihrem Portfolio hat, und wir haben mit ähnlichen Problemen gekämpft.

Das Problem, in unserem Fall, und ich nehme auch Ihren Fall an, kommt aus dem 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 in die Zeit um 1700-1800 zurückgehen).

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 einen davon auswählt.


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.


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


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.


Abgesehen von den möglichen rechtlichen Implikationen scheint es ganz sicher, dass Sie einen "Knoten" in einem Familienstammbaum als eine Vorgänger-Person behandeln müssen, anstatt anzunehmen, dass der Knoten die einzige Person sein kann.

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


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.


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.


Sie sollten sich darauf konzentrieren, was wirklich Wert für Ihre Software ausmacht . 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.


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 glaube nicht, dass Sie einen beliebigen Familienstammbaum nehmen und eine Punktdatei automatisch generieren können, in der GraphViz immer gut aussieht.

Aber ich denke, Sie können es immer gut aussehen lassen, wenn Sie:

  • Verwenden Sie den Rang = die gleichen anderen Antworten, um die vom OP gewünschten 'T'-Verbindungen zu erhalten
  • Benutze den Ordnungstrick, den Brian Blank gemacht hat, um ungewöhnliche Linien zu verhindern
  • Angenommen, keine zweiten Ehen und Halbgeschwister
  • Zeichnen Sie nur eine Teilmenge des Baums, die den folgenden Regeln folgt:
    • Sei S die "zentrale" Person
    • Wenn S Geschwister hat, stellen Sie sicher, dass S über allen von ihnen Recht hat.
    • Wenn S einen Ehepartner hat und der Ehepartner Geschwister hat, vergewissern Sie sich, dass sich der Ehepartner links von allen seinen Geschwistern befindet.
    • Zeigen Sie keine Neffen, Nichten, Tanten oder Onkel von S oder S 'Ehepartner
    • Keine Ehepartner von Geschwistern zeigen
    • Zeigen Sie keine Ehepartner von Geschwistern des Ehepartners
    • Zeigen Sie Kinder von S, aber nicht deren Ehepartner oder Kinder
    • Zeigen Sie Eltern von S und Eltern von Ehepartner

Am Ende werden nicht mehr als 3 Generationen gleichzeitig angezeigt, wobei S in der mittleren Generation steht.

Im Bild unten ist S = Homer (etwas von Brian Blanks Version geändert):

digraph G {
  edge [dir=none];
  node [shape=box];

  "Herb"      [shape=box, regular=0, color="blue", style="filled" fillcolor="lightblue"] ;
  "Homer"     [shape=box, regular=0, color="blue", style="bold, filled" fillcolor="lightblue"] ;
  "Marge"     [shape=oval, regular=0, color="red", style="filled" fillcolor="pink"] ;
  "Clancy"    [shape=box, regular=0, color="blue", style="filled" fillcolor="lightblue"] ;
  "Jackeline" [shape=oval, regular=0, color="red", style="filled" fillcolor="pink"] ;
  "Abraham"   [shape=box, regular=0, color="blue", style="filled" fillcolor="lightblue"] ;
  "Mona"      [shape=oval, regular=0, color="red", style="filled" fillcolor="pink"] ;
  "Patty"     [shape=oval, regular=0, color="red", style="filled" fillcolor="pink"] ;
  "Selma"     [shape=oval, regular=0, color="red", style="filled" fillcolor="pink"] ;
  "Bart"      [shape=box, regular=0, color="blue", style="filled" fillcolor="lightblue"] ;
  "Lisa"      [shape=oval, regular=0, color="red", style="filled" fillcolor="pink"] ;
  "Maggie"    [shape=oval, regular=0, color="red", style="filled" fillcolor="pink"] ;

  a1 [shape=diamond,label="",height=0.25,width=0.25];
  b1 [shape=circle,label="",height=0.01,width=0.01];
  b2 [shape=circle,label="",height=0.01,width=0.01];
  b3 [shape=circle,label="",height=0.01,width=0.01];
  {rank=same; Abraham -> a1 -> Mona};
  {rank=same; b1 -> b2 -> b3};
  {rank=same; Herb; Homer};
  a1 -> b2
  b1 -> Herb
  b3 -> Homer

  p1 [shape=diamond,label="",height=0.25,width=0.25];
  q1 [shape=circle,label="",height=0.01,width=0.01];
  q2 [shape=circle,label="",height=0.01,width=0.01];
  q3 [shape=circle,label="",height=0.01,width=0.01];
  {rank=same; Homer -> p1 -> Marge};
  {rank=same; q1 -> q2 -> q3};
  {rank=same; Bart; Lisa; Maggie};
  p1 -> q2;
  q1 -> Bart;
  q2 -> Lisa;
  q3 -> Maggie;

  x1 [shape=diamond,label="",height=0.25,width=0.25];
  y1 [shape=circle,label="",height=0.01,width=0.01];
  y2 [shape=circle,label="",height=0.01,width=0.01];
  y3 [shape=circle,label="",height=0.01,width=0.01];
  {rank=same; Clancy -> x1 -> Jackeline};
  {rank=same; y1 -> y2 -> y3};
  {rank=same; Patty; Selma; Marge};
  x1 -> y2;
  y1 -> Marge;
  y2 -> Patty;
  y3 -> Selma;
}

Dies ergibt den folgenden Baum von GraphViz (mit Anmerkungen, die ich mit Power Point hinzugefügt habe):





c++ graph cycle assertions family-tree