Was ist die beste Datenstruktur für eine Nachkommenschaft?

Question

Es muss eine standardisierte Datenstruktur geben, in der beispielsweise Informationen zur Züchtung von Hunden, pflanzengenetische Kreuzungen und komplexe menschliche Beziehungen gespeichert werden.

Man könnte denken, es wäre eine einfache Baumstruktur, aber die Kombination von zwei (oder mehr, für die Gentechnik) Eltern pro Nachkommen, mehrere verschiedene Nachkommen pro Elternteil, mehrere Bewegungen der Eltern (Hengste Pferde paaren sich mit vielen anderen) Pferde), Adoption usw. macht dies eine sehr fragmentierte Struktur.

Ich erwarte, dass jemand das vorher angepackt hat. Irgendwelche Ressourcen, die ich untersuchen sollte?

Answer 1

Ich denke, was Sie haben, ist nur eine einfache relationale Datenbank, wo die Haupt Beziehung „child_of“, „direct_descendant“ usw.

Natürlich ist die besondere Datenstruktur hier ist azyklisch, und möchten Sie vielleicht transitive Abfragen (Abkömmling von Abkömmling von ...) zu tun, die normalerweise nicht von SQL-Standard-Engines unterstützt werden.

Also wenn Sie es im Speicher tun möchten, könnten Sie uns eine gerichtete azyklische Grafik (DAG).

Answer 2

Riecht wie ein DAG. Wenn die gerichtete und azyklische zu einschränkend ist, sollten Sie sich die graph theory data-structures ansehen.

Mit Graphen für abstrakte Probleme stellen Vertices Entitäten dar und die Kanten repräsentieren die Beziehung.