CODEWITHSUNDEEP
algorithmgraph-algorithmdirected-acyclic-graphsgenealogy
user3013613
user3013613

Reputation: 77

What structure and algorithm use for building genealogy tree?

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.

Upvotes: 5

Views: 4552

Answers (4)

David A Stumpf
David A Stumpf

Reputation: 793

DAGs will not work. Might look at prior post using GEDCOM model in Neo4j

The lineages can have complex relationships such as double cousins, step-sibling marriages, consangienity, etc. These are easily managed in a non-sql data base such as Neo4j.

Upvotes: 1

coret
coret

Reputation: 211

To present the relations between people found in historic record, Open Archives uses a flexible force-directed graph layout implementation. In this graph every node is a person, and there are two types of vertices: one depicting a marriage (orange) and one depicting a parent relation (the red 'blood' line). An example of a graph can be seen here.

Upvotes: 1

lkessler
lkessler

Reputation: 20132

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.

Upvotes: 3

Codor
Codor

Reputation: 17605

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.

Upvotes: 1

Related Questions