What structure and algorithm use for building genealogy tree?

Question

I found in one book, that for presenting genealogy (family) tree good to use DAG (directed acyclic graph) with topological sorting, but this algorithm is depending on order of input data.

Answer 1

Genealogy databases typically use what's called a lineage-linked structure.

This means that partners (husbands/wives) are linked and called a family. And a family is linked to it's children with a link back from the children to its parent family.

I do not know of a specific graph type that represents this. Most programs custom program it with a family table and an individual table with the appropriate links between them.

Genealogy databases generally follow this structure to match the GEDCOM (Genealogy Data Communications) standard that was developed to allow transfer of data between programs.

In that standard, you'll specifically see FAM and INDI records. FAM records are connected to INDI records with HUSB, WIFE and CHIL links. INDI records are connected to FAM records with FAMS (spouse) and FAMC (parent) links.

Using this data structure will allow you easily to read a GEDCOM file and import data from other genealogy software, and also export your data to a GEDCOM file so that other genealogy programs can read it.

Answer 2

In genealogy, the so-called Ahnentafel indexing (German for "ancestor table") is used for representation of the ancestors of a single person; basically this is a suitable linearization of a binary tree.