Graph Modelling Example: Grouping Library Cards Into Households

Cards that share a phone number or an email address belong to one household, even through a chain of other cards: join them as each shared detail is seen.

Records that are linked by sharing a detail form a graph whose groups are the answer, and union-find builds those groups in one pass over the records without comparing every pair. A library wants to count households: two cards belong to the same household when they share a phone number or an email address, and a household can be joined through a chain, A sharing a phone with B and B an email with C. Nothing in the data links one card to another; the links have to be seen.

The six cards, with phone numbers from the range set aside for fiction:

Six library cards
Card	Phone	Email
C1	07700 900101	[email protected]
C2	07700 900202	[email protected]
C3	07700 900101	[email protected]
C4	07700 900303	[email protected]
C5	07700 900202	[email protected]
C6	07700 900404	[email protected]

How many households are there?

3: C1, C3 and C4; C2 and C5; and C6 alone. C4 shares nothing with C1 and joins it only through C3.

Each card is a vertex, and an edge joins two cards that share a detail. The question asks which cards are joined, directly or through others, so the algorithm is union-find, from the Union-Find topic in Data Structures, which keeps each group as a tree and joins two groups by pointing one root at the other. The listing remembers the first card seen with each detail and joins every later card that has the same detail to it, so no pair of cards is ever compared directly.

households.pypy

cards = [
    ("C1", "07700 900101", "[email protected]"),
    ("C2", "07700 900202", "[email protected]"),
    ("C3", "07700 900101", "[email protected]"),
    ("C4", "07700 900303", "[email protected]"),
    ("C5", "07700 900202", "[email protected]"),
    ("C6", "07700 900404", "[email protected]"),
]
parent = {card: card for card, _, _ in cards}


def find(card: str) -> str:
    while parent[card] != card:
        parent[card] = parent[parent[card]]
        card = parent[card]
    return card


def union(first: str, second: str) -> None:
    parent[find(second)] = find(first)


first_with: dict[str, str] = {}
for card, phone, email in cards:
    joined = []
    for detail in (phone, email):
        if detail in first_with:
            union(first_with[detail], card)
            joined.append(f"{first_with[detail]} by {detail}")
        else:
            first_with[detail] = card
    print(card, phone, email, "|", "; ".join(joined) or "nothing")

households: dict[str, list[str]] = {}
for card, _, _ in cards:
    households.setdefault(find(card), []).append(card)
print("households:", len(households))
for members in households.values():
    print(" ", " ".join(members))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

C1 07700 900101 [email protected] | nothing
C2 07700 900202 [email protected] | nothing
C3 07700 900101 [email protected] | C1 by 07700 900101
C4 07700 900303 [email protected] | C3 by [email protected]
C5 07700 900202 [email protected] | C2 by 07700 900202
C6 07700 900404 [email protected] | nothing
households: 3
  C1 C3 C4
  C2 C5
  C6

The joins, read from the run, show the chain.

What each card was joined with, from the run
Card	Joined with	Through
C1	Nothing	Nothing
C2	Nothing	Nothing
C3	C1	07700 900101
C4	C3	[email protected]
C5	C2	07700 900202
C6	Nothing	Nothing

Comparing every pair of cards would also find the shared details, at the cost of the pairs.

Two ways to group n cards with d details each
Approach	Cost
Compare every pair of cards, then search the links	O(n² · d)
Union-find, joining each card to the first card seen with each detail	O(n · d) map lookups plus near-constant time per join

The number of households is the number of roots once every card is joined. A search from each unreached card over the shared details would give the same groups, but needs the edges listed first, while union-find takes each link as it is found.

← → move through sections and cards