Headline:Scanning Family trees with Dijkstra's algorithm, in JavaScript
Date:Friday, May 29, 2020
Posted By:Plaid Hatter Games

When I world build, I tend to world-build like a Technocrat. Not only does the world have to make sense from a physics side (even if there is magic), it also has to make sense from a record keeping side.

I have been toying with the idea of including some sort of dating sim in my game, and it occurred to me that in small populations, one really has to keep track of who is related to who. The problem is so profound in places like Iceland, dating apps exist to ensure you don't accidentally hook up with a relative.

Space adventurers are going to have some, shall we say, complex mating habits. Many will kling to the old ways where a he and a she mate for life. Others will hook up and get knocked up more or less at random. Still others are going to adopt some sort of monogamous polyandry. And there will be still others, like the specialist, who are conceived in a lab from random sperm and ova. Oh yes... and clones...

Regardless of who mated, how, and why, we do know that for conception to happen there has to be a male and female. Their relationship to one another and the circumstances of their union we will leave as an external complexity. In the case of identical twins and clones we know that even though the individual is a different organism, their genetic code and ancestors will be the same.

What emerges is a database record that lists each person and their (assumed) direct male ancestor and their direct female ancestor. From there we form a tree of ancestry that can be searched to produce metrics like our conventional "brother/sister","aunt/uncle", "first cousins", and so on.

var Characters = {
  "25bd86-13798ff0": {
    "name_first": "Steven",
    "name_last": "Patel",
    "name_maiden": "",
    "gender": "Male",
    "generation": 1,
    "age": 41,
    "born": 2473350,
    "spouse": "25b9ac-5fdd982c",
    "father": "256ae6-a4521515",
    "mother": "257304-f8ee0df7",
    "vocation": "",
    "deceased": ""
  }
}

All of this information would be captured on a normal birth certificate. Sometimes the mother and father would be unknown individuals. Unknown because they are not listed in the system, or unknown because, well, the facts surrounding the child's conception are somewhat nebulous. This could be from a number of causes. The individual could be a foundling. The mother could have sex (consensual or not) with a stranger. The mother could have had sex with someone who was not her spouse. And there are the science fiction X factors of test tube babies, engineered organism, and clones.

I suspect that rather than use birth certificates, any decent system would actually sample the DNA from every child and file away genetic markers. That genetic analysis would be able to identify common ancestors enough for genetic screening purposes without having to bring up questions about who was sleeping with who decades before. I suspect that system would also be shielded by a number of privacy regulations.

The system that would emerge would probably be something similar to that bump app in Iceland. Rather than know all of the details, two interested parties can punch their identifiers into a system and get back a simple number of how closely related they are. Everyone's genes are probably sampled and indexed when they enter the system, so the computer can work with that, and not violate anyone's privacy. Or have to provide uncomfortable answers about disputed parentage.

The system I wrote assumes that the identity of the father and the mother are known and accurate and indexed using some sort of Government Identification Number. Mainly because, this is fiction and I can say they are. From that we work backwards to develop a Coefficient of relationship.

A real system would have to list all sorts of DNA profiling metrics. The coefficient produced would be an actual read of the individual's genetic profile, and not based on assumptions made during the capture of vital records onto birth certificates.

Regardless of whether we are working backwards from birth certificates or performing numerical analysis on dna markers, the coefficient is still the same. It's a number between 0 and 1.0 indicating how much two individuals have in common, at least genetically speaking. An individual is a 1.0 match to him/her self, any clones of theirs, and any identical twins. From there the number gets smaller and smaller the more distant the relation.

Here is a handy table of coefficients of kinship, degrees of kinship, and common human family relationships.

Coefficient Relations Expression
1.0 self / clone / identical twin 1.0
0.5 parent / child 2.0**-1.0
0.5 full sibling 2.0*2.0**-2.0
0.25 half sibling 2.0**-2.0
0.25 grandparent / grandchild 2.0**-2.0
0.25 aunt / uncle / nephew / niece 2.0*2.0**-3.0
0.125 first cousin 2.0*2.0**-4.0
0.0625 first cousin once removed 2.0*2.0**-5.0
0.03125 second cousin 2.0*2.0**-6.0
0.0078125 third cousin 2.0*2.0**-8.0
0.001953125 fourth cousin 2.0*2.0**-10.0

In all jurisdictions a pairing of higher than 0.25 is considered a verboten pairing. Many also cast at least a serious side-eye to first-cousin (0.125) pairings. But, let's just assume the metric delivers a number and the parties do with that number as they see fit.

For story telling/expert system purposes I need this factor as a safety to drive behavior. Some of my characters are probably going to engage is procedurally generated banter and flirting. Having an "incest metric" ensures that they avoid flirty dialog with relatives.

I am envisioning similar metrics for other group affiliations.

The tree structured nature of the database lends itself to Dijkstra's algorithm. As I move from record to record, I connect them with a link. That link, instead of "distance" or "time" is marked with "relation", "degree", and "generation". This allows me to capture cases like spouses of blood relatives, and their various relations. I can also use that information to distinguish cousins from aunts even though the related coefficient is the same.

The output for Leonard, son of Steven, looks like:

Tests for 25e0f3-e6750bd6 Patel-Reid, Leonard
 *** BEGIN FAMILY ***
{"entity":"25e0f3-e6750bd6","distance":0,"related":1,"generation":0}
{"entity":"25bd86-13798ff0","type":"father","of":"25e0f3-e6750bd6","distance":1,"related":0.5,"generation":-1}
{"entity":"256ae6-a4521515","type":"father","of":"25bd86-13798ff0","distance":2,"related":0.25,"generation":-2}
{"entity":"257304-f8ee0df7","type":"mother","of":"25bd86-13798ff0","distance":2,"related":0.25,"generation":-2}
{"entity":"25bbcf-2f7f13a5","type":"mother","of":"25e0f3-e6750bd6","distance":1,"related":0.5,"generation":-1}
{"entity":"25dedd-269fc4f0","type":"child","of":"25bbcf-2f7f13a5","distance":2,"related":0.5,"generation":0}
{"entity":"25ba96-f1b7af10","type":"spouse","of":"25bbcf-2f7f13a5","distance":2,"related":0,"generation":-1}
{"entity":"25ddcc-1ff6fdd2","type":"child","of":"25ba96-f1b7af10","distance":3,"related":0,"generation":0}
{"entity":"25df06-3cdec35a","type":"child","of":"25ba96-f1b7af10","distance":3,"related":0,"generation":0}
{"entity":"25b675-36634981","type":"child","of":"257304-f8ee0df7","distance":3,"related":0.25,"generation":-1}
{"entity":"25e26e-5cd95ff8","type":"child","of":"25b675-36634981","distance":4,"related":0.125,"generation":0}
{"entity":"25dedf-228f955e","type":"child","of":"25b675-36634981","distance":4,"related":0.125,"generation":0}
{"entity":"25af05-1e298d16","type":"spouse","of":"25b675-36634981","distance":4,"related":0,"generation":-1}
{"entity":"25b9ac-5fdd982c","type":"spouse","of":"25bd86-13798ff0","distance":2,"related":0,"generation":-1}
 *** END FAMILY ***

I can also run the analysis from the other end with his cousin, Priya

Tests for 25dedf-228f955e Dutta, Priya
 *** BEGIN FAMILY ***
{"entity":"25dedf-228f955e","distance":0,"related":1,"generation":0}
{"entity":"25af05-1e298d16","type":"father","of":"25dedf-228f955e","distance":1,"related":0.5,"generation":-1}
{"entity":"25b675-36634981","type":"mother","of":"25dedf-228f955e","distance":1,"related":0.5,"generation":-1}
{"entity":"256ae6-a4521515","type":"father","of":"25b675-36634981","distance":2,"related":0.25,"generation":-2}
{"entity":"257304-f8ee0df7","type":"mother","of":"25b675-36634981","distance":2,"related":0.25,"generation":-2}
{"entity":"25bd86-13798ff0","type":"child","of":"257304-f8ee0df7","distance":3,"related":0.25,"generation":-1}
{"entity":"25e0f3-e6750bd6","type":"child","of":"25bd86-13798ff0","distance":4,"related":0.125,"generation":0}
{"entity":"25dedd-269fc4f0","type":"child","of":"25bd86-13798ff0","distance":4,"related":0.125,"generation":0}
{"entity":"25b9ac-5fdd982c","type":"spouse","of":"25bd86-13798ff0","distance":4,"related":0,"generation":-1}
{"entity":"25ddcc-1ff6fdd2","type":"child","of":"25b9ac-5fdd982c","distance":5,"related":0,"generation":0}
{"entity":"25df06-3cdec35a","type":"child","of":"25b9ac-5fdd982c","distance":5,"related":0,"generation":0}
{"entity":"25e26e-5cd95ff8","type":"child","of":"25b675-36634981","distance":2,"related":0.5,"generation":0}
 *** END FAMILY ***

It's hard to read without the entire database in front of you, so here is a quick pictorial family tree:

Sharp eyes will note two relations on Leonards map that are not on Priya's. Those would be Leonard's Sisters. Leonard has a blended family where two homosexual couples paired up to have children with each other. Leonard and his full brother Benjamin have two sisters, Ellen and Sydney that are not actually blood related. But they are considered a relation for family purposes. Priya's search stops at spouses of blood relatives. Leonard's includes children of spouses.

Compare that family situation with a more, shall we say, complex one. That of Anastasia Von Aalen:

Tests for 25daa4-ed67b990 Von Aalen, Anastasia
 *** BEGIN FAMILY ***
{"entity":"25daa4-ed67b990","distance":0,"related":1,"generation":0}
{"entity":"25ab5e-e4be31a9","type":"father","of":"25daa4-ed67b990","distance":1,"related":0.5,"generation":-1}
{"entity":"25bda6-dca1e70d","type":"mother","of":"25daa4-ed67b990","distance":1,"related":0.5,"generation":-1}
{"entity":"25e53c-93e5ec9f","type":"child","of":"25bda6-dca1e70d","distance":2,"related":0.25,"generation":0}
{"entity":"25e374-d0317d37","type":"child","of":"25bda6-dca1e70d","distance":2,"related":0.25,"generation":0}
{"entity":"25e836-ac56ec6a","type":"child","of":"25ab5e-e4be31a9","distance":2,"related":0.25,"generation":0}
{"entity":"25e3da-c4f4e99d","type":"child","of":"25ab5e-e4be31a9","distance":2,"related":0.25,"generation":0}
{"entity":"25e151-dc51ff18","type":"child","of":"25ab5e-e4be31a9","distance":2,"related":0.25,"generation":0}
{"entity":"25bc8f-6297b07c","type":"spouse","of":"25ab5e-e4be31a9","distance":2,"related":0,"generation":-1}
 *** END FAMILY ***

On the surface, this looks pretty straightforward. There is Anastasia. And her mother. And her father. And some children of her mother and father. Hmm. And a spouse?

Here is the situation in picture form.

Long story short, Anastasia's mom had kids by three different men. And those men had kids by several different women. And each of those women had kids by several differen men. The boxes with the dashed lines are blood relatives of Anastasia's half-siblings that will not be listed on her map, but would be listed on theirs.

At this point I could write a short story on how that situation must play out for family get-togethers. But as crazy as that contrived situation may seem (to some of us), it is probably relatively simple compared to the real-life situations of other people.

The best is going to be down the road when I start staging sequels after a few more generations have lived on board. My head is already starting to hurt...