grouping.py

"""
Input:     
    A -> B
    A -> C
    D -> A
    E -> F
    F -> C
    G -> H
    I -> J
    K -> L
    L -> M
    M -> N

Output:
    { A, B, C, D, E, F }
    { G, H }
    { I, J }
    { K, L, M, N }
"""

def get_groups_method_2(input_pairs):
    mapping = {}
    for pair in input_pairs:
        left = pair[0]
        right = pair[1]
        
        parent_left = None if left not in mapping else mapping[left]
        parent_right = None if right not in mapping else mapping[right]
        
        if parent_left is None and parent_right is None:
            mapping[left] = left
            mapping[right] = left
            continue
        
        if parent_left is not None and parent_right is not None:
            if parent_left == parent_right:
                continue
                
            top_left_parent = mapping[parent_left]
            top_right_parent = mapping[parent_right]
            while top_left_parent != mapping[top_left_parent]:
                mapping[left] = top_left_parent
                top_left_parent = mapping[top_left_parent]
                
            mapping[top_left_parent] = top_right_parent
            mapping[left] = top_right_parent
            
            continue
            
        if parent_left is None:
            mapping[left] = parent_right
        else:
            mapping[right] = parent_left
    
    groups = {}
    for elt, parent in mapping.items():
        if parent not in groups:
            groups[parent] = set()
        groups[parent].add(elt)
            
    return list(groups.values())
            

########################################################################################################################    
    

def get_groups_method_1(input_pairs):
    groups = []
    
    for pair in input_pairs:
        left = pair[0]
        right = pair[1]
        
        left_group = None
        right_group = None
        for i in range(0, len(groups)):
            group = groups[i]
            
            if left in group:
                left_group = (group, i)
                
            if right in group:
                right_group = (group, i)
        
        if left_group is not None and right_group is not None:
            merged = right_group[0].union(left_group[0])
            groups[right_group[1]] = merged
            groups.pop(left_group[1])
            continue
        
        if left_group is None and right_group is None:
            new_group = {left, right}
            groups.append(new_group)
            continue
            
        if left_group is None:
            right_group[0].add(left)
        else:
            left_group[0].add(right)
        
    return groups


########################################################################################################################


input = [('A', 'B'), 
         ('A', 'C'), 
         ('D', 'A'), 
         ('E', 'F'), 
         ('F', 'C'), 
         ('G', 'H'), 
         ('I', 'J'), 
         ('K', 'L'), 
         ('L', 'M'), 
         ('M', 'N')]
groups = get_groups_method_2(input)
print(groups)