How related are two relatives?

Question

The coefficient of relationship refers to how much DNA two persons have in common. A parent has 50% common DNA with their child (unless the parents are related), so to calculate it we have to find all pairs of directed disjoint paths starting at same node (common ancestor) and ending at each of the two siblings, and sum 2^-(m+n) for all pairs of paths of length m and n.

Your program should accept a list of pairs of numbers (or names if you prefer) representing parent-child relations followed by another pair of number for which it should output the coefficient of relationship (either as a fraction, a decimal number, or a percentage).

For example:

Format: [list of parent-child relations] pair of relatives we want to compare -> expected output
-----------------------------------------------
[(1,2)] (1, 2) -> 50% (parent-child)
[(1,2), (2, 3), (3, 4)] (2, 3) -> 50% (still parent-child, make sure your path pairs are disjoint)
[(1,3), (2, 3)] (1, 2) -> 0% (not related, make sure your paths are directed)
[(1, 2), (2, 3)] (1, 3) -> 25% (grandparent-child)
[(1, 3), (1, 4), (2, 3), (2, 4)] (3, 4) -> 50% (siblings)
[(1, 2), (1, 3)] (2, 3) -> 25% (half-siblings)
[(1, 3), (1, 4), (2, 3), (2, 4), (3, 5)] (4, 5) -> 25% (aunt/uncle-nephew/niece)
[(1, 3), (1, 4), (2, 3), (2, 4), (3, 5), (4, 6)] (5, 6) -> 12.5% (cousins)
[(1, 3), (1, 4), (2, 3), (2, 4), (5, 7), (5, 8), (6, 7), (6, 8), (3, 9), (7, 9), (4, 10), (8, 10)] (9, 10) -> 25% (double cousins)
[(1, 3), (1, 4), (2, 3), (2, 4), (3, 5), (4, 5)] (3, 5) -> 75% (parent-(child-with-sibling) incest)
[(1, 2), (1, 3), (2, 3)] (1, 3) -> 75% ((parent-and-grandparent)-(child-with-child) incest)

No person will have more than two parents and there will be no cycles in it. You can also assume that the number is the order in which they were born (so a < b in all (a, b)).

Answer 1

Python 3, 259 247 226 bytes

lambda l,a,b:sum(2**-len({*m}^{*n})for v in{*sum(l,())}for m in p(v,a,l)for n in p(v,b,l)if not{*zip(m,m[1:])}&{*zip(n,n[1:])})
p=lambda i,j,l:sum([[[r+[i]for r in p(y,j,l)],[[y,x]]][j==y]for x,y in l if i==x],[])+[[i]]*(i==j)

Try it online!

This can probably be golfed down quite a bit, but for now I'm just happy it works.

Answer 2

Python3, 206 bytes:

lambda l,a:(a in l)/2+sum(2**-len((x|y)-(x&y))for x in f(a[0],l,a)for y in f(a[1],l,a)if x&y)
def f(n,l,o,p=[],K=1):
 for a,b in l:
  if(b==n)&(K:=[a,b]!=o):yield from f(a,l,o,p+[b]);K=0
 if K:yield{*p+[n]}

Try it online!

Answer 3

Wolfram Language (Mathematica), 188 166 154 bytes

e_~h~f_:=4Tr[2^-Tr[Length/@#]&/@Select[Flatten[Tuples[i@r_:=If[#==r,{{r}},FindPath[g,#,r,∞,All]];i/@f]&/@VertexList[g=Rule@@@e],1],DisjointQ@@Rest/@#&]]

Try it online!