Dynamic union find algorithm in Prolog

Question

Lets assume I have sets S1,..,Sn and we want to find smallest covers C1,..,Cm so that in each cover there are never disjoint connected components.

for example with the sets S1=[X,Y], S2=[Y,Z], S3=[T] I would find the covers C1=[X,Y,Z] and C2=[T]. What about a dynamic algorithm that can split covers dynamically?

Assume the element Y dies, then we are left with S1'=[X], S2'=[Z] and S3'=[T]. The covers are now C1'=[X], C2'=[Z] and C3'=[T]. So the number of covers has increased.

The union find algorithm can determine a cover for a given collection of sets, but I am afraid that recalculating the full collection whenever an element dies, isn't efficient.

Answer 1

To tap the resources of a Prolog system, I made a little union find algorithm based on copy_term/2 and keysort/2. The main entry point of the algorithm here does the following:

covers(L, S) :-
   vars_list(L, K),
   copy_term(K, R),
   make_keys(L, R, H),
   keysort(H, J),
   collect_keys(J, S).

Here is an example run:

?- covers([X+Y,Y+Z,T], C).
C = [[X+Y, Y+Z], [T]]

To get a dynamic algorithm we might try the following. Maintain a backtrackable structure that allows finding covers from elements. Then if an element dies, only recalculate the cover that belongs to the died element.

This would reduce the complexity a little bit. Otherwise I don't have a more better idea here, except the observation that a died element only splits its own cover into smaller covers.