Calculate Coefficient of Inbreeding

Question

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.

Answer 1

Jelly, 43 33 bytes

ịW€;Ɱ0ịịɗ¥€Ẏ¥ƬẎ¥€ŒpṪ€E$ƇF€QƑƇẈ.*S

Try it online!

A dyadic link taking the individual as the left argument and the pedigree as the right. The pedigree is a list of lists where each (possibly empty) list represents the parents of the person at that index. Returns a floating point number.

Explanation

ị                                 | Index into pedigree to find parents of desired individual
 W€                               | Wrap each in a list
               ¥€                 | For each parent:
            ¥Ƭ                    | - Do the following as a dyad, keeping intermediate results:
         ¥€                       |   - Do the following as a dyad for each member of the list
   ;Ɱ   ɗ                         |     - Concatenate the following (as a dyad) to the end of the list:
     0ị                           |       - Last member of the list
       ị                          |       - Indexed into pedigree to find parents
           Ẏ                      |   - Remove one level of lists (concatenating outer sublists together)
              Ẏ                   | - Remove one level of lists (concatenating outer sublists together)
                 Œp               | Cartesian product of the two lists of possible chains of ancestors for each parent
                      $Ƈ          | Keep those where:
                   Ṫ€             | - The tail of each chain (removing from the chain in the process)
                     E            | - Is equal
                        F€        | Flatten each
                            Ƈ     | Keep those where:
                           Ƒ      | - The list is invariant when:
                          Q       |   - Uniquified
                             Ẉ    | Lengths of each list
                              .*  | 0.5 to the power of the lengths
                                S | Sum

Answer 2

Python 2, 304 294 293 278 bytes

Takes as input: list of lists of relatives; name of person to calculate coefficient.

P={}
I,Z=input()
for R in I:
 for r in R[:2]:P[r]=P.get(r,[])+R[2:]
l=lambda c,p,X:c==Z and X.append(p)or c in P and[l(z,p*1+[z],X)for z in P[c]]and X
print sum(pow(.5,len(a+b)-2)for k in P for a in l(k,[],[])for b in l(k,[],[])if~-len(a+b)==len(set(a+b))if a>b if a[-2]!=b[-2])

Try it online!

---

Python 2, 274 bytes

If input is allowed as single list of lists, where last list contains name of person to calculate coefficient, some bytes can be saves, using leaked variable from for loop.

P={}
for Z in input():
 for r in Z[:2]:P[r]=P.get(r,[])+Z[2:]
l=lambda c,p,X:c==Z[0]and X.append(p)or c in P and[l(z,p*1+[z],X)for z in P[c]]and X
print sum(pow(.5,len(a+b)-2)for k in P for a in l(k,[],[])for b in l(k,[],[])if~-len(a+b)==len(set(a+b))if a>b if a[-2]!=b[-2])

Try it online!

---

Some explanation

# Converts input lists into dictionary, where keys - each parent
# and values - list of its children
# In this task we don't care about direct relations between any parents
P={}
for R in I:
 # for parents in cells [0] and [1] add cells [2:]
 for r in R[:2]:
  P[r] = P.get(r, []) + R[2:]

# Lambda collects all paths from node c to the person of interest
# It's recursive function, which stores all paths in argument X and then returns it
# Each paths is guarantied to have person of interest as last element
# and one of its parents as previous to last element
l=lambda c,p,X: c==Z and X.append(p) or c in P and [l(z, p*1+[z], X) for z in P[c]] and X

# For each node with children:
# calculate all paths to person of interest
# get all pairs of this paths
for k in P
 for a in l(k,[],[])for b in l(k,[],[]) 
# filters out dublicates
  if a>b 

# if paths from pair have unique items 
# (except only 1 same item, that each path have - person of interest)
# and if previous to last elements are different
# (i.e. paths through different parents)
  if ~-len(a+b)==len(set(a+b)) and a[-2]!=b[-2]

# This pair of paths forms simple inbreed path, so add up to result
   sum(pow(.5,len(a+b)-2) .. )

Note, that algorithm also covers cases when one of parents is ancestor to other one, as node of elder parent will produce similar paths, that will add up to result sum.