/* Christophe GRENIER                  		*
 * grenier@esiea.fr		       		*
 *                                          	*
 * Probleme de la fermeture transitive       	*
 * Il faut trouver les classes d equivalence 	*/

/* test d'appartenance d'un element a une liste */
app(X,[X|_]).
app(X,[_|L]):- app(X,L).

/* supprime un element dans une liste */
ote(X,[X|L],L):-!.
ote(X,[C|L1],[C|L2]):-ote(X,L1,L2).

r2(X,Y,_):-r(X,Y),!.
/* On definit une relation d'equivalence */
/* Reflexive */
r2(X,X,_):-!.
/* Symetrique */
r2(X,Y,L):-app(X,L),ote(X,L,L2),r2(Y,X,L2),!.
/* Transitive */
r2(X,Z,L):-app(Y,L), ote(Z,L,L1t),ote(Y,L1t,L1),r2(X,Y,L1),
                                  ote(X,L,L2),r2(Y,Z,L2),!.
/* NB: On ne peut verifier la relation r2 que sur des constantes */

/* Effectue les tests de relations sur l'element X */
do_test_liste(_,[],ResteFinal,ResteFinal,_):-!.
do_test_liste(X,[Y|Suite],Reste,ResteFinal,Full):-
	r2(X,Y,Full),
	write(Y),
	ote(Y,Reste,Reste2),
	do_test_liste(X,Suite,Reste2,ResteFinal,Full),!.
do_test_liste(X,[_|Suite],Reste,ResteFinal,Full):-
	do_test_liste(X,Suite,Reste,ResteFinal,Full).

/* Donne toute les relations entres les elements de la premiere Liste */
relation([],_).
relation([X|Suite],Full):-
	nl,
	write(X),
	do_test_liste(X,Suite,Suite,ResteFinal,Full),
	relation(ResteFinal,ResteFinal).

/* Donne toute les relations entre les elements de la liste L */
do_relation(L):-relation(L,L).
/* Donne toute les relations entre les elements de la liste */
/* Relations */
r(a,b).
r(b,c).
r(d,c).
r(e,f).
r(f,b).
r(g,h).
r(j,h).
go:-do_relation([a,b,c,d,e,f,g,h,i,j]).