AlgoVerse

Equivalence classes

From a list of pairs i ≡ j, find the equivalence classes: put each pair on both objects' lists, then gather each class with a stack; O(n + m).

An equivalence relation is reflexive, symmetric and transitive, so a few pairs i ≡ j determine every equivalent object. Horowitz–Sahni's algorithm has two phases:

Read the full explanation ↓
Input:
pairs 9×2PDF export

12 objects and 9 pairs; three classes come out: {0, 4, 11, 2, 7}, {1, 3, 5} and {6, 10, 8, 9}.

  1. def equivalence(pairs):
  2. # Objects are 0..n-1; each row of pairs says i ≡ j.
  3. n = 0
  4. for i, j in pairs:
  5. n = max(n, i + 1, j + 1)
  6. seq = [[] for _ in range(n)]
  7. rows = [[x, seq[x], "·"] for x in range(n)] # for the picture: object, partners, class
  8. for i, j in pairs:
  9. seq[i].append(j)
  10. seq[j].append(i)
  11. out = [False] * n
  12. classes = []
  13. for i in range(n):
  14. if out[i]:
  15. continue
  16. out[i] = True
  17. cls = [i]
  18. rows[i][2] = len(classes)
  19. stack = [i]
  20. while stack:
  21. x = stack.pop()
  22. for y in seq[x]:
  23. if not out[y]:
  24. out[y] = True
  25. cls.append(y)
  26. rows[y][2] = len(classes)
  27. stack.append(y)
  28. classes.append(cls)
  29. return classes

Invariant: Every object with out set is in exactly one class; every partner of the current class's members is in the class or on the stack.

Start

stack—
cls—
classes—

The table is still empty.

Local variables

Orange = changed in this step

pairs list

[0, 4][3, 1][6, 10][8, 9][7, 4][6, 8][3, 5][2, 11][11, 0]

Call stack

  1. equivalence()line 1
Step 1 of 214
Black = pair, new_class · Orange = key steppair: 0/9 · new_class: 0/3 · add: 0/9 · class_done: 0/3
    Explanation

    The idea

    An equivalence relation is reflexive, symmetric and transitive, so a few pairs i ≡ j determine every equivalent object. Horowitz–Sahni's algorithm has two phases:

    1. Read the pairs: for each pair put j on i's list and i on j's list (symmetry).
    2. Build the classes: start from the first object not yet in a class, push it, and repeatedly pop a member and add all its new partners to the class, pushing them too (transitivity).

    This is finding the connected components of a graph with DFS.

    Cost

    With n objects and m pairs, each pair appears twice on the lists and each appearance is looked at once: O(n + m).

    The input

    Each row is a pair [i, j]. The number of objects comes from the largest number.