List operation to summarize and shrink down list with sublists-CodePudding

I have a list which basically looks like this:

[[A, B], [A, C], [D,E]]

where A, B, C, D and E are nodes of an electrical circuit. When two nodes are together in one list, they are at the same potential, so in my case, A and B, A and C, and finally also D and E are basically equal.

Because A and B, but also A and C are equal, also B and C should be equal.

What I want to do is the following: I need to create a list which basically looks like this:

[[A, B, C], [D,E]]

So it should summarize all nodes which are basically equal into one list and put every list of equal nodes into a final list like the one above. I was thinking about using sets, for example by using intersection and union, but I have not figured it out already.

Maybe somebody can help and thanks in advance!

[Edit] This is my attempt so far:

wireEnds = self.wireEnds.copy()
for currentNodePair in wireEnds:
    foundInSubSet = False
    print("currentNodePair:",currentNodePair)
    for subSet in self.commonNodes:
        print("subSet:",subSet)
        if (currentNodePair[0] in subSet) or (currentNodePair[1] in subSet): 
            subSet.add(currentNodePair[0])
            subSet.add(currentNodePair[1])
            print("Adding to subset:",currentNodePair)
            foundInSubSet = True
            continue
    if not foundInSubSet:
        print("Not found, creating new subSet:",currentNodePair)
         self.commonNodes.append({currentNodePair[0], currentNodePair[1]})

Note that I'm using sets instead of sublists because I don't want duplicates in my sublists.

CodePudding user response：

Since what you have is a graph and you want to find connected components, you can use Networkx which has an implementation of union find datastructure:

from networkx.utils.union_find import UnionFind
sets = UnionFind()
for gp in lst:
    sets.union(*gp)
out = [list(s) for s in sets.to_sets()]


[['A', 'B', 'C'], ['E', 'D']]

CodePudding user response：

Ok, thanks @enke, this is by far easier than my solution, but maybe you can have a look!

def version_3(list_in):
  output = [set(list_in[0])]
  for sublist in list_in[1:]:
    current_set = set(sublist)
    found_in = []
    for group in output:
      current_group = set(group)
      if current_set.intersection(current_group):
        found_in.append(current_group)
    
    if found_in:
      for group in found_in:
        output.remove(group)
        current_set = current_set.union(group)
      output.append(current_set)
    else:
      output.append(set(sublist))
      
  return output