Combine lists with common elements

by

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'}]

What about sublists with multiple (>2) items?

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)

enter image description here

On connected components (graph theory)

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.

More Related Contents:

  1. Co-occurrence matrix from nested list of words
  2. I don’t know how to display step 3 for this assignment
  3. How do I concatenate items in a list to a single string?
  4. Split a string by a delimiter in python
  5. Access a particular field in arbitrarily nested JSON data [duplicate]
  6. Is there a zip-like function that pads to longest length?
  7. Why does this iterative list-growing code give IndexError: list assignment index out of range?
  8. Different behaviour for list.__iadd__ and list.__add__
  9. Non-alphanumeric list order from os.listdir()
  10. How do I check if there are duplicates in a flat list?
  11. Memory errors and list limits?
  12. Plotting networkx graph with node labels defaulting to node name
  13. How to find the min/max value of a common key in a list of dicts?
  14. How does the max() function work on list of strings in python?
  15. Complexity of list.index(x) in Python
  16. How to transform string of space-separated key,value pairs of unique words into a dict
  17. Nested list comprehensions
  18. How to convert list of numpy arrays into single numpy array?
  19. How can I format a list to print each element on a separate line in python? [duplicate]
  20. Group list by values [duplicate]
  21. What are dict_keys, dict_items and dict_values?
  22. Ordered intersection of two lists in Python
  23. What to consider before subclassing list?
  24. How do I send list of dictionary as Body parameter in FastAPI?
  25. Counting depth or the deepest level a nested list goes to
  26. Which is the most efficient way to iterate through a list in python?
  27. How does str.startswith really work?
  28. Best way to remove elements from a list
  29. All possible permutations of a set of lists in Python
  30. Length of longest word in a list

Leave a Comment