Class unionFind

Discussions related to Visual Prolog
Post Reply
Martin Meyer
VIP Member
Posts: 235
Joined: 14 Nov 2002 0:01

Class unionFind

Post by Martin Meyer » 11 Sep 2018 23:32

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.
Regards Martin

User avatar
Thomas Linder Puls
VIP Member
Posts: 2344
Joined: 28 Feb 2000 0:01

Re: Class unionFind

Post by Thomas Linder Puls » 12 Sep 2018 10:05

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).
Regards Thomas Linder Puls
PDC

Post Reply