Cisco

Paradigmas de Programación. Año 2006

EJERCICIOS RESUELTOS DE PROLOG
Ejercicio N° 1
Dado el grafo dirigido representado en la siguiente figura:
b a d c e

Una representación para el mismo en Prolog podría consistir en una lista que contenga dos sublistas: una representando el conjunto de nodos (o vértices) y otra representando el conjunto de arcos, donde cada arco es a su vez una lista dedos elementos, el nodo inicial y el final. Por ejemplo: (A) [[a b c d e] [[a b] [b c] [b d] [c e] [d a] [d e] [e a]]]

Otra representación válida consiste en una lista de listas, donde cada sublista contiene como elementos un nodo y una lista de los nodos hacia los cuales éste está conectado, por ejemplo: (B) [[a [b]] [b [c d]] [c [e]] [d [a e]] [e [a]]]

Note que el elemento [d [a e]]representa la existencia de los arcos [d a] y [d e] en la representación anterior. Una tercera representación, basada en la idea de (B), considera que cada sublista contiene el nodo en primer lugar seguido de la lista de nodos con los cuales está conectado (sin colocar estos dentro de otra lista), por ejemplo: (C) [[a b] [b c d] [c e] [d a e] [e a]]

(Note que esta representación es más sencilla que laanterior) Se le pide que desarrolle predicados que permitan obtener: a) la representación (A) de un grafo dado en la representación (B) ... y viceversa. b) la representación (A) de un grafo dado en la representación (C) ... y viceversa. c) la representación (B) de un grafo dado en la representación (C) ... y viceversa.

Resolución: La transformación entre la representación (A) y otra tal como(B) no puede definirse con un único predicado que brinde ambos servicios, por lo cual será necesario definir cada sentido de la consulta en forma separada. % Pasar de (A) ---> (B) pasarAB([Nodos, Arcos], Resultado):pasarAB_sublista(Nodos, Arcos, Resultado). pasarAB_sublista([],_,[]). pasarAB_sublista([Nodo|Ns], Arcos, [[Nodo, Conectados]|Rs]):pasarAB_arcos(Nodo, Arcos, Conectados),pasarAB_sublista(Ns, Arcos, Rs).

Ejercicios Resueltos Prolog

1

Paradigmas de Programación. Año 2006

pasarAB_arcos(_, [], []). pasarAB_arcos(N1, [[N1,N2]|As], [N2|Ns]):pasarAB_arcos(N1, As, Ns). pasarAB_arcos(N1, [[N2,_]|As], Ns):N1 \= N2, pasarAB_arcos(N1, As, Ns). % Pasar de (A) ---> (C) pasarAC(GrafoA, GrafoC):pasarAB(GrafoA, GrafoB), pasarBC(GrafoB, GrafoC). % Pasar de (B) ---> (C) pasarBC([],[]). pasarBC([[Nodo,Conectados]|Xs], [[Nodo|Conectados]|Ys]):pasarBC(Xs, Ys). % Pasar de (B) ---> (A) pasarBA(Grafo, [Nodos, Arcos]):pasarBA_armar(Grafo, Nodos, Arcos). pasarBA_armar([], [], []). pasarBA_armar([[Nodo, Conectados]|Rs], [Nodo|Ns], Arcos):pasarBA_arcos(Nodo, Conectados, ArcosNodo), pasarBA_armar(Rs, Ns, As), concatenar(ArcosNodo, As, Arcos). pasarBA_arcos(_N, [], []). pasarBA_arcos(N,[C|Cs], [[N,C]|Rs]):pasarBA_arcos(N, Cs, Rs). % Pasar de (C) ---> (A) pasarCA(GrafoC, GrafoA):pasarCB(GrafoC, GrafoB), pasarBA(GrafoB, GrafoA). % Pasar de (C) ---> (B) pasarCB(GrafoC, GrafoB):pasarBC(GrafoB, GrafoC). concatenar([], L, L). concatenar([X|Xs], Y, [X|Zs]):- concatenar(Xs, Y, Zs). grafoA( [[a,b,c,d,e],[[a,b],[b,c],[b,d],[c,e],[d,a],[d,e],[e,a]]] ). grafoB([[a,[b]],[b,[c,d]],[c,[e]],[d,[a,e]],[e,[a]]] ). grafoC( [[a,b],[b,c,d],[c,e],[d,a,e],[e,a]] ). Consultas (trabajando siempre con el grafo de la figura) En general: ? – grafoX( X ), pasarXY( X, Y ). donde X e Y serán A, B o C, según el caso que se desee probar.

Ejercicios Resueltos Prolog

2

Paradigmas de Programación. Año 2006

Ejemplos: ?– grafoA( A ), pasarAB( A, B ). A = [[a, b, c, d, e], [[a, b], [b, c], [b,d], [c, e], [d, a], [d, e], [e, a]]] B = [[a, [b]], [b, [c, d]], [c, [e]], [d, [a, e]], [e, [a]]] ; No ?– grafoB( B ), pasarBC( B, C ). B = [[a, [b]], [b, [c, d]], [c, [e]], [d, [a, e]], [e, [a]]] C = [[a, b], [b, c, d], [c, e], [d, a, e], [e, a]] ; No ?– grafoC( C ), pasarCA( C, A ). C = [[a, b], [b, c, d], [c, e], [d, a, e], [e, a]] A = [[a, b, c, d, e], [[a, b], [b, c], [b, d], [c, e], [d, a],...