[Martin Meyer]

Hello Thomas,

in unionFind.pro is a predicate which does the path compression:

Code: Select all

predicates
    find_node2 : (node{@Node} Node) -> node{@Node} Component.
clauses
    find_node2(Node) = Component :-
        Parent = Node:parent,
        if Node = Parent then
            Component = Node
        else
            Component = find_node2(Parent),
            Node:parent := Component
        end if.

The predicate disconnects nodes from their old parents and makes them point to their component node. The component node does not change its number of descendants thereby, but the old parents do. To update the old parents' size properties accordingly the predicate could be changed to:

Code: Select all

predicates
    find_node2 : (node{@Node} Node) -> node{@Node} Component.
clauses
    find_node2(Node) = Component :-
        Parent = Node:parent,
        if Parent = Parent:parent then
            Component = Parent
        else
            Component = find_node2(Parent),
            Node:parent:size := Node:parent:size - Node:size,
            Node:parent := Component
        end if.

[Thomas Linder Puls]

Ok, thank you. I was not aware that anybody had at all noticed that class .

You should notice that the performance considerations are actually wrong .

But now I have added an additional constructor new_hash which will make the performance considerations correct:

Code: Select all

class unionFind{@Node} : unionFind{@Node}
    open core
 
constructors
    new : ().
    new_hash : (function{@Node, unsigned} HashFunction).
 
end class unionFind

The implementation is changed like this:

Code: Select all

facts
    nodeMap : mapM{@Node, node{@Node}}.
    unionNodeCallback : predicate{@Node Parent, @Node Child} := {  :- succeed }.
    firstComponent : component{@Node} := erroneous.
    count : positive := 0.
 
clauses
    new() :-
        nodeMap := mapM_redBlack::new().
 
clauses
    new_hash(Hash) :-
        nodeMap := mapM_hash::new(Hash).