python - Merging tuples if they have one common element

Question

Consider the following list:

tuple_list = [('c', 'e'), ('c', 'd'), ('a', 'b'), ('d', 'e')]

How can I achieve this?

new_tuple_list = [('c', 'e', 'd'), ('a', 'b')]

I have tried:

for tuple in tuple_list:
    for tup in tuple_list:
        if tuple[0] == tup[0]:
            new_tup = (tuple[0],tuple[1],tup[1])
            new_tuple_list.append(new_tup)

But it only works if I have the elements of the tuple in a certain order which means it will result in this instead:

new_tuple_list = [('c', 'e', 'd'), ('a', 'b'), ('d', 'e')]

Answer 1

You could consider the tuples as edges in a graph and your goal as finding connected components within the graph. Then you could simply loop over vertices (items in tuples) and for each vertex you haven't visited yet execute DFS to generate a component:

from collections import defaultdict

def dfs(adj_list, visited, vertex, result, key):
    visited.add(vertex)
    result[key].append(vertex)
    for neighbor in adj_list[vertex]:
        if neighbor not in visited:
            dfs(adj_list, visited, neighbor, result, key)

edges = [('c', 'e'), ('c', 'd'), ('a', 'b'), ('d', 'e')]

adj_list = defaultdict(list)
for x, y in edges:
    adj_list[x].append(y)
    adj_list[y].append(x)

result = defaultdict(list)
visited = set()
for vertex in adj_list:
    if vertex not in visited:
        dfs(adj_list, visited, vertex, result, vertex)

print(result.values())

Output:

[['a', 'b'], ['c', 'e', 'd']]

Note that in above both the components and elements within a component are in random order.