/* PRODOTTO CARTESIANO MOLTO PARTICOLARE */

f(a,1).
f(a,2).
f(a,3).
g(b,1).
g(b,2).
g(b,3).
g(b,4).


esercizio(L):-  listaf(L1),
		listag(L2),
		cart(L1,L2,L).

listaf(R):-findall((X,Y),f(X,Y),R).
listag(R):-findall((X,Y),g(X,Y),R) .


cart([],_,[]).
cart([T|C],B,R):- prod( T,B,R1 ),
                  cart(C,B,R2),
                  append(R1,R2,R),!.

prod(_,[],_).
prod( (A,N), [(B,M)|Coda], [(A,B,S)|R] ):- S is N+M,
					  prod((A,N),Coda,R).   




append([],L,L).
append([T|C],L,[T|R]):-append(C,L,R).




/* ESERCIZIO DI UN ESAME */


prefix([],_).

prefix([T|C],[T|C2]):-prefix(C,C2).

sublist(L,L).
sublist(L1,L2):-prefix(L1,L2).
sublist(L,[T|C]):-prefix(L,C).




/* PERCORSI IN UN ALBERO */

arco(a,b).
arco(a,c).
arco(a,d).
arco(c,e).
arco(c,f).
arco(d,g).
arco(e,h).
arco(e,i).
arco(e,l).



perc0(A,B,[A,B]):-arco(A,B).

perc0(A,B,[A|L]):-arco(A,C),
		  perc0(C,B,L).


perc1(A,B,L):-percorso1(A,B,L,[A]).

percorso1(A,A,L,L).

percorso1(A,B,L,Q):-arco(A,C),
                    percorso1(C,B,L,[C|Q]).


perc2(A,B,L):-percorso2(A,B,L,[B]).

percorso2(A,A,L,L).
percorso2(A,B,L,Q):-arco(C,B),
                    percorso2(A,C,L,[C|Q]).



/* ALBERO PESATO */


arco(a,b,30).
arco(a,c,2).
arco(a,d,12).
arco(c,e,4).
arco(c,f,22).
arco(d,g,4).
arco(e,h,2).
arco(e,i,1).
arco(e,l,0).
 

/* Programma che trova il percorso di peso minimo 
dalla radice alle foglie.
Il comando che lo avvia  è  min(P,C). 
dove C sarà il costo del percorso P. */
   

radice(A):-arco(A,_,_),
           not arco(_,A,_),!.

foglia(A):-arco(_,A,_),
           not arco(A,_,_).

foglie(L):-findall(A,foglia(A),L).

min(P,Costo):-radice(A),
              foglie(L),
              percorsomin(A,L,P,Costo).

percorso_pesato(A,B,Costo,P):- p_costo(A,B,Costo,P,[B]).

p_costo(A,A,0,L,L).
p_costo(A,B,Costo,P,Q):- arco(D,B,C1),
                         p_costo(A,D,C2,P,[D|Q]),
                         Costo is C1+C2.

percorsomin(A,[T|C],P,Costo):-percorso_pesato(A,T,Costo1,P1),
                              minimo(A,C,P1,Costo1,P,Costo).


minimo(A,[],P,C,P,C).

minimo(A,[T|C],P1,Costo1,P,Costo):-percorso_pesato(A,T,Costo2,P2),
                                   Costo1 =< Costo2,
                                   minimo(A,C,P1,Costo1,P,Costo).

minimo(A,[T|C],P1,Costo1,P,Costo):-percorso_pesato(A,T,Costo2,P2),
                                   Costo1 > Costo2,
                                   minimo(A,C,P2,Costo2,P,Costo).



/* GRAFO ACICLICO PESATO */


grafo(a,b,10).
grafo(a,h,2).
grafo(b,c,4).
grafo(b,d,7).
grafo(d,e,1).
grafo(d,f,1).
grafo(e,h,8).
grafo(e,g,5).
grafo(f,g,4).
grafo(h,i,9).


/* camgr(A,B,L,C). trova un cammino da A a B che
memorizza nella lista L e  calcola il suo costo C */


camgr(A,B,[A,B],C):-grafo(A,B,C).

camgr(A,B,[A|L],Costo):-grafo(A,D,C1),
			camgr(D,B,L,C2),
                        Costo is C1+C2. 


/* camgr2(A,B,L,C). */

camgr2(A,B,L,C):-cgr2(A,B,L,[B],C).

cgr2(A,A,L,L,0).

cgr2(A,B,L,Q,Costo):-grafo(D,B,C1),
		     cgr2(A,D,L,[D|Q],C2),
                     Costo is C1+C2.            

		
/* totgr(A,B,R). trova tutti i cammini possibili da A a B con i
   loro rispettivi costi */

totgr(A,B,R):-findall((L,C),camgr(A,B,L,C),R).


/* lungr(A,B,N). restituisce il numero di cammini esistenti da A a B */

lungr(A,B,N):-totgr(A,B,R),
	      cardinalita(R,N).

cardinalita([],0).
cardinalita([T|C],N):-cardinalita(C,M),
		      N is M+1.         


/* mingr(A,B,L,C). trova il cammino L da A a B di peso minimo C */

mingr(A,B,L,C):-totgr(A,B,R),
		m_gr(R,L,C).

/* m_gr(R,L,C). stabilisce quale dei cammini  e  di costo minore */

m_gr( [(P,Costo)|Coda] ,L,C):-minimogr(Coda,P,Costo,L,C).

minimogr([],P,C,P,C).

minimogr([(P1,C1)|Coda],P2,C2,L,C):-C2=C1,
                                    minimogr(Coda,P1,C1,L,C).           




/* GRAFO ORIENTATO CICLICO */


grafo(a,b).
grafo(b,f).
grafo(c,b).
grafo(d,b).
grafo(d,h).
grafo(e,d).
grafo(e,g).
grafo(e,i).
grafo(f,e).
grafo(f,g).
grafo(g,l).
grafo(h,e).
grafo(h,i).
grafo(l,h).


percorso_aciclico(A,B,L):-aciclico(A,B,L,[]).

aciclico(A,A,[A|L],L):- not member(A,L).

aciclico(A,B,L,Q):-grafo(D,B),
                   not member(B,Q),
                   aciclico(A,D,L,[B|Q]).

member(A,[A|C]).
member(A,[T|C]):-member(A,C).



/*    *************************************************    */



/* ESERCIZIO:  CAMMINI IN UN GRAFO
   Dati due nodi, costruire in ordine casuale tutti
   i cammini che li congiungono con la relativa 
   distanza.

   Dato un grafo  e  due suoi nodi, trova tutti i
   percorsi aciclici con rispettivo peso. 
   Nel caso che i nodi siano uguali, il risultato e'
   una lista vuota. 
   Nel caso che almeno uno dei due nodi non appartenga
   al grafo, il risultato è una lista vuota. */


/* Gli archi sono del tipo:
            arco(<nodo>,<nodo>,<peso>) */


/* grafo piccolo */


arcu(a,b,3).
arcu(b,c,9).
arcu(c,d,2).
arcu(d,e,4).
arcu(c,e,5).
arcu(a,c,6).
arcu(a,e,6).
arcou(X,Y,Z):-arcu(X,Y,Z).
arcou(X,Y,Z):-arcu(Y,X,Z).


/* GRAFO GRANDE: 

		CON QUESTO GRAFO IL PROGRAMMA DA' L'ERRORE:  
		
                ERR 212 Not enough global stack
   
		a causa dell'eccessiva dimensione del grafo */

arc(a,b,5).
arc(a,c,4). 
arc(a,d,3).
arc(a,e,2).
arc(a,f,1).
arc(b,c,2).
arc(c,d,3).
arc(d,e,4).
arc(e,f,5).
arc(b,g,6).
arc(c,h,7).
arc(d,h,8).
arc(d,i,9).
arc(e,i,30).
arc(e,l,1).
arc(f,m,11).
arc(g,h,4).
arc(h,i,5).
arc(i,l,1).
arc(l,m,3).
arc(g,p,3).
arc(g,n,8).
arc(i,n,2).
arc(m,n,4).
arco(X,Y,Z):-arc(X,Y,Z).
arco(X,Y,Z):-arc(Y,X,Z).

/* ---------------------------------------------- */

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

append([],A,A).
append(A,[],A).
append([T|C1],L2,[T|C3]):-append(C1,L2,C3).

/* ----------------------------------------------- */



/* es(<nodo>,<nodo>) */

es(A,B):-nl,write('Lista dei percorsi aciclici nel grafo piccolo:'),
	 e0([t([A],0)],B,[],L0),
	 nl,write(L0),nl,
         nl,write('Lista dei percorsi aciclici nel grafo d''esame:'),
	 e1([t([A],0)],B,[],L1),
	 nl,write(L1).



/* ---------- Ricerca percorsi nel grafo piccolo ----------*/


e0([],B,Q,[]):-Q=[t([B],0)]. /* se i nodi sono illegali */
e0([],B,L,L).
e0([T|C],B,Q,L):-agg0(T,C,K),
                 pure0(T,K,B,Q,L).

agg0(T,C,K):-figli0(T,F),
             append(C,F,K). /* visita in larghezza */

figli0(T,F):-findall(W,p0(T,W),F).

p0(t([T|L],D),t([T1|L1],D1)):-arcou(T,T1,H),
                              not member(T1,L),
			      D1 is D+H,
			      L1 = [T|L].

pure0(t([B|Lista],Peso),K,B,Q,L):-e0(K,B,[t([B|Lista],Peso)|Q],L).
pure0(t([Z|Lista],Peso),K,B,Q,L):-not eq(Z,B),
				  e0(K,B,Q,L). 


/* ----------------- Ricerca percorsi nel grafo d'esame --------------*/



e1([],B,Q,[]):-Q=[t([B],0)]. /* se i nodi sono illegali */
e1([],B,L,L).
e1([T|C],B,Q,L):-agg(T,C,K),
                 pure(T,K,B,Q,L).

agg(T,C,K):-figli(T,F),
            append(C,F,K). /* visita in larghezza */

figli(T,F):-findall(W,p(T,W),F).

p(t([T|L],D),t([T1|L1],D1)):-arco(T,T1,H),
                             not member(T1,L),
			     D1 is D+H,
			     L1 = [T|L].

pure(t([B|Lista],Peso),K,B,Q,L):-e1(K,B,[t([B|Lista],Peso)|Q],L).
pure(t([Z|Lista],Peso),K,B,Q,L):-not eq(Z,B),
				 e1(K,B,Q,L). 



/*    ******************     */




/* Quanti elementi ha una lista? */

cardinalita([],0).
cardinalita([T|C],P):-cardinalita(C,K),
		      P is K+1. 




/* ALTERNATIVA: METODO PROCEDURALE */


cardp(L,S):-car_p(L,S,0).     /* INIZIALIZZAZIONE */

car_p([],S,S).  /* CRITERIo D'ARRESTO */
car_p([T|C],S,P):-Q is P+T,
		 car_p(C,S,Q).



/* Somma degli elementi di una lista di numeri */

somma([],0).
somma([T|C],N):-somma(C,M),
		N is M+T.




/* ALTERNATIVA: METODO PROCEDURALE */


sommap(L,S):-somp(L,S,0).      /* INIZIALIZZAZIoNE */

somp([],S,S). /* CRITERIO D'ARRESTO */
somp([T|C],S,P):-Q is P+T,
                 somp(C,S,Q).




/* PRODOTTO SCALARE di due liste aventi cardinalita' 
   uguale: */


sca([T1|C1],[T2|C2],K):-sca(C1,C2,Q),
			K is Q+T1*T2.



/* con controllo sulla cardinalita' */


sca2(L1,L2,R):-cardinalita(L1,N1),
	       cardinalita(L2,N2),
               prod_scalare(L1,N1,L2,N2,R).

prod_scalare(_,N1,_,N2,R):- N1 \= N2,
                            write('Le due liste non hanno la stessa'),
			    write(' cardinalità.'),
                            R = nessun_valore.

prod_scalare([],0,[],0,0). /* PASSO BASE */
prod_scalare([T1|C1],N1,[T2|C2],N2,R):- N1 = N2,
					M1 is N1-1,
					M2 is N2-1,     
                                        prod_scalare(C1,M1,C2,M2,W),
					R is W+T1*T2.

/* ALTERNATIVA (senza controllo cardinalita'): 
        METODO PROCEDURALE      */


prod_scp(L1,L2,P):-prod_p(L1,L2,P,0).   /* inizializzazione */

prod_p([],[],P,P).      /*criterio d'arresto */
prod_p([T1|C1],[T2|C2],P,N):-M is N+T1*T2,
                             prod_p(C1,C2,P,M).



/* FATTORIALE */


/* il fatto fatt(1,1).  e' ridondante, quindi non e' stato inserito */

fatt(0,1):- !.
fatt(N,F):- M is N-1,
	    fatt(M,K),
	    F is N*K.   



/* Sottinsieme: */
/* sott(L1,L2). stabilisce se gli elementi della prima lista
   sono tutti anche elementi della seconda lista, cioe' se la
   prima lista e' un 'sottoinsieme' della seconda */


sott([],_).

sott([T|C],L):- member(T,L),
                sott(C,L).
member(T,[T|C]).
member(T,[T2|C]):-member(T,C).



/* attenzione_orlo(L1,L2). ha successo se la lista L1 si puo' ricavare 
                           'orlando' la seconda.
   ATTENZIONE: non usare se L1 non e' orlo di L2 perche' il calcolatore
               cerca tutte i possibili modi di eseguire il primo append,
               cioe' infiniti */
	       

attenzione_orlo(L1,L2):- append(_,L1,T),
			 append(T,_,L2).


/* orlo(L1,L2). ha successo se la lista L1  e  'orlo' della seconda
                ed ha il vantaggio che il numero di volte in cui si puo
                eseguire il primo append  e  limitato perche'  corrisponde
                esattamente al numero di volte in cui si puo formare
                la lista L2 giustapponendo due liste */


orlo(L1,L2):- append(X,_,L2),
	      append(_,L1,X).


append([],L,L).
append([T|C],L,[T|A]):-append(C,L,A).


/* la domanda ?-orlo(X,[a,b]).   ha un numero limitato di risposte,
                                 quindi il processo termina */

/* la domanda ?-attenzione_orlo(X,[a,b]).  e  tale per cui il processo
                                          di risposte e' infinito */    



/* MASSIMO TRA GLI ELEMENTI DI UNA LISTA */


max1([],P):- write('Lista vuota, impossibile calcolare il valore massimo'),
            P = nessun_valore.

max1([T],T).
	
max1([T|C],M):-max(C,N),
              comp_max(T,N,M),
	      !.

comp_max(T,N,T):- T>=N.
comp_max(T,N,N):- T<N.
			

max2([T|C],M):- massimo(C,T,M).

massimo([],M,M).
massimo([T|C],X,M):-maggiore(T,X,Y),
                    massimo(C,Y,M).

maggiore(A,B,A):- A>=B.
maggiore(A,B,B):- A<B.  



/* Elimina Elementi Ripetuti in una lista 
   creando cosi' un Insieme */


set(L,R):-elimina(L,R,[]).

elimina([],R,R).

elimina([T|C],R,Q):- member(T,C),
		     elimina(C,R,Q).
elimina([T|C],R,Q):- not member(T,C),
		     elimina(C,R,[T|Q]).        



/* DATE DUE LISTE STABILISCE SE LA PRIMA E' 
   UN PREFISSO DELLA SECONDA */


prefix([],_).

prefix([T|C],[T|L]):-prefix(C,L).




/* DATE DUE LISTE STABILISCE SE LA PRIMA E'
   UN SUFFISSO DELLA SECONDA */


suffix(L,L).

suffix(L,[T|C]):-suffix(L,C).



/* DATE DUE LISTE STABILIRE SE LA PRIMA E' UNA SOTTOLISTA DELLA SECONDA */


sublist(L,L).
sublist(L1,L2):-prefix(L1,L2).
sublist(L,[T|C]):-prefix(L,C).



/* ********************************* */