What is the best data structure to use for an offspring relationship?

Question

There must be a standard data structure to hold, for instance, dog breeding information, plant genetic crossbreeding, and complex human relationships.

One might think it would be an easy tree structure, but the combination of two (or more, for genetic engineering) parents per offspring, multiple different offspring per parent set, multiple moves of parents (stud horses mate with many other horses), adoption, etc makes this a very fragmented structure.

I expect someone has tackled this before though. Any resources I should look into?

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.