Say I have for example the following nested list:
L = [['John','Sayyed'], ['John' , 'Simon'] ,['bush','trump'],
['Sam','Suri','NewYork'],['Suri','Orlando','Canada']]
How can I group these sublists, by getting the union of sublists which have a common element with at least another sublist within the group? So for the previous example the result should be:
[['John','Sayyed','Simon'] ,['bush','trump'],
['Sam','Suri','NewYork','Orlando','Canada']]
Thus the first two sublists are joined as they share 'John'
.
Could someone please share their valuable thoughts ?
In many cases, modeling a problem as a graph, can make make fairly complicated tasks much easier. In this case, what we'd be looking for from a graph theory point of view, are the connected components of the graph.
So a simple way to go about this, is to generate a graph with NetworkX, and add your list as the graph edges using add_edges_from
. Then use connected_components
, which will precisely give you a list of sets of the connected components in the graph:
import networkx as nx
L = [['John','Sayyed'], ['John' , 'Simon'] ,['bush','trump']]
G=nx.Graph()
G.add_edges_from(L)
list(nx.connected_components(G))
[{'John', 'Sayyed', 'Simon'}, {'bush', 'trump'}]
In the case of having sublists with more than 2
elements, you can add them as paths instead of nodes using nx.add_path
, since they can connect multiple nodes:
L = [['John','Sayyed'], ['John' , 'Simon'] ,['bush','trump'],
['Sam','Suri','NewYork'],['Suri','Orlando','Canada']]
G=nx.Graph()
for l in L:
nx.add_path(G, l)
list(nx.connected_components(G))
[{'John', 'Sayyed', 'Simon'},
{'bush', 'trump'},
{'Canada', 'NewYork', 'Orlando', 'Sam', 'Suri'}]
We can also vivisualize these connected components with nx.draw
:
pos = nx.spring_layout(G, scale=20, k=2/np.sqrt(G.order()))
nx.draw(G, pos, node_color='lightgreen', node_size=1000, with_labels=True)
More detailed explanation on connected components:
In graph theory, a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph
So essentially, this code creates a graph, with edges from the list, where each edge is composed by two values u,v
where u
and v
will be nodes connected by this edge.
And hence, the union of sublists with at least one sublist with a common element can be translated into a Graph Theory problem as all nodes that are reachable between each other through the existing paths.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With