Basic Adjacency List Questions

ancestors.py

# 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 positive integer identifier.

# For example, in this diagram, the earliest ancestor of 6 is 14, and the earliest ancestor of 15 is 2. 

#          14
#          |
#   2      4
#   |    / | \
#   3   5  8  9
#  / \ / \     \
# 15  6   7    11

# Write a function that, for a given individual in our dataset, returns their earliest known ancestor -- the one at the farthest distance from the input
# individual. If there is more than one ancestor tied for "earliest", return any one of them. If the input individual has no parents, the function should return null (or -1).

# Sample input and output:

# parent_child_pairs_3 = [
#     (2, 3), (3, 15), (3, 6), (5, 6), (5, 7),
#     (4, 5), (4, 8), (4, 9), (9, 11), (14, 4),
# ]

# find_earliest_ancestor(parent_child_pairs_3, 8) => 14
# find_earliest_ancestor(parent_child_pairs_3, 7) => 14
# find_earliest_ancestor(parent_child_pairs_3, 6) => 14
# find_earliest_ancestor(parent_child_pairs_3, 15) => 2
# find_earliest_ancestor(parent_child_pairs_3, 14) => null or -1
# find_earliest_ancestor(parent_child_pairs_3, 11) => 14


# Additional example:

#   14
#   |
#   2      4    1
#   |    / | \ /
#   3   5  8  9
#  / \ / \     \
# 15  6   7    11

# parent_child_pairs_4 = [
#     (2, 3), (3, 15), (3, 6), (5, 6), (5, 7),
#     (4, 5), (4, 8), (4, 9), (9, 11), (14, 2), (1, 9)
# ]

# find_earliest_ancestor(parent_child_pairs_4, 8) => 4
# find_earliest_ancestor(parent_child_pairs_4, 7) => 4
# find_earliest_ancestor(parent_child_pairs_4, 6) => 14
# find_earliest_ancestor(parent_child_pairs_4, 15) => 14
# find_earliest_ancestor(parent_child_pairs_4, 14) => null or -1
# find_earliest_ancestor(parent_child_pairs_4, 11) => 4 or 1

# n: number of pairs in the input




parent_child_pairs = [
    (1, 3), (2, 3), (3, 6), (5, 6), (15, 9),
    (5, 7), (4, 5), (4, 8), (4, 9), (9, 11)
]

def find_num_parents(pairs):
    adj_graph = dict()
    
    for pair in pairs:
        if pair[1] in adj_graph:
            adj_graph[pair[1]].add(pair[0])
        else:
            adj_graph[pair[1]] = { pair[0] }
        
        if pair[0] not in adj_graph:
            adj_graph[pair[0]] = set()
            
    zero_parents = list()
    one_parent = list()
    
    for k, v in adj_graph.items():
        if len(v) == 1:
            one_parent.append(k)
        elif len(v) == 0:
            zero_parents.append(k)
            
    return [zero_parents, one_parent]

# print(find_num_parents(parent_child_pairs))

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),
    (15, 13)
]

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


def has_common_ancestor(pairs, a, b):
    adj_graph = dict()
    
    for pair in pairs:
        if pair[1] in adj_graph:
            adj_graph[pair[1]].add(pair[0])
        else:
            adj_graph[pair[1]] = { pair[0] }
        
        if pair[0] not in adj_graph:
            adj_graph[pair[0]] = set()
    
    a_ancestors = set()
    b_ancestors = set()
    
    def dfs(visited, node):
        for parent in adj_graph[node]:
            visited.add(parent)
            dfs(visited, parent)
    dfs(a_ancestors, a)
    dfs(b_ancestors, b)
    
    return len(a_ancestors.intersection(b_ancestors)) > 0

# print(has_common_ancestor(parent_child_pairs_1, 3, 8))
# print(has_common_ancestor(parent_child_pairs_1, 5, 8))
# print(has_common_ancestor(parent_child_pairs_1, 6, 8))
# print(has_common_ancestor(parent_child_pairs_1, 6, 9))
# print(has_common_ancestor(parent_child_pairs_1, 1, 3))
# print(has_common_ancestor(parent_child_pairs_1, 3, 1))
# print(has_common_ancestor(parent_child_pairs_1, 7, 11))
# print(has_common_ancestor(parent_child_pairs_1, 6, 5))
# print(has_common_ancestor(parent_child_pairs_1, 5, 6))


def find_earliest_ancestor(pairs, x):
    adj_graph = dict()
    
    for pair in pairs:
        if pair[1] in adj_graph:
            adj_graph[pair[1]].add(pair[0])
        else:
            adj_graph[pair[1]] = { pair[0] }
        
        if pair[0] not in adj_graph:
            adj_graph[pair[0]] = set()
    
    # edge case
    if x not in adj_graph or not adj_graph[x]:
        return None
    
    def dfs(node, depth):
        if not adj_graph[node]:
            return (depth, node)
        max_depth = 0
        max_node = None
        for parent in adj_graph[node]:
            d, n = dfs(parent, depth + 1)
            if d > max_depth:
                max_depth = d
                max_node = n
            
        return max_depth, max_node
            
    max_depth, max_node = dfs(x, 0)
    
    return max_node

parent_child_pairs_3 = [
    (2, 3), (3, 15), (3, 6), (5, 6), (5, 7),
    (4, 5), (4, 8), (4, 9), (9, 11), (14, 4),
]

# print(find_earliest_ancestor(parent_child_pairs_3, 8))
# print(find_earliest_ancestor(parent_child_pairs_3, 7))
# print(find_earliest_ancestor(parent_child_pairs_3, 6))
# print(find_earliest_ancestor(parent_child_pairs_3, 15))
# print(find_earliest_ancestor(parent_child_pairs_3, 14))
# print(find_earliest_ancestor(parent_child_pairs_3, 11))

parent_child_pairs_4 = [
    (2, 3), (3, 15), (3, 6), (5, 6), (5, 7),
    (4, 5), (4, 8), (4, 9), (9, 11), (14, 2), (1, 9)
]


print(find_earliest_ancestor(parent_child_pairs_4, 8))
print(find_earliest_ancestor(parent_child_pairs_4, 7))
print(find_earliest_ancestor(parent_child_pairs_4, 6))
print(find_earliest_ancestor(parent_child_pairs_4, 15))
print(find_earliest_ancestor(parent_child_pairs_4, 14))
print(find_earliest_ancestor(parent_child_pairs_4, 11))