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

Class unionFind

Unread post 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.
Regards Martin
User avatar
Thomas Linder Puls
VIP Member
Posts: 1398
Joined: 28 Feb 2000 0:01

Re: Class unionFind

Unread post 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).
Regards Thomas Linder Puls
PDC
Post Reply