/*----------------------------------------------------------*/
/*  Attribute-Value Clustering by LGG (Sicstus Prolog V2+)  */
/*----------------------------------------------------------*/
/*  (C) 1997 Zdravko Markov                                 */
/*----------------------------------------------------------*/
cluster(E,Tree) :-
    cluster(E,[],Tree).

cluster(E,CTree,Tree) :-
    min_lgg(E,LGG), !,
    cover(E,LGG,Cover,Rest),
    cluster([LGG|Rest],[[LGG|Cover]|CTree],Tree).
cluster(_,Tree,Tree).

min_lgg(E,C) :-
    findall(C/D,(pair(E,A,B),lgg(A,B,C,D)),All),
    min(All,C/_).

cover([],_,[],[]).
cover([X|T],LGG,[X|Cov],R) :-
    subsumes(LGG,X), !,
    cover(T,LGG,Cov,R).
cover([X|T],LGG,Cov,[X|R]) :-
    cover(T,LGG,Cov,R).

subsumes(T1,T2) :-
    \+(\+((numbervars(T2,0,_),T1=T2))).

lgg([],[],[],0).
lgg([X|T],[Y|L],[X|V],D) :-
    X==Y, !,
    lgg(T,L,V,D).
lgg([_|T],[_|L],[_|V],D) :-
    lgg(T,L,V,D1),
    D is D1+1.

member(X,[X|_]).
member(X,[_|T]) :- member(X,T).

min([X],X) :- !.
min([X/M|T],Y/N) :- min(T,Z/K), (M<K,Y/N=X/M;Y/N=Z/K), !.

pair([A|L],A,B) :- member(B,L).
pair([_|L],A,B) :- pair(L,A,B).

/*----------------------- Show tree ------------------------*/
show([X|T]) :-
    show_tree(X,T,0).

show_tree([Node|Subtree],Tree,N) :-
    tab(N),write(Node),nl,
    M is N+3,
    write_children(Subtree,Tree,M).

write_children([],_,_).
write_children([Node|Brothers],Tree,M) :-
    same_node(Node,Subtree,Tree), !,
    show_tree([Node|Subtree],Tree,M),
    write_children(Brothers,Tree,M).
write_children([Leaf|Brothers],Tree,M) :-
    tab(M),write(Leaf),nl,
    write_children(Brothers,Tree,M).

same_node(X,Y,[[Z|Y]|_]) :- X==Z, !.
same_node(X,Y,[_|T]) :- same_node(X,Y,T).

tab(0).
tab(N) :- write(' '), M is N-1, tab(M).

/*--------------- Change of representation -----------------*/

examples(L) :-
    findall(Vs,(example(_,C,AVs),remove_names(AVs,Vs)),L).

remove_names([],[]).
remove_names([_=V|T],[V|R]) :-
    remove_names(T,R).