

In [ ]:

    
%%HTML
<style>
.container { width:100% } 
</style>

A Naive Implementation of the Union-Find Algorithm

Given a set of frozen sets FS this function turns this set into a string that looks like a set of sets.



In [ ]:

    
def toStr(FS):
    result = '{ '
    for S in FS:
        result += str(set(S)) + ', '
    result = result[:-2]
    result += ' }'
    return result

The function $\texttt{arb}(S)$ returns an arbitrary element from the set $S$,



In [ ]:

    
def arb(S):
    for x in S:
        return x

Given a set $M$ and a binary relation $R \subseteq M \times M$, the function $\texttt{union_find}$ returns a partition $\mathcal{P}$ of $M$ such that we have $$ \forall \langle x, y \rangle \in R: \exists S \in \mathcal{P}: \bigl(x \in S \wedge y \in S\bigr) $$



In [ ]:

    
def union_find(M, R):
    print(f'R = {R}')
    P = { frozenset({x}) for x in M }  # the trivial partition of M
    print(f'P = {toStr(P)}')
    for x, y in R:
        Sx = find(x, P)
        Sy = find(y, P)
        if Sx != Sy:
            print(f'{x} ≅ {y}: combining {set(Sx)} and {set(Sy)}')
            P -= { Sx,  Sy }
            P |= { Sx | Sy }
            print(f'P = {toStr(P)}')
    return P

Given a partition $\mathcal{P}$ of a set $M$ and an element $x$ from $M$, the function $\texttt{find}(x, \mathcal{P})$ returns the set $S \in \mathcal{P}$ such that $x \in S$.



In [ ]:

    
def find(x, P):
    return arb({ S for S in P if x in S })



In [ ]:

    
def demo():
    M = set(range(1, 10))
    R = { (1, 4), (7, 9), (3, 5), (2, 6), (5, 8), (1, 9), (4, 7) }
    P = union_find(M, R)



In [ ]:

    
demo()



In [ ]: