Function update_groups

ar.py:181–270

Update groups of equivalent elements. Given groups1 = [set1, set2, set3, ..] where all elems within each set_i is defined to be "equivalent" to each other. (but not across the sets) Incoming groups2 = [set1, set2, ...] similar to set1 - it is the additional equivalent information on elem

(
    groups1: list[Any], groups2: list[Any]
)

def update_groups(
    groups1: list[Any], groups2: list[Any]
) -> tuple[list[Any], list[tuple[Any, Any]], list[list[Any]]]:
  """Update groups of equivalent elements.

  Given groups1 = [set1, set2, set3, ..]
  where all elems within each set_i is defined to be "equivalent" to each other.
  (but not across the sets)

  Incoming groups2 = [set1, set2, ...] similar to set1 - it is the
  additional equivalent information on elements in groups1.

  Return the new updated groups1 and the set of links
  that make it that way.

  Example:
    groups1 = [{1, 2}, {3, 4, 5}, {6, 7}]
    groups2 = [{2, 3, 8}, {9, 10, 11}]

  => new groups1 and links:
    groups1 = [{1, 2, 3, 4, 5, 8}, {6, 7}, {9, 10, 11}]
    links = (2, 3), (3, 8), (9, 10), (10, 11)

  Explain: since groups2 says 2 and 3 are equivalent (with {2, 3, 8}),
  then {1, 2} and {3, 4, 5} in groups1 will be merged,
  because 2 and 3 each belong to those 2 groups.
  Additionally 8 also belong to this same group.
  {3, 4, 5} is left alone, while {9, 10, 11} is a completely new set.

  The links to make this all happens is:
  (2, 3): to merge {1, 2} and {3, 4, 5}
  (3, 8): to link 8 into the merged({1, 2, 3, 4, 5})
  (9, 10) and (10, 11): to make the new group {9, 10, 11}

  Args:
    groups1: a list of sets.
    groups2: a list of sets.

  Returns:
    groups1, links, history: result of the update.
  """
  history = []
  links = []
  for g2 in groups2:
    joins = [None] * len(groups1)  # mark which one in groups1 is merged
    merged_g1 = set()  # merge them into this.
    old = None  # any elem in g2 that belong to any set in groups1 (old)
    new = []  # all elem in g2 that is new

    for e in g2:
      found = False
      for i, g1 in enumerate(groups1):
        if e not in g1:
          continue

        found = True
        if joins[i]:
          continue