Qual è la migliore struttura di dati da utilizzare per una relazione di discendenza?

Question

Deve esistere una struttura di dati standard per contenere, ad esempio, informazioni sull'allevamento dei cani, incroci genetici vegetali e relazioni umane complesse.

Si potrebbe pensare che sarebbe una struttura ad albero facile, ma la combinazione di due (o più, per ingegneria genetica) genitori per progenie, più discendenti per gruppo genitore, più movimenti di genitori (cavalli da monta si accoppiano con molti altri cavalli ), l'adozione, ecc. rende questa struttura molto frammentata.

Mi aspetto che qualcuno abbia già affrontato questo problema. Qualche risorsa che dovrei esaminare?

Answer 1

I think what you have is just a simple relational database, where the main relation is "child_of", "direct_descendant", etc.

Of course, the particular data structure here is acyclic, and you might want to do transitive queries (descendant of descendant of ...), which are not usually supported by standard SQL engines.

So if you want to do it in memory, you could us a directed acyclic graph (DAG).

Answer 2

Smells like a DAG. If the directed and acyclic is too limiting, you might want to look at the graph theory data-structures.

Using graphs for abstract problems, vertices represent entities and the edges represent the relationship.