mcfly mcfly - 1 year ago 86
Python Question

Find all common elements and combinations in tuples using Python

I am trying to group all values together that share common elements across tuples - essentially find groups of numbers that for any combination of them (no order required) - I have the tuple. For example, if I have the following set of tuples:

(1,2),(1,3),(1,5),(1,6),(2,3),(2,5),(2,7),(3,5),(3,7),(3,9)


I want to understand all the elements that are in common. For this example, this would be:

1, 2, 3, 5 (since I have any combination of 1,2,3 and 5)
2, 3, 7 (since I have any combination of 2,3 and 7)
1, 6 (since I have any combination of 1 and 6)
3, 9 (since I have any combination of 3 and 9)


Any thoughts on how to solve this?

Answer Source

As mentioned by @alfasin, you're looking for the maximal cliques in your graph.

A clique, C, in an undirected graph G = (V, E) is a subset of the vertices, C ⊆ V, such that every two distinct vertices are adjacent.

A maximal clique is a clique that cannot be extended by including one more adjacent vertex, that is, a clique which does not exist exclusively within the vertex set of a larger clique.

NetworkX with find_cliques is your friend:

>>> import networkx as nx
>>> G = nx.Graph([(1,2),(1,3),(1,5),(1,6),(2,3),(2,5),(2,7),(3,5),(3,7),(3,9)])
>>> list(nx.find_cliques(G))
[[3, 9], [3, 2, 1, 5], [3, 2, 7], [6, 1]]
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download