Your task is, given a family tree, to calculate the Coefficient of Inbreeding for a given person in it.
Definition
The Coefficient of Inbreeding is equal to the Coefficient of Relationship of the parents. The Coefficient of Relationship between two people is defined as weighed sum over all common ancestry as follows:
Each simple path P (meaning it visits no node more than once) which goes upwards to a common ancestor from A and then down to B adds \$(\frac{1}{2})^{length(P)}\$ to the Coefficient. Also, if A is an ancestor of B (or vice versa), each simple path linking them also adds \$(\frac{1}{2})^{length(P)}\$ to the Coefficient.
Challenge Rules
- Input consists of a directed graph representing the family tree and a single identifier for a node of the graph. As usual, any convenient method is valid.
- The graph can be input in any convenient representation. Used below is a csv style in which each line represents a marriage between the first two entries, with the offspring being all following entries. Other representations, like a list of parent-child pairs, or a connectivity matrix, are also allowed.
- Similarly, the node identifier can be in any format working for that graph representation, like a string for the format used here, or an index for a connectivity matrix.
- Output is either (in any convenient method):
- A single rational number between 0 and 1, representing the Coefficient of Inbreeding for the identified node in the graph.
- Two integers, the second of which is a power of two such that the first number divided by the second is the Coefficient of Inbreeding (you do not need to reduce the fraction).
- In either case, make sure you have enough bits available to handle the given test cases (11 bits for the Charles II case) with full accuracy.
- Standard Loopholes are of course not allowed.
- You can assume the input graph to be well-formed as family tree, meaning you are allowed to fail in any way you want for the following cases:
- The graph being cyclic
- The node not being in the graph
- The node in question not having exactly 2 parent nodes
- The chosen input format not being followed
- This is code-golf. Shortest code for each language wins.
Test cases
1 In:
F;M;S;D
S;D;C
F;D;I
C
Out:
0.5
There are two paths of length 2: S-F-D and S-M-D, thus the total is \$(\frac{1}{2})^{2}+(\frac{1}{2})^{2}=0.5\$
2 In:
F;M;S;D
S;D;C
F;D;I
S
Out:
0
F and M have no common ancestors.
3 In:
F;M;S;D
S;D;C
F;D;I
I
Out:
0.5
F is direct ancestor of D with path length 1, thus the Coefficient is \$(\frac{1}{2})^{1}=0.5\$
4 In:
F;M1;S1;S2
F;M2;D1;D2
S1;D1;C1
S2;D2;C2
C1;C2;I
I
Out:
0.375
There are 6 paths of length 4: Two go over M1 and M2 as C1-S1-M1-S2-C2 and C1-D1-M2-D2-C2. The remaining four all are distinct ways to connect over F: C1-S1-F-S2-C2, C1-S1-F-D2-C2, C1-D1-F-S2-C2 and C1-D1-F-D2-C2
Thus the Coefficient is \$6 \cdot (\frac{1}{2})^{4}=0.375\$
5 In:
F;M;C1;C2;C3
F;C1;N1
C2;N1;N2
C3;N2;I
I
Out:
0.5
There are 5 contributing paths, 3 over F and 2 over M. Two paths for F have length 3: N2-N1-F-C3 and N2-C2-F-C3, and one has length 4: N2-N1-C1-F-C3. One path to M has length 3: N2-C2-M-C3 and one length 4: N2-N1-C1-M-C3
Thus the Coefficient is \$3 \cdot (\frac{1}{2})^{3}+2 \cdot (\frac{1}{2})^{4}=0.5\$
6 In:
Ptolemy V;Cleopatra I;Ptolemy VI;Cleopatra II;Ptolemy VIII
Ptolemy VI;Cleopatra II;Cleopatra III
Ptolemy VIII;Cleopatra III;Cleopatra IV;Ptolemy IX;Cleopatra Selene;Ptolemy X
Ptolemy IX;Cleopatra IV;Ptolemy XII
Ptolemy IX;Cleopatra Selene;Berenice III
Ptolemy X;Berenice III;Cleopatra V
Ptolemy XII;Cleopatra V;Cleopatra VII
Cleopatra VII
Out:
0.78125
or 200/256
There are 51 contributing paths, with lengths from 3 to 8. A full list can be found here.
7 In:
Philip I;Joanna;Charles V;Ferdinand I;Isabella 2
Isabella 1;Charles V;Maria;Philip II
Ferdinand I;Anna 1;Maximillian II;Charles IIa;Anna 2
Isabella 2;Christian II;Christina
Maria;Maximillian II;Anna 3
Anna 2;Albert V;Maria Anna 1;William V
Christina;Francis I;Renata
Philip II;Anna 3;Philip III
Charles IIa;Maria Anna 1;Margaret;Ferdinand II
William V;Renata;Maria Anna 2
Philip III;Margaret;Philip IV;Maria Anna 3
Ferdinand II;Maria Anna 2;Ferdinand III
Maria Anna 3;Ferdinand III;Mariana
Philip IV;Mariana;Charles IIb
Charles IIb
Out:
0.4267578125
or 874/2048
There are 64 contributing paths with lengths between 3 and 11. A full list can be found here.