def toDot(Parent):
    dot = gv.Digraph()
    M   = Parent.keys()
    for x in M:
        p = Parent[x]
        dot.node(str(x))
        if x == p:
            dot.edge(str(p), str(x), dir='back', headport='nw', tailport='ne')
        else:
            dot.edge(str(p), str(x), dir='back')
    return dot

"""
Explanation: The function $\texttt{toDot}(\texttt{Parent})$ takes a dictionary $\texttt{Parent}$.
For every node $x$, $\texttt{Parent}[x]$ is the parent of $x$.   It draws this dictionary 
as a family tree using graphviz.
End of explanation
"""


def union_find(M, R):
    Parent = { x: x for x in M } # trivial partition
    for x, y in R:
        print(f'{x} ≅ {y}')
        root_x = find(x, Parent)
        root_y = find(y, Parent)
        display(toDot(Parent))
        if root_x != root_y:
            Parent[root_y] = root_x
            display(toDot(Parent))
    Roots = { x for x in M if Parent[x] == x }
    return [{y for y in M if find(y, Parent) == r} for r in Roots]

"""
Explanation: A Tree Based Implementation of the Union-Find Algorithm
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) $$
The resulting partition defines the equivalence relation that is generated by $R$.
End of explanation
"""


def find(x, Parent):
    p = Parent[x]
    if p == x:
        return x
    return find(p, Parent)

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)
    return P

demo()

def worst_case(n):
    M = set(range(1, n+1))
    R = [ (k+1, k) for k in M if k < n ]
    print(f'R = {R}')
    P = union_find(M, R)
    print(f'P = {P}')

worst_case(10)

"""
Explanation: Given a dictionary Parent and an element $x$ from $M$, the function $\texttt{find}(x, \texttt{Parent})$ 
returns the ancestor of $x$ that is its own parent.
End of explanation
"""


def worst_case_set(n):
    M = set(range(1, n+1))
    R = { (k+1, k) for k in M if k < n }
    print(f'R = {R}')
    P = union_find(M, R)
    print(f'P = {P}')

worst_case_set(20)

"""
Explanation: The previous example was a worst case scenario because we had defined the relation $R$ as a list so that we were able to control the order of the
joining of different trees.  If we represent $R$ as a set, the order of the pairs is more or less random and the trees do no degenerate to lists.
End of explanation
"""


