mcfly - 1 year ago 68

Python Question

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?

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

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**