Handle Transitivity in Python

Question

I have set of pairwise relationship something like this

col_combi = [('a','b'), ('b','c'), ('d','e'), ('l','j'), ('c','g'), 
             ('e','m'), ('m','z'), ('z','p'), ('t','k'), ('k', 'n'), 
             ('j','k')]

Number of such relationship is big enough to check it individually. These tuple indicates that both values are same. I would like to apply transitivity and find out common groups. Output would be like following:

[('a','b','c','g'), ('d','e','m','z','p'), ('t','k','n','l','j')]

I tried following code but it has bug,

common_cols = []
common_group_count = 0

for (c1, c2) in col_combi:
    found = False
    for i in range(len(common_cols)):
        if (c1 in common_cols[i]):
            common_cols[i].append(c2)
            found = True
            break
        elif (c2 in common_cols[i]):
            common_cols[i].append(c1)
            found = True
            break
    if not found:
        common_cols.append([c1,c2])

Output of above code is following

[['a', 'b', 'c', 'g'], ['d', 'e', 'm', 'z', 'p'], ['l', 'j', 'k'], ['t', 'k', 'n']]

I know why this code is not working. So I would like to know how can I perform this task.

Thanks in advance

Answer 1

You can approach this as a graph problem using the NetworkX library:

import networkx

col_combi = [('a','b'), ('b','c'), ('d','e'), ('l','j'), ('c','g'), 
             ('e','m'), ('m','z'), ('z','p'), ('t','k'), ('k', 'n'), 
             ('j','k')]

g = networkx.Graph(col_combi)

for subgraph in networkx.connected_component_subgraphs(g):
    print subgraph.nodes()

Output:

['m', 'z', 'e', 'd', 'p']
['t', 'k', 'j', 'l', 'n']
['a', 'c', 'b', 'g']