Quelle est la meilleure structure de données à utiliser pour une relation progéniture?

Question

Il doit y avoir une structure de données standard pour contenir, par exemple, l'information sur l'élevage canin, le croisement génétique végétal et les relations humaines complexes. On pourrait penser que ce serait une structure arborescente facile, mais la combinaison de deux parents (ou plus, pour le génie génétique) par progéniture, plusieurs progénitures différentes par parent ensemble, de multiples déplacements des parents (les chevaux de haras s'accouplent avec beaucoup d'autres chevaux), l'adoption, etc rend cette structure très fragmentée.

Je m'attends à ce que quelqu'un ait abordé ceci avant cependant. Toutes les ressources que je devrais examiner?

Answer 1

Je pense que ce que vous avez est une simple base de données relationnelle, où la relation principale est « child_of », « direct_descendant », etc.

Bien sûr, la structure de données particulière ici est acyclique, et vous voudrez peut-être faire des requêtes transitives (descendant de descendant de ...), qui ne sont généralement pas supportées par les moteurs SQL standard. Donc, si vous voulez le faire en mémoire, vous pouvez utiliser un graphe acyclique dirigé (DAG).

Answer 2

Ça sent comme DAG. Si la direction et acyclique est trop limitatif, vous pouvez regarder le graph theory data-structures. En utilisant des graphiques pour des problèmes abstraits, les sommets représentent des entités et les arêtes représentent la relation.