c++ beste - Zyklen in der Stammbaum-Software





mac genealogie (16)


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.

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?




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.




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



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.




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




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.




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.




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.




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.




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.




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.




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.




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




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 eine Knotenversion des Python-Codes.

const graph = [[1, 2], [1, 3], [1, 4], [2, 3], [3, 4], [2, 6], [4, 6], [8, 7], [8, 9], [9, 7]]
let cycles = []

function main() {
  for (const edge of graph) {
    for (const node of edge) {
      findNewCycles([node])
    }
  }
  for (cy of cycles) {
    console.log(cy.join(','))
  }
}

function findNewCycles(path) {
  const start_node = path[0]
  let next_node = null
  let sub = []

  // visit each edge and each node of each edge
  for (const edge of graph) {
    const [node1, node2] = edge
    if (edge.includes(start_node)) {
      next_node = node1 === start_node ? node2 : node1
    }
    if (notVisited(next_node, path)) {
      // eighbor node not on path yet
      sub = [next_node].concat(path)
      // explore extended path
      findNewCycles(sub)
    } else if (path.length > 2 && next_node === path[path.length - 1]) {
      // cycle found
      const p = rotateToSmallest(path)
      const inv = invert(p)
      if (isNew(p) && isNew(inv)) {
        cycles.push(p)
      }
    }
  }
}

function invert(path) {
  return rotateToSmallest([...path].reverse())
}

// rotate cycle path such that it begins with the smallest node
function rotateToSmallest(path) {
  const n = path.indexOf(Math.min(...path))
  return path.slice(n).concat(path.slice(0, n))
}

function isNew(path) {
  const p = JSON.stringify(path)
  for (const cycle of cycles) {
    if (p === JSON.stringify(cycle)) {
      return false
    }
  }
  return true
}

function notVisited(node, path) {
  const n = JSON.stringify(node)
  for (const p of path) {
    if (n === JSON.stringify(p)) {
      return false
    }
  }
  return true
}

main()




c++ graph cycle assertions family-tree