Page 1 of 1

Class unionFind

Posted: 11 Sep 2018 23:32
by 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.

Re: Class unionFind

Posted: 12 Sep 2018 10:05
by 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 :oops:.

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).