Find Common Ancestors

find_common_ancestor.py

"""
PROBLEM

Suppose we have some input data describing a graph of relationships between
parents and children over multiple generations. The data is formatted as a
list of (parent, child) pairs, where each individual is assigned a unique
integer identifier.

For example, in this diagram, 6 and 8 have common ancestors of 4 and 14.

         14  13
         |   |
1   2    4   12
 \ /   / | \ /
  3   5  8  9
   \ / \     \
    6   7     11

parent_child_pairs_1 = [
    (1, 3), (2, 3), (3, 6), (5, 6), (5, 7), (4, 5),
    (4, 8), (4, 9), (9, 11), (14, 4), (13, 12), (12, 9)
]

Write a function that takes the graph, as well as two of the individuals in our
dataset, as its inputs and returns true if and only if they share at least one
ancestor.

Sample input and output:

has_common_ancestor(parent_child_pairs_1, 3, 8) => false
has_common_ancestor(parent_child_pairs_1, 5, 8) => true
has_common_ancestor(parent_child_pairs_1, 6, 8) => true
has_common_ancestor(parent_child_pairs_1, 6, 9) => true
has_common_ancestor(parent_child_pairs_1, 1, 3) => false
has_common_ancestor(parent_child_pairs_1, 3, 1) => false
has_common_ancestor(parent_child_pairs_1, 7, 11) => true
has_common_ancestor(parent_child_pairs_1, 6, 5) => true
has_common_ancestor(parent_child_pairs_1, 5, 6) => true

Additional example: In this diagram, 4 and 12 have a common ancestor of 11.

        11
       /  \
      10   12
     /  \
1   2    5
 \ /    / \
  3    6   7
   \        \
    4        8

parent_child_pairs_2 = [
    (11, 10), (11, 12), (2, 3), (10, 2), (10, 5),
    (1, 3), (3, 4), (5, 6), (5, 7), (7, 8),
]

has_common_ancestor(parent_child_pairs_2, 4, 12) => true
has_common_ancestor(parent_child_pairs_2, 1, 6) => false
has_common_ancestor(parent_child_pairs_2, 1, 12) => false

n: number of pairs in the input
-----------------------------------------------------------------------------

SOLUTION

Step 1: Build an adjacency list (child -> list of parents).

    graph = {
        10: [11],
        12: [11],
        3: [2, 1],
        4: [3],
        2: [10],
        5: [10],
        6: [5],
        7: [5],
        8: [7],
    }

Step 2: Traverse the tree upwards collecting all the ancestors for each node.

    Node 1:
    4 -> [3, 2, 1, 10, 11]

    Node 2:
    12 -> [11]

Step 3: Return whether the set intersection of both node's ancestors has any members.
-----------------------------------------------------------------------------

GRADING

Communication = 3/5
Problem-Solving = 5/5
Syntax = 5/5
Verification = 4/5

Total: 17/20
"""

from typing import List, Tuple
from collections import defaultdict, deque
import operator
from functools import reduce


def has_common_ancestor(
    parent_child_pairs: List[Tuple[int, int]], node1: int, node2: int
) -> bool:
    def build_graph(parent_child_pairs):
        graph = defaultdict(list)
        for parent, child in parent_child_pairs:
            graph[child].append(parent)
        return graph

    def get_ancestors_bfs(root, graph):
        ancestors = set()
        queue = deque([root])
        while queue:
            node = queue.popleft()
            # A node is not it's own ancestor
            if node is not root:
                ancestors.add(node)
            queue.extend(graph[node])

        return ancestors

    graph = build_graph(parent_child_pairs)
    ancestors = [get_ancestors_bfs(node, graph) for node in (node1, node2)]
    common_ancestors = reduce(operator.iand, ancestors)
    return bool(common_ancestors)


parent_child_pairs_1 = [
    (1, 3),
    (2, 3),
    (3, 6),
    (5, 6),
    (5, 7),
    (4, 5),
    (4, 8),
    (4, 9),
    (9, 11),
    (14, 4),
    (13, 12),
    (12, 9),
]
parent_child_pairs_2 = [
    (11, 10),
    (11, 12),
    (2, 3),
    (10, 2),
    (10, 5),
    (1, 3),
    (3, 4),
    (5, 6),
    (5, 7),
    (7, 8),
]

import pytest


@pytest.mark.parametrize(
    "parent_child_pairs, node1, node2, expected",
    [
        (parent_child_pairs_1, 3, 8, False),
        (parent_child_pairs_1, 5, 8, True),
        (parent_child_pairs_1, 6, 8, True),
        (parent_child_pairs_1, 6, 9, True),
        (parent_child_pairs_1, 1, 3, False),
        (parent_child_pairs_1, 3, 1, False),
        (parent_child_pairs_1, 7, 11, True),
        (parent_child_pairs_1, 6, 5, True),
        (parent_child_pairs_1, 5, 6, True),
        (parent_child_pairs_2, 4, 12, True),
        (parent_child_pairs_2, 1, 6, False),
        (parent_child_pairs_2, 1, 12, False),
    ],
)
def test_solution(parent_child_pairs, node1, node2, expected):
    result = has_common_ancestor(parent_child_pairs, node1, node2)
    assert result == expected


if __name__ == "__main__":
    pytest.main([__file__])