Class unionFind
Posted: 11 Sep 2018 23:32
Hello Thomas,
in unionFind.pro is a predicate which does the path compression:
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:
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.
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.